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

Российская Академия Наук Институт системного программирования УДК 681 3 Об на правах рукописи

Гринева Мария Павловна

Методы поддержки активного поведения систем управления базами ХМЬ-данных

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

АВТОРЕФЕРАТ

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

ООЗ163030

Москва - 2007

003163030

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

Научный руководитель доктор физико-математических наук,

профессор

Томилин Александр Николаевич

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

профессор

Васенин Валерий Александрович,

кандидат физико-математических наук Шапоренков Дмитрий Александрович

Ведущая организация Вычислительный центр имени А А Дородницина

Российской академии наук

Защита диссертации состоится Щ'Н&лУрЯ 2007 года в ¡5 часов на заседании диссертационного совета Д 002 087 01 в Институте системного программирования Российской академии наук по адресу 109004, Москва, ул Большая Коммунистическая, д 25

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

Автореферат разослан 2007 г

Ученый секретарь диссертационного совета канд физ мат наук

СП Прохоров

Общая характеристика работы

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

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

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

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

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

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

1 Разработка языка определения XML-триггеров, основанного на XML-модели данных

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

3 Разработка методов реализации XML-триггеров в системах управления базами XML-данных

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

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

1 Разработан язык определения XML-триггеров на модификацию данных и XML-триггеров на выборку данных

2 Разработана семантика выполнения XML-триггеров на модификацию данных и XML-триггеров на выборку данных

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

4 Разработан метод эффективной реализации XML-триггеров на выборку данных, основанный на использовании теневого механизма

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

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

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

На основе предложенных методов реализации XML-триггеров на модификацию данных разработана подсистема поддержки XML-триггеров на модификацию данных в промышленной XML-СУБД Sedna, разрабатываемой в ИСП РАН

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

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

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

• на семинаре шестнадцатой международной конференции по базам данных и экспертным системам (DEXA), посвященном логическим аспектам и приложениям ограничений целостности (LAAIC)(2005 г),

• на семинаре семнадцатой международной конференции по базам данных и экспертным системам (DEXA), посвященном средствам управления XML-данными (XANTEC) (2006 г),

• на двенадцатой международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2005»,

• на семинаре «Проблемы современных информационно-вычислительных систем» под руководством дф-мн, профессора Васенина В А (2005 г),

• на сто тринадцатом семинаре Московской Секции ACM SIGMOD (2006 г),

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метод поддержки правил посредством перезаписи запросов в POSTGRES неприменим в силу особенностей языка запросов XML-СУБД XQuery, возможности которого для анализа в статике более ограничены по сравнению с языком РСУБД SQL Для языка XQueiy в общем случае статический вывод типов невозможен, и, следовательно, невозможно, проанализировав запрос на статической фазе выполнения, выявить правила, которые должны сработать при выполнении этого запроса и сгенерировать соответствующий набор запросов, учитывающий эти правила

Анализ описанного подхода Active XQuety показывает его неэффективность, которая объясняется выбранной архитектурой активной СУБД подсистема поддержки XML-триггеров в этом подходе является внешним модулем, разработанным «над» XQuery-процессором, то есть представляет собой пример многоуровневой архитектуры с обработкой триггеров на стадии компиляции операций В силу упомянутых особенностей языка XQuery обработка триггеров на стадии компиляции подразумевает выполнение вспомогательных запросов, что приводит к значительным накладным расходам

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

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

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

CREATE TRIGGER <иыя-триггера>

( BEFORE | AFTER ) ( INSERT | DELETE | REPLACE ) OF <ХРа^-выражение> (, <ХРаЦ1-выражение>) * { FOR EACH NODE | FOR EACH STATEMENT )

DO {

<<XOpdate-Bbipa*eHHe($NEW, $OLD, $WHERE)>, )* <ХОиегу-выражение($ЫЕИ, $OLD, $WHERE)>,

)

Далее в данном разделе подробно рассматриваются компоненты определения и семантика выполнения XML-триггеров При рассмотрении компонентов определения XML-триггера описывается их взаимосвязь с семантикой выполнения Наиболее важными аспектами языка определения и семантики выполнения XML-триггеров на модификацию являются следующие

