«Методы управления транзакциями в XML-ориентированных СУБД ...»

Далее мы будем использовать обозначение Wi (x) для операции изменения элемента данных x, транзакцией Ti. Аналогично, Ri (x) - для операции чтения x. В том случае, когда мы не желаем указывать конкретный тип операции, мы будем использовать обозначения Pi (x) и Qi (x).

Каждая такая операция поступает на вход 2PL-планировщику. В зависимости от типа операции и уже обработанных запросов он определяет, выполнить ли операцию или же заблокировать транзакцию до того момента, когда конфликт будет разрешен.

В 2PL операция записи конфликтует с любой операцией другой транзакции над тем же элементом данных. Операции чтения совместимы между собой. При выборе сценария поведения планировщик руководствуется следующими правилами:

1. Когда 2PL-планировщик получает запрос на операцию Pi (x), он проверяет, конфликтует ли данная операция хотя бы с одной из запланированных ранее. Если нет, то транзакция становится обладателем соответствующего захвата, и операция выполняется. Если да, то выполнение транзакции приостанавливается до тех пор, пока она не сможет получить доступ к требуемому элементу.

2. Если планировщик захватил элемент x в каком-либо режиме доступа, то он не может отпустить захват как минимум до тех пор, пока физическая операция, соответствующая запросу не завершится.

3. Если планировщик отпустил хотя бы один захват, принадлежащий транзакции Ti, то эта транзакция больше не может захватывать никаких объектов БД.

Первые два правила защищают транзакции от совместного доступа к данным в конфликтующих режимах. Третье правило принято называть фазовым. От него, кстати говоря, и происходит название протокола. Каждая транзакция логически разделяется на две фазы. Во время первой фазы она берет захваты на те объекты, которые ей требуются, а во время второй отпускает их по мере завершения работы с ними.

Именно третье правило обеспечивает логическую корректность работы параллельных транзакций. Фактически, оно обеспечивает сериализуемость допускаемых протоколом планов. Транзакции, обрабатываемые 2PL-планировщиком, сериализуются в порядке завершения. Иными словами, результат их работы эквивалентен последовательному выполнению в том порядке, в котором они завершились.

Важным частным случаем протокола 2PL является строгий двухфазный протокол синхронизации. Он отличается от 2PL только тем, что блокировки транзакциями могут сниматься только при фиксации транзакции. Как правило, строгий двухфазный протокол обозначают символом S2PL (Strict Two Phase Locking).

Протокол, основанный на временных метках Следующий рассматриваемый нами протокол сериализует транзакции по временной метке их старта. Согласно этому протоколу, каждая транзакция получает временную метку в момент старта. Подсистема управления транзакциями присваивает эту метку каждой последующей операции этой транзакции.

Основным правилом работы планировщика, основанного на временных метках, является правило “временного упорядочивания” (Timestamp Ordering rule, TO rule): Для каждой пары конфликтующих операций Pi (x) и Qj (x) операция Pi выполняется раньше Qj тогда и только тогда когда временная метка Pi меньше временной метки Qj.

Простейший TO-планировщик обрабатывает транзакции следующим образом:

1. Если для операции Qi (x) имеется операция Pj (x), уже выполненная на этот момент, такая, что временная метка Tj (здесь и далее мы будем использовать обозначение ts(Tj )) больше чем ts(Qi ), то для транзакции Ti должен быть выполнен откат, и затем она может быть запущена заново с новой временной меткой.

2. В противном случае операция выполняется. Информация об этом запоминается во внутренних структурах планировщика, который должен учитывать этот факт при последующей работе (например, при обработке операции другой транзакции над этим элементом данных).

Этот протокол очевидным образом допускает лишь сериализуемые планы. Однако на практике он фактически не используется из-за очень высокой степени откатов при сильной нагрузке. При этом важно отметить, что чаще всего это “воображаемые” конфликты.

TO-планировщики слишком строги. Они накладывают слишком жесткие ограничения на порядок поступления операций, чтобы гарантировать сериализуемость. В реальности многие из операций, вызывающих откат согласно TO-правилу, не нарушают сериализуемости генерируемого плана.

Таким образом, протокол имеет скорее теоретический, чем практический интерес, в отличие от 2PL, который очень широко используется в индустрии. Однако различные гибридные протоколы (например многоверсионный протокол MVTO), использующие TOпланировщик в качестве базы, широко используются на практике.

Версионные методы В этом разделе мы рассмотрим наиболее известные версионные алгоритмы. Мы будем следовать изложению, предложенному в [9]. Сначала мы рассмотрим версионную модификацию алгоритма на временных метках (MVTO), затем обсудим версионный вариант двухфазного протокола синхронизации и его упрощенную версию (в которой число версий ограничивается двумя). В конце раздела приводится комбинированный алгоритм (ROMV), предназначенный для минимизации ожидания читающих ( read-only) транзакций.

Версионный протокол, основанный на временных метках (MVTO) MVTOпланировщик (Multiversion Timestamp Ordering) обрабатывает операции таким образом, чтобы суммарный результат выполнения операций был эквивалентен последовательному выполнению транзакций. При этом, как и в неверсионном TO, их порядок задается порядком временных меток, которые транзакции получают во время старта. Временные метки также используются для идентификации версий данных при чтении и модификации – каждая версия получает временную метку той транзакции, которая ее создала. Планировщик не только следит за порядком выполнения действий транзакций, но также отвечает за трансформацию операций над элементами базы данных в операции над версиями, т.е. каждая операция вида “прочитать элемент данных x”, должна быть преобразована планировщиком в операцию “прочитать версию y элемента данных x”.

Для описания алгоритма введем ряд обозначений. Временную метку, полученную транзакцией Ti в начале ее работы, будем обозначать как ts(Ti ). Операция чтения транзакцией Ti элемента данных x будет обозначаться как ri (x). Для обозначения того, что транзакция Ti читает версию элемента данных x, созданную транзакцией Tk, будем писать ri (xk ). Для обозначения того, что транзакция Ti записывает версию элемента данных x, будем использовать запись wi (x).

Теперь опишем алгоритм работы MVTO-планировщика:

1. Планировщик преобразует операцию ri (x) в операцию ri (xk ), где xk – это версия элемента x, помеченная наибольшей временной меткой ts(Tk ), такой что ts(Tk ) ts(Ti ).

2. Операция wi (x) обрабатывается планировщиком следующим образом.

(a) Если планировщик уже обработал действие вида rj (xk ), такое что ts(Tk ) < ts(Ti ) < ts(Tj ), то операция wi (x) отменяется, а Ti откатывается.

(b) В противном случае wi (x) преобразуется в wi (xi ).

3. Фиксация транзакции Ti откладывается до того момента, когда завершатся все транзакции, которые записывали версии данных, прочитанные Ti .

Заметим, что последний шаг нужен только в том случае, когда мы хотим предотвратить “грязное” чтение.

Многоверсионный двухфазный протокол мы рассмотрим вариант двухфазного протокола синхронизации транзакций (2PL), адаптированный для применения в версионной базе данных.

Рассматривая алгоритм работы MVTO-планировщика, мы использовали ряд терминов, которые теперь определим строго. Будем различать три типа версий элемента данных.

1. Зафиксированные версии (commited versions). Эти версии, созданные теми транзакциями, которые уже успешно закончили свою работу.

2. Текущая версия (current version). Это последняя из зафиксированных версий.

3. Незафиксированные версии (uncommited versions). Это версии, созданные теми транзакциями, которые еще находятся в работе.

В MV2PL планировщик следит за тем, чтобы в каждый момент времени существовало не более одной незафиксированной версии. В зависимости от того, позволяется ли транзакциям читать незафиксированные версии данных, различаются два варианта этого алгоритма. Мы будем одновременно рассматривать оба варианта MV2PL (с чтением незафиксированных данных и без него). Сначала рассмотрим схему работы MV2PL в предположении, что все версии элементов данных сохраняются в базе. Затем обсудим вариант этого алгоритма, в котором допускается одновременное существование не более двух версий одного и того же элемента данных.

