автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы управления транзакциями в XML-ориентированных СУБД

Российская Академия Наук Институт Системного Программирования

УДК 681.3.06 на правах рукописи

Плешачков Петр Олегович

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

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА 2006

Работа выполнена в Институте системного программирования Российской академии наук.

Научный руководитель: доктор технических наук

Кузнецов Сергей Дмитриевич.

Официальные оппоненты: доктор физико-математических наук,

профессор Новиков Борис Асенович;

кандидат технических наук,

доцент

Когаловский Михаил Рувимович.

Ведущая организация: Институт механики МГУ им. М. В. Ломоносова

Защита диссертации состоится "10" ноября 2006 года в 15 часов на заседании диссертационного совета Д 002.087.01 в Институте системного программирования Российской академии наук по адресу: 109004, Москва, ул. Большая Коммунистическая, д. 25.

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН.

Автореферат разослан "б" октября 2006 г.

Ученый секретарь

дйссертационного совета

канд. физ.мат. наук

С.П. Прохоров

Общая характеристика работы Актуальность темы

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

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

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

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

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

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

Цель и задачи работы

Целью диссертационной работы является исследование и разработка новых методов управления транзакциями в XML-ориентированных СУБД, в полной

мере учитывающих иерархическую структуру XML и семантику XML-операций. Для достижения этой цели были поставлены следующие задачи:

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

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

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

4. Разработка методов обеспечения атомарности и надежности транзакций в прирожденных XML-СУБД.

Научная новизна

Научной новизной обладают следующие результаты диссертационной работы:

1. Разработан новый протокол изоляции XML-транзакций XDGL для XML-ориентированных СУБД, основанный на описывающей схеме XML-документа.

2. Предложен новый семантический метод управления XML-транзакциями для реляционных СУБД с поддержкой XML на основе двухуровневой модели транзакций.

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

оперативной памятью в этих СУБД; протокол позволяет выполнять читающие и изменяющие транзакции без взаимных блокировок.

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

Практическая значимость

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

На основе предложенных методов и подходов разработаны: (1) прототип семантического менеджера управления XML-транзакциями SXTM над реляционной СУБД MS SQL Server 2005; (2) прототип менеджера управления XML-транзакциями, используемый в качестве основы для создания в ИСП РАН промышленной прирожденной XML-СУБД Седна.

Апробация работы и публикации

По материалам диссертации опубликовано восемь работ [1-8]. Основные положения работы докладывались на следующих конференциях и семинарах:

• на девятой международной конференции в области баз данных и информационных систем (ADBIS) (2005 г);

• на двадцать второй британской национальной конференции по базам данных (BNCOD) (2005 г);

• на симпозиуме аспирантов на двадцать третьей британской национальной конференции по базам данных (PhD Forum BNCOD) (2006 г);

• на первом и втором весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (SYRCoDIS) (2004 и 2005 гг);

• на сто третьем семинаре Московской Секции ACM SIGMOD (2005 г);

• на семинаре "Современные сетевые технологии" под руководством д.ф.-м.н., профессора Васенина В А. (2006 г).

Структура и объем диссертации

Работа состоит из введения, пяти глав, заключения и списка литературы. Общий объем диссертации составляет 166 страниц. Список литературы содержит 100 наименований.

Краткое содержание работы

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

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

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

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

Во втором разделе делается обзор технологий платформы XML в приложении к управлению слабоструктурированными данными. Рассматриваются язык XML как формат для представления слабоструктурированных данных, язык путевых выражений XPath, язык запросов XQuery, а также язык модификаций XUpdate.

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

Методы поддержки XML в РСУБД можно разделить на три типа.

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

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

Ко второму типу относятся методы хранения XML-документов, основанные на отображении XML-документов на отношения. Рассматриваются основные методы декомпозиции XML-документов на таблицы, среди которых методы Edge, Attribute, Inlining и STORED.

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

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

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

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

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

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

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

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

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

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

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

языков запросов XQuery/XUpdate. Поэтому, по мнению автора, протокол синхронизации должен учитывать специфику именно этих языков. Кроме того, предложенные методы требуют непосредственный доступ к дереву XML-доку мента, что в некоторых случаях может быть невозможно.

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

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