■ Событием, инициирующим срабатывание определяемого XML-триггера, является заданная операция модификации данных языка XUpdate — insert, delete или replace (обозначаемая ключевыми словами insert, delete или replace), - примененная к узлам XML-документа, адресуемым одним или более XPath-выражениями, заданными после ключевого слова of (OF-выражениями) Таким образом, XML-триггер устанавливается на узлы XML-документа, заданные OF-выражениями в определении XML-тригтера, и срабатывает при модификации этих узлов. Это является принципиальным отличием от триггеров SQL, которые устанавливаются на всю таблицу (имя которой задается в определении триггера) и срабатывают при модификациях кортежей этой таблицы

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

Ontfaußui JSMLepeiay4^ INSERT DELETE REPLACE

INSERT leogtbfT-piUil >- lengtl<ljp«ü$> — lengthiT-peth) >4 lenglWU path)

DELETE - length<T-p«th) >» lengU<0-p41h) lMlgtbCT-path) >« fcngtbjí

REPLACE -- ... ItnglKT pity lengtbflj-pailí)

Таблица 1 Соотношение длин пути триггера и пути операции модификации, необходимые для возникновения инициирующего события

■ Действие XML-триггера состоит из любого количества XUpdate-выражений (включая их отсутствие) и одного XQuery-выражения, выполняемых при срабатывании XML-триггера Поскольку XUpdate-выражение в действии триггера может приводить к срабатыванию других XML-триггеров, допускается каскадное выполнение XML-тригтеров В действии XML-триггеров с выполнением, ориентированном на экземпляр, возможен доступ к переходным значениям посредством использования переменных с зарезервированными именами

$NEW, $OLD И $WHEHE

■ Выделяется важная группа XML-триггеров - XML-григгеры категории BEFORE с выполнением, ориентированным на экземпляр Такие триггеры позволяют задавать гибкие сценарии активного поведения, которые невозможно реализовать при помощи остальных групп XML-триггеров XML-триггеры этой группы имеют возможность отменять действие операции модификации для узла, для которого сработал XML-триггер, а для операций insert и replace могут модифицировать вставляемый или новый при замене узел

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

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

Язык определения XML-триггеров на выборку данных предоставляет конструкцию для определения XML-триггеров, обладающую следующим синтаксисом

CREATE TRIGGER <имя-триггера> ON RETRIEVE

OF <XPath вь:ражен-ие> (, <хРаЬЬ-выражение>) *

DO {

(<XUpdate-Bbipa:KeHHe ($CURRENT) >, )* <ХОиегу-выражение ($ CURRENT) >,

}

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

■ XML-триггер на выборку данных устанавливается на узлы, адресуемые одним или более OF-выражениями Событием, инициирующим срабатывание XML-триггера на выборку данных, является выборка узлов, на которые установлен этот XML-триггер При этом под узлами, выбираемыми некоторым XQuery/XPath-запросом, понимаются как узлы, являющиеся результатом запроса, так и узлы, доступ к которым был осуществлен при выполнении запроса

■ При срабатывании XML-триггера выполняются операции модификации данных, специфицированные в действии, а также строятся новые узлы, описываемые XQuery-выражением действия XML-триггера

Говоря неформально, семантика выполнения XML-триггеров на выборку такова, что при выполнении XQuery/XPath-запроса, инициирующего срабатывание XML-триггера, вместо узлов, на которые установлен XML-тригтер, должны быть «видны» новые узлы, построенные сработавшим XML-триггером При этом подмена узлов при срабатывании XML-триггера не должна изменять узлы постоянного хранения в базе данных Логически XML-тригтер строит новые XML-документы с подмененными узлами на основе документов, хранящихся в базе данных Такие документы предназначены только для выполнения запроса, инициировавшего срабатывание XML-триггера

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

реализации ХМЬ-триггеров на модификацию данных, а второй раздел -методам реализации ХМЬ-триггеров на выборку данных

Реализация поддержки ХМЬ-триггеров на модификацию данных в прирожденной ХМЬ-СУБД состоит из реализации возможности определять новые ХМЬ-тргатеры в системе и обработки ХМЬ-триггеров при выполнении операций модификации согласно семантике выполнения ХМЬ-триггеров В первом разделе данной главы предлагаются следующие разработанные автором методы реализации ХМЬ-триггеров на модификацию данных «.наивный» метод, метод, основанный на использовании фиксаторов на описывающей схеме, метод, основанный на объединении планов выполнения путевых выражений

