Диссертация на соискание ученой степени кандидата




PDF просмотр
НазваниеДиссертация на соискание ученой степени кандидата
Дата конвертации17.11.2012
Размер1.12 Mb.
ТипДиссертация
Московский государственный университет
имени М.В. Ломоносова
На правах рукописи
ЛИЗОРКИН ДМИТРИЙ АЛЕКСЕЕВИЧ
ФУНКЦИОНАЛЬНЫЕ МЕТОДЫ
ОБРАБОТКИ XML-ДАННЫХ
05.13.11  математическое и программное обеспечение
вычислительных машин, комплексов и компьютерных сетей
ДИССЕРТАЦИЯ
на соискание ученой степени кандидата
физико-математических наук
Научный руководитель
член-корреспондент РАН, профессор
Иванников Виктор Петрович
Москва 2005

P
Содержание
Введение
5
1 Платформа XML и функциональные методы
10
IFI Платформа €wv F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F
IH
IFIFI Расширяемый язык разметки ! €wv F F F F F F F F F F F F F F F F F F F F
IH
IFIFP Пространства имен в €wv F F F F F F F F F F F F F F F F F F F F F F F F F F
IP
IFIFQ Язык €wv Ђ—th @€Ђ—thA F F F F F F F F F F F F F F F F F F F F F F F F F F F
IS
IFIFR Язык ссылок €wv @€vinkA F F F F F F F F F F F F F F F F F F F F F F F F F F
PH
IFP Обработка €wvEданных и проблема потери соответствия F F F F F F F F F F F F
PQ
IFQ ѓ€wvX €wvEдокумент как ѓEвыражение F F F F F F F F F F F F F F F F F F F F F F
PU
IFQFI €wvD информационное пространство €wv и ѓ€wv F F F F F F F F F F F
PU
IFQFP Спецификация ѓ€wv F F F F F F F F F F F F F F F F F F F F F F F F F F F F F
PW
IFQFQ Пространства имен в ѓ€wv F F F F F F F F F F F F F F F F F F F F F F F F F
QP
IFQFR Свойства ѓ€wv F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F
QR
IFR Библиотека ѓ€Ђ—thX
реализация некоторых конструкций языка €Ђ—th
функциональными методами F F F F F F F F F F F F F F F F F F F F F F F F F F F F F
QU
IFRFI Низкоуровневые функции ѓ€Ђ—th F F F F F F F F F F F F F F F F F F F F F F
QU
IFRFP Высокоуровневая функция ѓ€Ђ—th F F F F F F F F F F F F F F F F F F F F F
RI
2 Интеграция XPath с языком функционального программирования и язык
запросов к XML-данным
43
PFI Статический анализ и динамическое вычисление выражений €Ђ—th F F F F F F
RQ
PFP Расширение набора примитивов библиотеки ѓ€Ђ—th F F F F F F F F F F F F F F F
SH
PFQ Отображение выражения €Ђ—th на суперпозицию функций F F F F F F F F F F F
SP
PFQFI Лексический и синтаксический анализ выражений €Ђ—th F F F F F F F F
SQ
PFQFP Грамматическое правило выражение пути F F F F F F F F F F F F F F F F
SS
PFQFQ Грамматическое правило абсолютный путь доступа F F F F F F F F F F
SU
PFR Расширение €Ђ—th за счет интеграции со ѓ™heme F F F F F F F F F F F F F F F F F
SV
PFS ѓ€Ђ—th как язык запросов F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F
TP

