Содержание к диссертации
Введение
1 Платформа XML и функциональные методы 10
1.1 Платформа XML 10
1.1.1 Расширяемый язык разметки - XML 10
1.1.2 Пространства имен в XML 12
1.1.3 Язык XML Path (XPath) 15
1.1.4 Язык ссылок XML (XLink) 20
1.2 Обработка XML-данных п проблема потери соответствия 23
1.3 SXML: XML-документ как S-иыраженне 27
1.3.1 XML, информационное пространство XML и SXML 27
1.3.2 Спецификация SXML 29
1.3.3 Пространства имен в SXML 32
1.3.4 Свойства SXML 34
1.4 Библиотека SXPath: реализация некоторых конструкций языка XPath
функциональными методами 37
1.4.1 Низкоуровневые функции SXPath 37
1.4.2 Высокоуровневая функция SXPath 41
2 Интеграция XPath с языком функционального программирования и язык запросов к XML-данным 43
2.1 Статический анализ и динамическое вычисление выражений XPath 43
2.2 Расширение набора примитивов библиотеки SXPath 50
2.3 Отображение выражения XPath на суперпозицию функции 52
2.3.1 Лексический и синтаксический анализ выражении XPath 53
2.3.2 Грамматическое правило "выражение пути" 55
2.3.3 Грамматическое правило "абсолютный путь доступа" 57
2.4 Расширение XPath за счет интеграции со Scheme 58
2.5 SXPath как язык запросов 62
2.6 Абстрактное синтаксическое дерево вираження XPatli в пиде SXML Go
3 Расширенно языка запросов для обработки соїюкупііостсіі XML- докумептоп, снизанных ссылками XLink С8
3.1 Мотивация поддержки XLink її языке запросов 68
3.2 Пример связанных ХМ L-документе в 69
3.3 Родственные работы в области обработки связанных ХМL-документов . 72
3.3.1 XQuery 72
3.3.2 Браузеры с поддержкой XLink 73
3.3.3 Интерфейсы прикладного программирования 73
3.4 Расширение XPatli переходами по дугам языка XLink 74
3.5 Адресация к дугам языка XLink 78
3.5.1 Дуга XLink г> виде информационной единицы 79
3.5.2 Оси для адресации к дугам XLink 85
3.6 Реализация 88
3.6.1 Разбор разметки языка XLink 88
3.6.2 Реализация предложенных осей как расширение библиотеки SXPath . 90
3.7 Ограничения предлагаемого языка запросов 93
4 Оптимизация выполнения запросов 95
4.1 Эксперименты в отношении существующих промышленных реализации XPatli 95
4.1.1 Эксперимент 1: дублирующие узлы 96
4.1.2 Эксперимент 2: глубоко вложенные предикаты 100
4.2 Оптимизация вычислении обратных осей XPatli ввиду отсутствия и SXML уч<азателсн на родительские узлы 101
4.2.1 Родственные работы в области вычисления обратных oceli XPatli . 104
4.2.2 Иллюстрация предлагаемого подхода 105
4.2.3 Алгоритм вычисления выражении XPatli, содержащих обратные осп . 106
4.2.4 Свойства предложенного алгоритма 11G
4.2.5 Ограничения алгоритма 120
4.2.6 Эксперименты 121
4.3 Удаление дублирующих узлов при вычислении oceii XPatli 124
4.3.1 Предварительные соглашения 124
4.3.2 Оси ancestor и ancestor-or-sclf 126
1.3.1 Ось attribute 133
4.3.1 Oct, child 134
4.3.2 Оси descendant и dcscendant-or-sclf 139
4.3.3 Оси following и preceding 144
4.3.7 Осп following-sibling it preceding-sibling 147
4.3.8 Ось namespace 152
4.3.9 Ось parent 153
4.3.10 Ось self 157
4.4 Вычисление осей XPath для случая расположения узлов на одном уровне . 158
4.4.1 Осп child, descendant и desccndant-or-self 1G1
4.4.2 Оси following п preceding 1G3
4.4.3 Оси following-sibling и preceding-sibling 104
4.4.4 Ось parent 1G6
4.5 Вычисления occii XPatli u присутствии в шаге доступа позиционных предикатов 1G7
4.5.1 Выявление позиционных предикатов с помощью статического вывода типов 171
4.G Оптимизация вычисления глубоко вложенных предикатов 172
4.7 Оптимизация вычисления операции обобщенного сравнения 177
4.7.1 Вычисление обобщенного сравнения сортировкой слиянием 178
4.7.2 Вычисление обобщенного сравнения поразрядной сортировкой 180
4.8 Верхняя оценка сложности выполнения запросов ввиду предложенных способов оптимизации 185
4.9 Детали реализации , 204
4.10 Эксперименты 209
4.10.1 Эксперимент 1: устранение дублирующих узлов 209
4.10.2 Эксперимент 2: глубоко вложенные предикаты 211
4.10.3 Сравнительные тесты производительности 213
Заключение 218
Список литературы
- Обработка XML-данных п проблема потери соответствия
- Расширение набора примитивов библиотеки SXPath
- Родственные работы в области обработки связанных ХМL-документов
- Оптимизация вычислении обратных осей XPatli ввиду отсутствия и SXML уч<азателсн на родительские узлы
Введение к работе
Актуальность темы
В настоящее время язык XML используется как осмоііпос средство для представления слабоструктурнровапных данных.
Для обработки XML-данных могут использоваться языки платформы XML, такие как XPath, XQuery и XSLT. Поскольку большинство языков платформы XML не являются языками программирования общего назначения, при реализации XML-приложении они обычно используются совместно с некоторыми традиционными языками программирования. Комбинирование дізух различных но своей природе языков (например, XPath и Java), — использующих разные модели данных п разные парадигмы программирования, — приводит к проблеме, известной как потеря соответствия (impedance mismatch). Для XML-прнложешш необходим язык, который бы по своей природе понимал структуры данных XML и предоставлял оптимизированные алгоритмы для обработки ХМL-данных.
ФункционалЕлше методы к, в частности, язык программирования Scheme семейстпа Lisp являются привлекательными для преодоления проблемы потерн соответствия в контексте обработки XML-данных, что мотивируется следующими свойствами языка Scheme:
Естественным представлением вложенных элементов XML являются вложенные списки, и язык Scheme использует вложенные списки для представления п своих данных, и своего кода.
Язык Scheme является функциональным языком, как и большинство языков платформы XML (XSLT, XQuery).
Разработка и оптимизация алгоритмов для обработки XML-данных функциональными методами п интеграция Scheme с языками платформы XML н определяют актуальность диссертационной работы.
Цель и задачи работы
Целью диссертационной работы является создание среды разработки XML-прпложешш, поддерживающей единую модель данных и позволяющей облегчить и ускорить процесс создания XML-ігршюжешги.
Для достижения основной цели работы поставлены следующие задачи: создать язык запросов к XML-дапным, обладающий следующими свойствам»: язык запросов должен обеспечивать тесную интеграцию языка адресации частей XML-документа XPath с функциональным языком программирования общего назначения Scheme; язык запросов должен обеспечивать средство формулирования запросов к совокупности XML-документов, семантически связанных при помощи XLink -языка ссылок XML; разработать методы оптимизации выполнения запросов с целью достижения гарантированной полиномиальной алгоритмической сложности.
Основные результаты работы
В работе были получены следующие основные результаты:
Создан язык запросов к XML-дапным, обладающий следующими свойствами: язык запросои обеспечивает тесную интеграцию языка адресации частей XML-доку.мента XPatli с функциональным языком программирования общего назначения Scheme; язык запросов обеспечивает средство формулирования запросов к совокупности XML-документов, семантически связанных ссылками языка XLink.
Разработаны методы оптимизации выполнения запросов, гарантирующие полиномиальную сложность от размера запроса и размера документа.
Реализован прототип среды разработки XML-прнложсішн, поддерживающей единую моделі) данных и позволяющей облегчить н ускорить процесс создания XML- прнложеннп.
Научная новизна работы
Научной uoninitoii обладают следующие результаты работы: преодолена проблема потерн соответствия при интеграции языка адресации частей XML-документа XPath с языком программирования общего назначения; разработан язык запросов к совокупности XML-документов, ашзапных между собой при помощи XLink - языка ссылок XML; разработан оригинальный метод устранения дублирующих узлов в процессе вычисления выражений языка XPath, основанный па поддержании порядка документа при нычислешш каждой конструкции языка XPath.
Практическая значимость
Достигнутая интеграция языка адресации частей XML-докумснтон XPath с языком функционального программирования Scheme может быть использована для достижения большей гибкости и расширяемости при формз'лировашш критериев выборки XML-данных.
Разработанный язык запросов к совокупности XML-докумснтов, связанных ссылками языка XLink, может быть использован для повышения наглядности представления объектов прикладной предметной области на XML н упрощения задач обработки XML-данных для приложения.
Разработанные способы оптимизации выполнении запросов могут быть использованы для повышения эффективности процессоров языков XPath и XQnery н вычислителей запросов в XML-СУБД.
Реализованный прототип среды разработки XML-приложешій функциональными методами был использован при создании в Институте системного программирования РАН промышленной системы виртуальной интеграции BizQuery и XML-СУБД Sedna.
Доклады и публикации
Основные положения работы докладывались на восьмой международной конференции "Advances in Databases and Information Systems" (ADBIS) (2004 г), на носьмндесятом и девяносто восьмом семинарах Московской Секции ACM SIGMOD {2002 и 2005 гг) и на семинаре ''Современные сетевые технологии" (2005 г).
По материалам диссертации опубликовано восемь работ [1, 2, 3, -1, 5, 6, 7, 8].
Структура и объем диссертации
Работа состоит из введения, четырех глав, заключения и списка литературы. Общин объем диссертации составляет 22G страниц. Список литературы содержит 71 наименование.
Краткое содержание работы
Первая глава является обзорной и содержит изложение методов и средств, которые лежат в основе разработок, описанных в последующих трех главах. В даниоіі главе дастся обзор основных понятий платформы XML, необходимых для изложения последующего материала, рассматриваются существующие подходы к обработке XML-данных н обсуждается присущая существующим подходам проблема потери соответствия. Обсуждаются преимущества функциональных методов в контексте обработки ХМL-данных как средства преодоления проблемы потери соответствия. Описывается формат SXML — представление XML-документов в виде вложенных списков — и его свойства. Обсуждаются идеи вычисления путсіі доступа языка адресации частей XML-документа XPath функциональными методами, над документами формата SXML.
Вторая глава посвящена описанию разработанного автором подхода к интеграции языка XPath с языком программирования общего назначения Scheme на уровне представлення данных к вычислительной парадигмы. Описываются разработанные автором способы отображения фаз статического анализа и динамического вычисления выражения XPath на вызов функции высокого порядка языка функционального программирования и отображения произвольного выражения XPath па суперпозицию функций, обеспечивающих обработку списковых структур данных. Предлагаются способы интеграции и едином запросе шлраженпіі языка XPath и пользовательских функций языка Scheme и иллюстрируется достигаемая в результате предложенной интеграции функциональность языка запросов к данным формата SXML.
Третья глава посвящена описанию разработанного автором расширения языка запросов, которое предоставляет приложению возможность формулирования запросов к совокупности XML-документов, семантически связанных ссылками XLink - языка ссылок XML, - и осуществления переходов по дугам, определяемым этими ссылками. Практическая потребность расширения языка запросов поддержкой ссылок XLink обосновывается иллюстративными примерами. Описывается предлагаемое расширение языка запросов, достигаемое за счет добавления трех новых осей к языку XPath и добавления к узлу каждого типа, представленного в модели данных языка XPath, по одному дополнительному свойству. Рассматриваются детали реализации предлагаемого расширения языка запросов функциональными методами.
Четвертая плана посвящена описанию предлагаемых актором способов оптимизации исполнении запросом. В данной плане исследуется проблема экспоненциального времени, » неблагоприятном случае затрачиваемого рядом существующих промышленных реализации языка XPatli на вычисление выражений XPath, и выявляются конструкции языка XPath, недостаточно предусмотрительный подход к вычислению которых может приводить к экспоненциальной алгоритмической сложности нсего вычислителя запросов. Предлагаются способы оптимизации выполнения запросов и доказывается, что данные способы оптимизации обеспечивают полиномиальную сложность выполнения запросов от размера Xj\IL-доку ментов и размера запросов. Обсуждаются детали реализации функциональными методами предложенных способов оптимизации и приводятся результаты экспериментов, произведенных в отношении сделанной реализации.
В заключении перечисляются основные результаты работы.
Обработка XML-данных п проблема потери соответствия
Информация о том, как осуществлять переход между парой ресурсов, включающая в себя направление перехода п его семантику, задается при помощи дуги (arc).
Ввиду того, что расширенная ссылка предоставляет моэцшле возможности по связыванию ресурсов, структура расширенной ссылки может быть достаточно сложной. В общем случае расширенная ссылка включает в себя элементы типа локатор [9], которые указывают на удаленные ресурсы; элементы типа ресурс, содержащие локальные ресурсы; элементы типа дуга, которые определяют дуги и условия перехода по ним.
Дута в языке XLink является ориентированной, и два ресурса, соединяемые дугой, называются соответственно исходным (starting resource) и целевым (ending resource) [9]. Дута, имеющая локальный ресурс в качестве своего исходного ресурса н удаленный ресурс в качестве нелепого, называется исходящей [19]. Дугу называют входящей (inbound), если ее исходный ресурс является удаленным ресурсом, а целевой ресурс — локальным. Дуга называется сторонней (third-party), если ни один из соединяемых сю ресурсов не является локальным. Благодаря наличию в языке XLink входящих и сторонних дут обеспечивается возможность соединять ресурсы без их модификации [8].
Обычно элементы типа "расширенная ссылка" располагаются отдельно от тех ресурсеrs, которые они соединяют (например, в совершенно разных документах). Расширенные ссылки важны для ситуации, когда соединяемые ресурсы доступны только;], ]л чтения; или когда модификация этих ресурсов является дорогостоящей л сложной операцией, тогда как модификация отдельно располагающейся ссылки достаточно проста; или когда ресурсы имеют форматы, не поддерживающие встроенные ссылки (как дли многих мультимедийных форматов) [19].
На рис. 1.5 показан пример использовании расширенной ссылки языка XLink. В данном примере ссылкой соединяются текст некоторой электронной книги, описание об авторе книги и сайт издательства [7). Описание автора дано в локальном ресурсе языка XLink, т.е. это описание целиком располагается внутри ссылочного элемента. Книга и издательство — это удаленные ресурсы языка XLink, потому что па них ссылаются по унифицированным идентификаторам ресурсов. Каждый из трех ресурсов помечен собственной меткой (значение атрибута xlink: label). Эти метки используются при описании переходов. В данной расширенной ссылке определяются два перехода: от автора к книге и от книги к издательству. Каждый переход описывается своим собственным элементом типа дуга (arc). Заметим, что дуга, ведущая от книги к издательству, соединяет два удаленных ресурса [4].
В языке XLink определяется способ, когда к расширенной ссылке добавляется специальная семантика для указания па ссылочные базы (Hnkbascs). Когда ссылка используется в таком назначении, она помогает приложению обрабатывать другие ссылки [19.
Хотя простые ссылки концептуально являются подмножеством расширенных ссылок, они синтаксически различны. В частности, простая ссылка определяет дугу неявным образом, и поэтому для преобразования простой ссылки в расширенную ссылку требуется осуществить несколько структурных преобразований [19].
Можно говорить о том, что предназначением простої! ссылки является удобная короткая форма записи для эквивалентного случая расширенной ссылки (4]. Одни элемент вида "простая ссылка" объединяет в себе базовую функциональность элементов типа "расширенная ссылка", "локатор", "дуга" и "ресурс". В том случае, когда реально требуется лишь подмножество свойств этих элементов, простая ссылка удобна как альтернатива расширенной ссылке.
Обработка XML-дашшх .может производиться с использованием соответствующих языков платформы XML, разрабатываемых консорциумом W3C, например, XPath, XSLT и XQuery. В то же время, существующие в настоящее время языки платформы XML не позиционируются как языки программирования общего назначения [1J п, как правило, в одиночку недостаточны для реализации XML-ирнложешіП. Большинство XML-прнложепнй реалпзз стся при помощи традиционных языков программирования, таких как С или Java, или скрипт-язЕЛков, например Perl, JavaScript или Python (2 lJ. !--Расширенная ссылка XLink. Элемент может носить произвольное имя-- MyExtendedLink xmlns:xlink="http;//www.w3.org/1999/xlink" xlink:type=,lextended" !—Ресурс. Специфицирует локальный ресурс в тернинах XLink— author xlink:type="resource" xlink:label="All !--Некоторая разметка, относящаяся к локальному ресурсу— name John /name surnaae Sinith /surnaEie /author !--Элемент типа локатор. Адресуется к удаленному ресурсу по его URI-- book xlink:type="locatox" xlink:label="B" xlink: href="http://library.com/book.pdf"/ publisher xlink:type="locator" xlink:label="P" xlink:href="http://publisher.cora"/ !--Дуга. Определяет переход между ресурсами с метками "А" и "В"— MyArcElenient xlink:typG="arc" xlink:fron=, A" xlink:to="B"/ MyArcElement xlink:type="arc" xlink:frora="B" xlink:to=;"P,,/ /MyExtendedLink
Комбинирование двух различных по своей природе языков (например, XPath и Java) приводит к проблеме, известной как потеря соответствия (impedance mismatch). Проблема потери соответствия более широко известна в области комбинирования реляционной и объектно-ориентированной моделей [25], по в аналогичной степени имеет место также для языков платформы XML и языков программирования общего назначения [26]. Проблема потерн соответствия включает п себя два аспекта:
разные способы внутреннего представления данных. Так, внутренним представлением XML-документа служит дерево, тогда как многие языки программирования общего назначения не предоставляют такой тип данных в качестве базового;
различные вычислительные парадигмы. Языки XSLT и XQuery платформы XML являются функциональными, тогда как язык программирования Java является объектно-ориентированным, а язык Perl - процедурным,
Проблема потерн соответствия означает, что структуры данных и стиль написания программного кода должны быть некоторым образом преобразованы из одной модели в другую в процессе работы XML-приложения.
Такие понятия, как различия элементов и атрибутов языка XML, порядок документа п пр., не имеют соответствующих аналогов в традиционных объектпо-орнентнрованшлх языках программирования4. Проблема потери соответствия в этой связи зачастую может приводить к искажениям и потере информации при отображении XML-данных на объекты и при проведении обратного отображения.
При использовании при разработке XML-прпложешш языков платформы XML, таких как XPath, XSLT и XQuery, для получения пол нефункциональных возможностей по обработке XML-данных от разработчика приложения требуется детальное знание соответствующего языка платформы XML, равно как и знание основного языка программирования общего назначения, выбранного для написания XML-прпложеішя5. При этом многие преимущества, предоставляемые интегрированной средой разработки основного языка, часто не могут быть использованы прикладным программистом при обработке XML-даппых [2С.
Еще одним широко распространенным подходом к обработке XML-данных при помощи языков нрограммироиаппя общего назначения является использование для доступа к структуре и содержимому XML-документов некоторого интерфейса прикладного программирования, такого как Объектная Модель Документа (Document Object Model,
4 Obasanjo D, Integrating XML into Popular Programming Languages. Ли Overview of С-О mega. Microsoft Corporation. - 2003, 13 .Lin. - bttp://mS(]ii.inicrosoft.com/library/ lefni]lt.a -p?url-/]ibrary/{4i us/(Jnexxinl/btml/xml01M200j.a.4p
Расширение набора примитивов библиотеки SXPath
В диссертационной работе был разработан механизм отображения произвольного выражения языка XPath, записанного в соответствии со спецификацией XPatli 1.0 консорциума W3C, па суперпозицию функций языка функционального программирования Scheme. В предлагаемом отображении семантика выражений XPath по адресации частей документа формата SXML достигается при помощи низкоуровневых примитивов библиотеки SXPath, ранее рассмотренной в разделе 1.4.
Поскольку набор исходно имеющихся в библиотеке SXPath примитивов по достаточен для выражения семантики всех конструкции языка XPath, были разработаны дополнительные примитивы, такие, что расширенный набор примитивов обеспечивает вычисление любой конструкции XPath в соответствии со спецификацией XPatli. Можно выделит:, следующие основные расширения библиотеки SXPath, предложенные в диссертационной работе: Поиск элемента по уникальному идентификатору.
Уникальный идентификатор элемента языка XML определяется значением атрибута типа ID, который может быть у данного элемента. Типы атрибутов могут задаваться в предписывающей схеме ХМL-документа, например, в Определении Типа Документов {Document Type Definition, DTD) [9]. Во многих спецификациях платформы XML ставится акцепт на быстром нахождении элемента по его уникальному идентификатору: в частности, в спецификации Информационного Пространства XML ссылка па элемент но уникальному идентификатору (IDREF) рассматривается как ссылка по указателю (32J.
Для быстрого нахождения и SXML-доку менте элемента, имеющего данный уникальный идентификатор, предлагается создавать для документа специальный индекс идентификаторов (id-index). Индекс идентификаторе» представляет собой список ассоциативного поиска: он состоит из точечных пар 37], каждая из которых ставит в соответствие уникальному идентификатору элемент в документе с данным идентификатором. Do ішутреішем представлении данных языка программирования Scheme «се идентификаторы, связанные со списками (и, в частности, с элементами SXML-документа), являются указателями на структуры данных в шшятп, благодари чему построение индекса идентификаторов не требует глубокого копирования данных, а получение элемента по индексу обеспечивает попадание па нужный адрес тоіі области памяти, где расположен искомый элемент SXML-доку мента.
Построение индекса идентификаторов предполагает не более чем однократное сканирование документа и не требует специальных накладных расходов, поскольку может осуществляться одновременно с разбором XML-документа и конструированием его представлении на SXML. D ходе обработки документа нужный элемент с требуемым значением уникального идентификатора извлекается из индекса идентификаторов с помощью ассоциативного поиска. Функциональная парадигма программирования позволяет гарантировать, что индекс идентификаторов остается и консистентном состоянии с SXML-документом на протяжении всего времени работы приложения. Операции сравнения языка XPath.
Операции сравнения языка XPath 1.0 (называемые также операциями обобщенного сравнения [40]) по своей семантике не совпадают пи с одной стандартной функцией Scheme для сравнения базовых типов данных [37). Отличительной особенностью операций обобщенного сравнения языка XPath заключается и том, что в этих операциях, во-первых, осуществляется неявное преобразование сравниваемых аргументов к общему для них тину данных языка XPath, и, во-вторых, при вычислении результата операции сравнения неявно используется семантика квантора существования.
В диссертационной работе были предложены алгоритмы вычисления операций обобщенного сравнения XPath функциональными методами, обеспечивающие параметризацию функциями сравнения скалярных типов данных, что достигается благодаря свойству функции быть объектами первого класса. В разделе 1.7 диссертационной работы проводится более подробное обсуждение операции обобщенного сравнения языка XPath, а также предлагаются способы оптимизации вычисления этих операций. Полный набор occii XPath.
В библиотеке SXPath из всего набора осей языка XPath были исходно представлены реализации лишь нескольких оспоппых, наиболее используемых па практике oceii. Хотя в статье [13 и утверждается, что все остальные оси XPath могут быть вычислены через эти основные, при таком подходе возникает необходимость многократного посещения одних и тех же узлов SX ML-доку мента при вычислении осп.
В диссертационной работе были предложены алгоритмы вычисления нсех осей XPath над SXML-документом, обладающие тем свойством, что для произвольного контекстного узла вычисление оси требует посещения любого узла SXML-документа не более одного раза. Описание алгоритмов вычисления осей XPath над SXML-документом в данном разделе не приводится, поскольку и разделах 4.3 и 4.4 предлагаются модифицированные разновидности этих алгоритмов, которые обеспечивают устранение дублирующих узлов, потенциально возникающих при вычислении осеіі над наборами узлов, и которые за счет этого обеспечивают оптимизацию вычисления выражении языка XPath.
Родственные работы в области обработки связанных ХМL-документов
В качестве языка запросов, применимого к источникам XML-данных разнообразных типов, консорциум W3C [9] позиционирует язык XQuery [46]. Хотя на момент написання диссертационной работы язык XQuery еще не был переведен из чернового статуса п статус рекомендации консорциума W3C, уже можно с уверенностью говорить о том [52], что в своей текущей версии XQuery не предоставляет средств по обработке ссылок языка XLink в соответствии со спецификацией XLink, что подтверждается следующими соображениями:
Описания ссылок языка XLink строятся на сложном и многословном синтаксисе, базирующемся па пространстве имен и иерархической взаимосвязи элементов языка XLink. При написании на XQuery запросов к XML-документам, содержащим элементы языка XLink, «сн работа по распознаванию ссылок XLink и интерпретации их семантики целиком ложится на разработчика запросов. Необходимо также заметить, что получение информации о дугах, описанных в единственной расширенной ссылке языка XLink, требует написании па XQuery нескольких операции естественного соединения (join) [53], выполнение которых в общем случае даег значительную нагрузку на вычислитель языка XQuery.
При соединении с помощью ссылки XLink удаленного ресурса, представляющего собой фрагмент некоторого ХМ L-доку мента, идентификация данного фрагмента внутри документа осуществляется с помощью языка XPointcr, и идентификатор фрагмента включается в значение одного из глобальных атрибутов языка XLink. При обработке ссылок XLink с помощью XQuery для определения ресурсов, соединяемых с помощью ссылки, необходимо динамически вычислить идентификатор фрагмента на языке XPointcr, полученный в качестве значення атрибута. В спецификации функций и операторов XQuery 5-1] не существует функции, позволяющей интерпретировать идентификатор фрагмента, записанный па языке XPointcr. Также, насколько известно автору из произведенного анализа существующих реализации языка XQuery, не существует ни одной такоії реализации XQuery, которая бы предоставляла интерпретатор языка XPointcr внутри вычислителя запросов.
Предлагаемый и диссертационной работе язык запросов к совокупности XML-доку ментов, связанных ссылками XLink, базируется на подмножестве XQuery — языке XPath, назначением которого является адресация структурных частей XML-документа. В диссертационной работе предлагается расширение XPath высокоуровневой поддержкой XLink, и функциональность языка запросов достигается благодаря достигнутой интеграции XPath с функциональным языком программирования общего назначения Scheme.
Под поддержкой языка XLink браузером будем понимать способность браузера распознавать элементы языка XLink в XML-документе и обеспечивать пользовательский интерфейс для переходов между ресурсами по дугам XLink, Среди браузеров, обеспечивающих поддержку языка XLink, следует упомянуть такие, как Лтауа, Mozilla u DocZtlla. Первые два реализуют поддержку языка XLink лишь в масштабе простых ссылок XLink, браузер DocZilla обеспечивает также навигацию по расширенным ссылкам.
Наличие лишь одного браузера, поддерживающего ссылки языка XLink в полном объеме (DocZilla), объясняется, по мнению автора, сформулированными консорциумом W3C требованиями к языку XLink [21]. В то время как простые ссылки XLink явным образом ориентированы на внешнее представление, презентационный аспект расширенных ссылок XLink многими аналитиками ставится под сомнение1.
Необходимо заметить, что браузеры с поддержкой языка XLink но своему предназначению нацелены па наглядное представление документов со ссылками XLink человеку. Поскольку браузеры являются прикладным программным продуктом, при их разработке обычно не ставятся задачи обеспечения других приложений средствами высокоуровневой обработки XML-документов со ссылками XLink. В диссертационной работе решается системная задача, и язык запросов к совокупности XML-докумситов, связанных ссылками XLink, разрабатывается из расчета на то, чтобы быть используемым другими приложениями.
Интерфейсы прикладного программирования для обработки XML-докумсптон, соединенных ссылками языка XLink, предоставляют системы XLip, Х2Х и ExtremeKnit. Все три обозначенные системы предоставляют интерфейсы прикладного программирования на языке объектно-ориентированного программирования Java.
Ввиду использования объектно-орнептнроваиного языка программирования для обработки XML-докумсптов, псе три системы — XLip, Х2Х и ExtremeKnit — страдают от їШіСЬлгтс В. XLink: Who Cares?. - 2002, 13 Mar. - http://www.xml.eom/pub/a/2002/03/13/xlirik.html проблемы потери соответствия (impedance mismatch) 2 1]. Так, и интерфейсах прикладного программирования, предоставляемых каждой из рассматриваемых трех систем, для представления и обработки XML-доку ментов со ссылками XLink разработана собственная система классоп, и внутреннее представление XML-докумсіпа и каждой из этих систем классов значительно отличается от древовидной структуры информационного пространства XML [32].
Помимо показанной проблемы потерн соответствия, все три интерфейса прикладного программирования являются достаточно низкоуровневыми. С различными вариациями, отдельные методы языка Java используются для таких базовых операции, как загрузка отдельного X ML-доку мента, получения набора ссылок, нахождения исходного или целевого ресурса для данной ссылки и т.п. Упомянутые методы связаны друг с другом только по своим аргументам и возвращаемым результатам, что вынуждает разработчиков приложении вводить много локальных переменных и прослеживать сложные взаимосвязи между классами языка Java. При написаним приложения приходится проводить много низкоуровневой рутшшоп работы, прежде чем будут получены «се необходимые данные для переходов по ссылкам XLink и обработки связанных этими ссылками XML-документов.
Язык запросов, предлагаемый в диссертационной работе, обеспечивает более высоким уровень абстракции над синтаксисом языка XLink по сравнению с рассмотренными интерфейсами прикладного программирования. Использование функциональных методов программирования для еделаїшоіі реализации обеспечивает интеграцию предлагаемого языка запросов с языком программирования общего назначения Scheme па уровне представления данных и вычислительной парадигмы, что позволяет избежать проблемы потери соответствия [1].
Предлагаемый в диссертационном работе язык запросов к XML-документам, связанным между собой с помощью ссылок XLink, базируется на языке адресации частей XML-документа XPath. Обзор языка XPath был проведем в подразделе 1.1.3; в данном разделе рассматривается предлагаемое расширение функциональности XPath, обеспечивающее переходы по дугам языка XLink.
Заметим, что термин ось (axis) в XPath очень близок термину псреход (traverse) в XLink, поскольку оба подразумевают перемещение с одного места и документе на другое. Данное наблюдение убеждает пас в том, что при построении на основе XPath языка запросов к совокупности связанных XML-докумеитов операции перехода по дуге XLink в языке XPath должна соответствовать ось. По аналогии с англоязычным названием для перехода в XLink мазонем эту ось "traverse".
Оптимизация вычислении обратных осей XPatli ввиду отсутствия и SXML уч<азателсн на родительские узлы
Предложенное в диссертационной работе расширение языка запросов поддержкой языка XLink не предоставляет средств по работе с ресурсами XLink, которые не являются узлами или наборами узлов. Такими ресурсами могут быть только удаленные ресурсы (т.е. те, которые участвуют в ссьглкс XLink за счет того, что к ним адресуются с помощью унифицированного идентификатора URI), и к их числу относятся: ресурсы, которые имеют формат, отличный от XML и XHTML, например, мультимедийные форматы; ресурсы, при адресации к которым используется идентификатор фрагмента на языке XPointcr, вычисляющийся н интервал (range) или последовательность символов внутри текстового узла.
Введенные ограничения мотннпрованы требованием обеспечения замкнутости всех операции языка запросов относительно объектов, предстаинмых в модели данных языка XPath. Так, интервалы языка XPointer нарушают иерархическую структуру документа, поскольку разрывают границы разметки, и поэтому не могут быть представлены п виде набора узлов модели данных XPath.
Заметим, что идентичные ограничения приняты и в спецификации языка Преобразовании XSL при обеспечении доступа к документам, отличным от обрабатываемого XML-документа [41]. Данная аналогия подтверждает, что введенные ограничения предложенного в диссертационной работе расширения языка запросов являются оправданными.
В данной гласе описываются предлагаемые автором способы оптимизации запросов, обеспечивающие полиномиальную алгоритмическую сложность выполнения: запросов от размера XML-докумснтов и размера запросов.
В статье [55] была поднята проблема экспоненциального времени, в неблагоприятном случае затрачиваемого наиболее известными промышленными процессорами языка XPath на вычисление выражении XPath в зависимости от размера этих вираженні!.
Исследованием семантики выражении XPath, проведенным и диссертационной работе, были выделены такие конструкции языка XPath, недостаточно предусмотрительный подход к вычислению которых может приводить к экспоненциальной алгоритмической сложности всего вычислителя языка XPath от размера вычисляемых выражений1. Автором были выделены две основные причины, приводящие к экспоненциальной сложности при вычислении выражений XPath:
Количество узлов в наборе узлов на промежуточных тагах доступа может возрастать экспоненциально, ввиду возникновения в наборе дублирующих узлов.
Понятие дублирующего узла было введено в спецификации XPath 2.0 и обозначает многократное вхождение одного и того же узла в последовательность узлов. Термин "последовательность" имеет в языке XPath 2.0 семантику, близкую к семантике термина "набор узлов" в языке XPath 1.0. Несколько узлов рассматриваются как
Люоркнл Д. Способы оптимизации вычисления выражений языка, XPath и их реализация функциональными методами : 93-й ежемесячный семинар Московской Секции ЛСМ SIGMOD, 24 фопрлля 2005 г. - http://synthesis.ipi.ac.ru/siginod/scminar/s2005022t многократное вхождение одного и того же узла тогда и только тогда, когда все эти узлы идентичны, т.е. имеют одинаковые значения индивидуальности (node identity) [40]. Несовпадающие относительно индивидуальности узлы XML-документа, даже имеющие равные значения всех своих своПств [32], считаются различными узлами.
Несмотря на то, что в спецификации XPath 1.0 дублирующие узлы и наборе узлов, полученном в результате вычисления выражения XPath, строго говоря, исключены но определению набора узлов, при разработке алгоритмов вы числения конструкции языка XPath бывает необходимым в ходе промежуточных вычислении рассматривать набор узлов в качестве мультимножества [55, 5G], что делает актуальной для такого мультимножества задачу устранения дублирующих узлов.
Предикаты, синтаксически глубоко вложенные внутрь других предикатов, могут требовать экспоненциального роста времени вычисления с ростом глубины вложенности.
Поскольку в языке XPath фильтрация набора узлов по предикату предполагает получение значения предиката для каждого узла из этого набора, семантика вложенных друг в друга предикатов в значительной степени напоминает семантику вложенных циклов в языках программирования. Ввиду того, что время вычисления пложенных циклов может возрастать экспоненциально с ростом глубины их вложенности, аналогичная проблема может возникать и для глубоко вложенных предикатов языка XPnth.
Эксперименты, предложенные в статье [55], в диссертационной работе были воспроизведены над промышленными процессорами языка XPath Saxon, Xaln.ii и XT. Результаты экспериментов подтверждают паличне в неблагоприятном случае экспоненциальной зависимости между размером путей доступа XPath и временем, необходимым для их вычисления и использованием упомянутых процессоров языка XPath, и косвенным образом иллюстрируют влияние отмеченных выше двух причин на время вычисления выражении XPath.
