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

Московский государственный университет им. М.В. Ломоносова

На правах рукописи

/

Фомичев Андрей Владимирович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ ОРГАНИЗАЦИИ ВЫПОЛНЕНИЯ И ФИЗИЧЕСКОЙ ОПТИМИЗАЦИИ ЗАПРОСОВ К ХМЪ-ДАННЫМ

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

АВТОРЕФЕРАТ

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

Работа выполнена на кафедре системного программирования факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова.

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

старший научный сотрудник Кузнецов Сергей Дмитриевич.

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

профессор

Марков Александр Сергеевич;

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

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

Защита диссертации состоится " ил-гьрл^А^ 2006 года в часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория

бе?.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК

МГУ.

Автореферат разослан "_"_2006 г.

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

Н.П. Трифонов

fm

3

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

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

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

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

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

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

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

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

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

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

работы:

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

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

• разработан оригинальный метод выполнения ХРаЛ-запросов над предложенным внутренним представлением.

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

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

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

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

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

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

• на седьмой международной конференции Advances in Databases and Information Systems (ADBIS) 2003;

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

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

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

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

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

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

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

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

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

Во втором разделе выявляются недостатки современных систем управления XML-данными такие, как:

• не поддерживаются базовые понятия модели данных XPath и XQuery и/или языков XPath и XQuery;

• отсутствует поддержка больших объемов хранимых XML-данных;

• ряд систем ориентирован на решение узкого класса задач управления XML-данными;

• невозможно производить изменения данных на уровне узлов XML-документа;

• обеспечивается очень низкая производительность на относительно небольших объемах данных.

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

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

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

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

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

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

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

(content management; когда контент представляется в виде XML-данных). При решении подобных задач на языке XQuery будет выражаться достаточно сложная логика. Однако для описания логики приложения требуется использовать относительно сложные структуры данных. В XML/XQuery основным способом моделирования таких структур данных является вложенность узлов. При использовании подобных структур естественно предполагать наличие поддержки эффективной навигации по этим структурам. С позиции модельно-языковых средств достаточно поддержки путевых выражений, но на уровне структур хранения требуется обеспечить эффективное выполнение операций переходов от данного узла к его ребенку, соседу, родителю и т.д.

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

• "точечные" путевые выражения: при вычислении путевых выражений производится сканирование только необходимых данных;

• "локальные" операции изменения данных: локальное изменение дерева XML-документа не должно приводить к перестройке всего документа;

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

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

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

• Индивидуальность узлов и поддержка порядка документа. Поддержка этих свойств модели данных XPath и XQuery обеспечивается при помощи так называемой нумерующей схемы.

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

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

• Использование инфраструктуры реляционных баз данных для хранения XML-данных. Анализируются два способа хранения XML-данных в реляционных СУБД — хранение XML-документов как BLOB- или CLOB-обьектов и декомпозиция XML-документа на отношения. Делаются выводы, что у реляционных СУБД имеются принципиальные ограничения для эффективной обработки больших объемов XML-данных.

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

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

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

Определение 1 Обратным путем для некоторого узла х в XML-документе X называется последовательность пар (тип_узла, имя_узла), таких что:

1. первая пара последовательности представляет собой описание исходного узла х;

2. последняя пара последовательности представляет собой описание корневого узла XML-документа Х\

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

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

Определение 2 Описывающей схемой XML-документа X называется XML-документ dX, который обладает следующими двумя свойствами:

1. для каждого обратного пути в X существует, и причем единственный, обратный путь в dX\

2. для каждого обратного пути в dX существует обратный путь в X.

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

Определение 3 Структурным путевым выражением называется путевое выражение, удовлетворяющее следующим синтаксическим правилам (приведенные здесь правила опираются на грамматику языка XQuery и являются модификацией правил 68-73):