Q
PFT Абстрактное синтаксическое дерево выражения €Ђ—th в виде ѓ€wv F F F F F F
TS
3 Расширение языка запросов для обработки совокупностей XML-
документов, связанных ссылками XLink
68
QFI Мотивация поддержки €vink в языке запросов F F F F F F F F F F F F F F F F F F
TV
QFP Пример связанных €wvEдокументов F F F F F F F F F F F F F F F F F F F F F F F F
TW
QFQ Родственные работы в области обработки связанных €wvEдокументов F F F F
UP
QFQFI €Ѓuery F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F
UP
QFQFP Браузеры с поддержкой €vink F F F F F F F F F F F F F F F F F F F F F F F F
UQ
QFQFQ Интерфейсы прикладного программирования F F F F F F F F F F F F F F F
UQ
QFR Расширение €Ђ—th переходами по дугам языка €vink F F F F F F F F F F F F F F
UR
QFS Адресация к дугам языка €vink F F F F F F F F F F F F F F F F F F F F F F F F F F F
UV
QFSFI Дуга €vink в виде информационной единицы F F F F F F F F F F F F F F F
UW
QFSFP Оси для адресации к дугам €vink F F F F F F F F F F F F F F F F F F F F F F
VS
QFT Реализация F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F
VV
QFTFI Разбор разметки языка €vink F F F F F F F F F F F F F F F F F F F F F F F F
VV
QFTFP Реализация предложенных осей как расширение библиотеки ѓ€Ђ—th F F
WH
QFU Ограничения предлагаемого языка запросов F F F F F F F F F F F F F F F F F F F F
WQ
4 Оптимизация выполнения запросов
95
RFI Эксперименты в отношении существующих промышленных реализаций €Ђ—th
WS
RFIFI Эксперимент IX дублирующие узлы F F F F F F F F F F F F F F F F F F F F F
WT
RFIFP Эксперимент PX глубоко вложенные предикаты F F F F F F F F F F F F F F IHH
RFP Оптимизация вычисления обратных осей €Ђ—th ввиду отсутствия в ѓ€wv
указателей на родительские узлы F F F F F F F F F F F F F F F F F F F F F F F F F F IHI
RFPFI Родственные работы в области вычисления обратных осей €Ђ—th F F F IHR
RFPFP Иллюстрация предлагаемого подхода F F F F F F F F F F F F F F F F F F F F IHS
RFPFQ Алгоритм вычисления выражений €Ђ—thD содержащих обратные оси F IHT
RFPFR Свойства предложенного алгоритма F F F F F F F F F F F F F F F F F F F F F IIT
RFPFS Ограничения алгоритма F F F F F F F F F F F F F F F F F F F F F F F F F F F IPH
RFPFT Эксперименты F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F IPI
RFQ Удаление дублирующих узлов при вычислении осей €Ђ—th F F F F F F F F F F F IPR
RFQFI Предварительные соглашения F F F F F F F F F F F F F F F F F F F F F F F F IPR
RFQFP Оси —n™estor и —n™estorEorEself F F F F F F F F F F F F F F F F F F F F F F F F IPT
RFQFQ Ось —ttri?ute F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F IQQ
RFQFR Ось ™hild F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F IQR
RFQFS Оси des™end—nt и des™end—ntEorEself F F F F F F F F F F F F F F F F F F F F F IQW
RFQFT Оси following и pre™eding F F F F F F F F F F F F F F F F F F F F F F F F F F F IRR