Третья глава посвящена описанию разработанного автором протокола изоляции XML-транзакций XDGL (XPath-based DataGuide Locking), основанного на двухфазном протоколе блокирования.

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

Кроме того, использование описывающей схемы позволяет абстрагироваться от системы хранения XML-документа, что, в свою очередь, ведет к универсальности XDGL: он может быть реализован над

любой системой хранения XML-доку ментов.

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

К первому типу относятся ограничения на структуру XML-документа. Этому ограничению соответствуют структурные блокировки. В XDGL вводится 11 типов структурных блокировок: Р, S, SI, SA, SB, X, XN, ST, XT, IS и IX. Выделяется два типа структурных блокировок: узловые и древовидные. Узловые блокировки накладывают ограничения только на выполнение операций над узлами XML-документа, соответствующих блокируемому узлу схемы, а древовидные блокировки неявно накладывает ограничения на выполнение операций над поддеревьями в XML-доку менте, соответствующих блокируемому узлу. К узловым относятся блокировки Р, S, SI, SA, SB, X и XN.

Ко второму типу относятся ограничения на значения узлов в XML-документе, выражаемые при помощи предикатов. Этому типу ограничений соответствуют предикатные блокировки, которые ассоциируются со структурными блокировками. Таким образом, совместимость двух структурных блокировок возможна в двух случаях: (1) типы структурных блокировок совместимы или (2) коньюнкция предикатов, ассоциированных со структурными блокировками, тождественно равна false.

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

Основным компонентом, отвечающим за реализацию протокола XDGL, является XDGL-планировщик. В работе формально описан алгоритм работы

ХБСЬ-планировщика, доказан ряд свойств ХОСЬ-планировщика, а также на основе этих свойств обоснована его корректность. Введем ряд определений и обозначений.

Определение 1 Транзакцией 7} мы будем называть последовательность пар (орууТх). Причем последней в этой последовательности всегда является операция фиксации транзакции.

Определение 2 Планом Б множества транзакций Т — {Т\,Т2, ...,Тп} мы будем называть перемешанную последовательность операций транзакций из Т (при этом порядок операций в транзакциях не меняется).

Определение 3 Мы будем обозначать символом Ь^ множество всех блокировок, установленных транзакциями после выполнения г-го шага в плане 5.

Определение 4 Мы будем говорить, что план 5 является допустимым, тогда и только тогда, когда на каждом шаге г в плане Б множество всех установленных блокировок Ь^ содержит только совместимые блокировки (разных транзакций), в соответствии с матрицей совместимости протокола ХИСЬ.

Определение 5 Планы 5 и 5' мы будем называть эквивалентными, если (1) план Б является перестановкой плана 5' (при этом порядок операций в транзакции сохраняется), (2) после выполнения планов 5 и5' полученные документы являются одинаковыми, и (3) все запросы в плане Я возвращают те же ответы, что и соответствующие запросы в плане Б'.

Определение 6 План Б называется сериальным, если для произвольных двух транзакций Т» и Т^ из плана Б все операции транзакции Т{ предшествуют (или следуют) всем операциям транзакции 7).

Определение 7 План S является сериализуемым если он эквивалентен какому-нибудь сериальному плану.

Определение 8 Мы будем обозначать символом lf(opi) множество всех блокировок, установленных (или освобожденных) в ходе выполнения операции opi в плане S.

Определение 9 Мы будем обозначать символом Df документ (или набор документов), полученный после выполнения i-ой операции в плане S.

Свойства протокола XDGL формулируются в следующих трех леммах. Отметим, что далее в этом разделе мы будем считать, что план S' отличается от плана S перестановкой двух смежных пар (opi,Ti) и (opi+i,Tj) (Tj < Ti).

Лемма 1 Если план S является допустимым, то и план S' также является допустимым.

Лемма 2 Если план S является допустимым, и, по крайней мере, одна из операций opi или opi+\ в плане S является запросом на выборку, то результаты выполнения этого (этих) запроса (запросов) па выборку в планах S и S' одинаковые.

Лемма 3 Если план S является допустимым, то Df+1 =