Все операции, которые обрабатывает планировщик, разделяются на два класса:

обычные операции и финальные операции. Под финальной операцией понимается последняя операция транзакции перед ее завершением или же сама операция фиксации (commit). Обе интерпретации допустимы. При этом каждая отдельная операция транзакции обрабатывается следующим образом.

1. Если операция не является финальной, то:

(a) операция r(x) выполняется незамедлительно; ей сопоставляется последняя из зафиксированных к данному моменту версий x (или последняя из незафиксированных версий x во втором варианте алгоритма);

(b) операция w(x) выполняется только после фиксации транзакции, записавшей 2. Если операция является финальной для транзакции Ti, то она откладывается до тех пор, пока не завершатся следующие транзакции:

(a) все транзакции Tj, прочитавшие текущую версию данных, которую должна заменить версия, записанная Ti (таким образом устраняется возможность неповторяющегося чтения).

(b) все транзакции Tj, которые записали версии, прочитанные Ti (это требуется только во втором варианте алгоритма).

Как видно, этот алгоритм ничего не говорит о числе версий одного и того же элемента, которые могут одновременно существовать в базе данных. Это вызывает проблемы с хранением версий. Во-первых, они могут занимать слишком много места (легко вообразить ситуацию, когда объем старых версий становится в несколько раз больше, чем объем всей “текущей” базы данных). Во-вторых, возникают трудности с размещением этих “старых” данных. Учитывая, что количество версий заранее не известно, сложно придумать эффективную структуру их хранения, которая бы не вызывала заметных накладных расходов. И, наконец, такая система слишком сложна в реализации.

Вероятно, именно из-за этих проблем на практике чаще используется протокол 2V2PL, предложенный впервые в работе Байера [68]. В этом протоколе возможно одновременное существование двух версий элемента данных: одной текущей версии данных и не более одной незафиксированной. Такая организация версий выгодна, прежде всего, для транзакций, выполняющих операцию чтения.

В 2V2PL используются три типа блокировок. Каждая блокировка удерживается до конца транзакции:

1. rl (read lock): эта блокировка устанавливается на текущую версию элемента данных x непосредственно перед ее прочтением;

2. wl (write lock): блокировка устанавливается перед тем, как создать новую (незавершенную) версию элемента x;

3. cl (commit lock): блокировка устанавливается перед выполнением последней операции транзакции (обычно перед операцией commit) по отношению к каждому элементу данных, который она записала. Эта блокировка играет роль монопольной блокировки для 2PL. Она необходима для корректной смены версий.

Таблица совместимости блокировок для протокола 2V2PL изображена на рисунке 1.1.

Рис. 1.1: Таблица совместимости блокировок в протоколе 2V2PL Очевидно, что использование блокировок rl и wl обеспечивает выполнение правил 1(a) и 1(b) алгоритма MV2PL (с учетом того, что одновременно позволяется поддерживать не более одной незавершенной версии). Блокировка cl, в свою очередь, обеспечивает выполнение правил 2(a) и 2(b).

Многоверсионный протокол для транзакций, не изменяющих данные (ROMV) В работе многих приложений преобладают транзакции, не изменяющие данные (read-only transactions). Такие приложения считывают и анализируют большие объемы данных.

В случае наличия хотя бы небольшого числа параллельно выполняемых транзакций, производящих изменения, компонент, который отвечает за управление параллельными транзакциями, должен обеспечить согласованность прочитанных данных. В случае использования алгоритмов планирования без поддержки версий такие долговременные транзакции могут привести к чрезвычайному падению производительности системы.

Например, при использовании 2PL станет крайне велика вероятность блокировки транзакций, производящих обновления данных. В результате у этих транзакций будет очень большое время отклика.

Многоверсионные алгоритмы позволяют избежать подобных проблем благодаря тому, что транзакция, вносящая изменения в базу данных, не конфликтует с транзакциями чтения.

Но в то же время многоверсионные алгоритмы обычно сложны в реализации, и запросы к версионным СУБД вызывают заметные накладные расходы.

Рассматриваемый в этом разделе протокол ROMV (Multiversion Protocol for ReadOnly Transactions) является гибридным, основанным на MVTO и 2PL. Он ориентирован на приложения, для которых наиболее важна скорость выполнения транзакций, не производящих изменений данных. Заметим что, в литературе отсутствует согласие по поводу названий алгоритмов. Так, Пол Боббер и Майкл Кэри в [66] называют обсуждаемый здесь протокол MV2PL. Мы следуем терминологии, принятой в книге Вайкума и Воссена [9]. В ней под термином MV2PL понимается протокол, рассмотренный в предыдущем разделе.

ROMV-планировщик разделяет все транзакции во время их создания на две группы – запросы (queries) и транзакции, изменяющие данные (update transactions). Соответственно, транзакции разных типов обрабатываются по-разному. Такой протокол оказывается проще в реализации и позволяет получить большую часть выгод, предоставляемых версионными протоколами, которые описаны выше.

Транзакции обрабатываются следующим образом.

1. Транзакции, модифицирующие данные, выполняются в соответствием с протоколом S2PL. Этот протокол является вариантом 2PL. В нем все монопольные блокировки отпускаются лишь в конце транзакции. Каждая операция, изменяющая элемент данных, создает новую версию этого элемента. При завершении транзакции каждая такая версия помечается временной меткой, соответствующей времени завершения 2. Запросы (read-only transactions) обрабатываются подобно тому, как это происходит в протоколе MVTO. Каждому запросу также ставится в соответствие временная метка.

Но в данном случае она соответствует времени начала транзакции. При выборе версии для чтения запрос выбирает последнюю, завершенную к моменту старта запроса 1.1.2 Методы обеспечения атомарности и надежности транзакций В этом разделе мы приводим краткий обзор методов обеспечения атомарности и надежности транзакций при возможном возникновении сбоев в системе.

Далее мы будем подразумевать, что при возникновении сбоя теряются данные только из энергозависимой памяти (обычно это оперативная память), но при этом данные во внешней памяти (дисках, магнитных лентах) не теряются. Иными словами мы будем рассматривать мягкие сбои [9]2. Рассмотрение жестких сбоев в системе, когда повреждается внешняя память, выходит за рамки нашей работы.

Основная задача процедуры восстановления после сбоев заключается в том что:

(1) результаты зафиксированных транзакций должны быть сохранены в восстановленном состоянии базы данных (redo recovery); (2) результаты незафиксированных транзакций должны отсутствовать в восстановленном состоянии базы данных (undo recovery).

Основой идеей восстановления является избыточное хранение данных. Эти избыточные данные хранятся в журнале, содержащем последовательность записей об изменении базы данных. Как правило, в СУБД существует один общий журнал, в который заносятся записи об изменении базы данных всех транзакций.

Для журнала в оперативной памяти отводится специальная область для буферизации, поскольку если бы запись об изменении базы данных, которая должна поступить в Далее термин сбой без указания его типа будет обозначать мягкий сбой.

Рис. 1.2: Архитектура компонентов СУБД, относящихся к процедуре восстановления после сбоев журнал при выполнении любой операции модификации базы данных, реально немедленно записывалась бы во внешнюю память, это привело бы к существенному замедлению работы системы. Таким образом, при нормальной работе очередная страница выталкивается во внешнюю память журнала только при полном заполнении записями.

Итак, имеются два вида буферов - буфер журнала и буфер страниц оперативной выталкиваться во внешнюю память. На рисунке 1.2 графически изображены взаимосвязи между этими компонентами.

Проблема состоит в выработке некоторой общей политики выталкивания буферов, которая обеспечивала бы возможности восстановления состояния базы данных после сбоев.

Основным принципом согласованной политики выталкивания буфера журнала и буферов страниц базы данных является то, что запись об изменении элемента базы данных должна попадать во внешнюю память журнала раньше, чем измененный элемент оказывается во внешней памяти базы данных. Соответствующий протокол журнализации (и управления буферизацией) называется Write Ahead Log (WAL) [89] - “пиши сначала в журнал”, и состоит в том, что если требуется вытолкнуть во внешнюю память измененный элемент базы данных, то перед этим нужно гарантировать выталкивание во внешнюю память журнала записи о его изменении.