«Наивный» метод реализации представляет собой наиболее простой и очевидный подход к реализации Изучение его достоинств и недостатков позволяет выявить этапы обработки ХМЬ-триггеров, для которых требуется разработка более эффективных методов

Анализ «наивного» метода позволяет сделать вывод, что определение нового ХМЬ-тригтера в системе состоит только из необходимых действий создается соответствующая структура аналогично тому, как это реализовано в большинстве активных СУБД Однако в оптимизации нуждается поиск инициируемых ХМЬ-триггеров, который является частью обработки ХМЬ-тригтеров при выполнении операции модификации Дело в том, что при «наивном» подходе каждый раз при модификации узлов некоторого документа вычисляются все ОР-выражения всех ХМЬ-триггеров, установленных на узлы этого документа Очевидно, что такой подход приведет к неприемлемым на практике накладным расходам Поэтому автором разработаны описываемые далее в этом разделе методы, позволяющие определять инициируемые ХМЬ-тригтеры более эффективно

Метод, основанный на использовании фиксаторов на описывающей схеме (метод с фиксаторами), является адаптацией рассмотренного в первой главе метода поддержки правил на уровне кортежей Данный метод применим для ХМЬ-СУБД, в которых поддерживаются описывающие схемы ХМЬ-документов, хранящихся в базе данных, и нумерующая схема Вследствие использования описывающей схемы документа метод с фиксаторами накладывает следующее ограничение на язык определения ХМЬ-триггеров ОР-выражения ХМЬ-триггеров должны быть структурными ХРаЛ-выражениями, то есть ХРаЛ-выражениями, не содержащими предикатов Основная идея метода состоит в следующем при выполнении модификаций узлов ХМЬ-документа, для каждого узла выполняется переход на соответствующий ему узел описывающей схемы и проверка наличия в нем фиксатора ХМЬ-триггера, наличие фиксатора означает, что выполняемая модификация инициирует срабатывание

данного ХМЬ-триггера, и должно быть выполнено его действие Метод с фиксаторами значительно эффективней «наивного» метода, поскольку за счет использования фиксаторов удается избежать вычисления ХРаЛ-выражений всех ХМЬ-тригтеров, установленных на модифицируемый ХМЬ-документ, каждый раз при выполнении операции модификации Вместо этого в методе с фиксаторами выполняются структурные ХРаШ-выражения над описывающими схемами модифицируемых ХМЬ-документов, что не требует ощутимых накладных расходов, так как описывающие схемы в ХМЬ-СУБД в подавляющем большинстве случаев при обработке помещаются в оперативную память.

Второй из предлагаемых методов — метод реализации ХМЬ-тригтеров, основанный на объединении планов выполнения путевых выражений (метод с общим выполнением), позволяет эффективно осуществлять поиск ХМЬ-тригтеров, инициируемых некоторой операцией модификации, за счет следующих двух техник Во-первых, посредством анализа операции модификации и имеющихся в системе ХМЬ-тргатеров на стадии компиляции операции происходит сужение набора рассматриваемых ХМЬ-тригтеров Во-вторых, ля ОБ-выражений суженного набора ХМЬ-тригтеров и ХРаШ-выражения, определяющего целевые узлы изменения в операции модификации, специальным образом строится объединенный план выполнения Такой объединенный план выполнения позволяет вычислить последовательность целевых улов изменения и при этом, в процессе его выполнения, определить инициируемые ХМЬ-триггеры и узлы, для которых они должны сработать