На основе лемм 1, 2 и 3 доказывается теорема о корректности протокола XDGL:

Теорема 1 Все планы S, сгенерированные XDGL-планировщиком, являются сериализуемыми.

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

Отмечается, что в описывающей схеме теряется очень важная информация о документе - порядок следования узлов и множественность узлов, в то время как из DTD такую информацию можно получить. На основе информации о порядке дочерних узлов удается оптимизировать количество необходимых блокировок при вычислении осей preceding-sibling и following-sibling. Информация о множественности узлов используется при разрешении конфликтов на одном узле схемы за счет проверки предикатов на других узлах схемы.

В четвертой главе описывается предложенный автором метод управления XML-транзакциями в реляционных СУБД (РСУБД). Метод основывается на применении протокола XDGL для семантической изоляции XML-транзакций в рамках двухуровневой модели транзакций.

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

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

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

схема. Во втором методе предполагается, что априори предписывающая схема XML-документа неизвестна. Для этого случая описывается метод поддержки описывающей схемы в актуальном состоянии за счет вычисления новых потенциальных узлов в схеме, которые могут появиться в XML-документе при выполнении очередной операции изменении ХМL-документа.

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

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

Важным следствием этого свойства является то, что менеджеру восстановления SXTM никогда не требуется производить повторное выполнение (REDO) XML-операций, поскольку при выполнении операции фиксации XML-транзакции, когда производится вставка в журнал записи COMMIT для этой транзакции, происходит фиксация последней DB-транзакции. Таким образом, тот факт, что SXMT успешно зафиксировал XML-транзакцию, означает, что РСУБД успешно зафиксировала все субтранзакции, и поэтому при восстановлении после сбоя повторное выполнение всех субтранзакций будет выполнять РСУБД.

В работе приводятся алгоритмы восстановления глобальных транзакций

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

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

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

В первом разделе главы формулируются следующие специфичные требования к управлению транзакциями в XML-СУБД:

• Читающие транзакции не должны конфликтовать с изменяющими транзакциями.

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

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

• Версионный механизм не должен приводить к неограниченному росту размера базы данных.

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

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

Транзакции, осуществляющие только чтение элементов базы данных, мы будем обозначать символом Т7*. Транзакции, осуществляющие как чтение элементов базы данных, так и их изменение, будем обозначать символом Т4". Элемент базы данных будем обозначать символом х, а символом Х{ - 1-ю физическую версию элемента х. Наконец, временную метку версии Х{ мы будем обозначать символом ts(xi).