Другими словами, если во внешней памяти базы данных находится некоторый элемент базы данных, по отношению к которому выполнена операция модификации, то во внешней памяти журнала обязательно находится запись, соответствующая этой операции. Обратное неверно, т.е. если во внешней памяти журнала содержится запись о некоторой операции изменения элемента базы данных, то сам измененный элемент может отсутствовать во внешней памяти базы данных.

WAL-протокол гарантирует, что после сбоя во внешней памяти журнала есть вся необходимая информация для произведения отката всех незавершившихся транзакций (undo recovery). Однако это правило не гарантирует, что после сбоя в журнале будет необходимая информация для проведения “наката” (redo) зафиксированных транзакций.

Поэтому требуется еще одно условие на политику вытеснения записей журнала: перед фиксацией транзакции во внешнюю память должны быть вытеснены все записи журнала, относящиеся к этой транзакции (включая запись о фиксации транзакции).

Индивидуальный откат транзакций Для того, чтобы можно было выполнить по журналу индивидуальный откат транзакции, все записи в журнале от данной транзакции связываются в обратный список. Началом списка для незакончившихся транзакций является запись о последнем изменении базы данных, произведенном данной транзакцией. Для закончившихся транзакций (индивидуальные откаты которых уже невозможны) началом списка является запись о конце транзакции, которая обязательно вытолкнута во внешнюю память журнала. Концом списка всегда служит первая запись об изменении базы данных, произведенном данной транзакцией.

Обычно в каждой записи проставляется уникальный идентификатор транзакции, чтобы можно было восстановить прямой список записей об изменениях базы данных данной транзакцией.

Итак, индивидуальный откат транзакции выполняется следующим образом:

• Выбирается очередная запись из списка данной транзакции.

• Выполняется противоположная по смыслу операция: вместо операции INSERT выполняется соответствующая операция DELETE, вместо операции DELETE выполняется INSERT, и вместо прямой операции UPDATE - обратная операция UPDATE, восстанавливающая предыдущее состояние объекта базы данных.

• Любая из этих обратных операций также журнализуются (такие записи называются компенсационными). Непосредственно для индивидуального отката это не нужно, но при выполнении индивидуального отката транзакции может произойти мягкий сбой, при восстановлении после которого потребуется откатить такую транзакцию, для которой не полностью выполнен индивидуальный откат.

• При успешном завершении отката в журнал заносится запись о конце транзакции. С точки зрения журнала такая транзакция является зафиксированной.

Восстановление после мягкого сбоя К числу основных проблем восстановление после мягкого сбоя относится то, что одна логическая операция изменения базы данных может изменять несколько физических блоков базы данных, например, страницу данных и несколько страниц индексов. Страницы базы данных буферизуются в оперативной памяти и выталкиваются независимо. Несмотря на применение протокола WAL, после мягкого сбоя набор страниц внешней памяти базы данных может оказаться несогласованным, т.е. часть страниц внешней памяти соответствует объекту до изменения, часть - после изменения. К такому состоянию объекта не применимы операции логического уровня. Поэтому перед тем, как применять логические операции, необходимо некоторым образом восстановить физически целостное состояние базы данных. Состояние внешней памяти базы данных называется физически согласованным, если наборы страниц всех объектов согласованы, т.е. соответствуют состоянию объекта либо после его изменения, либо до изменения.

Существует два основных метода восстановления физической согласованности базы данных: теневой механизм и журнализация изменений внутри каждой страницы (pageoriented logging). Первый метод использовался в System R [89], а второй метод используется в очень популярном на данный момент алгоритме восстановления - ARIES [45]. Далее мы рассмотрим оба этих метода восстановления.

Восстановление на основе теневого механизма Основная идея теневого механизма заключается в следующем. При открытии файла базы данных таблица отображения номеров его логических блоков в адреса физических блоков внешней памяти считывается в оперативную память. При модификации любого блока файла во внешней памяти выделяется новый блок. При этом текущая таблица отображения (в оперативной памяти) изменяется, а теневая - сохраняется неизменной. Если во время работы с открытым файлом происходит сбой, во внешней памяти автоматически сохраняется состояние файла до его открытия. Для явного восстановления файла достаточно повторно считать в оперативную память теневую таблицу отображения.

В контексте базы данных теневой механизм используется следующим образом.

Периодически выполняются операции установления контрольных точек (checkpoints в System R). Для этого все логические операции завершаются, все буфера оперативной памяти, содержимое которых не соответствует содержимому соответствующих страниц внешней памяти, выталкиваются. Теневая таблица отображения файлов базы данных заменяется на текущую (правильнее сказать, текущая таблица отображения записывается на место теневой).

Физическое восстановление в этом случае происходит следующим образом: текущая таблица отображения заменяется на теневую (при восстановлении просто считывается теневая таблица отображения). После этого получается состояние базы данных как на момент сбоя. Тогда по логическим операциям журнала можно откатить все транзакции, которые начались до установки контрольной точки, но не завершились до сбоя, и восстановить транзакции, которые завершились после установки контрольной точки.

Основным недостатком метода является излишний перерасход памяти. Кроме того, при восстановлении c теневой копии приходится перевыполнять большое количество изменений, которые и так присутствовали во внешней памяти. Всех этих недостатков удается избежать в ARIES.

Алгоритм ARIES В ARIES все изменения производимые над блоками базы данных при выталкивании на внешний носитель, заменяют предыдущее значение этого блока (update in-place). Поэтому для восстановления как физической, так и логической согласованности БД используется журнал. Выделяется два типа записей в журнале: (1) логическая запись, которая содержит информацию о производимой операции, (2) страничная запись, которая содержит информацию об изменениях производимых в конкретной странице. Первый тип записей используется для отката (undo), а второй тип записей - для наката (redo).

Процесс восстановления выглядит следующим образом. Сначала проходит стадия анализа, во время которой на основе журнальной информации собираются сведения, необходимые для восстановления. В основном эта работа связана с определением тех транзакций, действия которых необходимо повторить, и тех, действия которых нужно отменить. После этого следуют стадии повторения и отмены. Обычно во время повторения в базу данных вносятся все изменения, которые были внесены в нее транзакциями, успевшими к моменту сбоя завершиться, а отмена, соответственно, заключается в том, чтобы отменить действия, совершенные транзакциями, нуждающимися в откате. В ARIES имеется некоторое отличие от этой схемы, а именно то, что на стадии повторения ARIES повторяет все действия, которые были отражены в журнале к моменту сбоя. То есть после этой стадии база данных находится в том же состоянии, в каком она была в момент сбоя. После этого уже происходит откат всех незавершенных транзакций.

Как и в System R, в ARIES время от времени выполняются контрольные точки. Однако в ARIES эта операция гораздо более эффективная, поскольку она не требует синхронного сброса всех буферов на диск и не приостанавливает на это время все текущие транзакции на изменение. Вместо этого в журнал записывается информация о грязных страницах в базе данных, а также таблица активных транзакций. На основе этих данных при восстановлении определяется точка в журнале, начиная с которой необходимо производить стадию повторения.

Отметим, что на стадии повторения необходимо определять, есть ли изменения в базе данных, относящиеся к данной записи или нет. Для этого в заголовке самой страницы хранится идентификатор записи журнала, которая описывает последнее изменение в данной страницы. В результате, сравнивая эти идентификаторы, удается узнать, есть ли рассматриваемые изменения на странице или нет.

Существуют и другие технические нюансы. Их описание можно найти в обзорной статье П. Чардина [43].

1.2 Платформа XML В данном разделе дается обзор основных технологий платформы XML, необходимых для изложения последующего материала.