[68'] StructuralPathExpr ::= ("/" RelativePathExpr?)

I ("//" RelativePathExpr) I RelativePathExpr [69'] RelativePathExpr ::= StepExpr {("/" I "//")

StepExpr)*

[70'] StepExpr : := AxisStep

[71'] AxisStep ::= ForwardStep

[72'] ForwardStep ::= (ForwardAxis NodeTest)

I AbbrevForwardStep [73'] ForwardAxis ("child" "::")

I ("descendant" "::") I ("attribute" "::") I ("self" "::") I ("descendant-or-self" "::")

Определение 4 Абсолютным структурным путевым выражением называется структурное путевое выражение, примененное к узлу-документу.

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

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

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

Коротко говоря, вычисление абсолютного структурного путевого выражения сводится к вычислению этого выражения на описывающей схеме (которая умещается в оперативную память) и последующему переходу к искомым узлам, хранящимся в блоках внешней памяти. Корректность данного алгоритма подтверждается следующей теоремой (через Р(Х) обозначается множество узлов документа X, удовлетворяющих Р, а через Р(с1Х) — множество узлов документа с1Х, удовлетворяющих Р).

Теорема 1 Пусть даны ХМЬ-документ X, его описывающая схема с1Х и некоторое абсолютное структурное путевое выражение Р. Тогда х принадлежит Р(Х) тогда и только тогда, когда сЬс принадлежит Р(<ЗХ).

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

• не читается ни один блок внешней памяти, который не содержит

искомые узлы;

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

Заявленные результаты подкрепляются оценками сложности метода, приведенными ниже.

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

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

• символом "<" — отношение порядка на множестве узлов документа (то есть запись х\ < х2 означает, что узел х\ предшествует узлу х2 в порядке документа);

• символом "ч" — отношение "быть предком''' на множестве узлов документа (то есть запись х\ 4 х2 означает, что узел х\ является предком узла д^);

• символом "<1" — отношение "соответствовать узлу описывающей схемы" (то есть запись x<dx означает, что узел х соответствует узлу схемы dx);

• через Р \dX) — множество е WI V<&'-< dx,dx'e P(dX)}.

• через a(x*,dx) — количество блоков, которые содержат всех потомков узла х*, соответствующих узлу описывающей схемы dx;

• через m(dx) функцию такую, что

о если 3 dx',dx"eP(dX): dx -< dx',dx ■< dx", то

m(dx) = max (a(x*,dx)), где dx* e P'(dX), dx -< dx*;

x* < dx *

о иначе m(dx) = 1.

Определение 6 Абсолютное структурное путевое выражение Р называется односложным для документа X с описывающей схемой dX, если множества P(dX) и Р \dX) совпадают. Иначе Р называется многосложным.

Теорема 2 (о стоимости операции поиска узлов, удовлетворяющих абсолютному структурному путевому выражению) Пусть даны XML-документ X, его описывающая схема dX и некоторое абсолютное структурное путевое выражение Р. Пусть \P(dX)\ ф 0, пусть также доступно 2-\P(dX)\ блоков буферной памяти, если \P{dX)\ Ф 1, и 1 блок буферной памяти, если \P{dX)\ - 1. Тогда стоимость операции поиска узлов документа X, удовлетворяющих Р, рассчитывается по формуле Cost = V b(dx) + S

ASPEFmd ^ ' dx е P(dX)

где 5 = 0, если \P(dX)\ = 1, и S представляет собой количество блоков внешней памяти, в которых хранятся нумерующие метки дескрипторов

узлов, соответствующих узлам описывающей схемы P(dX), в противном случае.

Теорема 3 (о стоимости вычисления односложного абсолютного структурного путевого выражения) Пусть даны XML-документ X, его описывающая схема dX и некоторое односложное для X абсолютное структурное путевое выражение Р. Пусть |Р(сЙ)( Ф пусть также доступно

2|W I (Ю

dx s P{dX) q < dx

блоков буферной памяти, если \P(dX)\ Ф 1, и

4<dx

блоков буферной памяти, если \P(dX)\ = 1 (при этом dx представляет собой единственный элемент множества P(dX)). Тогда стоимость вычисления Р над документом X рассчитывается по формуле

Cost = У (b(dx) + Yb(q)) + S

ASPEEvaluaUM i-d v

dx e P(dX) q < dx

где S = О, если \P(dX)\ = 1, и S представляет собой количество блоков внешней памяти, в которых хранятся нумерующие метки дескрипторов узлов, соответствующих узлам описывающей схемы P(dX), в противном случае.

Теорема 4 (о стоимости вычисления многосложного абсолютного структурного путевого выражения) Пусть даны XML-документ X, его описывающая схема dX и некоторое многосложное для X абсолютное структурное путевое выражение Р. Пусть \P(dX)\ ф 0. Тогда

1. Если доступно

2-IWI+ I (Ю

dxeP'(dX) q < dx

блоков буферной памяти, то стоимость вычисления Р над документом X ограничена следующим значением

Cost < У (b(dx) + У b(q)) + S

ASPEEvahu&Pl ¿-I V V ' ¿-i dx e P(dX) q-tdx

2. Если доступно

2ЩЩ+ £ (£»(<?))

dx € r(dX) q « dx

блоков буферной памяти, то стоимость выполнения Р над документом X рассчитывается по следующей формуле

Cost = У (b(dx) + V b(q)) + S

ASPEEyaluaePl ¿-i V 4 '

dx е P(dX) q<dx

В обоих случаях 5 представляет собой количество блоков внешней памяти, в которых хранятся нумерующие метки дескрипторов узлов, соответствующих узлам описывающей схемы Р{с1Х).

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

Определение 7 Под стоимостью операции изменения хранимых ХМЬ-данных понимается количество блоков внешней памяти, которые необходимо изменить для выполнения операции.

Определение 8 Операция изменения хранимых ХМЬ-данных называется локальной, если стоимость выполнения этой операции не зависит от размера ХМЬ-данных.

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

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

• Фиксированный размер дескриптора узла в блоке упрощает учет свободного места в блоке.

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

• Неперестраивая нумерующая схема позволяет избежать перестройки дерева ХМЬ-документа, связанной с перенумерацией при вставке новых узлов.

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

Теорема 5 (о свойстве локальности микрооперации вставки узла) Микрооперация вставки узла в методе хранения ХМЬ-данных во внешней памяти на основе описывающей схемы обладает свойством локальности. При этом верны следующие оценки:

1

3 + я 5 Сол* ,„„., <11 + « 1

3

4 + л<С<м/Лц„., <5£ + 11 + $

4

где к — количество дескрипторов в блоке, содержащем родительский узел вставляемого узла; 5 = 0, если нумерующая метка вставляемого узла умещается в дескрипторе узла, и л представляет собой количество блоков, которые надо модифицировать при вставке нумерующей метки узла, в противном случае. Граничные значения оценок достигаются.

Теорема б (о свойстве локальности микрооперации удаления узла) Микрооперация удаления узла в методе хранения ХМЬ-данных во внешней памяти на основе описывающей схемы обладает свойством локальности. При этом верны следующие оценки:

2 + ¿5 + 5

1

2 + <7 + 5

2

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

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

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

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

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

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

1. Адресное пространство базы данных должно иметь размер, достаточный для представления ХМЬ-документов большого размера (ориентировочные требования к размеру ХМЬ-документов, которые должна уметь обрабатывать ХМЬ-СУБД, составляют сегодня как минимум гигабайты).

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

3. Требуется сократить накладные расходы, связанные с переключением страниц. Это требование тесно связано с предыдущим. По причине кластеризации узлов ХМЬ-документа в соответствии с описывающей схемой многие операции (такие, как переход от отца к сыну и наоборот, в некоторых случаях переход к соседу и др.) приводят к смене текущей страницы, то есть страницы, с которой в данный момент работает транзакция.

4. Требуется сократить накладные расходы, связанные с "подменой" указателей, или полностью избежать их.

5. Требуется, чтобы метод управления памятью обеспечивал свободу в выборе алгоритма вытеснения страниц, а не полагался, например, на алгоритмы вытеснения, применяемые в операционной системе.

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

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

Определение 9 Адресом в слоистом адресном пространстве называется

пара {layer, addr), где layer — номер слоя (представляет собой целое *

число) и addr — адрес объекта в этом слое (представляет собой указатель).

Благодаря тому, что количество слоев в САП можно варьировать, размер САП можно выбрать сколь угодно большим.

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

Эффективность перехода по указателю обеспечивается за счет простого отображения САП на виртуальное адресное пространство. Если программисту требуется обратиться к объекту, находящемуся в САП по адресу {layer, addr), то он переходит по адресу addr в адресном пространстве процесса. Если в данный момент страница, содержащая объект, не загружена в оперативную память, или по этому адресу располагается страница из другого слоя, то эта ситуация обрабатывается о

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

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

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

Определение 10 Структурным путевым выражением с предикатом называется путевое выражение, удовлетворяющее следующим синтаксическим правилам (приведенные здесь правила опираются на грамматику языка XQuery и являются модификациями правил 68-73, 83):

[68'] StructuralPathExprWithPred : : =

( ("/" RelativePathExpr?) v I ("//" RelativePathExpr)

I RelativePathExpr) Predicate [69'] RelativePathExpr ::= StepExpr (("/" I "//")

StepExpr)*

[70'] StepExpr ::= AxisStep

[71'] AxisStep ::= ForwardStep

[72'] ForwardStep ::= (ForwardAxis NodeTest)

I AbbrevForwardStep [73'] ForwardAxis ::= ("child" "::")

| ("descendant" "::") I ("attribute" "::") I ("self" "::") I ("descendant-or-self" "::") [83'] Predicate ::= "[" RelativePathExpr GeneralComp

Literal "]" I "[" Literal GeneralComp RelativePathExpr "]"

Определение 11 Абсолютным структурным путевым выражением с предикатом называется структурное путевое выражение с предикатом, примененное к узлу-документу.

* В работе предлагаются три базовых способа вычисления

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

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

• "Сверху-вниз" {top-down). Способ заключается в вычислении абсолютного структурного путевого выражения для нахождения целевых узлов и последующей проверкой предиката для каждого найденного узла (для этого выполняется относительное путевое выражение). Для перехода от целевого узла к предикатному используются указатели между узлами.

• "Снизу-вверх" {bottom-up). Способ заключается в применении предиката как можно раньше — то есть вычисляется абсолютное структурное путевое выражение с целью нахождения предикатных узлов, для каждого найденного узла проверяется предикат, и для тех узлов, которые удовлетворяют предикату, осуществляется переход к целевым узлам посредством указателей.

• "Фильтрация с помощью нумерующей схемы " {numbering scheme based filter). Способ заключается в независимом нахождении целевых и предикатных узлов путем вычисления соответствующих абсолютных структурных путевых выражений, применении предиката к предикатным узлам и последующей фильтрацией целевых узлов с использованием нумерующей схемы.

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

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

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

• Вводится необходимая статистическая информация. Пусть даны узлы описывающей схемы dxi, dx2,..., dxt, причем для любого j = \,t~\ узел dXj является родителем узла dxJ+]. Начальный и конечный узлы совпадают с целевым и предикатным узлами

соответственно. Для каждого узла описывающей схемы сЫр у = £7 известны следующие данные:

и, — количество узлов ХМЬ-документа, соответствующих с1х/, Ъ, — количество блоков с данными, соответствующих <£с/, г} — количество блоков внешней памяти, которые содержат записи таблицы косвенности для узлов ХМЬ-документа, соответствующих сЬс/,

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

Для метода "сверху вниз" оценочная стоимость рассчитывается по формуле

I

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

Теорема 7 Пусть некоторому узлу сЬс описывающей схемы ХМЬ-документа соответствует т узлов. Пусть узлу (¿у, являющемуся непосредственным потомком узла сЬс, соответствует тг узлов, причем эти узлы равномерно распределены между узлами, соответствующими узлу схемы сЫ. Пусть к узлов из этих тг узлов удовлетворяют некоторому предикату ргес/, причем эти к узлов равномерно распределены среди всех узлов, соответствующих Лу. Тогда при вычислении абсолютного структурного путевого выражения с предикатом способом "сверху-вниз" для определения того, какие узлы, соответствующие <зЬс, удовлетворяют предикату ргес1, придется прочитать

тЯ

узлов, соответствующих узлу схемы с¡у, где

Л = Х-^-—РО,тг,к)

ТЗ*тг-к-1 + \

Данная теорема позволяет получить оценку для В:

Л Л , Г Л 1

ь,\ —ь + 1 /и

тг - ) ,

Для метода "снизу-ввсрх" оценочная стоимость рассчитывается по формуле:

= 6 + -«/(А )]) + Г(//В/,[и ■ве1{вх))]))

1 = I

И, наконец, для метода "фильтрации с помощью нумерующей схемы" оценочная стоимость определяется формулой

= \ +■6 + + *

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

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

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

1. разработан метод организации хранения ХМЬ-данных во внешней памяти, обеспечивающий эффективное выполнение запросов и операций изменения данных;

1.1.для важного подкласса ХРаЛ-запросов (абсолютных структурных ХРаЙ1-запросов) доказана оптимальность разработанных структур данных по числу требуемых операций ввода-вывода;

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

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

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

1. Фомичев А.В., "Методы эффективного выполнения XQuery-запросов к XML данным", Материалы Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов 2003", Москва, 2003.

2. Konstantin Antipin, Andrey Fomichev, Maxim Grinev, Sergey Kuznetsov, Leonid Novak, Peter Pleshachkov, Maria Rekouts, and Denis Shiryaev, "Efficient Virtual Data Integration Based on XML", Proceedings of ADBIS 2003.

3. Антипин K.B., Фомичев A.B., Гринев M.H., Кузнецов С.Д., Новак Л.Г., Плешачков П.О., Рекуц М.П., Ширяев Д.Р., Оперативная интеграция данных на основе XML: системная архитектура BizQuery, Труды Института системного программирования РАН, 2004.

4. Andrey Fomichev, "XML Storing and Processing Techniques", Proceedings of SYRCoDIS 2004.

5. Максим Гринев, Сергей Кузнецов, Андрей Фомичев, "Особенности СУБД Sedna. XML-СУБД Sedna: технические особенности и варианты использования", журнал "Открытые системы" #8, издательство "Открытые системы", 2004.

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

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

5 4 9 3

Оглавление.

Введение.

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

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

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

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

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

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

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

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

Глава 1 Управление хранимыми XML-данными.

1.1 Технологии платформы XML для управления данными.

1.1.1 Язык XML, .слабоструктурированные данные и платформа XML.

1.1.2 Модель данных XPath и XQuery.

1.1.3 Язык путевых выражений XPath и язык запросов XQuery.

1.2 Управление хранимыми XML-данными в полнофункциональной XML-СУБД.

1.2.1 Полнофункциональная XML-СУБД.

1.2.2 Требования к полнофункциональной XML-СУБД в контексте управления хранимыми данными.

1.3 Подходы к храпению XML-данных.

1.3.1 Связи между узлами: по значению или по ссылке?.

1.3.2 Определение отношения предок-потомок и порядка документа: нумерующая схема.

1.3.3 Использование реляционных СУБД для хранения XML-данных.

1.3.4 Специально разработанные методы для хранения XML-данных.

1.4 Выводы.

Глава 2 Метод хранения XML-данных во внешней памяти на основе описывающей схемы.

2.1 Описывающая схема XML-документа и структурные путевые выражения.

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

2.2 Организация хранения XML-данных во внешней памяти на основе описывающей схемы.

2.2.1. Блоки данных.

2.2.2 Частичный порядок дескрипторов узлов.

2.2.3 Структура дескриптора узла.

2.2.4 Связи между дескрипторами узлов.

2.2.5 Фиксированный размер дескриптора узла в блоке.

2.2.6 Таблица косвенности.

2.2.7 Хранение текстовых данных.

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

2.3 Оценка метода хранения XML-данных во внешней памяти на основе описывающей схемы.

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

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

2.3.3 Оценка стоимости изменения данных.

2.3.3.1 Микрооперация вставки узла.

2.3.3.2 Микрооперация удаления узла.

2.3.4 Навигация по документу.

2.3.5 Экспериментальные данные.

2.3.6 Сравнение с другими методами хранения XML-данных.

2.4 Выводы.

Глава 3 Управление памятью для хранимых XML-данных и слоистая организация адресного пространства.

3.1 О необходимости разработки единого адресного пространства базы данных для представления данных во внешней и оперативной памяти.

3.2 Слоистая организация адресного пространства базы данных.

3.2.1 Требования к управлению памятью для хранимых XML-данных.

3.2.2 Слоистое адресное пространство.

3.2.3 Страничная организация слоистого адресного пространства.

3.2.4 Реализация слоистого адресного пространства.

3.2.4.1 Отображение на виртуальное адресное пространство процесса.^.

3.2.4.2 Отображение на буферную память.

3.2.4.3 Отображение на внешнюю память.

3.2.5 Переход по указателю в слоистом адресном пространстве.

3.2.5.1 Понятие текущей страницы.

3.2.5.2 Переход по указателю в слоистом адресном пространстве для программиста.

3.2.6 Реализация слоистого адресного пространства в многопользовательской среде.

3.2.7 Дополнительные возможности слоистого адресного пространства.

3.2.8 Экспериментальные данные.

3.2.9 Преимущества и недостатки слоистого адресного пространства.

3.2.10 Слоистое адресное пространство и методы управления памятью, основанные на приеме "подмены" указателей.

3.3 Выводы.

Глава 4 Пути доступа к XML-данным, хранимым на основе описывающей схемы.

4.1 Задача поиска оптимального пути доступа к данным.

4.2 Вычисление абсолютного структурного путевого выражения с предикатом. 127 4.2.1 Абсолютное структурное путевое выражение с предикатом.

4.2.2 Способы вычисления абсолютного структурного путевого выражения с предикатом.

4.2.3 Метрика оценки стоимости и селективность путевых выражений.

4.2.4 Оценка стоимости вычисления выражения способом "сверху-вниз".

4.2.5 Оценка стоимости вычисления выражения способом "снизу-вверх".

4.2.6 Оценка стоимости вычисления выражения способом "фильтрации с помощью нумерующей схемы".

4.2.7 Комбинирование способов вычисления выражения.

4.3 Выводы.

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

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

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

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

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

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

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

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

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

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

1.1. Для важного подкласса XPath-запросов (абсолютных структурных XPath-запросов) доказана оптимальность разработанных структур данных по числу требуемых операций ввода-вывода;

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

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

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

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

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

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

3. Разработан оригинальный метод выполнения XPath-запросов над предложенным внутренним представлением.

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

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

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

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

Основные положения работы докладывались на десятой международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2003», на седьмой международной конференции Advances in Databases and Information Systems (ADBIS) 2003, на первом Весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (SYRCoDIS) 2004, на девяносто первом и девяносто седьмом семинарах Московской Секции ACM SIGMOD (2004 и 2005 гг), на семинаре "Современные сетевые технологии" под руководством д.ф.-м.н., профессора Васенина В.А. (2005 г).

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

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

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

4.3 Выводы

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

Заключение

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

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

1.1. Для важного подкласса XPath-запросов (абсолютных структурных XPath-запросов) доказана оптимальность разработанных структур данных по числу требуемых операций ввода-вывода;

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

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

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

• Оптимизация размера дескриптора узла с целью сокращения объема памяти, занимаемой данными;

• Адаптация предложенного метода управления памятью к многопоточным аппаратным архитектурам для обеспечения параллельной обработки запросов;

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

1. Фомичев А.В., "Методы эффективного выполнения XQuery запросов к XML данным", Материалы Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов 2003", Москва, 2003

2. Konstantin Antipin, Andrey Fomichev, Maxim Grinev, Sergey Kuznetsov, Leonid Novak, Peter Pleshachkov, Maria Rekouts, and Denis Shiryaev, "Efficient Virtual Data Integration Based on XML", Proceedings of ADBIS 2003

3. Антипин K.B., Фомичев A.B., Гринев M.H., Кузнецов С.Д., Новак Л.Г., Плешачков П.О., Рекуц М.П., Ширяев Д.Р., Оперативная интеграция данных на основе XML: системная архитектура BizQuery, Труды Института системного программирования РАН, 2004

4. Andrey Fomichev, "XML Storing and Processing Techniques", Proceedings of SYRCoDIS 2004

5. Максим Гринев, Сергей Кузнецов, Андрей Фомичев, "Особенности СУБД Sedna. XML-СУБД Sedna: технические особенности и варианты использования", журнал "Открытые системы" #8, издательство "Открытые системы", 2004

6. Extensible Markup Language (XML) 1.0 (Third Edition), W3C Recommendation 4th February 2004, Fran£ois Yergeau, Tim Bray, Jean Paoli, С. M. Sperberg-McQueen, Eve Male, http://www.w3.org/TR/! 998/REC-xml-19980210

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

8. HTML 4.01 Specification, W3C Recommendation 24 December 1999, Dave Raggett, Arnaud Le Hors, Ian Jacob, http://www.w3.org/TR/1999/REC-html401 -19991224

9. World Wide Web Consortium (W3C), http://www.w3.org/

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

11. Buneman P., Semistructured data. In proceedings of the ACM SIGMOD/SIGACT Conference on Principle of Database Systems (PODS), Tucson, AZ, 1997, May, 117121

12. Гринев, М., Системы управления полуструктурированными данными, журнал "Открытые системы" #05-06, издательство "Открытые системы", 1999

13. ACM SIGMOD (Special Interest Group on Management of Data) Conference, http://www.sigmod.org/sigmod/

14. Very Large Data Bases (VLDB) Conference, http://www.vldb.org/dblp/db/conf/vldb/index.html

15. Zhen Hua Liu, Muralidhar Krishnaprasad, Vikas Arora: Native XQuery processing in Oracle XMLDB. SIGMOD Conference 2005

16. Matthias Nicola, Bert Van der Linden: Native XML Support in DB2 Universal Database. VLDB 2005

17. Shankar Pal, Istvan Cseri, Oliver Seeliger, Michael Rys, Gideon Schaller, Wei Yu, Dragan Tomic, Adrian Baras, Brandon Berg, Denis Churin, Eugene Kogan: XQuery Implementation in a Relational Database System. VLDB 2005

18. ISO/IEC 10646: Universal multi-octet character set UCS, ed. M. Suignard

19. Когаловский, M.P., Стандарты платформы XML и базы данных, Российские Электронные Библиотеки, 2001,http://www.elbib.ru/index.phtml?page=elbib/rus/methodology/xmlbase/tutorial

20. W3C Web Services Activity, http://www.w3.org/2002/ws/

21. W3C Semantic Web. http://www.w3.org/2Q01/sw/

22. SOAP Version 1.2, W3C Recommendation 24 June 2003, http://www.w3.org/TR/soapl 2

23. XML Path Language (XPath) 2.0, W3C Candidate Recommendation 3 November 2005, ed. Anders Berglund et al, http://www.w3.org/TR/2005/CR-xpath20-20Q51103/

24. XML Query Working Group, http://www.w3.org/XML/Query/

25. XQuery 1.0: An XML Query Language, W3C Candidate Recommendation 3 November 2005, ed. Scott Boag et al, httn://www.w3.org/TR/2005/CR-xquery-20Q51103/

26. Namespaces in XML, World Wide Web Consortium 14-January-1999, ed. Tim Bray et al, http://www.w3.org/TR/1999/REC-xml-names-19990114

27. XML Schema Part 2: Datatypes Second Edition, W3C Recommendation 28 October 2004, ed. Paul V. Biron et al,httn://www.w3.org/TR/2004/REC-xmlschema-2-20041028/

28. RELAX NG schema language for XML, http://www.relaxng.org/

29. Когаловский M.P., Энциклопедия технологий баз данных, М.: Финансы истатистика, 2002

30. XQuery 1.0 and XPath 2.0 Data Model (XDM), W3C Candidate Recommendation 3 November 2005, ed. Mary Fernandez et al, http://www.w3.org/TR/20Q5/CR-xpath-datamodel-20051103/

31. Mary Fernandez, Jerome Simeon: Growing XQuery, In Proc of ECOOP'2003 (European Conference on Object-Oriented Programming)

32. Dean Meltz, Rick Long, Mark Harrington, Robert Hain, Geoff Nicholls, An Introduction to IMS: Your Complete Guide to IBM's Information Management System, IBM Press, 2004 CODASYL DBTG Report, April 1971

33. Alfons Kemper, Donald Kossmann: Adaptable Pointer Swizzling Strategies in Object Bases. ICDE 1993: 155-162 46. Li, Q., Moon, В.: Indexing and Querying XML Data for Regular Path Expressions,

34. Proceedings of the 27th VLDB Conference, Roma, Italy, 2001

35. J. McHugh, S. Abiteboul, R. Goldman, D. Quass, J. Widom. Lore: A Database Management System for Semistructured Data, SIGMOD Record, 2001

36. Patrick O'Neil, Elizabeth O'Neil, Shankar Pal, Istvan Cseri, Gideon Schaller, Nigel Westbury: ORDPATHs: Insert-Friendly XML Node Labels, In Procof the ACM SIGMOD Conference, 2004

37. H.A. Азнаурян, С.Д. Кузнецов, Л.Г. Новак, М.Н. Гринев: SLS: Нумерующая схема для больших XML-документов, Программирование, 2006, № 1 (принята к публикации)

38. Goldman R., McHugh J., Widom J. From simistructured data to XML: Migrating the Lore data model and query language. In ACM SIGMOD Workshop on the Web (WebDB), Philadelphia, PA, 1999

39. Tian, F., DeWit, D., Chen, J., Zhang, C.: The Design and Performance Evaluation of Alternative XML Storage Strategies. SIGMOD Record 31(1): 5-10 (2002)

40. Igor Tatarinov, Stratis Viglas, Kevin S. Beyer, Jayavel Shanmugasundaram, Eugene J. Shekita, Chun Zhang: Storing and querying ordered XML using a relational database system. SIGMOD Conference 2002: 204-215

41. Jagadish, H., Al-Khalifa, S., Chapman, A., Lakshmanan, L., Nierman, A., Paparizos S., Patel, J., Srivastava D., Wiwatwattana N. Wu, Y. and Yu, C.: TIMBER: A Native XML Database, The VLDB Journal, Volume 11, Issue 4 (2002)

42. Al-Khalifa, S., Jagadish, H., Patel, J., Wu, Y., Koudas, N. Srivastava, D.: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of ICDE 2002, San Jose, California

43. Barbara Catania, Wen Qiang Wang, Beng Chin Ooi, Xiaoling Wang: Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency. SIGMOD Conference 2005

44. Fiebig, Т., Helmer, S., Kanne, C.-C., Moerkotte, G., Neumann, J., Schiele, R., Westmann, Т.: Anatomy of a native XML base management system, The VLDB Journal, Volume 11, Issue 4 (2002)

45. Leela, K., Haritsa, J.: SphinX: Schema-conscious XML Indexing, Technical Report, TR-2001-04, DSL/SERC, http://dsl.serc.iisc.ernet.in/pub/TR/TR-2001-04.pdf

46. Xiaofeng Meng, Daofeng Luo, Mong-Li Lee, Jing An: OrientStore: A Schema Based Native XML Storage System. VLDB 2003

47. Albrecht Schmidt, Florian Waas, Martin L. Kersten, Michael J. Carey, Ioana

48. Manolescu, Ralph Busse: XMark: A Benchmark for XML Data Management. VLDB 2002

49. Stephane Bressan, Gillian Dobbie, Zoe Lacroix, Mong-Li Lee, Ying Guang Li, Ullas Nambiar, Bimlesh Wadhwa: X007: Applying 007 Benchmark to XML Query Processing Tool. CIKM 2001

50. Shakespeare in XML the collection of Shakespeare's plays marked up in XML, http://www.ibiblio.org/xml/examples/shakespeare/

51. DBLP XML records, http://dblp.uni-trier.de/xml/

52. L. Mignet, D. Barbosa, P. Veltri. The XML Web, A First Study. Proc. 12th Intl.WWW Conference, Budapest, 2003

53. Грииев M.H.: Модельно-языковые средства управления данными, Диссертация на соискание ученой степени кандидата физико-математических наук, Москва, 2003

54. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998

55. Persistent Heap, http://modis.ispras.ru/~fomichev/tools/ph/ph.htm

56. Э. Таненбаум, Современные операционные системы, 2-е издание, «Питер», 2002

57. Silberschatz, A., Korth, Н., Sudarshan, S.: Database System Concepts, Third Edition, McGraw-Hill, 1997

58. Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979

59. XSLT 2.0 and XQuery 1.0 Serialization, W3C Working Draft 15 September 2005, ed. Michael Kay et al,http://www.w3.org/TR/2005/WD-xslt-xquerv-serialization-20050915/

60. Гектор Гарсиа-Молина, Джеффри Ульман, Дженнифер Уидом: Системы баз данных. Полный курс, «Вильяме», 2003

61. Michael J. Carey, David J. DeWitt, Joel E. Richardson, Eugene J. Shekita: Object and

62. File Management in the EXODUS Extensible Database System. VLDB 1986

63. Microsoft Developers Network, http://msdn.microsoft.com/

64. Linux Documentation (including Manual Pages), http://www.linux.org/docs/index.html

65. Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985

66. David R. Butenhof, Programming with POSIX Threads, Addison-Wesley, 1997

67. Seth J. White, David J. DeWitt: A Performance Study of Alternative Object Faulting and Pointer Swizzling Strategies. VLDB 1992

68. Wilson, P., Kakkad, S.: Pointer Swizzling at Page Fault Time: Efficiently and Compatibly Supporting Huge Address Spaces on Standard Hardware, Proceedings of Workshop on Object Orientation and Operating Systems, Paris, France, 1992

69. Wilson, P., Kakkad, S.: Pointer Swizzling at Page Fault Time: Efficiently and Compatibly Supporting Huge Address Spaces on Standard Hardware, Proceedings of Workshop on Object Orientation and Operating Systems, Paris, France, 1992

70. C. Lamb, G. Landis, J. Orenstein, D. Weinreb, "The ObjectStore Database System", Communications of the ACM, Vol. 34, No. 10, October 1991.

71. Seth J. White, David J. DeWitt: QuickStore: A High Performance Mapped Object Store. SIGMOD Conference, 1994

72. Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993

73. Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989

74. Ashraf Aboulnaga, Alaa R. Alameldeen, Jeffrey F. Naughton: Estimating the Selectivity of XML Path Expressions for Internet Scale Applications. VLDB 2001

75. Wei Wang, Haifeng Jiang, Hongjun Lu, Jeffrey Xu Yu: Bloom Histogram: Path Selectivity Estimation for XML Data with Updates. VLDB 2004

76. Neoklis Polyzotis, Minos N. Garofalakis, Yannis E. Ioannidis: Selectivity Estimation for XML Twigs. ICDE 2004

77. Куржанский А.Б., Учебник по курсу «Динамическое программирование и процессы управления», 2005

78. Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987

79. Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of

80. Tuples Satisfying a Condition. SIGMOD Conference, 1984

81. S. B. Yao: Approximating Block Accesses in Database Organizations, Communications of the ACM, Volume 20 , Issue 4, April 1977

82. George Diehr, Aditya N. Saharia: Estimating Block Accesses in Database Organizations. IEEE Trans. Knowl. Data Eng. 6(3): 497-499 (1994)