Определение 10 Консистентным снимком базы данных, сделанным в момент времени ¿, мы будем называть такое состояние базы данных, в котором каждый элемент х базы данных представлен версией Х{, удовлетворяющей двум условиям: (1) Х{ создана транзакцией, зафиксированной в момент времени, меньший чем и (2) не существует другой версии худовлетворяющей условиям (1) и < ¿з(х^) < £.

В работе предлагается использовать два консистентных снимка базы данных 5<0 и (£о < Ь) для изоляции Т* и Т™ транзакций. На каждом из этих снимков выполняется набор Тг транзакций. Причем новые Т7" транзакции выполняются на новом снимке. В результате, когда все Тг транзакции, выполняющиеся на старом снимке £г0, завершатся, можно произвести продвижение снимков, при котором новый снимок становится старым, а консистентный снимок БД на текущий момент времени становится новым снимком. Отмечается, что эта операция может выполняться очень эффективно, поскольку она не требует доступа к диску. Кроме того, использование двух снимков позволяет реализовать процедуру продвижения снимков без приостановки читающих транзакций.

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

БД: (1) версия, необходимая для старого снимка <5г0, которую мы будем обозначать Х5<о; (2) версия, необходимая для нового снимка которую мы будем обозначать ; (3) последняя зафиксированная версия элемента (эта версия будет использоваться в очередном снимке), которую мы обозначим хьс, и (4) версия, в которой производятся изменения текущей транзакцией, которую мы будем обозначать х\у (эта версия отражает незафиксированное состояние элемента). А также отмечается, что одна физическая версия может соответствовать нескольким логическим версиям. Кроме того, вводятся правила переходов физических версий от одного множества логических версий в другое. Также отмечается, что переходы физических версий осуществляются неявно, а соответствие физической версии множеству логических версий определяется динамически при обращении к странице с данными.

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

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

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

В шестом разделе описывается версионный протокол изоляции транзакций в XML-СУБД - 4VXDGL. В протоколе описывается изоляция !Г и Г транзакций на основе консистентных снимков БД, а изоляция Т" транзакций на основе протокола XDGL. Особое внимание уделяется проблеме совмещения версионности на уровне блоков и блокировок на уроне узлов, которая решается за счет введения дополнительной структуры - графа зависимостей между транзакциями (DTG).

Кроме того описывается алгоритм сборки устаревших страниц, которые возникают при устаревании снимков БД.

В конце раздела доказываются теоремы, о корректности и свойствах протокола 4VXDGL.

Теорема 2 Протокол 4VXDGL генерирует сериализуемые планы выполнения XML-транзакций

Теорема 3 Максимальное количество версий одного блока, используемых в протоколе 4 VXDGL, ограничено числом 4-

Теорема 4 Процедура продвижения снимков не приводит к приостановке выполнения 7* или Т™ транзакций

Теорема 5 Параллельное выполнение Т* и Т"3 транзакций на основе протокола 4VXDGL никогда не приводит к конфликту между этими транзакциями.

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

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

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

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

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

Основные результаты работы

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

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

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

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

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

5. Разработаны методы обеспечения атомарности и надежности

S

транзакций в прирожденных XML-СУБД.

По теме диссертации опубликованы следующие работы

1. P. Pleshachkov, L. Novak. Transaction Isolation In the Sedna Native XML DBMS. Proc. SYRCoDIS 2004, Saint-Petersburg, Russia.

2. P. Pleshachkov, P. Chardin, S. Kuznetsov. A DataGuide-Based Concurrency Control Protocol for Cooperation on XML Data. Proc. ADBIS 2005, LNCS 3631 Springer 2005, Tallinn, Estonia.

3. P. Pleshachkov, P. Chardin, S. Kuznetsov. XDGL: XPath-Based Concurrency Control Protocol for XML Data. Proc. BNCOD 2005, LNCS 3567 Springer 2005, Sunderland, UK.

4. P. Pleshachkov, P. Chardin, S. Kuznetsov. A Locking Based Scheduler for XML Databases. Proc. SEBD 2005, ISBN 8-548-0122-4, Brixen-Bressanone, Italy.

5. P. Pleshachkov, P. Chardin. A Locking Protocol for Scheduling Transactions on XML Data. Proc. SYRCoDIS 2005, Saint-Petersburg, Russia.

6. P. Pleshachkov. Transaction Management for XML Stored in Relational Database Systems. Proc. PhD Forum BNCOD 2006, Belfast, Northern Ireland, UK.

7. П. О. Плешачков, С. Д. Кузнецов. Управление транзакциями в РСУБД с поддержкой XML. Программирование. - М.: Наука, 2006. - N 5.

8. Плешачков П. О. SXTM: высокопроизводительный менеджер управления XML-транзакциями. Препринт 11 Института Системного Программирования РАН, 2006.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 03.10.2006 г. Формат 60x90 1/16. Усл.печл. 1,25. Тираж 100 экз. Заказ 679. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение

1 Управление транзакциями и технологии XML

1.1 Обзор методов управления транзакциями в СУБД.

1.1.1 Методы обеспечения изоляции параллельных транзакций.

1.1.2 Методы обеспечения атомарности и надежности транзакций.

1.2 Платформа XML.

1.2.1 Расширяемый язык разметки - XML.

1.2.2 Язык запросов XQucry.

1.2.3 Язык модификаций XUpdate.

1.3 XML-орнептированныс СУБД.

1.3.1 РСУБД с поддержкой XML.

1.3.2 Прирожденные XML-СУБД.

1.4 Выводы.

2 Существующие методы управления параллельными XML-транзакциями

2.1 XML-транзакции в реляционных СУБД.

2.1.1 Блокировки в РСУБД для XML-документов при использовании отображения XML-документов па отношения.

2.1.2 Блокировки в РСУБД для XML-документов при использовании типа XML или метода STORED.

2.2 XML-трапзакции в прирожденных XML-СУБД.

2.2.1 Основные приложения XML-СУБД.

2.2.2 Обзор родственных работ по изоляции XML-транзакций.

2.3 Выводы.

3 Протокол изоляции XML-транзакций XDGL

3.1 Введение.

3.2 Основные определения и обозначения.G

3.3 Семантические особенности языков XQuery/XUpdate.6G

3.3.1 Путевые выражения.GG

3.3.2 Запросы па XQuery.G

3.3.3 Операция вставки новых узлов .G

3.3.4 Операция удаления узлов.G

3.3.5 Операция переименования узлов.G

3.4 XDGL-блокировкн.G

3.4.1 Структурные блокировки.G

3.4.2 Предикатные блокировки.

3.4.3 Логические блокировки.

3.5 XDGL-плапнровщик.

3.G Обоснование корректности протокола XDGL

3.7 Дополнительные оптимизации в XDGL.

3.8 Примеры использования протокола XDGL.

3.9 Выводы.

4 Управление XML-транзакциями в реляционных СУБД

4.1 Многоуровневые модели транзакций и их применение для управления XML-трапзакцпями в РСУБД

4.2 Применение XDGL для изоляции транзакции в РСУБД.

4.2.1 Поддержка описывающей схемы в SXTM

4.3 Атомарность XML-трапзакций в двухуровневой модели.

4.4 Индивидуальные откаты транзакций и восстановление базы данных после сбоев

4.5 Повышение параллелизма внутри XML-трапзакций.

4.G Экспериментальная оценка семантического менеджера управления XMLтрапзакциями

4.G.1 Экспериментальная установка.

4.6.2 Эксперимент 1: накладные расходы.

4.6.3 Эксперимент 2: пропускная способность.10G

4.G.4 Эксперимент 3: время отклика.

4.6.5 Эксперимент 4: время отклика транзакций при использовании параллелизма внутри транзакций.

4.7 Выводы.

5 Управление транзакциями в прирожденных XML-СУБД

5.1 Требования к управлению транзакциями в прирожденных XML-СУБД

5.2 Снимки базы данных и их применение для изоляции читающих и изменяющих транзакций.11G

5.3 Продвижение снимков.

5.4 Отображение логических версий па физические версии

5.5 Адресация версий и идентификация страниц из снимков базы данных.

5.G Изоляция Tw транзакции.12G

5.6.1 Изоляция Tw транзакций па уровне блоков.

5.6.2 Изоляция Тт транзакций на основе протокола XDGL.

5.7 Метод восстановления транзакций после мягких сбоев в системе.

5.7.1 Физический журнал.

5.7.2 Логический журнал.

5.7.3 Контрольные точки базы данных.

5.7.4 Индивидуальный откат транзакции.

5.7.5 Восстановление базы данных после сбоя.

5.8 Экспериментальная оценка методов управления XML-транзакциями.

5.8.1 Эксперимент 1: пропускная способность.

5.8.2 Эксперимент 2: время отклика.

5.9 Выводы.

Актуальность темы

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

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

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

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

Решение этих проблем и определяет актуальность диссертационной работы.

Цель и задачи работы

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

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

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

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

4. Разработка методов обеспечения атомарности и надежности транзакций в прирожденных XML-СУБД.

Основные результаты работы

В рамках диссертационной работы получены следующие результаты:

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

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

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

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

5. Разработаны методы обеспечения атомарности и надежности транзакции в прирожденных XML-СУБД.

Научная новизна работы

Научной новизной обладают следующие результаты диссертационной работы:

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

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

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

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

Практическая значимость

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

На основе предложенных методов и подходов разработаны: (1) прототип семантического менеджера управления XML-транзакциями SXTM над реляционной СУБД MS SQL Server 2005, (2) прототип менеджера управления XML-транзакциями, используемый в качестве основы для создаиия в ИСП РАН промышленной прирожденной XML-СУБД Седна.

Доклады и печатные публикации

Основные положения работы докладывались па девятой международной конференции в области баз данных и информационных систем (ADBIS 2005), па тринадцатом итальянском симпозиуме по базам данных (SEDD 2005), па двадцать второй британской национальной конференции по базам данных (DNCOD 2005), па симпозиуме аспирантов па двадцать третьей британской национальной конференции по базам данных (PhD Forum DNCOD 2006), на первом и втором весеннем коллоквиуме молодых исследователей в области баз данных п информационных систем (SYRCoDIS 2004, SYRCoDIS 2005), па сто третьем семинаре Московской Секции ACM SIGMOD (2005 г).

По материалам диссертации опубликовано восемь печатных работ [1, 2, 3, 4, 5, G, 7, 8).

Структура и объем диссертации

Работа состоит из введения, пяти глав, заключения и списка литературы. Общий объем диссертации 1G6 старппц. Список литературы содержит 100 наименований.

5.9 Выводы

В главе описан эффективный версиоппый метод управления транзакциями в прирожденных XML-СУБД. Основные свойства предложенного метода, необходимые для удовлетворения требований, изложенных в начале главы, доказываются в теоремах 2, 3, 4, 5. Кроме того, экспериментальная оценка также подтверждает эффективность предложенных методов. Особенно важно то, что верспоппый механизм пе приводит к значительному понижению эффективности операции перехода по указателю, которая является базовой в прирожденных XML-СУБД.

Заключение

В диссертационной работе получены следующие результаты:

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

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

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

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

5. Разработаны методы обеспечения атомарности и надежности транзакций и прирожденных XML-СУБД.

В дальнейшей работе автор намерен сконцентрироваться иа решении следующих задач:

• Адаптация предложенных методов управления транзакциями в XML-СУБД к распределенным архитектурам. Актуальность этой задачи объясняется высокой привлекательностью XML как средства интеграции разнородных и распределенных источников данных в глобальной сети [97, 98, 99, 100].

• Расширение предложенного версиоипого протокола 4VXDGL поддержкой W|R транзакций [96], когда на первой W-фазс транзакция производит модификацию БД и устанавливает блокировки на изменяемые данных, а па второй R-фазс производит только чтение данных (возможно старых версий) без установки каких-либо блокировок. В частности, поддержка W|R транзакций позволит выполнять проверки ограничений целостности БД (ограничения по ключам, валидация па основе предписывающей схемы и т.д.) на R-фазе без установки блокировок, что может существенно может повысить параллелизм транзакции в XML-СУБД.

1. P. Pleshachkov, P. Chardin, S. Kuznetsov. XDGL: XPath-Based Concurrency Control Pro- tocol for XML Data. Proc. BNCOD 2005, LNCS 3567 Springer 2005, Sunderland, UK.

2. P. Pleshachkov, P. Chardin, S. Kuznetsov. A Locking Based Scheduler for XML Databases. Proc. SEBD 2005, ISBN 8-548-0122-4, Brixen-Bressanone, Italy.

3. P. Pleshachkov, P. Chardin. A Locking Protocol for Scheduling Transactions on XML Data. Proc. SYRCoDIS 2005, Saint-Petersburg, Russia.

4. P. Pleshachkov. Transaction Management for XML Stored in Relational Database Systems. Proc. PhD Forum BNCOD 2006, Belfast, Northern Ireland, UK.

5. Weikurn G., Vossen G. Transactional Information Systems Morgan KaufTmaim, 2002

6. J. Gray, A. Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1993.

7. P.A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987.159

8. G. Wcikurn, H. J. Scliek. Database Transaction Models for Advanced Applications. Morgan Kaufniann, 1992.

9. The World Wide Web Consortium (W3C). XQuery 1.0: An XML Query Language : W3C working draft. Boag S. et al. (eds.). - 2004, 29 Oct. littp://www.w3.org/TR/2004/WD-x(iuery-20041029/

10. The World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Eunctions and Operators: W3C Candidate Recommendation. J. Melton et al. (eds.), 2006, 8 June.http://www.w3.org/TR/xpatli-functions/160

11. Conrad A. MSDN Library. http://msdn.microsoft.com/library/eii-us/dnexxml/html/xnil071 6200Lasp. Jul 2001..26] Klein S. Interactive Microsoft SQL Server and XML online tutorial. http://vvww.topxml.com/tutorials/main.asp?id—sqlxml.

12. Rys i\L Bringing the Internet to Your Database: Using SQL Server 2000 and XML to Buiki 1.oosely-Coupled Systems. Proc. 17th ICDE Conference, Heidelberg, Germany, 2-6 April.,2001.

13. S. Pal, M. Fussell, and Irwin Dolobowsky. XML Support in Microsoft SQL Server 2005. Microsoft Corporation, Dec. 2005. http://msdn.microsoft.com/xml/default.aspx?pull=/library/en-us/dnsql90/html/sql2k5xmLasp

14. Eisenberg A., Melton J. SQL/XML is making good progress. SIGMOD Record VoL 31, N. 2 (2002).

15. Oracle Corporation. Concurrency Control, Transaction Isolation, and Serializability in SQL92 and Oracle7. Technical report, Oracle Corporation, 1995. Part No. A33745.

16. Cheng .]., Xu J. XML and DB2. Proc. 16th ICDE Conference, San Diego, USA, 28 Feb. 3 March, 2000.

17. K. Beyer et al. DB2 goes hybrid: Integrating XML and XQuory with relational data and SQL. IBM Systems Journal, Vol. 45, N. 2, 2006.

18. SQL Server 7.0, SQL Server 2000, and SQL Server 2005 logging and data storage al- gorithms extend data reliability Microsoft Corp., Article Num. 230785, Feb. 9, 2006http://support.microsoft.com/default.aspx?scid=kb;en-us;230785

19. S. Pal, I. Cseri, G. Schaller, O. Seeliger, L. Giakoumakis, V. Zolotov. Indexing XML Data Stored in a Relational Database. Proc. VLDB Conference 2004, Toronto, Canada.

20. Z. H. Liu, M. Krishnaprasad, V. Arora. Native Xquery processing in oracle XMLDB. Proc. ACM SIGMOD Conference 2005, Baltimore, USA.161

21. Mastering XML DB Storage in Oracle Database lOg Release 2. http://ww\v.oracle.com/tcclmology/tech/xml/xmldb/index.html

22. Corp. Extensible Information Server. Technical rei)ort, Excelon Corp., 2001. littp://\vww.exceloncorp.com/platforrn/extinfserver.