1.2.1 Расширяемый язык разметки - XML Расширяемый язык разметки XML (Extensible Markup Language) [14] является подмножеством стандартного обобщенного языка разметки SGML (Standard Generalized Markup Language) [15]. Первоначально XML был разработан для представления информационных ресурсов в Web, в частности, как замена языка гипертекстовой разметки HTML (Hyper Text Markup Language) [16]. Одним из основных достоинств XML является его расширяемость, т.е. имеется возможность вводить новые тэги разметки, что невозможно в HTML. Однако применение XML не ограничивается только Web. В настоящее время XML широко используется в качестве средства обмена данными между различными приложениями в сети. Кроме того, XML стал стандартом де-факто для представления слабоструктурированных данных [54, 55]. В настоящей работе язык XML представляет интерес именно как формат представления слабоструктурированных данных.

На рисунке 1.3 изображен пример XML-документа. XML-документ состоит из различных элементов разметки и непосредственно содержимого документа - данных, Unix Network Programming Computer Networks представленных в текстовой форме. Тэги предназначены для определения элементов документа, их атрибутов и других конструкций языка. XML-документ определяется в спецификации языка как объект данных, который является правильно сформулированным (well-formed) в соответствии с требованиями спецификации XML. Все эти требования достаточно просты и естественны. Например, требуется, чтобы каждому открывающему тэгу соответствовал закрывающий тэг.

На сегодняшний день консорциумом W3C выпущена первая версия языка - XML 1.0, которая имеет статус рекомендованной.

Важной частью спецификации XML является язык описания схемы XML-документов - DTD (Document Type Denition). Фактически, при помощи DTD можно накладывать ограничения на структурный вид XML-документа. Для наложения более сложных ограничений существует более мощный язык описания схем XML Schema [17, 18].

1.2.2 Язык запросов XQuery Основным языком запросов к XML-данным является язык запросов XQuery [21]. На сегодняшний день процесс стандартизации XQuery практически завершен, и в скором времени будет выпущена первая официальная версия языка. С появлением XQuery большинство компаний, производящих коммерческие реляционные СУБД, заявило о введении дополнительных расширений для поддержки стандартов платформы XML (включая XQuery) в ближайших версиях своих продуктов.

Базовой частью языка XQuery являются путевые выражения (location path). Путевое выражение в XQuery основывается на синтаксисе языка XPath [20] и состоит из серии шагов, разделенных символом слэш (“/”). Результатом каждого шага является последовательность узлов. Результатом вычисления путевого выражения является последовательность узлов, формируемая на последнем шаге. Каждый шаг определяется тремя компонентами:

осью (axis), тестом (test) и предикатом (predicate). Синтаксически шаг записывается следующим образом: ::[]. Каждый шаг вычисляется в контексте, сформированном на предыдущем шаге. Вычисление шага для узла (будем называть этот узел текущим) осуществляется в несколько этапов, на каждом из которых строится промежуточная последовательность.

На первом этапе происходит перемещение от текущего узла по иерархии узлов в направлении, определяемом осью. В XQuery поддерживается 12 осей: child (последовательность дочерних узлов), (последовательность всех узлов потомков), parent (отец узла), attribute (последовательность узлов-атрибутов), self (текущий узел), descendant-or-self (последовательность всех потомков, дополненная самим узлом), ancestor (последовательность всех узлов предков), ancestor-or-self (последовательность всех узлов предков, дополненная самим узлом), following (последовательность всех последующих узлов), preceeding (последовательность всех предшествующих узлов), following-sibling (последовательность всех последующих узлов братьев) и preceeding-sibling (последовательность всех предшествующих узлов братьев).

Второй этап состоит в исключении из последовательности, полученной на первом этапе, узлов, не удовлетворяющих тесту. Тестом в XQuery может быть имя узла или символ “*”, обозначающий любое имя. Проверка на удовлетворение тесту состоит в сравнении имени узла с тестом.

На третьем этапе происходит фильтрация последовательности узлов, полученных на предыдущем этапе, на основании результата вычисления предиката для каждого узла.

Приведем пример путевого выражения, результатом которого является последовательность описания всех товаров, предлагаемых к продаже Смитом:

document("items.xml")/child::*/ child::item[self::*/child::seller="Smith"] /child::description Существует сокращенная форма записи путевых выражений, в которой ось child можно не указывать; ось descendant опускается, но перед этим шагом ставится два слэша;

переход по оси parent описывается через две точки; вместо оси attribute ставится @.

Основной конструкцией XQuery является FLWOR-выражение, обладающее следующим синтаксисом:

( for $var1 in expr1 | let $var2 := expr2 )+ where expr order by expr return expr FLWOR-выражение состоит из пяти составляющих: разделов for, let, where, order by и return. В разделе for определяется переменная $var1, которая последовательно связывается с каждым из элементов последовательности, получаемой в результате вычисления выражения expr1. В разделе let переменная $var2 связывается с результатом вычисления выражения expr2. Допускается несколько разделов for или let. В разделе where значения переменных фильтруются на основе предиката expr3. Раздел order by позволяет отсортировать кортежи связанных переменных в соответствии с выражением expr4. Наконец, раздел return определяет результат FLWOR-выражения: выражение expr вычисляется для каждого связывания переменных, для которого результатом вычисления предиката в разделе where секции является “истина”. Результатом всего FLWOR-выражения является последовательность узлов, полученных после вычисления раздела return.

При помощи FLWOR-выражений на XQuery можно выражать операции соединения, трансформации, группировки и т. д. Особую роль играет операция трансформации, поскольку она очень часто используется в Web-приложениях при построении динамических HTML-страниц. В XQuery операция трансформации выражается при помощи конструкторов элемента и атрибута. Примером трансформации является следующий запрос, результатом которого является новое представление книг с названием “Data on the Web” и автором “Serge Abiteboul”:

for $book in //book where $book/author = ’Serge Abiteboul’ and XQuery является функциональным языком, поэтому в нем выражения могут быть вложены друг в друга произвольным образом. Например, в разделе for FLWOR-выражения может находиться другое FLWOR-выражение и т. д. с любым уровнем вложенности. Помимо этого, на XQuery пользователь может определять и использовать свои собственные функции.

Также существует достаточно большое количество встроенных стандартных функций [22].

Более детальное описание XQuery можно найти в статье Чемберлина [41].

1.2.3 Язык модификаций XUpdate К настоящему времени рабочая группа XQuery в W3C находится только в процессе разработки стандартного языка изменений частей XML-документов. В нашей работе мы используем подмножество языка изменения частей XML-документов, который был предложен в статье Татаринова [56]. В дальнейшем язык изменений мы будем называть XUpdate. Синтаксис этого языка выглядит следующим образом:

update := ’InsertInto’ ’(’ constr1 ’,’ locpath ’)’ | ’InsertBefore’ ’(’ constr2 ’,’ locpath ’)’ | ’InsertAfter’ ’(’ constr2 ’,’ locpath ’)’ | constr1:= ’element’ ’{’ QName ’}’ content | ’attribute’ ’{’ QName ’}’ content constr2 := ’element’ ’{’ QName ’}’ content content := ’{’ PCDATA ’}’ | ’{’ ’}’ Каждая операция принимает на вход несколько аргументов (constr1, constr2 и locpath).

Выражения constr1 и constr2 определяют новые узлы. Выражение locpath1 определяет путь адресации узлов в XML-документе, которые являются целевыми узлами операции изменения.

Ниже приводится описание каждой операции.

• InsertInto(constr1, locpath): вставляет новый узел (элемент или атрибут) в каждый целевой узел в позицию последнего дочернего узла.

• InsertBefore(constr2, locpath): вставляет новый узел (только элемент) для каждого целевого узла в позицию предшествующего брата.

• InsertAfter(constr2, locpath): вставляет новый узел (только элемент) для каждого целевого узла в позицию последующего брата.

• Delete(locpath): осуществляет глубокое удаление узлов (вместе со всеми потомками), определяемых locpath.

• Rename(locapth, QName): присваивает новое имя QName целевым узлам операции.

1.3 XML-ориентированные СУБД С ростом популярности XML в качестве формата описания слабоструктурированных данных появились огромные массивы XML-данных, для которых необходимы развитые средства управления. Это стало толчком к развитию XML-ориентированных СУБД, позволяющих эффективным образом управлять XML-данными. XML-ориентированные СУБД делятся на два класса [42].

