close

Вход

Забыли?

вход по аккаунту

?

bd000100879

код для вставкиСкачать
На правах^укописи
ШлМ/
ЛИЗОРКИН ДМИТРИЙ АЛЕКСЕЕВИЧ
ФУНКЦИОНАЛЬНЫЕ МЕТОДЫ
ОБРАБОТКИ XML-ДАННЫХ
05.13.11 — математическое и программное обеспечение
вычислительных машин, комплексов и компьютерных сетей
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата физико-математических наук
М О С К В А 2005
Работа выполнена на кафедре системного программирования факультета
вычислительной математики и кибернетики Московского государственного
университета им. М.В. Ломоносова.
Научный руководитель:
Официальные оппоненты:
член-корреспондент РАН,
профессор
Иванников В и к т о р Петрович.
доктор физико-математических наук,
профессор
Абрамов Сергей Михайлович;
кандидат физико-математических наук,
старший научный сотрудник
К у л я м и н В и к т о р Вячеславович.
Ведущая организация: Вычислительный центр имени А. А. Дородницына
Российской академии наук.
Защита диссертации состоится "1L"
М ^ я 1 р 2005 года в
часов
на заседании диссертационного совета Д 501.001.44 в Московском
государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК,
аудитория
С диссертацией можно ознакомиться^ в библиотеке факультета В М и К
МГУ. Автореферат разослан "iO_" 0^<^^аил^ 2005 г.
Ученый секретарь
диссертационного совета,
профессор
J/0d^'^
Трифонов
Общая характеристика работы
Актуальность т е м ы
В настоящее время язык X M L используется как основное средство для
представления слабоструктурированных данных.
Поскольку большинство
языков платформы X M L не является языками программирования общего
назначения, при реализации XML-приложений языки платформы X M L
обычно используются совместно с некоторыми традиционными языками
программирования. Комбинирование различных по своей природе языков
приводит к проблеме, известной как потеря соответствия (impedance mis­
match). Преодоление проблемы потери соответствия в контексте обработки
XML-данных, разработка и оптимизация алгоритмов обработки XMLданных функциональными методами и интеграция языка функционального
программирования Scheme с языками платформы X M L
и определяют
актуальность диссертационной работы.
Цель и задачи работы
Целью диссертационной работы является создание среды разработки XMLприложений, поддерживающей единую модель данных и позволяющей
облегчить и ускорить процесс создания XML-ириложений.
Для достижения основной цели работы поставлены следующие задачи:
• создать язык запросов к XML-данным, обладающий следующими
свойствами:
- язык запросов должен обеспечивать тесную интеграцию языка
адресации частей XML-документа XPath с функциональным языком
программирования общего назначрятгя-б^нея»
РОС НАЦИОНАЛЬНАЯ
БИБЛИОТЕКА
СВ(
ОЭ
:Siii
— язык запросов должен обеспечивать средство формулирования
запросов к совокупности XML-документов, семантически связанных
при помощи XLink - языка ссылок X M L ;
• разработать методы оптимизации выполнения запросов для достижения
гарантированной полиномиальной алгоритмической сложности.
Н а у ч н а я новизна
Научной новизной обладают следующие результаты работы:
• преодолена проблема потери соответствия при интеграции языка
адресации частей XML-документа XPath с языком программирования
общего назначения;
• разработан язык запросов с поддержкой семантики языка ссылок X M L —
XLink;
• разработан оригинальный метод устранения дублирующих узлов в
процессе вычисления выражений XPath, основанный на поддержании
порядка документа при вычислении каждой конструкции языка XPath.
Практическая значимость
Достигнутая интеграция языка адресации частей XML-документов XPath
с
языком
функционального
программирования
Scheme
может
быть
использована для достижения большей гибкости и расширяемости при
формулировании критериев выборки XML-данных.
Разработанный
язык
запросов
к
совокупности
XML-документов,
связанных ссылками языка XLink, может быть использован для повышения
наглядности представления объектов прикладной предметной области на
X M L и упрощения задач обработки XML-данных для приложения.
'(
■)*5-,- 1 -
"ч
'
5
Разработанные способы оптимизации выполнения запросов могут быть
использованы для повышения эффективности процессоров языков XPath и
XQuery и вычислителей запросов в XML-СУБД.
Реализованный
прототип
среды
разработки
XML-приложений
функциональными методами был использован при создании в Институте
системного программирования РАН промышленной системы виртуальной
интеграции BizQuery и XML-С'УБД Sedna.
Апробация работы и публикации
По материалам диссертации опубликовано восемь работ [1-8].
Основные
положения работы докладывались на следующих конференциях и семинарах:
• на восьмой международной конференции "Advances in Databases and In­
formation Systems" (ADBIS) (2004 r);
• на восьмидесятом и девяносто восьмом семинарах Московской Секции
АСМ SIGMOD (2002 и 2005 гг);
• на семинаре "Современные сетевые технологии" под руководством д.ф.M.H., профессора Васенина В.А. (2005 г).
Структура и объем диссертации
Работа состоит из введения, четырех глав, заключения, списка литературы
и приложения. Общий объем диссертации составляет 229 страниц. Список
литературы содержит 71 наименование.
Краткое содержание работы
Во
введении
обосновываются
цель
и
задачи
данной
актуальность, научная новизна и практическая значимость.
краткий обзор работы.
работы,
ее
Приводится
6
П е р в а я глава является обзорной и содержит изложение методов и
средств, которые лежат в основе разработок, описываемых в последующих
трех главах.
В
первом разделе данной главы дается краткий обзор основных
понятий платформы X M L : расширяемого языка разметки (XML), механизма
пространств имен в X M L , языка адресации частей XML-доку мента XPath и
языка ссылок XLink.
Во втором разделе первой главы рассматриваются существующие
подходы к обработке XML-данных и обсуждается присущая существующим
подходам проблема потери соответствия (impedance mismatch). Отмечается
сходство между XML-данными и S-выражениями, где последние служат
текстуальным
представлением
нетипизированных
вложенных
списков,
являющихся основной конструкцией для представления программ и данных
в языках функционального программирования Lisp и Scheme.
Выбор
функциональных методов для обработки XML-данных мотивируется как
средство преодоления проблемы потери соответствия.
В
третьем
разделе
первой
главы
рассматривается
представление XML-доку мента в виде S-выражения.
SXML
—
Составляющие
XML-документ информационные единицы информационного пространства
XML
(XML
Information Set) хорошо поддаются описанию в виде S-
выражения, что делает внешние текстуальные нотации X M L и SXML
достаточно похожими. Поскольку внутренним представлением S-выражений
в языках функционального программирования Lisp и Scheme служат
вложенные списки, формат SXML обеспечивает возможность использования
стандартных функций обработки списков для обработки XML-данных:
конструирования тегов разметки, выполнения запросов и проведения
трансформаций.
В
четвертом
разделе первой главы
рассматривается
библиотека
SXPath, предоставляющая интерфейс прикладного программирования на
7
Scheme для вычисления некоторых конструкций языка XPath над SXMLдокументами Описываются основные низкоуровневые функции библиотеки
SXPath, внутренняя логика которых иллюстрирует удобство формата S X M L
для адресации частей документа при вычислении практически важных
конструкций языка XPath.
Рассматривается высокоуровневый списковый
синтаксис библиотеки SXPath, выступающий в качестве "родного" синтаксиса
для языка функционального программирования Scheme и являющийся
аналогом сокращенного синтаксиса языка XPath по сравнению с его полным
синтаксисом.
В т о р а я глава посвящена описанию разработанного автором подхода
к интеграции языка XPath с языком программирования общего назначения
Scheme на уровне представления данных и вычислительной парадигмы.
Достигнутая в работе интеграция XPath
и Scheme обеспечивает
приложение гибкостью и расширяемостью при формулировании критериев
выборки, в соответствии с которыми производится адресация интересуготцих
приложение частей XML-документа.
Реализованные средства интеграции
обеспечивают приложение функциональностью языка запросов и могут
быть использованы как для формулирования запросов к XML-данным,
представленным на SXML, так и для задания трансформаций этих данных.
Предлахаехся построение вычислителя языка XPath функциональными
методами.
Для достижения преимуществ наличия двух отдельных фаз
обработки, определенных в спецификации XPath 2.0,
фазы статического
анализа и фазы динамического вычисления — предлагается представление
данных фаз функцией высокого порядка.
Фазе статического анализа
сопоставляется вызов разработанной автором функции, которая принимает
выражение XPath и возвращает снова функцию, представляющую данное
выражение XPath в прекомпилированпом виде.
При вызове последней
функции с входными данными формата SXML, вычислению этой функции
соответствует
фаза динамического
вычисления
выражения
XPath,
а
возвращаемым результатом служит результат вычисления выражения XPath
над входными данными.
Автором был разработан способ конструирования прекомпилированного
представления
выражения
в
чистом
XPath,
функциональном
соответствующего
стиле
для
произвольного
спецификации
XPath
1.0
консорциума W3C, индукцией по сложности выражения. В предлагаемом
подходе каждое подвыражение, соответствующее нетерминальному символу
грамматики XPath, отображается на функцию языка функционального
программирования,
которая, будучи вызвана,
обеспечивает получение
результата вычисления данного подвыражения в соответствии с семантикой
языка XPath.
Библиотека SXPath была расширена поддержкой выражений XPath,
благодаря чему формулирование запросов к документам формата SXML
может осуществляться в двух различных синтаксисах:
в текстовом
синтаксисе языка XPath и в списковом синтаксисе библиотеки SXPath.
Каждый
Так,
из
двух
синтаксисов
обладает
своими
преимуществами.
текстовый синтаксис позволяет прозрачным образом переносить
существующие навыки программистов XML-приложений на созданную
среду обработки XML-данных функциональными методами.
Списковый
синтаксис за счет своей близости к синтаксису языка функционального
программирования
Scheme
обеспечивает
приложение
удобными
и
наглядными возможностями по конструированию и анализу запросов.
Преимущества каждого из двух синтаксисов - текстового и спискового делают привлекательным комбинирование обоих синтаксисов внутри единого
запроса.
В
работе предлагается расширение спискового синтаксиса
возможностью использования выражения XPath в текстовом синтаксисе в
качестве составного шага доступа. Предложенный способ комбинирования
текстового и спискового синтаксисов обеспечивает расширение языка XPath
за счет его интеграции со Scheme:
9
• Разные части запроса могут быть записаны в разных синтаксисах,
что позволяет прикладному программисту удобно комбинировать части
запроса, записанные в соответствии со спецификацией языка XPath,
с теми частями, которые конструируются приложением, возможно,
динамически.
• Поскольку
функции в языке функционального
программирования
Scheme являются объектами первого класса, в роли шага доступа может
выступать произвольная функция Scheme, которая принимает объект
типа "набор узлов" языка XPath и возвращает новый набор узлов:
/ : набор_узлоБ —> набор_узлов .
Возможность использования произвольной функции Scheme с заданной
сигнатурой в качестве шага доступа обеспечивает расширение языка XPath
до языка запросов к XML-данным. Тогда как в языке XPath путь достзтта
позволяет получить набор узлов, с необходимость принадлежащих исходному
XML-документу, язык запросов предоставляет возможность создания XMLданных в рамках используемого внутреннего представления.
Так, язык
запросов к XML-данным XQuery консорциума W3C содержит, помимо
прочих операций, конструкторы новых узлов дерева X M L во внутреннем
представлении.
Для узлов,
представленных на SXML, операции конструирования
новых узлов достигаются стандартными функциями языка Scheme по
конструированию списков. Более того, операции квази-цитирования (quasiquote) и снятия цитирования (unquote) языка Scheme предоставляют
наглядный синтаксис для комбинирования вычислимых фрагментов с
фрагментами результата и являются близкой аналогией вычислимых и
литеральных конструкторов языка XQuery.
В работе отмечается, что семантика FLWOR-выражения — ос1Ювной
конструкции языка
XQuery,
обеспечивающей итерацию и связывание
10
локальных переменных с промежуточными результатами, — в значительной
степени напоминает семантику выражения, записанного с использованием
функциональной
парадигмы
организации
фильтрация-отображение-накопление"
вычислений
"перечисление-
(enumerate-filter-map-accumulate).
Ввиду семантического сходства между операциями FLWOR-выражения и
этапами обработки в парадигме "перечисление-фильтрация-отображениенакопление", FLWOR-выражения из практически важного подмножества
запросов
языка
XQuery
имеют
прямолинейные
аналоги
в
терминах
парадигмы "перечисление-фильтрация-отображение-накопление". Поскольку
все необходимые составляющие для организации вычислений в парадигме
"перечисление-фильтрация-отображение-накопление"
представлены
в
языке Scheme стандартными функциями обработки списков, достигнутая
интеграция возможностей языка XPath по адресации частей документа
с
возможностями
обеспечивает
Scheme по обработке списковых структур
функциональность
языка
запросов
для
данных
XML-данных,
представленных на S X M L .
Предложенная в работе интеграция XPath и Scheme обеспечивает
приложение возможностью использования функций Scheme в качестве шагов
доступа в запросах и возможностью комбинирования вызовов разработанного
функционального вычислителя XPath и функций обработки списковых
структур данных.
В предлагаемом подходе обеспечивается интеграция
XPath и Scheme на уровне представления данных и функциональной
вычислительной парадигмы.
Третья
расширения
глава
языка
посвящена
запросов,
описанию
которое
разработанного
предоставляет
автором
приложению
возможность формулирования запросов к совокупности XML-документов,
семантически связанных ссылками XLink - языка ссылок XML, ~ и
осуществления переходов по дугам, определяемым этими ссылками.
Язык XLink консорциума W3C является инструментом для описания
11
взаимосвязей между ресурсами в виде ссылок на X M L . Ссылка языка
XLink позволяет устанавливать отношение связи между более чем двумя
ресурсами и содержит несколько дуг, каждая из которых характеризуется
своим исходным ресурсом и целевым ресурсом.
В спецификации XLink определяются лишь структуры данных для
описания ссылок и минимальная модель их поведения.
Все действия
по распознаванию элементов языка XLink в XML-документе и обработке
описываемых этими элементами ссьшок перекладываются на приложение.
Возникает желание иметь в качестве надстройки над структурами данных
языка XLink язык более высокого уровня, который бы обеспечивал
манипуляционную составляющую над ссылками XLink.
Существующие
языки
запросов
и
интерфейсы
прикладного
программирования не обеспечивают высокоуровневых средств обработки
ссылок XLink в XML-документах
Так, язык XQuery, позиционируемый
консорциумом W3C как язык запросов к разнообразным типам источников
XML-данных,
не предоставляет специализированных возможностей по
обработке имеющихся в XML-документе ссылок языка XLink в соответствии
со спецификацией XLink. Интерфейсы прикладного программирования для
обработки соединенных ссылками языка XLink XML-документов являются
достаточно низкоуровневыми и, кроме того, страдают от проблемы потери
соответствия.
В
работе
предлагается
расширение
языка
запросов
поддержкой
семантики ссылок XLink. Разработанное расширение базируется на языке
адресации частей XML-документа XPath и состоит в добавлении трех новых
осей к грамматике XPath и добавлении к узлу каждого типа, представленного
в модели данных, по одному дополнительному свойству.
Разработанное расширение языка запросов поддержкой XLink может
быть использовано для повышения наглядности представления объектов
прикладной предметной области на X M L и упрощения задач обработки XML-
12
данных для приложения. Расширение языка запросов способствует удобству
применения ссылок языка XLink при моделировании и обработке объектов
прикладной предметной области.
Автором было замечено, что термин "ось" (axis) в XPath очень
близок термину "переход" (traverse) в XLink, поскольку оба подразумевают
перемещение с одного места в документе на другое. Из данного наблюдения
был сделан вывод, что при построении на основе XPath языка запросов
к совокупности связанных XML-документов операции перехода по дуге
XLink органичным образом соответствует ось. По аналогии с англоязычным
названием для перехода в XLink данная ось была названа traverse. Следуя
общему стилю, принятому в спецификации XPath при определении осей,
определение оси traverse записывается следующим образом:
Определение 1 Ось traverse годерокит все узлы, являющиеся целевыми
ресурсами для всех дуг ХЫпк, для которых контекстный
узел служит
исходным ресурсом.
С помощью оси traverse могут быть выбраны узлы, находящиеся в
другом XML-документе, нежели контекстный узел, т.к. дугами языка XLink
могут быть соединены ресурсы, находящиеся в разных XML-документах.
Предлагаемая ось traverse позволяет приложению осуществлять переходы
по дугам языка XLink полностью прозрачным образом, - независимо от того,
в ссылке какого типа и в каком XML-документе была определена дуга.
Для
тага
доступа
с
осью
traverse
присутствующие
в
шаге
доступа тест узла и предикаты позволяют приложению накладывать
условия на интересующие целевые ресурсы, но не на дуги, по которым
осуществляется переход в данном шаге. Для предоставления приложению
возможности формулирования запросов непосредственно к дугам XLink и
их семантическим параметрам, в работе предлагается представление каждой
дуги XLink в виде информационной единицы информационного пространства
13
X M L , что может рассматриваться как "представление" ('View") в терминах
реляционных баз данных и позволяет формулировать запросы к дуге XLink
единообразно с другими информационными единицами XML-документа. В
полной аналогии с атрибутами и объявлениями пространств имен, в работе
предлагается расширение модели данных XPath наличием ассоциированного
с узлом любого типа набора выходящих из него дуг XLink. Каждая дуга
реализуется в расширенной модели данных XPath узлом типа "элемент" и
является представлением дуги в виде информационной единицы.
Операция получения всех дуг, исходным ресурсом которых служит
контекстный узел, была оформлена в виде новой оси XPath. По аналогии с
англоязычным термином для дуги, введенным в спецификации языка XLink,
данная ось получила название arc:
Определение 2 Ось arc содержит все узлы, являющиеся представлением
в виде информационных единиц всех дуг ХЫпк, для каждой из которых
контекстный узел слуокит исходным ресурсом.
Каждый из узлов, возвращаемый предложенной осью arc, полностью
соответствует модели данных XPath, и потому к этим узлам далее
могут
быть
применены произвольные выражения XPath,
сохранением семантики этих выражений.
с полным
В частности, предикаты могут
быть использованы для фильтрации дуг в соответствии со структурой
представляюнщх их информационных единиц: например, при выборе дуги
с конкретным значением некоторого семантического параметра XLink или
при наложении условий на тип целевого ресурса дуги.
Когда интересующие приложение дуги XLink выбраны, приложению
может потребоваться осуществить по ним переход.
Для перехода к
целевому ресурсу дуги XLink из информационной единицы, представляющей
дугу, в работе предлагается дополнительная ось, названная traverse-arc.
Семантика оси traverse-arc во многом напоминает семантику оси traverse.
14
При реализации предложенного расширения языка запросов были
использованы функциональные методы программирования и формат SXML.
С целью создания единообразной среды для работы приложения как с
SXML-документом, так и с дугой XLink, в реализации последняя также
представлена в формате SXML. Предложенные в работе три дополнительные
оси, обеспечивающие поддержку в XPath языка XLink, были реализованы в
качестве дальнейшего расширения библиотеки SXPath.
В
четвертой главе описываются предлагаемые автором способы
оптимизации запросов, обеспечивающие полиномиальную алгоритмическую
сложность выполнения запросов от размера XML-документов и размера
запросов.
В
первом
разделе
данной
главы
рассматриваются
результаты
экспериментов, которые показывают проблему экспоненциального времени,
в неблагоприятном случае затрачиваемого на вычисление выражений
XPath промышленными процессорами языка
и
XT.
Выделяются
такие
конструкции
XPath
языка
— Saxon,
XPath,
Xalan
недостаточно
предусмотрительный подход к вычислению которых может приводить к
экспоненциальной алгоритмической сложности всего вычислителя языка
XPath от размера вычисляемых выражений:
• На промежуточных шагах доступа количество з^лов в наборе узлов
может возрастать экспоненциально, ввиду возникновения дублирующих
узлов.
• Предикаты, синтаксически вложенные внутрь других предикатов, могут
требовать экспоненциального роста времени вычисления с ростом
глубины вложенности.
В
шести
последующих
разделах
данной
главы
предлагаются
способы оптимизации, обеспечивающие гарантированную полиномиальную
сложность вычисления любого выражения XPath от размера выражения
15
и размера XML-документа.
оптимизации
в
Среди предложенных в работе способов
качестве наиболее значимых для улучшения оценки
сложности можно выделить следующие:
1. Вычисление осей XPath с устранением дублирующих узлов, для всего
входного набора узлов целиком. Предлагаемый подход, лежащий в
основе разработанных автором алгоритмов вычисления осей XPath,
состоит в поддержании порядка документа (document order) в наборе
узлов
во всех подвыражениях
вычисляемого
выражения XPath.
Показывается, что вычисление любой оси языка XPath может быть
организовано с линейной сложностью с сохранением порядка документа
и устранением узлов-дубликатов в результирующем наборе узлов.
2. Ускорение вычисления осей для подмножества практически важных
конструкций языка XPath. В работе выявляются практически важные
конструкции XPath, для которых во входном наборе узлов количество
узлов-предков для каждого узла одинаково.
Для входного набора
узлов, обладающего описанным свойством, в работе предлагаются
более быстрые алгоритмы вычисления осей XPath с устранением
дублирующих узлов и поддержанием порядка документа.
3. Устранение дублирующих узлов в шагах доступа, содержащих
позиционные предикаты. Позиционными предикатами были названы
такие предикаты XPath, результат вычисления которых существенным
образом зависит от контекстной позиции и (или) контекстного размера
узла. В связи с тем, что удаление дублирующих узлов до фильтрации
набора узлов по позиционному предикату нарушает семантику шага
доступа, в работе были предложены такие алгоритмы вычисления осей
XPath, которые обеспечивают сохранение информации о контекстной
позиции и контекстном размере каждого узла
и позволяют по
окончании фильтрации набора узлов по предикатам быстро устранять
16
дублирующие узлы и восстанавливать порядок документа.
Был
разработан алгоритм выявления позиционных предикатов XPath на фазе
статического анализа выражения за счет механизма вывода типов.
4. Предварительное вычисление всех глубоко влоокенных предикатов.
Глубоко вложенными были названы такие предикаты, которые при
прямолинейном способе их вычисления, заданном в спецификации
XPath, требуют своего вычисления потенциально большее количество
раз по сравнению с максимальным количеством различных контекстов.
Автором разработан способ выявления на фазе статического анализа
выражения XPath всех глубоко вложенных предикатов, и предлагается
вычислять такие предикаты в самом начале фазы динамического
вычисления, для всех возможных на данной фазе контекстов. Получение
значения глубоко вложенного
предиката
в
процессе
вычисления
выражения XPath достигается возвращением заранее вычисленного
значения данного предиката для требуемого контекста.
Для
формулирования
утверждения
основной
теоремы
вводятся
определения размера XML-документа и размера выражения XPath.
Определение 3 Размером
XML-документа
назовем полоокительное
число, равное сумме
количества
узлов в документе,
общей длины
текстовых
текстовых
узлах
атрибутов
строк
в
и
значениях
и
максимальной длины квалифицированного имени по ecejn именованным
узлам.
Определение 4 Размером
выражения
языка
XPath
назовем
положительное число, равное сумме количества вершин в абстрактном
синтаксическом дереве этого выражения, соответствующем
грамматике
языка XPath, и максимальной длины строки по всем фигурирующим в
выражении строковым литералам (XPath literals).
17
Теорема 1 Пуст,ъ
даны
произвольный
XML-документ,
имеющий
размер \D\, и произвольное выраокение языка XPath, имеющее размер \Е\.
Предложенные
в
диссертационной
работе
способы
оптимизации
обеспечивают вычисление данного выражения XPath над данным XMLдокументом с алгоритмической сложностью, не превосходящей величины
0{\E\'-\Df) .
Теоремой
1
устанавливается
гарантированная
полиномиальная
алгоритмическая сложность вычисления любого выражения XPath над
любым
XML-документом,
что
достигается
благодаря
предложенным
способам оптимизации.
Следствие 1 Полученная в теореме 1 гарантированная верхняя оценка
алгоритмической сложности
может
быть значительно улучшена для
широких классов практически важных выражений языка XPath.
Так, если выражение XPath является путем доступа, не содержащим
предикатов, то предлагаемые в работе способы оптимизации обеспечивают
линейную алгоритмическую сложность вычисления данного выражения от
размера XML-документа и от размера выраокения:
от-т.
Если выраокение XPath является
позиционных предикатов,
путем
доступа, не содероюащим
операций обобщенного сравнения и вызовов
функции concat, строковые литералы в котором имеют ограниченную
длину, то алгоритмическая сложность вычисления такого выраокения:
om-\D?).
Полученные
в
теореме
1
результаты
естественным
образом
распространяются на случай формулирования запросов к совокупности
ХМЬ-документов, связанных ссылками языка XLink.
Верхняя оценка
18
сложности, утверждаемая теоремой, в этом случае также справедлива,
с той модификацией, что в качестве величины \D\ берется суммарный
размер XML-доку ментов, на которые может быть осуществлен переход по
дугам языка XLink в процессе выполнения запроса, и размер этих дуг,
представленных в виде информационных единиц.
Рассуждения теоремы 1 верны и в
функции,
случае
выступающей в роли тага доступа,
наличия в запросе
если семантика этой
функции соответствует общей идее предлагаемого подхода, а именно, она
обеспечивает поддержание порядка документа и отсутствие дублирующих
узлов.
При естественном требовании полиномиальной алгоритмической
сложности функции, выступающей в роли шага доступа, рассуждения
теоремы 1 позволяют гарантировать полиномиальную сложность выполнения
всего запроса.
Описываются детали сделанной реализации прототипа среды разработки
XML-приложений функциональными методами, обеспечивающей единое
представление XML-данных
в
формате S X M L
и единую
парадигму
программирования и включающей в себя реализацию созданного в работе
языка запросов и предложенных способов оптимизации выполнения запросов.
В последнем разделе четвертой главы рассматриваются результаты
экспериментов, произведенных в отношении сделанной в работе реализации.
Результаты экспериментов показывают, что сделанная в работе реализация
языка запросов функциональными методами в сравнении с промышленными
процессорами языка XPath Saxon, Xalan и X T обеспечивает полиномиальное
время выполнения и в целом не проигрывает по производительности
процессорам XPath также и на множестве практически важных выражений
XPath.
В заключении диссертационной работы перечисляются ее основные
результаты.
19
Основные результаты работы
В работе были получены следующие основные результаты:
• Создан язык запросов к XML-данным, обладающий следующими
свойствами:
— язык запросов обеспечивает тесную интеграцию языка адресации
частей
XML-документа
XPath
с
функциональным
языком
программирования общего назначения Scheme;
- язык запросов обеспечивает средство формулирования запросов к
совокупности XML-документов, семантически связанных ссылками
языка XLink.
• Разработаны
методы
оптимизации
выполнения
запросов,
гарантирующие полиномиальную сложность от размера запроса и
размера документа.
• Реализован
прототип
среды
разработки
XML-приложений,
поддерживающей единую модель данных и позволяющей облегчить
и ускорить процесс создания XML-приложений.
20
По теме диссертации опубликованы следующие работы
1. Лизоркин Д.А.,
Лисовский К.Ю.
SXML:
XML-документ
как S-
выражение // Электронные библиотеки. - М.: ИРИО, 2003. - Т. 6,
вып. 2. - с. 9-17. - ISSN 1562-5419 = Russian digital libraries journal.
http://www.elbib.ru/index.phtml?page=elbib/ru8/journal/2003/part2/LK
2. Лизоркин Д.А., Лисовский К.Ю. Пространства имен в X M L и S X M L //
Электронные библиотеки. - М.: ИРИО, 2003. - Т. 6, вып. 3. - с. 42-52. ISSN 1562-5419 — Russian digital libraries journal.
http://www.elbib.ru/index.phtml?page=elbib/ru8/journal/2003/part3/LL
3. Лизоркин Д.А., Лисовский К Ю. Язык X M L Path (XPath) и его
функциональная реализация SXPath // Электронные библиотеки. - М.:
ИРИО, 2003. - Т. 6, вып. 4. - с. 34-46. - ISSN 1562-5419 = Russian digital
libraries journal.
http://www.elbib.ru/index.phtml?page=elbib/rus/journal/2003/part4/LL
4. Лизоркин Д.А., Лисовский К.Ю. Языки XSLT и XLink и их реализация
функциональными методами // Электронные библиотеки. - М.: ИРИО,
2003. - Т. 6, вып. 5. - с. 36-48. - ISSN 1562-5419 = Russian digital libraries
journal.
http://www.elbib.ru/index.phtml?page=elbib/rus/journal/2003/part5/LL
5. Grinev M., Lizorkin D. XQuery Function Inlining for Optimizing XQuery
Queries : Prac. 8th East-European conf. on Advances in Databases and
Information Systems (ADBIS'2004), Budapest, 22-25 Sep., 2004. - ADBIS'04
Proceedings / Bencziir A., Demetrovics J . (eds.). - Budapest: C A R I , 2004. 260 pp. - pp. 32-47. - ISBN 963 311 358 X.
http;//www.sztaki.hu/conferences/ADBIS/4-Lizorkin.pdf
6. Лизоркин Д.А. Оптимизация вычисления обратных осей языка X M L
Path при его реализации функциональными методами // Сборник трудов
21
Института системного программирования Р А Н / Под ред. чл.-корр. РАН
Иванникова В.П. - М.: ИСП РАН, 2004. - Т. 8, ч. 2. - 214 с. - с. 93-119. I S B N 5-89823-026-2.
http://modis.ispra8.ru/Lizorkin/Publications/xpath-context.ps
7. Лизоркин Д.А., Лисовский К.Ю. Реализация XLink - языка ссылок
X M L - с помощью фз^нкциснальных методов // Программирование. М.: Наука, 2005. - N 1. - С. 52-72. - ISSN 0361-7688 = Programming and
computer software.
8. Лизоркин Д.А.
Язык
запросов к совокупности XML-документов,
соединенных при помощи ссылок языка XLink // Программирование. М : Наука, 2005. - N 3. - ISSN 0361-7688 = Programming and computer
software.
Напечатано с готового оригинал-макета
Издательство 0 0 0 " М А К С Пресс"
Лицензия ВДЫ 00510 от 01.12.99 г.
Подписано к печати 05.10.2005 г.
Формат 60x90 1/16. Усл.печ.л. 1,5. Тираж 100 экз. Заказ 601.
Тел. 939-3890. Тел./факс 939-3891.
119992, ГСП-2, Москва, Легашские горы, М Г У им. М В. Ломоносова,
2-й учебный корпус, 627 к
«16454
РНБ Русский фонд
2006-4
19738
Документ
Категория
Без категории
Просмотров
0
Размер файла
803 Кб
Теги
bd000100879
1/--страниц
Пожаловаться на содержимое документа