23. Microsoft Developers Network. http://nis(ln.microsoft.com

24. Linux Documentation (including Manual Pages). http://www.linux.org/docs/in{lex.htrnl 40[ M. H. Kay. SAXON The XSLT and XQuery Processor. littp://saxon.sourceforge.net/

25. Д. '^ 1емберли11. XQuery: язык заиросои XML. Открытые системы, 2003. N. 1. .42] Буре P. XML и базы данпых. Открытые системы, N. 10, 2000.

26. Кузпецов, П. Чардип. Семейство алгоритмов ARIES. Открытые системы, N. 3, 2004.

27. А. Silberschatz and Z. Kedem. Consistency in hierarchical database systems. Journal of the ACM, 27(1): 72-80, 1980.

28. C. Mohan, D. Haderie, B. Lindsay, H. Pirahesh, P. Schwarz. ARIES: A Transaction Recov- ery Method Supporting Fine-Cranularity Locking and Partial Rollbacks Using Write-Ahead1.ogging. ACM Transactions on Database Systems, Voi. 17, N. 1, March 1992.

29. D. Florescu, A. Y. Levy, and D. Suciu. Query Containment for Conjunct Queries with R.egular Expressions. Proc. PODS Symposium, 1998, Seattle, Washington, USA.1G2

30. J. Shanmugasuiidaram, К. Tufte, et al. Relational Databases for Querying XML Documents: 1.imitations and Opi)ortimities. Proc. VLDB Conference, 1999, Edinburgh, Scotland.