R
RFQFU Оси followingEsi?ling и pre™edingEsi?ling F F F F F F F F F F F F F F F F F F F IRU
RFQFV Ось n—mesp—™e F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F ISP
RFQFW Ось p—rent F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F ISQ
RFQFIH Ось self F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F ISU
RFR Вычисление осей €Ђ—th для случая расположения узлов на одном уровне F F F ISV
RFRFI Оси ™hildD des™end—nt и des™end—ntEorEself F F F F F F F F F F F F F F F F F F ITI
RFRFP Оси following и pre™eding F F F F F F F F F F F F F F F F F F F F F F F F F F F ITQ
RFRFQ Оси followingEsi?ling и pre™edingEsi?ling F F F F F F F F F F F F F F F F F F F ITR
RFRFR Ось p—rent F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F ITT
RFS Вычисления осей €Ђ—th в присутствии в шаге доступа позиционных предикатовITU
RFSFI Выявление позиционных предикатов с помощью статического вывода
типов F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F IUI
RFT Оптимизация вычисления глубоко вложенных предикатов F F F F F F F F F F F F IUP
RFU Оптимизация вычисления операций обобщенного сравнения F F F F F F F F F F F IUU
RFUFI Вычисление обобщенного сравнения сортировкой слиянием F F F F F F F IUV
RFUFP Вычисление обобщенного сравнения поразрядной сортировкой F F F F F IVH
RFV Верхняя оценка сложности выполнения запросов ввиду предложенных
способов оптимизации F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F IVS
RFW Детали реализации F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F PHR
RFIH Эксперименты F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F PHW
RFIHFI Эксперимент IX устранение дублирующих узлов F F F F F F F F F F F F F PHW
RFIHFP Эксперимент PX глубоко вложенные предикаты F F F F F F F F F F F F F F PII
RFIHFQ Сравнительные тесты производительности F F F F F F F F F F F F F F F F F PIQ
Заключение
218
Список литературы
219
Приложение: тесты производительности XPath
227

S
Введение
Актуальность темы
В настоящее время язык €wv используется как основное средство для представления
слабоструктурированных данныхF
Для обработки €wvEданных могут использоваться языки платформы €wvD такие как
€Ђ—thD €Ѓuery и €ѓv„F Поскольку большинство языков платформы €wv не являются
языками программирования общего назначенияD при реализации €wvEприложений они
обычно используются совместно с некоторыми традиционными языками программированияF
Комбинирование двух различных по своей природе языков @напримерD €Ђ—th и t—v—AD "
использующих разные модели данных и разные парадигмы программированияD " приводит
к проблемеD известной как потеря соответствия @imped—n™e mism—t™hAF
Для €wvE
приложений необходим языкD который бы по своей природе понимал структуры данных €wv
и предоставлял оптимизированные алгоритмы для обработки €wvEданныхF
Функциональные методы иD в частностиD язык программирования ѓ™heme семейства
visp являются привлекательными для преодоления проблемы потери соответствия в
контексте обработки €wvEданныхD что мотивируется следующими свойствами языка ѓ™hemeX
• Естественным представлением вложенных элементов €wv являются вложенные
спискиD и язык ѓ™heme использует вложенные списки для представления и своих
данныхD и своего кодаF
• Язык ѓ™heme является функциональным языкомD как и большинство языков
платформы €wv @€ѓv„D €ЃueryAF
Разработка и оптимизация алгоритмов для обработки €wvEданных функциональными
методами и интеграция ѓ™heme с языками платформы €wv и определяют актуальность
диссертационной работыF

T
Цель и задачи работы
Целью диссертационной работы является создание среды разработки €wvEприложенийD
поддерживающей единую модель данных и позволяющей облегчить и ускорить процесс
создания €wvEприложенийF
Для достижения основной цели работы поставлены следующие задачиX
• создать язык запросов к €wvEданнымD обладающий следующими свойствамиX
 язык запросов должен обеспечивать тесную интеграцию языка адресации частей
€wvEдокумента €Ђ—th с функциональным языком программирования общего
назначения ѓ™hemeY
 язык запросов должен обеспечивать средство формулирования запросов к
совокупности €wvEдокументовD семантически связанных при помощи €vink !
языка ссылок €wvY
• разработать методы оптимизации выполнения запросов с целью достижения
гарантированной полиномиальной алгоритмической сложностиF
Основные результаты работы
В работе были получены следующие основные результатыX
• Создан язык запросов к €wvEданнымD обладающий следующими свойствамиX
 язык запросов обеспечивает тесную интеграцию языка адресации частей
€wvEдокумента €Ђ—th с функциональным языком программирования общего
назначения ѓ™hemeY
 язык запросов обеспечивает средство формулирования запросов к совокупности