К первому классу относятся СУБД с поддержкой XML, в которых технологии управления XML-данными реализованы на основе существующей модели данных. На сегодняшний день среди систем этого типа наиболее развиты средства поддержки XML в реляционных СУБД (РСУБД).

Во второй класс входят СУБД, изначально построенные с учетом модели данных XML3.

Этот тип систем на сегодняшний день переживает бурный этап развития. За счет того, что на физическом и модельном уровне эти системы учитывают особенности XML, они более эффективны для управления XML-данными, чем СУБД первого класса. Системы управления базами XML-данных, построенные с нуля и в полной мере основанные на модели данных XML мы будем назвать прирожденными XML-СУБД (или XML-СУБД).

1.3.1 РСУБД с поддержкой XML В настоящие время практически все коммерческие реляционные СУБД [28, 36, 32] предоставляют средства управления XML-данными. В последующих разделах мы делаем краткий обзор этих средств и обсуждаем их возможности и ограничения.

XML-представления XML-представления (XML views), которые появились в РСУБД достаточно давно, позволяют реализовать XML-оболочку между реляционным хранилищем данных и Далее в этой работе под моделью данных XML мы будем подразумевать модель данных языков XPath/XQuery [19].

Рис. 1.4: Определение XML-представления в MS SQL Server 2000/ /Customer[CustomerID="John Smith"]/Order[@ProductName="DVD"] приложениями. При помощи XML-представления можно интегрировать в один общий нематериализованный XML-документ (или набор нематериализованных XML-документов) уже существующие (legacy) реляционные данные. Фактически XML-представления позволяют приложениям оперировать с реляционными данными в терминах модели данных XML. Далее мы рассмотрим, как определяются XML-представления в РСУБД, на примере SQL Server 2000/2005.

специального языка [26], который синтаксически очень похож на язык описания схем XMLдокументов XML Schema [17, 18], но в нем еще есть средства определения отображения между нематериализованными XML-представлениями и реляционными отношениями. На основе этого отображения система преобразует запросы пользователя к XML-представлению в запросы к реляционным отношениям. На Рисунке 1.4 приведен пример XML-представления, определенного над двумя отношениями:

Customers(CustomerID int PRIMARY KEY, CompanyName varchar(20)) Orders(OrderID varchar(10) PRIMARY KEY, CustomerID int FOREIGN KEY REFERENCES, ProductName varchar(20)) Атрибуты sql:relation, sql:eld и sql:relationship определяют отображение отношений на представление. Представление на Рисунке 1.4 отображает строки отношения Customers в элементы с именем Customers, а соответствующие им заказы Orders отображаются в набор вложенных элементов Order. Важнейшей конструкцией является аннотация CustOrders, которая определяет соединение отношений Customers и Orders, и за счет этого в каждом элементе Customer содержатся вложенные элементы Order, которые относятся именно к этому Customer. Соединение отношений определяется на основе первичного ключа CustomerID в отношении Customers и внешнего ключа CustomerID в отношении Orders. Более подробное описание отображений можно найти в работе Майкла Риса [27].

На рисунке 1.5 изображен пример запроса к XML-представлению. Значением атрибута sql:mapping-schema является имя файла, в котором содержится определение XMLпредставления (в нашем примере это файл с именем CustOrders.xml ), а значением элемента sql:xpath-query служит запрос на языке XPath. Результатом этого запроса будет набор заказов DVD дисков, которые были сделаны Джоном Смитом.

Кроме того, в SQL Server 2000/2005 пользователь может производить элементарные операции модификации виртуальных XML-представлений на основе механизма updategrams. В основном этот механизм позволяет изменять значения атрибутов или текстовых эементов, но не позволяет изменять структуру XML-документа. Updategram представляет собой конструкцию, состоящую из двух блоков. В первом блоке before-image пользователь указывает узлы XML-документа, которые необходимо изменить, а во втором блоке after-image указывается новое значение узлов из блока before-image. В свою очередь, система автоматически вычисляет разницу между before-image и after-image, создает набор соответствующих операторов SQL и выполняет их. На рисунке 1.6 приведен пример updategram, выполнение которой приводит к замене значения элемента CompanyName для заказчика “LAZYK” на “Corp2” и смену идентификатора заказа 10482 на 10354.

В Oracle [29] средства определения нематериализованных XML-представлений очень похожи на аналогичные средства в SQL Server 2000/2005. Но операции обновления Рис. 1.6: Пример запроса на изменение к XML-представлению возможны только на уровне всего XML-документа - пользователь может удалять целиком XML-документ и вставлять новый, удовлетворяющий предписанной схеме. В IBM DB XML Extender 8.0 [31] также существуют схожие средства построения виртуальных XMLпредставлений. Спецификация отображения описывается в DAD (Document Access Denition) файле. При этом операции обновления можно выполнять только над отношениями и нет средств выполнять операции изменения через XML-представление.

Важно заметить, что на данный момент коммерческие РСУБД поддерживают только ограниченный вид XML-представлений, в которых соединения отношений производятся только на основе пары первичный ключ - внешний ключ, а также для избежания неопределенности при трансляции операции изменений над представлением в операции изменения реляционных отношений вложенность узлов поддерживается в ограниченном виде.

Хранение XML-документов в реляционных таблицах Вторым направлением исследований по поддержке XML в РСУБД являются методы хранения XML-документов в реляционных СУБД. При этом основной задачей здесь является метод отображения XML-документа на набор реляционных отношений. В следующих параграфах приводится обзор базовых методов отображения XML-документов на реляционные таблицы: Edge [95], Attribute [95], Inlining [51], STORED [52]. Детальный обзор и сравнение этих методов можно найти в [53].

Метод Edge основывается на интуитивном представлении XML-документа как дерева, состоящего из набора ребер. Создается одно отношение с именем edge, каждый кортеж которого хранит одно ребро дерева XML-документа. Как показано на рисунке 1.7, это Data on the Рис. 1.7: Отображение XML-документа на отношения на основе метода Edge XML-документе присваивается уникальный идентификатор. В атрибутах source и target содержатся идентификаторы верхних и нижних концов ребра соответственно. Атрибут ordinal служит для определения порядка ребер в XML-документе. В нем содержится порядковое число ребра среди других ребер, обладающих одним и тем же верхним (source) узлом.

Наконец, атрибут data определяет, является ли целевой узел ребра (target) листовым или внутренним. В первом случае значение data указывает текстовое значение узла; во втором случае значение этого атрибута равно NULL.

Недостатком метода Edge является его низкая эффективность, поскольку выполнение запросов над отношением edge требует выполнения большого количества операций соединения. Для иллюстрации этого факта рассмотрим пример.

1.7. Этот запрос выбирает содержание элемента rstname первого автора первой книги в документе. Этот запрос соответствует следующему оператору SQL над отношением edge:

SELECT data FROM edge e1, edge e2, edge e Рис. 1.8: Отображение XML-документа на реляционные таблицы на основе метода Attribute В этом запросе производится две операции соединения, выраженные при помощи условий (5) и (7).

Метод Attribute является развитием метода Edge. Фактически, в методе Attribute происходит горизонтальное разделение отношения edge по атрибуту name. В результате отношение edge разделяется на набор отношений, число которых определяется числом различных значений атрибута name. Заголовки полученных отношений отличаются от заголовка отношения edge отсутствием атрибута name. Семантика остальных атрибутов такая же, как и в методе Edge. На рисунке 1.8 изображен пример отображения XMLдокумент на отношения при помощи метода Attribute.

По сравнению с методом Edge в методе Attribute размер отношений меньше, чем размер отношения edge, но при этом количество операций соединения остается таким же. Количество предикатов на значения имен элементов сокращается. Метод Attribute очень хорошо подходит для запросов типа //, поскольку в этом случае все необходимые узлы хранятся в одной таблице Attrnodename.