31. A. Deutsch, M. F. Fernandez, et al. Storing Semi-structured Data with STORED. Proc. SIGMOD Conference, 1999, Philadelphia, Pennsylvania, USA.

32. F. Tian, D. J. DeWitt, J. Chen, C. Zhang. The Design and Performance Evaluation of Alternative XML Storage Strategies. SIGMOD Record Volume 31 N. 1, 2002.

33. D. Sucin. Seniistructured Data and XML. Kluwer Academic Publishers, 2000.

34. P. Buneman. Semistructured Data. In Proc. PODS Symposium 1997, Arizona, USA. 5G. I. Tatarinov, Z. Ives, A. Halevy, D. Weld. Updating XML. Proc. SIGMOD Conference 2001,Santa Barbara, California, USA.

35. I. Tatarinov, S. Viglas, K. S. Beyer, J. Shanmugasundaram, et al. Storing and querying ordered XML using a relational database system. Proc. SIGMOD Conference 2002, Madison,Wisconsin, USA.

36. Gray J., Lorie R., Putzolu G. Granularity of locks and degrees of consistency in a shared data base. Proc. VLDB Conference, 1975.

37. Raghavan, A., and Rcngarajan, Т.К. Database Availability for Transaction Processing. Digital Technical Journal 3(1), Winter 1991.