В отличие от метода с фиксаторами данный метод позволяет реализовать ХМЬ-триггеры с произвольными ХРаШ-выражениями (в том числе и содержащими предикаты) Однако метод с общим выполнением имеет собственное ограничение он применим для операций модификации, целевые узлы изменения которых заданы посредством ХРаЛ-выражений (а не произвольных Х(2иегу-выражений) При описании данного метода в работе обосновывается приемлемость такого ограничения для практических приложений

Метод с общим выполнением применим для ХМЬ-СУБД с поддержкой описывающей схемы, а также с наличием возможности расширения модели выполнения Х<3иегу-запросов объекты, полученные как промежуточный результат выполнения ХОиегу-запроса, могут быть «помечены» некоторыми метаданными

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

объединенного плана выполнения является последовательность узлов, адресуемых главным путевым выражением, и в этой последовательности помечены те узлы, которые адресуются побочными путевыми выражениями Для эффективного поиска XML-триггеров, инициируемых некоторой операцией модификации, строится объединенный план выполнения для ХРаШ-выражения, определяющего целевые узлы изменения в этой операции (главное путевое выражение) и OF-выражений XML-триггеров (побочные путевые выражения) Выполнение такого объединенного плана позволяет не только вычислить целевые узлы изменения операции модификации, но и определить XML-триггеры, инициируемые данной операцией модификации

Для построения объединенного плана выполнения предварительно путевые выражения должны быть преобразованы в прямые путевые выражения

Определение. Прямым путевым выражением будем называть такое путевое выражение, на каждом шаге которого осью является ось child либо ось attribute, и тест узла представляется именем

В работе доказана следующая теорема

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

В конце первого раздела четвертой главы приводятся экспериментальные оценки предложенных методов реализации XML-триггеров на модификацию данных Были сделаны следующие выводы Метод, основанный на использовании фиксаторов, является наиболее эффективным методом поддержки XML-триггеров со структурными OF-выражениями (время, затраченное на поиск инициируемых XML-триггеров, незначительно), при этом он оказался наименее эффективным при работе с XML-тригтерами, OF-выражения которых содержат предикаты Метод с общим выполнением в обоих случаях работает эффективно, и, таким образом, является универсальным по сравнению с методом с фиксаторами Тем не менее, при выборе метода поддержки XML-триггеров, стоит учитывать, во-первых, то, что метод с фиксаторами является более простым в реализации, чем метод с общим выполнением, а также рассматривать упомянутые ограничения, накладываемые методами на язык определения XML-тригтеров и операции модификации

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

Реализация поддержки ХМЬ-триггеров на выборку данных в прирожденной ХМЬ-СУБД состоит из реализации возможности определять новые ХМЬ-триггеры в системе и обработки определенных ХМЬ-триггеров при выполнении операций выборки согласно семантике выполнения ХМЬ-триггеров Аналогично предыдущему разделу сначала описывается и обсуждается «наивный» метод реализации, преимуществом которого является его простота реализации Однако «наивный» метод подразумевает копирование ХМЬ-документов каждый раз при выполнении операции выборки, что приводит к неприемлемым на практике накладным расходам Далее в разделе предлагается метод, основанный на использовании теневого механизма, позволяющий эффективно поддерживать ХМЬ-триггеры без накладного копирования ХМЬ-документов

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

Метод применим для ХМЬ-СУБД, в которых узлы хранящихся ХМЬ-документов связаны между собой посредством указателей, что, как показано во втором разделе второй главы, является вполне приемлемым требованием

В конце раздела подводится итог, где отмечается, что предложенный метод, основанный на использовании теневого механизма, значительно эффективней «наивного» метода реализации ХМЬ-триггеров на выборку данных как по времени выполнения, так и по объему требуемой памяти

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

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

1 Разработаны язык определения и семантика выполнения двух видов XML-триггеров XML-триггеров на модификацию данных и XML-триггеров на выборку данных Язык определения и семантика выполнения разработанных XML-тригтеров учитывают специфику XML-модели данных

2 Разработаны два метода эффективной реализации XML-триггеров на модификацию данных в системах управления базами XML-данных, метод, основанный на использовании фиксаторов на описывающей схеме, и метод, основанный на объединении планов выполнения путевых выражений

3 Произведена экспериментальная оценка предложенных методов реализации XML-триггеров на модификацию данных

4 Разработан метод эффективной реализации XML-тригтеров на выборку данных в системах управления базами XML-данных, основанный на использовании теневого механизма

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

1 Рекуц М П Виды ограничений целостности в базах XML-данных // Труды ИСП РАН, 2004 -Т8-Ч2-С 155-167

2 Rekouts М Application Programming Interface for XML DBMS design and implementation proposal // Proc of SYRCoDIS 2004 S Petersburg, Russia

3 Rekouts M, Gnnev M Introducing Trigger Support for XML Database Systems //Proc of SYRCoDIS 2005, S Petersburg, Russia

4 Rekouts, M Incorporating Active Rules Processing into Update Execution in XML Database Systems //Proc of DEXA Workshops 2005, pp 831-836 ISBN 0-7695-2424-9 Copenhagen, Denmark

5 Рекуц МП Метод поддержки триггеров в XML-ориентированных СУБД, основанный на анализе результатов промежуточных вычислений при выполнении операций модификации данных. U Материалы двенадцатой международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов 2005», Москва, 2005

6 Rekouts M, Gnnev M, Boldakov A A Method for XQuery Transform Implementation Based on Shadow Mechanism // Proc of DEXA Workshops 2006, pp 470-475 Krakow, Poland

7 Гринева M П, Гринев M H Триггеры на выборку данных в XML-ориентированных СУБД эффективная реализация с использованием теневого-механизма // Программирование — М • Наука, 2007 - N 4 -С 32-45

8 Rekouts М, Christiansen Н Integrity Checking and Maintenance with Active Rules in XML Databases // Proc of BNCODWebim 2007, pp 59-67 ISBN 0-7695-2912-7 Glasgow, UK

Подписано в печать 11 10 2007 г Исполнено 11 10 2007 г Печать трафаретная

Заказ № 871 Тираж 100 экз

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш , 36 (495) 975-78-56 уауц' аШогеГеШ ш

Оглавление.

Введение.

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

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

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

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

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

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

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

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

Глава 1 Активные СУБД.

1.1 Активные СУБД и триггеры.

1.1.1 Триггеры.

1.1.2 Общая форма определения триггеров.

1.1.3 Язык определения триггеров.

1.1.4 Семантика выполнения триггеров.

1.1.5 Архитектура активных СУБД.

1.1.6 Основные аспекты реализации активных СУБД.

1.2 Триггеры в реляционных СУБД.

1.2.1 Триггеры в стандарте SQL.

1.2.2 Методы реализации триггеров в РСУБД.

1.3 Выводы.

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

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

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

2.1.2 Язык запросов XQuery.

2.1.3 Язык модификаций XML-данных.

2.2. Аспекты реализации XML-СУБД.

2.2.1 Связи между узлами XML-документа в XML-СУБД.

2.2.2 Описывающая схема.

2.2.3 Нумерующая схема.

2.3 Триггеры для баз XML-данных: формирование требований и анализ применимости существующих методов реализации.

2.3.1 Анализ применимости методов реализации триггеров РСУБД.

2.3.2 Существующие методы реализации XML-триггеров.

2.4 Выводы.

Глава 3 Язык определения и семантика выполнения XML-триггеров.

3.1 XML-триггеры на модификацию данных.

3.1.1 Инициирующие события.

3.1.2 Выполнение, ориентированное на экземпляр, и выполнение, ориентированное на набор экземпляров.

3.1.3 Действия.

3.1.4 Выполнение нескольких XML-триггеров одной группы.

3.1.5 Видимость изменений данных.

3.1.6 Пример.

3.2 XML-триггеры на выборку данных.

3.2.1 Инициирующие события.

3.2.2 Действия.

3.2.3 Взаимодействие с операциями модификации.

3.2.4 Выполнение нескольких XML-триггеров.

3.2.5 Пример.

3.3 Выводы.;.

Глава 4 Методы реализации XML-триггеров для XML-СУБД.

4.1 Методы реализации XML-триггеров на модификацию данных.

4.1.1 «Наивный» метод реализации XML-триггеров на модификацию данных.

4.1.2. Метод реализации XML-триггеров на модификацию данных, основанный на использовании фиксаторов на описывающей схеме.

4.1.3 Метод реализации XML-триггеров на модификацию, основанный на объединении планов выполнения путевых выражений.

4.1.4 Экспериментальная оценка методов реализации XML-триггеров на модификацию данных.

4.2. Методы реализации XML-триггеров на выборку данных.

4.2.1. «Наивный» метод реализации XML-триггеров на выборку данных.

4.2.2. Метод реализации XML-триггеров на выборку данных, основанный на использовании теневого механизма.

4.3 Выводы.

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

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

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

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

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

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

1. Разработка языка определения XML-триггеров, основанного на XML-модели данных.

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

3. Разработка методов реализации XML-триггеров в системах управления базами XML-данных.

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

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

1. Разработаны язык определения и семантика выполнения двух видов XML-триггеров: XML-триггеров на модификацию данных и XML-триггеров на выборку данных. Язык определения и семантика выполнения разработанных XML-триггеров учитывают специфику XML-модели данных.

2. Разработаны два метода эффективной реализации XML-триггеров на модификацию данных в системах управления базами XML-данных: метод, основанный на использовании фиксаторов на описывающей схеме, и метод, основанный на объединении планов выполнения путевых выражений.

3. Произведена экспериментальная оценка предложенных методов реализации XML-триггеров на модификацию данных.

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

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

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

1. Разработан язык определения XML-триггеров на модификацию данных и XML-триггеров на выборку данных.

2. Разработана семантика выполнения XML-триггеров на модификацию данных и XML-триггеров на выборку данных.

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

4. Разработан метод эффективной реализации XML-триггеров на выборку данных, основанный на использовании теневого механизма.

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

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

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

На основе предложенных методов реализации XML-триггеров на модификацию данных разработана подсистема поддержки XML-триггеров на модификацию данных в промышленной XML-СУБД Sedna, разрабатываемой в ИСП РАН.

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

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

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

• на семинаре шестнадцатой международной конференции по базам данных и экспертным системам (DEXA), посвященном логическим аспектам и приложениям ограничений целостности (LAAIC) (2005 г);

• на семинаре семнадцатой международной конференции по базам данных и экспертным системам (DEXA), посвященном средствам управления XML-данными (XANTEC) (2006 г);

• на двенадцатой международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2005»;

• на семинаре «Проблемы современных информационно-вычислительных систем» под руководством д.ф.-м.н, профессора Васенина В.А. (2005 г);

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

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

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

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

4.3 Выводы

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

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

Заключение

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

1. Разработаны язык определения и семантика выполнения двух видов XML-триггеров: XML-триггеров на модификацию данных и XML-триггеров на выборку данных. Язык определения и семантика выполнения разработанных XML-триггеров учитывают специфику XML-модели данных.

2. Разработаны два метода эффективной реализации XML-триггеров на модификацию данных в системах управления базами XML-данных: метод, основанный на использовании фиксаторов на описывающей схеме, и метод, основанный на объединении планов выполнения путевых выражений.

3. Произведена экспериментальная оценка предложенных методов реализации XML-триггеров на модификацию данных.

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

1. Рекуц М.П.: Виды ограничений целостности в базах XML-данных. Труды Института Системного Программирования РАН. Том 8. Часть 2. Москва 2004.

2. М. Rekouts: Application Programming Interface for XML DBMS: design and implementation proposal. Proc. of SYRCoDIS 2004. S.Petersburg, Russia.

3. M. Rekouts, M. Grinev: Introducing Trigger Support for XML Database Systems. Proc. of SYRCoDIS 2005, S.Petersburg, Russia.

4. M. Rekouts: Incorporating Active Rules Processing into Update Execution in XML Database Systems. Proc. of DEXA Workshops 2005, pp. 831-836. ISBN 0-7695-24249. Copenhagen, Denmark.

5. М. Rekouts, М. Grinev, A. Boldakov: A Method for XQuery Transform Implementation Based on Shadow Mechanism. Proc. of DEXA Workshops 2006, pp. 470-475. Krakow, Poland.

6. M. П. Гринева, M. H. Гринев: Триггеры на выборку данных в XML-ориентированных СУБД: эффективная реализация с использованием теневого механизма. Программирование. М.: Наука, 2007. - N 4. - С. 32-45.

7. М. Rekouts, Н. Christiansen: Integrity Checking and Maintenance with Active Rules in XML Databases. Proc. of BNCODWebim. 2007, pp. 59-67. ISBN 0-76952912-7 Glasgow, UK.

8. L. Brownston, R. Farrell, E. Kant, N. Martin: Programming Expert Systems in OPS5: An Introduction to Rule-Based Programming. Addison-Wesley, Reading, Massachusetts, 1985.

9. H. Jasper, O. Zukunft, H. Behrends: Time Issues in Advanced Workflow Management Applications of Active Databases, Proc. of ATRDB, 1995.

10. K.P. Eswaran, D.D. Chamberlin: Functional specifications of a subsystem for data base integrity. Proc. of 1st VLDB Conference, 1975.

11. K.P. Eswaran: Specifications, implementations and interactions of a trigger subsystem in an integrated database system. IBM Research Report, 1976.

12. CODASYL data description language committee. CODASYL Data Description Language Journal of Development, 1973

13. M. Stonebraker: Implementation of integrity constraints and views by query modification. Proc. of ACM SIGMOD, 1975.

14. M. Stonebraker, L. Rowe, M. Hirohama: The implementation of POSTGRES. IEEE Transactions on Knowledge and Data Engineering, 1990.

15. M. Stonebraker, A. Jhingran, J. Goh, S. Potamianos: On rules, procedures, caching and views in data base systems. Proc. of ACM SIGMOD, 1990.

16. S. Potamianos: Semantics and Performance of Integrated DBMS Rule Systems. Ph.D. thesis, University of California, Berkeley, 1990.

17. J. Goh: Rule Processing with Query Rewrite. Master's thesis, University of California Berkeley, 1991.

18. X. Qian, G. Wiederhold: Incremental recomputation of active relational expressions. IEEE Transactions on Knowledge and Data Engineering. 1991.

19. С.Д. Кузнецов: Основы баз данных. Издательство Интернет-Университет Информационных Технологий, 2005.

20. J. Melton: Advanced SQL: 1999. Understanding Object-Relational and Other Advanced Features. Morgan Kaufmann Publishers, 2003.

21. D. Suciu: Semistructured data and XML. Kluwer Academic Publishers, 2000.

22. P. Buneman: Semistructured data. Proc. of ACM SIGMOD/SIGACT Conference on Principle of Database Systems (PODS), Tucson, 1997.

23. M. Гринев: Системы управления полуструктурированными данными. Журнал «Открытые системы» №05-06, издательство «Открытые системы», 1999.

24. The World Wide Web Consortium (W3C). Extensible Markup Language (XML) 1.0 (Third Edition) W3C Recommendation. Jean Paoli, С. M. Sperberg-McQueen et al., 2004.

25. The World Wide Web Consortium (W3C). HTML 4.0 Specification. W3C Recommendation. D. Raggett, A. Le Hors, I. Jacobs, 1998. http://www.w3 .org/TR11998/REC-html40-19980424

26. ISO 8879. Information Processing Text and Office Systems - Standard Generalized Markup Language (SGML), 1986

27. The World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Data Model: W3C Recommendation. M. Fernandez, M. Kay et at. (eds.), 2007. http://www.w3.org/TR/xpath-datamodel/

28. The World Wide Web Consortium (W3C). XQuery 1.0: An XML Query Language: W3C Recommendation. S. Boag et al. (eds.), 2007. http://www.w3 .org/TR/xquery

29. The World Wide Web Consortium (W3C). XML Path Language (XPath) 2.0: W3C Recommendation. D. Chamberlin, M. Fernandez, M. Kay et al. (eds.), 2007. http://www.w3 ,org/TR/xpath20/

30. The World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Functions and Operators: W3C Recommendation. J. Melton et al. (eds.), 2007. http://www.w3.org/TR/xpath-functions/

31. The World Wide Web Consortium (W3C). Namespaces in XML 1.0: W3C Recommendation, 2006. http://www.w3.org/TR/xmI-names/

32. T. Fiebig, S. Helmer, C.-C. Kanne, G. Moerkotte, J. Neumann, R. Schiele, T. Westmann: Anatomy of a native XML base management systems. VLDB Journal Vol. 11, Num. 26,2002.

33. Software AG. Tamino the XML Power Database. Technical report, Software AG, 2001.

34. H. Jagadish et al.: TIMBER: A native system for quering XML. Proc of SIGMOD, 2003.

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

36. X. Meng, D. Luo, M. Lee et al.: OrientStore: A Schema Based Native XML Storage System. Proc of VLDB, 2003.

37. J. McHugh, S. Abiteboul, R. Goldman, D. Quass, J. Widom.: Lore: A Database Management System for Semistructured Data. SIGMOD Record Vol. 26, N. 3, 1997.

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

39. Гринев M. H., Кузнецов С.Д., Фомичев А. В.: XML-СУБД Sedna: технические особенности и варианты использования. Открытые системы №8,2004.

40. Фомичев А. В.: Исследование и разработка методов организации выполнегия и физической оптимизации запросов к XML-данным. Диссертация на соискание ученой степени кандидата физико-математических наук, ВмиК МГУ, Москва, 2006.

41. А.А. Болдаков, М.Н. Гринев: Расширение языка XQuery функциональными update-выражениями. Препринт ИСП РАН, 2006.

42. I. Tatarinov, Z. Ives, A. Halevy, D. Weld: Updating XML. Proc. of SIGMOD Conference, 2001.

43. P. Lehti: Design and Implementation of a Data Manipulation Processor for an XML Query Language, Diplomarbeit, 2001.

44. J. Simeon, P. Wadler: The Essence of XML, Proc. of FLOPS, 2002.

45. J. Bailey, G. Papamarkos, A. Poulovassilis, P.T. Wood: An Event-Condition-Action Language for XML. Proc. of Web Dynamics, 2004

46. J. Bailey, A. Poulovassilis, P. Wood: Analysis and Optimisation of Event-Condition-Action Rules on XML, Computer Networks, Volume 39,2005.

47. Коллекция пьес Шекспира в формате XML. «Shakespeare in XML». http://www.ibiblio.org/xml/examples/shakespeare/

48. Digital Bibliography & Libraiy Project: DBLP XML records, http://dblp.uni-trier.de/xml/

49. M. Grinev: Rewriting-based Optimization for XQuery Transformational Queries -Revisited. Technical Report, MODISISPRAS, 2004.

50. Raymod A. Lorie: Physical Integrity in a Large Segmented Database. ACM Transactions on Database Systems, Vol.2, No. 1, (1977) 91-104

51. A. Schmidt, F. Waas, M. L. Kersten, M. Carey, I. Manulescu, R. Busse: XMark: A Benchmark for XML Data Management. Proc. of VLDB, 2002.

52. F. Fabret, M. Reignier, E. Simon: An adaptive algorithm for incremental evaluation of production rules in databases. Proc. of VLDB, 1993.

53. Y.-W. Wang, E. Hanson: A performance comparison of the Rete and TREAT algorithm for testing database rule conditions. Proc. of ICDE, 1992.

54. Oracle Database. Technical report, http://www.oracle.com/database/index.html

55. IBM DB2 Data Server. Technical report. http://www.oracle.com/database/index.html

56. Microsoft SQL Server. Technical report. http://www.microsoft.com/sql/default.mspx

57. Open Source Database PostgreSQL. Documentation on internals, http http://www.postgresql.0rg/docs/8.O/static/internals.html

58. The World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Functions and Operators. A. Malhotra, J. Melton, N. Walsh. Jan 2007. http://www.w3.org/TR/xpath-functions

59. D. Chamberlin: XQuery: An XML Query Language. IBM Systems Journal, Vol. 41, No. 4,2002.

60. The World Wide Web Consortium (W3C). XQuery Update Facility. W3C Working Draft. D. Chamberlin, D. Florescu, J. Robie. 2006, Jan. http://www.w3.org/TR/xqupdate

61. S. Abiteboul: Querying Semi-Structured Data. Proc.of ICDT, 1997

62. R. Bourret: XML and Databases. Technical report, 2005. http://www.rpbourret.com/xml/XMLAndDatabases.htm

63. XHive Corporation. XHive/DB. Documentation Extras. http://www.x-hive.com/products/db/specs.html

64. A. Bonifati, S. Paraboschi: Active XQuery. Proc. of Web Dynamics, 2004.

65. The World Wide Web Consortium (W3C). XML Schema Part 2: Datatypes Second Edition. W3C Recommendation. 2004, October. http://www.w3.org/XML/Schema.

66. A. Fomichev, M. Grinev, S. Kuznetsov: Descriptive Schema Driven XML Storage. ISP RAS. Technical Report, 2004.

67. U. Dayal, А.Р. Buchmann, S. Chakravarthy: The HiPAC Project. Active Database Systems. Chapter 7. Morgan Kaufmann Publishers, 1996.

68. N. Gehani, H.V. Jagadish: Active Database Facilities in Ode. Active Database Systems. Chapter 8. Morgan Kaufmann Publishers, 1996.