Метод Inlining отличается от предыдущих методов тем, что для его использования dept_id=”dept1” Рис. 1.9: Отображение XML-документа на реляционные таблицы на основе метода Inlining необходимо знать схему XML-документа4. XML-документ распределяется по некоторому набору таблиц. Этот набор определяется исходя из схемы XML-документа. Для каждого элемента по схеме, которому соответствуют дети с множественностью “+” или “*”, заводится отдельная таблица. Элементы с множественностью не более одного встраиваются в кортеж родителя. Каждый кортеж в таблице обладает уникальным идентификатором ID, а также содержит идентификатор родителя ParentId. Это необходимо для восстановления отношения предок-потомок между узлами. Пример этого отображения (заимствован из [53]) изображен на рисунке 1.9. В работе [51] показывается, что метод Inlining превосходит все методы, описанные выше. Это происходит за счет того, что количество операций соединения, требуемых для выполнения XPath запросов, сокращается. Отметим, что в оригинальном методе Inlining теряется информация о порядке следования узлов в XML-документе. Однако это не означает, что это является ограничением метода. Например в работе Татаринова [57] предлагается расширение метода Inlining, в котором поддерживается порядок следования узлов, и при этом сохраняются все преимущества оригинального метода.

Основная идея метода STORED заключается в следующем: XML-документ хранится в большом объекте типа BLOB/CLOB, который в свою очередь принадлежит кортежу Схема XML-документа может быть описана, например, на языке DTD.

некоторой таблицы, которую мы будем называть таблицей документов (document table). Для увеличения скорости выборки данных вводятся дополнительные индексированные таблицы.