38. R. Bayer, H. Heller, and A. Reiser. Parallelism and Recovery in Database Systems. ACM Trans. Database Syst. 5(2): 139-156 (1980).

39. M. Haustein, T Harder, K. Luttenberger. Contest of XML Lock Protocols. Proc. VLDB Conference 2006, Seoul, Korea.

40. S. Dekeyser, J. Hidders. Path Locks for XML Document Collaboration. Proc. WISE 2002, Singapore.

41. A. Fomichev, M. Grinev, S. Kuznetsov. Sedna: A Native XML DBMS. Proc. SOFSEM 2006,

43. Benchmark of Sedna XML DBMS. MODIS Group. http://modis.ispras.ru/Development/ Benchmarks, ISP RAS, 2006.164

44. Т. Ficbig, S. Helmer, C.-C. Kanne, G. Mocrkotte, J. Neumann, R. Schiclc, T. Westmann. Anatomy of a native XML base management system. VLDB Journal Vol. 11, Num. 26 (2002).

45. Software AG. Tamino - The XML Power Database. Technieal report. Software AG, 2001. http://www.softwareag.com/tainino/..80] H. Jagadish et al. TIMBER: A native system for quering XML. Proc. SIGMOD Gonference,2003, San Diego, USA.

46. W. Meier. eXist: An Open Source Native XML Database. Proc. Web, Web-Services, and Database Systems 2002, Erfurt, Germany.