€wvEдокументовD семантически связанных ссылками языка €vinkF
• Разработаны
методы
оптимизации
выполнения
запросовD
гарантирующие
полиномиальную сложность от размера запроса и размера документаF
• Реализован прототип среды разработки €wvEприложенийD поддерживающей единую
модель данных и позволяющей облегчить и ускорить процесс создания €wvE
приложенийF

U
Научная новизна работы
Научной новизной обладают следующие результаты работыX
• преодолена проблема потери соответствия при интеграции языка адресации частей
€wvEдокумента €Ђ—th с языком программирования общего назначенияY
• разработан язык запросов к совокупности €wvEдокументовD связанных между собой
при помощи €vink ! языка ссылок €wvY
• разработан оригинальный метод устранения дублирующих узлов в процессе
вычисления выражений языка €Ђ—thD основанный на поддержании порядка документа
при вычислении каждой конструкции языка €Ђ—thF
Практическая значимость
Достигнутая интеграция языка адресации частей €wvEдокументов €Ђ—th с языком
функционального программирования ѓ™heme может быть использована для достижения
большей гибкости и расширяемости при формулировании критериев выборки €wvEданныхF
Разработанный язык запросов к совокупности €wvEдокументовD связанных ссылками
языка €vinkD может быть использован для повышения наглядности представления объектов
прикладной предметной области на €wv и упрощения задач обработки €wvEданных для
приложенияF
Разработанные способы оптимизации выполнения запросов могут быть использованы
для повышения эффективности процессоров языков €Ђ—th и €Ѓuery и вычислителей
запросов в €wvEСУБДF
Реализованный прототип среды разработки €wvEприложений функциональными
методами был использован при создании в Институте системного программирования РАН
промышленной системы виртуальной интеграции fizЃuery и €wvEСУБД ѓedn—F
Доклады и публикации
Основные положения работы докладывались на восьмой международной конференции edE
v—n™es in h—t—?—ses —nd snform—tion ѓystems @ehfsѓA @PHHR гAD на восьмидесятом и девяносто
восьмом семинарах Московской Секции egw ѓsqwyh @PHHP и PHHS ггA и на семинаре
Современные сетевые технологии @PHHS гAF
По материалам диссертации опубликовано восемь работ ‘ID PD QD RD SD TD UD V“F

V
Структура и объем диссертации
Работа состоит из введенияD четырех главD заключения и списка литературыF Общий объем
диссертации составляет PPT страницF Список литературы содержит UI наименованиеF
Краткое содержание работы
Первая глава является обзорной и содержит изложение методов и средствD которые лежат
в основе разработокD описанных в последующих трех главахF В данной главе дается обзор
основных понятий платформы €wvD необходимых для изложения последующего материалаD
рассматриваются существующие подходы к обработке €wvEданных и обсуждается присущая
существующим подходам проблема потери соответствияF
Обсуждаются преимущества
функциональных методов в контексте обработки €wvEданных как средства преодоления
проблемы потери соответствияF
Описывается формат ѓ€wv " представление €wvE
документов в виде вложенных списков " и его свойстваF Обсуждаются идеи вычисления
путей доступа языка адресации частей €wvEдокумента €Ђ—th функциональными методамиD
над документами формата ѓ€wvF
Вторая глава посвящена описанию разработанного автором подхода к интеграции языка
€Ђ—th с языком программирования общего назначения ѓ™heme на уровне представления
данных и вычислительной парадигмыF
Описываются разработанные автором способы
отображения фаз статического анализа и динамического вычисления выражения €Ђ—th
на вызов функции высокого порядка языка функционального программирования и
отображения произвольного выражения €Ђ—th на суперпозицию функцийD обеспечивающих
обработку списковых структур данныхF Предлагаются способы интеграции в едином запросе
выражений языка €Ђ—th и пользовательских функций языка ѓ™heme и иллюстрируется
достигаемая в результате предложенной интеграции функциональность языка запросов к
данным формата ѓ€wvF
Третья глава посвящена описанию разработанного автором расширения языка
запросовD которое предоставляет приложению возможность формулирования запросов к
совокупности €wvEдокументовD семантически связанных ссылками €vink ! языка ссылок
€wvD ! и осуществления переходов по дугамD определяемым этими ссылкамиF Практическая
потребность расширения языка запросов поддержкой ссылок €vink обосновывается
иллюстративными примерамиF Описывается предлагаемое расширение языка запросовD
достигаемое за счет добавления трех новых осей к языку €Ђ—th и добавления к узлу
каждого типаD представленного в модели данных языка €Ђ—thD по одному дополнительному
свойствуF Рассматриваются детали реализации предлагаемого расширения языка запросов
функциональными методамиF