Для определения частей XML-документа, которые должны храниться в индексированной таблице, проектировщик базы данных должен определить STORED-запрос. Отметим, что индексированные таблицы частично дублируют содержание таблицы документов. На рисунке 1.10 на примере изображена основная идея метода STORED. Индексированная таблица в соответствии с STORED-запросом хранит значения price и description. Мы предполагем, что таблица проиндексирована по атрибуту price. В результате, например запрос /site/auction[price= /* пример изменения частей XML-документов */ UPDATE docs SET xCol.modify(’ Надо отметить, что тип данных XML появился сравнительно недавно и предоставляет наибольшую функциональность по управлению XML-документами в РСУБД.

Действительно, метод хранения в данном случае максимально приближен к прирожденным методам (например в работе [59] описан метод хранения в DB2), что положительно влияет на эффективность выполнения запросов на чтение и изменение XML-документов. Кроме того, средства выборки реализуются при помощи мощного функционального языка XQuery, на котором можно писать достаточно сложные запросы. Фактически, с появлением типа XML можно говорить, что в РСУБД появилась поддержка XML, максимально приближенная к прирожденным СУБД к обсуждению которых мы переходим.

1.3.2 Прирожденные XML-СУБД Появление класса прирожденных XML-СУБД обусловлено требованием эффективной обработки огромных объемов XML-данных. В работах [78, 80] обсуждается ограниченность реляционных баз данных для управления древовидными, слабоструктурированными XMLданными. Авторы этих работ приходят к выводу, что построение высокоэффективной системы управления XML-данными требует пересмотра ряда важнейших принципов, включая организацию внешней памяти, организацию обработки XML-данных в основной памяти, управление транзакциями, индексацию данных и т. д. На сегодняшний день во многих из этих областей ведутся активные исследования и появляются новые прототипы систем. Среди наиболее развитых прирожденных XML-СУБД можно выделить Natix [78], Tamino [79], Excelon [37], Timber [80], Sedna [76], eXist[81] и X-Hive [82].

В этом разделе мы рассмотрим общую архитектуру и основные физические особенности прирожденной XML-СУБД Sedna (Седна), которая разрабатывается в течении последних трех лет в институте системного программирования РАН. В контексте этой системы автором были разработаны методы управления XML-транзакциями, которые представлены в главе 5. Выбор системы Седна обуславливается не только участием автора в проекте разработки этой системы, но и тем фактом, что на сегодняшний день Седна является одной из самых эффективных XML-СУБД [77]. Важно отметить, что хотя предложенные методы были разработаны в контексте Седна, область их применения не ограничивается этой системой.

Далее мы переходим к обсуждению физических особенностей организации Седна. Более детальное описание можно найти в диссертационной работе Фомичева [61].

An Introduction to Database

Блоки данных, соответствующие одному узлу схемы, связываются при помощи указателей prev-block и next-block в двунаправленный список. Узлы в такой цепочке частично упорядочены. Это означает, что если block1 предшествует в списке block2, то каждый узел из block1 предшествует любому узлу из block2 в соответствии с порядком следования узлов в XML-документе. Порядок узлов в одном блоке не соответствует их порядку в XML-документе, но он может быть восстановлен при помощи специальных указателей, которые мы обсудим ниже.

В системе хранения разделяется структурная составляющая узла и текстовое значение этого узла. Для текстовых значений узлов применяется устоявшийся и хорошо себя зарекомендовавший метод - слоттированные страницы (slotted page) [62], специально разработанный для хранения записей переменной длины. Структурная составляющая, представленная в виде дескрипторов узлов, определяет взаимосвязь (например родитель, дескрипторов узлов является то, что в каждом блоке они обладают одинаковым размером.

В совокупности с тем, что дескрипторы узлов внутри блока неупорядочены, это существенно облегчает управление свободным местом в блоке и позволяет проводить операции вставки и удаления дескрипторов узлов в блоке без перемещения остальных дескрипторов в блоке.

Общая структура дескриптора узла изображена на рисунке 1.13. Дескриптор содержит несколько ссылок на соседние с ним узлы, которые мы сейчас подробно рассмотрим.

Важно отметить, что все ссылки реализуются при помощи указателей, переход по которым осуществляется очень эффективно.

Указатели left-sibling и right-sibling ссылаются на дескрипторы левого и правого братьев соответственно. Эти указатели служат для поддержания связанности узлов в документе. Дескрипторы братьев могут находиться как в том же блоке, что и рассматриваемый дескриптор, так и в другом блоке в зависимости от соответствия узлу схемы.

Указатели предыдущий узел в блоке (prev-in-block) и следующий узел в блоке (next-in-block) служат для связи узлов в одном блоке в соответствии с их порядком следования в документе. Таким образом, используя эти указатели, можно эффективно восстановить порядок следования узлов в XML-документе, соответствующих одному узлу схемы. Например, ответом на запрос /library/book/tittle должна быть последовательность узлов title, отсортированная в соответствии с порядком следования узлов title в XML-документе. В описываемом методе хранения такой запрос можно выполнить следующим образом: по описывающей схеме получить указатель на цепочку блоков title, а затем, используя указатель next-in-block и указатели между блоками prev-block и next-block, выбрать сразу в упорядоченном виде последовательность узлов title.

Хранение в дескрипторе узла указателей на всех детей данного узла может приводить к неограниченно большому размеру дескриптора узла, который даже возможно не будет указатели не на всех детей данного узла, а только на первых детей узла, принадлежащих разным узлам схемы. Рассмотрим это на примере узла library, изображенного на рисунке 1.12. Он имеет в качестве детей два узла book и один узел paper, которые соответствуют двум узлам по схеме. Вне зависимости от количества узлов book и paper в дескрипторе узла library будет храниться два указателя на детей: указатель на дескриптор первого узла book и указатель на первый узел paper. Стратегия выполнения запроса /library/book[2] с использованием этих указателей может быть следующая: получить по описывающей схеме указатель на блок, в котором хранится дескриптор узла library, затем по указателю перейти на первый узел book, и, наконец, по указателю next-in-block перейти ко второму узлу book.

Указатель на родителя (parent) служит для ссылки на родителя данного узла. Важно отметить, что этот указатель является косвенным. Он указывает на некоторую ячейку сделано для эффективного выполнения операции модификаций. Например, при вставке некоторого узла возможно переполнение блока, что влечет за собой перемещение части дескрипторов узлов в другой блок. В случае использования прямого указателя на родителя придется менять значение указателя parent для каждого узла, который является ребенком перемещаемого узла. При использовании же таблицы косвенности необходимо только соответствующим образом изменить значение в ячейке таблицы косвенности.

Запись узла в таблице косвенности (node handle) является указателем на запись для этого узла в таблице косвенности. Важнейшим свойством node handle является то, что он никогда не изменяется во время “жизни” узла в XML-документе. Поэтому node handle может использоваться в качестве уникального идентификатора узла.

Наконец, метка label является нумерующим числом узла. Нумерующие числа узлов позволяют эффективным образом определять структурную взаимосвязь между узлами.

Нумерующие числа позволяют определять порядок между узлами и отношение предокпотомок. Например, нумерующие числа могут использоваться при выполнении запроса //title для восстановления порядка следования узлов title. Детальное описание нумерующей схемы в Седна можно найти в работе Азнауряна, Новака и Кузнецова [87].

Управление памятью для хранимых XML-данных Как описывалось в предыдущей секции, связь между дескрипторами узлов реализуется при помощи указателей (прямых или косвенных). В результате при выполнении запросов над описанными структурами данных очень часто выполняется операция перехода по указателю.

Таким образом, эффективность этой операции существенным образом влияет на общее время выполнение запросов в системе.

В Седна реализован оригинальный метод управления памятью, основанный на слоистой организации адресного пространства базы данных, который позволяет выполнять операции перехода по указателям очень эффективно. Кроме того, метод позволяет иметь размер базы данных, достаточный для представления всех сущностей базы данных5. Мы в этой работе только отметим базовые идеи организации слоистого адресного пространства (САП), а подробное описание можно найти в диссертационной работе Фомичева [61].

На рисунке 1.14 изображена архитектура слоистого адресного пространства. Далее мы описываем компоненты этой архитектуры.

располагается в отдельном процессе операционной системы (рисунок 1.14). Для поддержки сессии пользователя на стороне сервера также запускается отдельный процесс, в котором Метод позволяет адресовать 64-х разрядные адресные пространства.

есть свои копии подсистемы выполнения запросов и подсистемы поддержки САП. В рамках одновременно может быть запущено несколько пользовательских сессий, в то время как менеджер буферной памяти - один на базу данных.

САП проще всего представить себе как набор слоев одинакового размера. Размер слоя фиксирован и не превышает размера адресного пространства процесса, а точнее той его части, которая может быть адресована процессом.

Адресом в слоистом адресном пространстве называется пара (layer, addr), где layer - номер слоя (представляет собой целое число) и addr - адрес объекта в этом слое адресном пространстве, мы будем употреблять более короткое обозначение xptr (от eXtended pointer ).

выполняемой в данный момент времени транзакции имеется свое адресное пространство, поскольку каждая транзакция выполняется в отдельном процессе. На рисунке 1.14 показаны четыре уровня памяти: (1) слоистое адресное пространство, (2) виртуальное адресное пространство процесса, (3) буферная память, (4) внешняя память.

Работа с САП обеспечивается через последовательное отображение САП на оставшиеся уровни памяти. При этом единицей отображения является страница6. Для каждой страницы САП должно быть выделено место на диске (отображение САП на внешнюю память), а во время работы с этой страницей она должна быть помещена в оперативную память (отображение САП на буферную память) и должна быть доступна по некоторому адресу в процессе транзакции (отображение САП на виртуальное адресное пространства процесса).

Отображение объекта САП с адресом xptr=(layer, addr) на виртуальное адресное пространство процесса, а точнее на его часть - область отображения САП, производится путем отбрасывания значения layer. В соответствии с таким отображением, для того чтобы обратиться к объекту по адресу xptr=(layer, addr) в САП, достаточно обратиться к объекту по адресу addr в виртуальном адресном пространстве процесса. Предложенное отображение не является однозначным, т.е нескольким адресам САП может соответствовать один адрес виртуального адресного пространства процесса. В [61] приводится эффективное решение этой проблемы.

Для отображения адреса виртуального адресного пространства процесса на буферную память используются стандартные системные вызовы: MapViewofFile [38] в Wndows и mmap [39] в Linux.

Наконец, отображение САП на внешнюю память (мы считаем, что это файл базы данных на жестком диске) осуществляется следующим образом. Для блока с адресом xptr=(layer, adrr) смещение в файле определяется по формуле f = layer s + (addr p1 ), где S - размер слоя САП, а p1 - левая граница области отображения САП.

Технологии платформы XML бурно развиваются как в научном сообществе специалистов по базам данных, так и ведущими коммерческими производителями СУБД. Разработано огромное количество методов хранения XML как в реляционных СУБД, так и в прирожденных XML-СУБД. Однако для получения зрелой и законченной технологии управления XML-данными, необходимо также иметь развитые средства управления транзакциями над XML-данными. С одной стороны, к сегодняшнему дню уже разработано Далее термины блок и страница мы будем использовать как взаимозаменяемые.

достаточно большое количество методов управления транзакциями, которые можно было бы использовать для управления XML-транзакциями. Однако применимость этих методов для XML является открытым исследовательским вопросом. Именно ответу на этот вопрос, а также обсуждению сопряженных методов управления XML-транзакциями посвящена следующая глава.

Глава Существующие методы управления параллельными XML-транзакциями Настоящая глава посвящена описанию существующих методов управления параллельными транзакциями в XML-ориентированных СУБД. Кроме того, делаются выводы о применимости этих методов для эффективного управления XML-транзакциями.

2.1 XML-транзакции в реляционных СУБД Реляционные СУБД уже достаточно давно достигли стадии зрелости, а это подразумевает, что в них существует эффективная поддержка транзакций. Однако управление транзакциями (в частности контроль параллельного выполнения транзакций) в них реализовано с учетом реляционной модели данных, которая существенно отличается от иерархической модели XML.

Поддержка XML в РСУБД реализуется в виде некоторой надстройки над реляционной моделью. Но реальная обработка XML-запросов происходит в реляционном ядре СУБД.

Когда XML-запрос доходит до реального выполнения, он уже транслирован в набор SQL-запросов, и подсистема выполнения воспринимает их как обычные запросы над реляционными данными. В результате во многом теряется информация о иерархической структуре XML и семантике XML-запросов. В частности, это приводит к тому, что реляционный менеджер блокировок во многих случаях создает искусственные конфликты между транзакциями, даже если он использует блокировки на уровне кортежей. Ниже для каждого типа хранения XML-документов в РСУБД, описанных в вводной главе, мы рассматриваем большое количество типичных ситуаций, в которых реляционный менеджер блокировок создает искусственные конфликты между транзакциями. Тем самым существенно снижается пропускная способность и время отклика транзакций в РСУБД при наличии конкурентных транзакций, работающих с одним XML-документом на чтение и изменение.

Отметим, что ниже мы не рассматриваем нематериализованные XML-представления, поскольку средства изменения XML-документов через нематериализованные представления на данный момент либо вообще отсутствуют в РСУБД, либо развиты очень слабо.

использовании отображения XML-документов на отношения Сценарий 1: вставка нового узла на верхнем и нижнем уровнях иерархии Предположим, что транзакция T1 выполняет запрос InsertInto(< author/ >, /book), а вторая транзакция T2, запущенная параллельно с T1, намерена выполнить запрос /book/author/f irstname. Рассмотрим, на какие кортежи будут устанавливать блокировки эти транзакциями для метода хранения Edge. Транзакция T1 должна, как минимум, заблокировать на чтение кортеж, соответствующий ребру (корень документа, book) (первый кортеж на рисунке 1.7), и заблокировать на запись новый, вставленный кортеж, соответствующий новому ребру (book, author). В то же время транзакции T2 необходимо выполнить SQL-запрос с двумя операциями соединения таблицы edge и двумя предикатами на значения имен узлов (см. пример для метода Edge). В результате транзакции T необходимо заблокировать кортежи с именем author. Но один из этих кортежей уже заблокирован на запись первой транзакцией. Поэтому вторая транзакция вынуждена ожидать завершения первой. Если даже в РСУБД используются предикатные блокировки (реализованные, например, на основе блокировок интервалов ключей в индексе), то транзакция T1 перед выполнением второго шага путевого выражения должна заблокировать на чтение предикат source = 1 name = “author, который запретит вставку новых элементов author. Фактически, получается, что вставка узла на верхнем уровне блокирует навигацию к нижним узлам. Схожая ситуация возникнет и для других методов хранения XML-документов.

Конфликт между транзакциями T1 и T2 является искусственным, поскольку вставка пустого элемента author никак не может повлиять на результат выполнения путевого выражения /book/author/f irstname. Фактически, эти операции коммутативны. Конфликт возник бы, если первая транзакция вставляла элемент author с вложенным элементом rstname.

Далее рассмотрим новую пару конкурентных транзакций. Транзакция T1 InsertInto(< f irstname > John < /f irstname >, /book/author), а T2 - /book//lastname.

Очевидно, что на логическом уровне между этими транзакциями нет конфликта, однако менеджер блокировок в РСУБД вновь зафиксирует конфликт. Действительно, вставка элемента rstname требует установки эксклюзивной блокировки на новый кортеж, а выполнение поиска всех элементов lastname требует просмотра всех кортежей, которые относятся к узлам, находящимся под узлом book. В результате транзакция T2 будет пытаться установить разделяемую блокировку и на кортеж, вставленный транзакцией T1, что приведет к ее блокировке. Таким образом, даже вставка узла на нижнем уровне иерархии приводит к искусственным конфликтам с читающими транзакциями.

Сценарий 2: вставка нового узла между существующими братьями Рассмотрим ситуацию когда транзакция намерена вставить узел, после некоторого существующего узла. Для этого она использует операцию InsertAf ter(< author/ > Поскольку эта вставка осуществляется между существующими узламиbook/title).

братьями title и author, то изменяется их относительный порядок. Таким образом, необходимо изменить значение атрибута ordinal для существующего элемента author. В результате менеджер блокировок установит на него эксклюзивную блокировку. Получается, что вставка узла приводит к блокировке всех узлов-братьев, находящихся справа от него. Очевидно, что создаст множество искусственных конфликтов с параллельными транзакциями на чтение.

Дополнительная проблема связана с тем, что менеджер блокировок в РСУБД, используя блокировки на уровне кортежей, иногда не может обеспечить сериализацию транзакций. Действительно, две параллельные транзакции, запускающие один и тот же запрос InsertInto(< author/ >, /book), не будут конфликтовать в РСУБД. Однако на самом деле конфликт существует, поскольку перестановка этих операций влияет на порядок вставленных узлов. Единственное возможное решение - использовать блокировки на уровне таблицы. Очевидно, что это слишком грубое решение, которое вообще заблокирует все читающие транзакции. Кроме того, как правило, в коммерческих РСУБД есть средство “сделать подсказку” (hint) менеджеру блокировок, какой уровень блокировок использовать.

Но при этом совершенно необязательно, что он будет использовать эту подсказку.

Сценарий 3: удаление листового узла При описании этого сценария мы подразумеваем, что для метода хранения используется метод Inlining (напомним, что согласно результатам сравнительного анализа, этот метод является наиболее эффективным для хранения XML-документов). Этот метод сокращает количество дорогостоящих операций соединения за счет встраивания улов-детей в кортеж родителя. Однако это приводит к возникновению дополнительных конфликтов, поскольку, вообще говоря, разные узлы собираются в одну гранулу.

(/Dept/Student[@st_id="123"]/Name) (см. рисунок 1.9). С логической точки зрения конфликта между этими транзакциями нет, но в РСУБД он возникнет, поскольку для элемента Student атрибут st_id и элемент Name хранятся в одном кортеже. При этом транзакции T1 необходимо установить на этот кортеж разделяемую блокировку, а транзакции T2 установить на него же эксклюзивную блокировку.

Сценарий 4: удаление поддерева В этом сценарии мы рассмотрим транзакцию T, которая удаляет поддерево Student с именем “st1”: Delete(/Dept/Student[Name=“st1”]). Мы вновь будем предполагать, что используется метод Inlining, хотя описанные ниже проблемы относятся и к другим методам.

В работе [56] показывается, что рассматриваемое удаление поддерева может быть реализовано следующими двумя операторами SQL:

DELETE FROM Student WHERE Name="st1" DELETE FROM Enroll WHERE ParentID NOT IN (SELECT ID FROM Student) Однако второй оператор SQL заблокирует все кортежи в таблице Student, как минимум, в разделяемом режиме, что является избыточным. Фактически, удаление поддерева приводит к блокировке в разделяемом режиме всех таблиц, в которых содержатся узлы-потомки. В результате, например, транзакция, которая присваивает новое имя студенту c идентификатором “st2”, будет конфликтовать с исходной транзакцией T.

Сценарий 5: путевые выражения с предикатом В этом сценарии мы рассмотрим транзакцию, которая выполняет путевое выражение с предикатом: /Dept/Student[@st_id=“123”]/Enroll[. !=“CS20”]/text(). Этот запрос транслируется в SQL-запрос в котором есть предикат-соединение и два предиката на значения узлов. Например для метода Inlining он будет выглядеть следующим образом:

SELECT TEXT

Эта стратегия соответствует плану в котором предикаты “опущены” и поэтому вполне может быть выбрана оптимизатором в качестве оптимальной.

Однако при такой стратегии на кортежи, которые не будут удовлетворять предикатусоединения, будут наложены разделяемые блокировки. Так, если бы у студента с идентификатором "124" были бы элементы Enroll, не удовлетворяющие предикату E.TEXT != "CS20", то они были бы заблокированы. Причем в оригинальном путевом выражении они не адресуются.

Фактически получается, что операции соединения могут заблокировать кортежи, которые не адресуются в исходном путевом выражении. С учетом того, что операция соединения выполняется несколько раз даже для простых путевых выражений, менеджер блокировок может создавать большое количество дополнительных искусственных конфликтов.

использовании типа XML или метода STORED При использовании для хранения XML-документа типа XML текущие реализации коммерческих РСУБД не используют каких-то специальных блокировок внутри иерархии XML (например, это явно указано в технической статье про MS SQL Server 2005 [28]).

Используется обычный менеджер блокировок, который при обращении к XML-документу блокирует кортеж, в котором находится этот XML-документ. Таким образом, в этом случае получается гранулированность на уровне всего XML-документа.

При использовании метода STORED ситуация примерно такая же. Например, при проведении операции изменения в любом случае РСУБД устанавливает эксклюзивную блокировку на весь BLOB/CLOB объект, даже если необходимые данные присутствуют в дополнительных индексированных таблицах. Это делается по той причине, что необходимо поддерживать BLOB/CLOB объект и дополнительные таблицы в консистентном состоянии.

2.2 XML-транзакции в прирожденных XML-СУБД В отличие от СУБД, в которых поддержка XML построена на основе уже существующих механизмов управления данными, в прирожденных XML-СУБД все базовые механизмы управления данными должны строиться с нуля. Это включает в себя и механизм управления транзакциями. С одной стороны, это требует больших усилий, но, с другой стороны, при разработке таких механизмов можно учитывать как особенности иерархической структуры XML, семантику XML-операций, организацию внешней памяти и методы обработки XMLданных в оперативной памяти, так и основные приложения прирожденных XML-СУБД.

Поэтому в этом разделе мы выделим некоторые важные приложения XML-СУБД, а затем рассмотрим существующие специальные методы управления XML-транзакциями в прирожденных XML-СУБД.

2.2.1 Основные приложения XML-СУБД На сегодняшний день одним из самых популярных приложений XML-СУБД являются Web-приложения [88], основанные на XML. Популярность XML-СУБД в данном случае объясняется тем, что функциональный язык XQuery, являющийся важнейшим компонентом технологии управления XML-данными, может использоваться не только в качестве языка запросов к XML-данным, но и как средство для выражения логики приложения, основанного на технологии XML. Прежде всего этот подход удобен тем, что преодолевается проблема потери соответствия [93], которая возникает при одновременном использовании нескольких языков программирования, основанных на разных моделях данных и парадигмах. Например, если разработчик использует язык Java для выражения логики приложения и язык XSLT для визуализации данных1, то он вынужден заботиться об отображении между объектно-ориентированной моделью данных и моделью данных XML.

Обеспечение такого отображения может приводить, как к усложнению кода приложения, так и к падению эффективности приложения.