47. X-IIive Gorporation, X-HIVE/DB. http://www.x-hive.com/products/db/index.litml

48. X. Meng, D. Luo, I\L Lee, J. OrientStore: A Schema Based Native XML Storage System. Proc. VLDB 2003 Gonference, Berlin, Germany.

49. K. P. Eswaran, J. Gray, R. A. Lorie, I. L. Traiger. The Notions of Gonsistency and Predicate 1.ocks in a Database System. Gominun. AGM Vol. 19, N. 11, 1976.

50. N. A. Aznauryan, S. D. Kuznetsov, L. G. Novak, and M. N. Grinev. SLS: A Numbering Scheme for Large XML Documents. Programming and Gomputer Software, N. 1, Vol. 32,2006.

51. D. Rosenkrantz, H. Hunt. Processing Gonjunctive Predicates and Queries. Proc. VLDB Gon- ference 1980, Montreal, Canada.165

52. G. Weikum. Principles and Realization Strategies of Multilevel Transaction Management. ACM Transactions on Database Systems (TODS), Vol. 16, issne 1, 1991.

53. JlncoiiCKnii K.IO. Разработка XML-приложеиий па язглке Scheme. Программиропаппе. Вып. 28 N.I, 2002.

54. А. Sclimidt, F. Waas, M. Kersten, D. Florescu, I. Manolescu, M. Carey, R. Busse. The XML Benchmark Project. Technical Report INS-R0103, CWI, Amsterdam, The Netherlands, April2001.

55. D. Florescu and D. Kossmann. Storing and Querying XML Data using an RDMBS. IEEE Data Engineering Bulletin, Vol. 22 N. 3, 1999.