W
Четвертая глава посвящена описанию предлагаемых автором способов оптимизации
выполнения запросовF В данной главе исследуется проблема экспоненциального времениD в
неблагоприятном случае затрачиваемого рядом существующих промышленных реализаций
языка €Ђ—th на вычисление выражений €Ђ—thD и выявляются конструкции языка €Ђ—thD
недостаточно предусмотрительный подход к вычислению которых может приводить к
экспоненциальной алгоритмической сложности всего вычислителя запросовF Предлагаются
способы оптимизации выполнения запросов и доказываетсяD что данные способы
оптимизации обеспечивают полиномиальную сложность выполнения запросов от размера
€wvEдокументов и размера запросовF Обсуждаются детали реализации функциональными
методами предложенных способов оптимизации и приводятся результаты экспериментовD
произведенных в отношении сделанной реализацииF
В заключении перечисляются основные результаты работыF

IH
Глава 1
Платформа XML и функциональные
методы
Настоящая глава является обзорной и содержит изложение методов и средствD которые лежат
в основе разработокD описанных в последующих трех главахF
1.1 Платформа XML
В данном разделе дается обзор основных понятий платформы €wvD необходимых для
изложения последующего материалаF
1.1.1 Расширяемый язык разметки  XML
Расширяемый язык разметки @ixtensi?le w—rkup v—ngu—geD далее €wvA является
подмножеством стандартного обобщенного языка разметки @ѓt—nd—rd qener—lized w—rkup
v—ngu—geD ѓqwvA ‘W“F Целью языка €wvD разработанного консорциумом ‡QgD служит
предоставление таких же широких возможностей по передаче и обработке документов €wv
в среде Веб @‡e?AD как и для документов r„wvD а также обеспечение взаимодействия €wv
как с ѓqwvD так и с r„wv ‘IH“F
Стандартный обобщенный язык разметки ѓqwv имеет ряд успешных внедрений в
больших и сложных приложениях издательского делаF Однако язык ѓqwv не нашел
применения в масштабах Веб @по крайней мереD до середины IWWT гFA1D несмотря на тот фактD
что о гипертекстовом языке разметки r„wv было заявлено как о конкретном варианте
применения ѓqwvF
Язык €wv является попыткой обобщения наиболее важных преимуществ и наиболее
широко используемых особенностей ѓqwv в компактный языкD специально предназначенный
1fr—y „F „he ennot—ted €wv ѓpe™i(™—tionF ! IWWVF ! httpXGGwwwFxmlF™omG—xmlG—xmlFhtml

II
для передачи и обработки данных в Веб2F
€wvEдокумент определяется в спецификации языка €wv как объект данныхD
который является правильно сформированным @wellEformedA в соответствии с требованиями
спецификации €wv ‘IH“F
Каждый €wvEдокумент имеет логическую и физическую
структуруF На уровне физической структуры документ состоит из единицD называемых
сущностямиD которые могут ссылаться на другие сущности и тем самым вызывать их
включение в документF На уровне логической структуры документ состоит из объявленийD
элементовD комментариев и инструкций обработкиD каждые из которых определяются при
помощи специальной разметки ‘IH“F
Относительно своей внутренней структуры €wvEдокументы могут быть нестрого
классифицированы на ориентированные на данные @d—t—EorientedA и ориентированные на
документ @do™umentEorientedAX
• ДокументыD ориентированные на данныеD " это такие документыD в которых
основным предназначением €wv является его использование в качестве формата для
передачи данныхF Примерами €wvEдокументовD ориентированных на данныеD служат
заказыD расписания полетовD научные данныеD котировки акций и тFпF ДокументыD
ориентированные на данныеD характеризуются достаточно регулярной структуройD
мелкой гранулированностью данных и незначительной долей или даже полным
отсутствием смешанного содержимого @mixed ™ontentA ‘II“F
• ДокументыD ориентированные на документD " это такие документыD которые
обычно предназначены для их обработки человекомF
Примерами служат книгиD
электронные письмаD рекламные объявления и большинство €wvEдокументовD
составленных вручнуюF ДокументыD ориентированные на документD характеризуются
менее регулярной или нерегулярной структуройD более крупной гранулированностью
данных и большим количеством смешанного содержимого ‘II“F
Относительный
порядок элементов и текстовых данных в документеD ориентированном на документD
практически всегда является значимымF
На рисF IFI в сравнении показана типичная внутренняя структура двух €wvEдокументовX
ориентированного на данные и ориентированного на документY примеры документов взяты
из спецификации ‘IP“F
Обработка €wvEданных включает в себяD с одной стороныD выборку из большого
€wvEдокумента некоторых интересующих приложение частей в соответствии с заданными
критериямиF Помимо выборкиD задачи обработки €wvEданных могут включать в себя
конструирование документов на €wv и их последующее преобразование в другие форматыD
напримерD в r„wv ‘IQ“F
2 fr—y „F „he ennot—ted €wv ѓpe™i(™—tionF

IP

1999-01-21
date='1999-03-23'>
1999-01-25
Paul V. Biron

Ashok Malhotra
Ashok Malhotra
Latest draft
Microsoft Ave.

Hawthorne
We need to discuss the latest
NY
draft immediately.
10532-0000
Either email me at 

mailto:paul.v.biron@kp.org
555-1234
or call 
555-9876

555-4321

Похожие:

Диссертация на соискание ученой степени кандидата iconДиссертация на соискание ученой степени кандидата 

Диссертация на соискание ученой степени кандидата iconДиссертация на соискание ученой степени кандидата физико

Диссертация на соискание ученой степени кандидата icon Диссертация на соискание ученой степени кандидата технических наук

Диссертация на соискание ученой степени кандидата icon  Диссертация на соискание ученой степени кандидата юридических наук 

Диссертация на соискание ученой степени кандидата iconДиссертация на соискание ученой степени кандидата педагогических наук
Социально-нравственное воспитание подростков в условиях молодежного объединения Новая
Диссертация на соискание ученой степени кандидата icon  Диссертация на соискание ученой степени кандидата 
    Теоретические  основы  изучения  речевого  жанра  «портрет  человека» в средствах массовой информации
Диссертация на соискание ученой степени кандидата icon  Диссертация на соискание ученой степени кандидата филологических наук 
Актуализация  употребления  аффиксоида  super  в  русском  языке  конца  XX  века  
Диссертация на соискание ученой степени кандидата iconДиссертация на соискание ученой степени

Диссертация на соискание ученой степени кандидата icon  Диссертация на соискание ученой степени 

Диссертация на соискание ученой степени кандидата icon  Диссертация на соискание ученой степени 
Введение                                                                                                            3 
Разместите кнопку на своём сайте:
TopReferat


База данных защищена авторским правом ©topreferat.znate.ru 2012
обратиться к администрации
ТопРеферат
Главная страница