Функциональные методы обработки XML-данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Лизоркин, Дмитрий Алексеевич

• Лизоркин, Дмитрий Алексеевич
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Лизоркин, Дмитрий Алексеевич

Введение

1 Платформа XML и функциональные методы

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

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

1.1.2 Пространства имен n XML.

1.1.3 Язык XML Path (XPath).

1.1.4 Язык ссылок XML (XLink).

1.2 Обработка XML-даппых п проблема потери соответствия.

1.3 SXML: XML-документ как S-выражепие.

1.3.1 XML, информационное пространство XML н SXML

1.3.2 Спецификация SXML.

1.3.3 Пространства имен в SXML.

1.3.4 Свойства SXML.

1.4 Библиотека SXPath: реализация некоторых конструкций языка XPath функциональными методами.

1.4.1 Низкоуровневые функции SXPath.

1.4.2 Высокоуровневая функция SXPath.

2 Интеграция XPath с языком функционального программирования и язык запросов к XML-данным

2.1 Статический анализ и динамическое вычисление выражений XPath.

2.2 Расширение набора примитивов библиотеки SXPath.

2.3 Отображение выражения XPath на суперпозицию функций.

2.3.1 Лексический и синтаксический анализ выражений XPath.

2.3.2 Грамматическое правило "выражение пути".

2.3.3 Грамматическое правило "абсолютный путь доступа"

2.4 Расширение XPath за счет интеграции со Scheme.

2.5 SXPath как язык запросов.G

2.С Абстрактное синтаксическое дерево ныражепия XPatli и виде SXML.Со

3 Расширение языка запросов для обработки совокупностей XML-докумеитоп, связанных ссылками XLink С

3.1 Мотивация поддержки XLink в языке запросов.С

3.2 Пример связанных XML-докумептов.G

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

3.3.1 XQnery.

3.3.2 Браузеры с поддержкой XLink.

3.3.3 Интерфейсы прикладного программирования.

3.4 Расширение XPatli переходами по дугам языка XLink.

3.5 Адресация к дугам языка XLink.

3.5.1 Дуга XLink в виде информационной единицы.

3.5.2 Оси для адресации к дугам XLink.

3.G Реализация.

3.G.1 Разбор разметки языка XLink.

З.С.2 Реализация предложенных осей как расширение библиотеки SXPath

3.7 Ограничения предлагаемого языка запросов.

4 Оптимизация выполнения запросов

4.1 Эксперименты в отношении существующих промышленных реализаций XPatli

4.1.1 Эксперимент 1: дублирующие узлы.9G

4.1.2 Эксперимент 2: глубоко вложенные предикаты.

4.2 Оптимизация вычисления обратных осей XPatli ввиду отсутствия в SXML указателей па родительские узлы.

4.2.1 Родственные работы и области вычисления обратных осей XPatli

4.2.2 Иллюстрация предлагаемого подхода.

4.2.3 Алгоритм вычисления выражений XPatli, содержащих обратные осп . 10G

4.2.4 Свойства предложенного алгоритма.11С

4.2.5 Ограничения алгоритма

4.2.С Эксперименты.

4.3 Удаление дублирующих узлов при вычислении осей XPath.

4.3.1 Предварительные соглашения.

4.3.2 Осп ancestor и ancestor-or-self.12С

4.3.3 Ось attribute.

4.3.4 Ось child

4.3.5 Оси descendant п desceiiclant-or-self.

4.3.С Оси following н preceding.

4.3.7 Оси following-sibling и preceding-sibling.

4.3.8 Ось namcspace.

4.3.9 Ось parent

4.3.10 Ось self.

4.4 Вычисление осей XPath для случая расположения узлов на одном уроине

4.4.1 Осп child, descendant и descendant-or-self.1G

4.4.2 Оси following н preceding.1G

4.4.3 Оси following-sibling и preceding-sibling.1G

4.4.4 Ось parent .1GG

4.5 Вычисления осей XPath и присутствии в шаге доступа позиционных предикатов 1G7 4.5.1 Выявление позиционных предикатои с помощью статического вывода типов.

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

4.7 Оптимизация вычисления операций обобщенного сравнения.

4.7.1 Вычисление обобщенного сравнения сортировкой слиянием.

4.7.2 Вычисление обобщенного сравнения поразрядной сортировкой.

4.8 Верхняя оценка сложности выполнения запросов ввиду предложенных способов оптимизации.

4.9 Детали реализации

4.10 Эксперименты.

4.10.1 Эксперимент 1: устранение дублирующих узлов

4.10.2 Эксперимент 2: глубоко вложенные предикаты.

4.10.3 Сравнительные тесты производительности.

Введение диссертации (часть автореферата) на тему «Функциональные методы обработки XML-данных»

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

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

Для обработки XML-даппых могут использоваться языки платформы XML, такие как XPath, XQuery и XSLT. Поскольку большинство языков платформы XML не являются языками программирования общего назначения, при реализации XML-приложений они обычно используются совместно с некоторыми традиционными языками программирования. Комбинирование двух различных но своей природе языков (например, XPath и Java), — использующих разные модели данных и разные парадигмы программирования, — приводит к проблеме, известной как потеря соответствия (impedance mismatch). Для XML-приложений необходим язык, который бы по своей природе понимал структуры данных XML и предоставлял оптимизированные алгоритмы для обработки XML-даппых.

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

• Естественным представлением вложенных элементов XML являются вложенные списки, п язык Scheme использует вложенные списки для представления и своих данных, и своего кода.

• Язык Scheme является функциональным языком, как и большинство языков платформы XML (XSLT, XQuery).

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

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

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

Для достижения основной цели работы поставлены следующие задачи:

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

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

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

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

• Создан язык запросов к XML-данпым, обладающий следующими свойствами: язык запросов обеспечивает тесную интеграцию языка адресации частей XML-документа XPath с функциональным языком программирования общего назначения Scheme; язык запросов обеспечивает средство формулирования запросов к совокупности XML-документов, семантически связанных ссылками языка XLink.

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

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

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

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

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

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

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

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

Достигнутая интеграция языка адресации частей XML-документов XPath с языком функционального программирования Schemc может быть использована для достижения большей гибкости и расширяемости при формулировании критериев выборки XML-данных.

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

Разработанные способы оптимизации выполнения запросов могут быть использованы для повышения эффективности процессоров языков XPath и XQnery и вычислителей запросов в XML-СУБД.

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

Доклады и публикации

Основные положения работы докладывались па восьмой международной конференции "Advances in Databases and Information Systems" (ADBIS) (2001 г), па восьмидесятом и девяносто восьмом семинарах Московской Секции ACM SIGMOD (2002 и 2005 гг) и па семинаре 'Современные сетевые технологии" (2005 г).

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

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Лизоркин, Дмитрий Алексеевич

Заключение

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

• Создан язык запросов к XML-данпым, обладающий следующими свойствами: язык запросов обеспечивает тесную интеграцию языка адресации частей XML-документа XPath с функциональным языком программирования общего назначения Scheme; язык запросов обеспечивает средство формулирования запросов к совокупности XML-документов, семантически связанных ссылками языка XLink.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Лизоркин, Дмитрий Алексеевич, 2005 год

1. Лизоркин Д.А., Лисовский К.Ю. Пространства имен в XML и SXML // Электронные библиотеки. М.: ИРИО, 2003. - Т. 6, вып. 3. - с. 42-52. - ISSN 1562-5419 = Russian digital libraries journal.http://www.elbib.ru/index.phtml?page=elbib/rus/journal/2003/part3/LL

2. Лизоркин Д.Л., Лисовский К.Ю. Реализация XLink языка ссылок XML - с помощью функциональных методов // Программирование. - М.: Наука, 2005. - N 1. - С. 52-72. -ISSN 03G1-7C88 = Programming and computer software.

3. Когаловский M.P. Глоссарий по технологиям платформы XML. М.: ИРИО, 2003. http://www.dbib.ru/index.phtml?page=elbib/rus/methodology/xmlbase/glossaryXML

4. Консорциум W3C. Расширяемый язык разметки (XML) 1.0 = Extensible Markup Language (XML) 1.0 : Рекомендация Консорциума W3C. 2-я ред. / Под ред. Bray Т. и др.; пер. с апгл. Усмаиов Р. - 2000, G окт.littp: / / www.w3.org/XML/Core/Translations

5. Kiselyov O., Lisovsky K. XML, XPath, XSLT Implementation as SXML, SXPath and SXSLT : Proc. International Lisp Conf. ILC'2002, San Francisco, 27-31 Oct., 2002. http://www.okmij.org/ftp/papers/SXs.pdf

6. The World Wide Web Consortium (W3C). Namespaces in XML : W3C recommendation / Bray T. et al. (cds.). 1999, 14 Jan.http://www.w3.org/TR/REC-xml-names/

7. Лизоркин Д.Л., Лисовский К.Ю. XML и (функциональное программирование : Методические материалы по стандартам платформы XML / Когалоиский М.Р. М.: IIPIIO, 2003.http://www.elbib.ru/index.phtml?page=elbib/rus/methodology/xmlbase/xmlfp

8. Kokkelink S., Schwiinzl R. Expressing Qualified Dublin Core in RDF/XML : DCMI proposed recommendation / Dublin Core Metadata Initiative. 2002, 15 May.littp://dublincore.org/documents/dcq-rdf-xml /

9. The World Wide Web Consortium (W3C). XML Linking Language (XLink) Version 1.0 : W3C recommendation / DeRose S. et al. (eds.). 2001, 27 Jun. http://www.w3.org/TR/xlink/

10. The World Wide Web Consortium (W3C). Extensible Markup Language (XML): Part 2. Linking : W3C working draft / Bray Т., DeRose S. (eds.). 1997, 00 Apr. http://www.w3.org/TR/\VD-xml-link-970-106.html

11. The World Wide Web Consortium (W3C). XML XLink Requirements Version 1.0 : W3C note / DeRose S.J. (editor). 1999, 24 Feb.http://www. w3 .org/TR/NOTE-xlink-req

12. Network Working Group. RFC 2396: Uniform Resource Identifiers (URI): Generic Syntax : Internet official protocol standards / Berners-Lee T. et al. 1998, Aug. http://www.cs.tut.fi/~jkorpela/rfc/2396/full.htinl

13. The World Wide Web Consortium (W3C). XPointer Framework : W3C recommendation / Grosso P. et al. (eds.). 2003, 25 Mar.http://www.w3.org/TR/2003/REC-xptr-framework-20030325/

14. Лисовский К.Ю. Разработка XML-ириложсний на языке Scheme // Программирование. -М.: Наука, 2002 Вып. 28, N 1. - С. 20-32. - ISSN 0361-7688 = Programming and computer software.

15. Кузнецов С.Д. Основы современных баз данных : информационно-аналитические материалы. Центр Информационных Технологий. http://www.citforum.ru/databasc/osbd/contents.slitml

16. Филд Л., Харрисон П. Функциональное программирование / Пер. с англ. Рябипин Л.А. и др.; под ред. акад. Горбатова В.Л. М.: Мир, 1993. - G37 е.: пл. - ISBN 5-03-001870-0 (РУС-)

17. Lisovsky K. Scheme Program Source Code as a Semistructured Data : Proc. 2nd Workshop on Scheme and Functional Programming, Florence, Italy, Sep. 2001 / Serrano M. (ed.). http://citeseer.ist.psu.edu/lisovsky01sclicme.html

18. Abclson II., Sussman G.J., Sussman J. Structure and Interpretation of Computer Programs. -2nd ed. London; New York: The MIT Press; McGraw Hill, 199G. - G57 pp. - ISBN 0-2G2-01153-0.http://mitpress.mit.edu/sicp/

19. Kisclyov O. Implementing Metcast in Scheme : Proc. Workshop on Scheme and Functional Programming, Montreal, 17 Sep., 2000 // Rice Tech. Report 00-3G8. 2000, Sep. - pp. 23-27. http://www.ccs.neu.edu/home/matthias/Schcme2000/olcg.ps

20. The World Wide Web Consortium (W3C). XML Information Set : W3C recommendation / Cowan J., Tobin R. (eds.). 2nd edition. - 2004, 4 Feb.http://www.w3.org/TR/xml-infoset/

21. Kisclyov O. SXML specification / Rev. 3.0. ACM SIGPLAN Notices. - New York: ACM Press, 2002. - Vol. 37, N G. - pp. 52-58. - ISSN 03G2-1310. http://okinij.org/ftp/Scliemc/SXML.litml

22. Organization for the Advancement of Structured Information Standards (OASIS). RELAX NG Specification : Committee specification / Clark J., Murata M. (eds.). 2001, 3 Dec.http://www.oasis-open.org/committces/relax-ng/spec-20011203.html

23. Laurent S.St. XML Elements of Style. Osborne: McGraw-Hill, 2000. - 301 pp. - ISBN 0-07-212220-X.

24. Shivers O. List Library : Scheme Request for Implementation (SRFI) 1. Final status.1999, 10 Sep.http://srfi.scliemers.org/srn-l/

25. The World Wide Web Consortium (W3C). XML Path Language (XPath) 2.0 : W3C working draft / Berglund A. et al. (eds.). 2001, 23 Jul. http://www.w3.org/TR/2004/WD-xpath20-20040723

26. Консорциум W3C. Язык преобразований XSL (XSLT). Версия 1.0 = XSL Transformations (XSLT). Version 1.0 : Рекомендация Консорциума W3C / Под ред. Clark J.; пер. с аигл. Усмапов Р. 1999, 1С ноя.http://www.rol.ru/news/it/helpdesk/xslt01.htm

27. Steele G.L. (Jr.). Lambda: The Ultimate Declarative : Artificial Intelligence Memo. Cambridge: Massachusetts Institute of Technology, 197G. - N. 379. http://repository.readsclieme.org/ftp/papers/ai-lab-pubs/AIM-379.pdf

28. Серебряков В.А. Лекции по конструированию компиляторов. М., ВЦ РАН, 1994. -175 с. - ISBN 5-201-09911-4.

29. Волкова И.А., Рудеико Т.В. Формальные грамматики и языки. Элементы теории трансляции. 2-е изд. - М.: МГУ, изд. отдел факультета ВМК, 1999. - G2 с. - ISBN 589107-032-5.http://sp.cmc.msii.rii/courscs/prak2/langgrams.pdf

30. The World Wide Web Consortium (W3C). XQuery 1.0: An XML Query Language : W3C working draft / Boag S. et al. (eds.). 2004, 29 Oct. http://www.w3.org/TR/2001/WD-xquery-20041029/

31. The World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Data Model : W3C working draft / Fernandez M. et al. (eds.). 2004, 29 Oct. http://www.w3.org/TR/2001/WD-xpath-datamodel-20041029/

32. Grinev M. XQuery Optimization Based on Rewriting : Ph.D. thesis overview. 2003, Oct. http://www.ispras.ru/~grinev/mypapers/plid-short.pdf

33. Schmidt A. et al. XMark: A Benchmark for XML Data Management : Proc. 28th VLDB int. conf., Hong Kong, China, 20-23 Aug., 2002 // VLDB. Morgan Kaufinann, 2002. - pp. 974985.http://www.vldb.org/conf/2002/S30P01.pdf

34. The World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Formal Semantics : W3C working draft / Draper D. et al. (eds.). 2001, 20 Feb. http://www.w3.org/TR/2001/WD-xquery-semantics-20040220/

35. Bender J. (X)Querying XML in Scheme. 2003, 13 Jul. http://ccltic.benderweb.net/wcbit/docs/xquery-pre/

36. Fankhauser P. XQuery formal semantics state and challenges // ACM SIGMOD Record. -New York: ACM Press, 2001. Vol. 30, issue 3. - pp. 14-19. - ISSN 0103-5808. http://portal.acm.org/citation.cfm?id=G03870

37. Гарсиа-Молииа Г., Ульман Дж.Д., Уидом Дж. Системы Баз Данных. Полный курс / Пер. с англ. Варакина С.А.; под ред. Слепцова А.В. М,: Вильяме, 2003. - 1088 е.: ил. -ISBN 5-8159-0384-Х (рус.)

38. The World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Functions and Operators : W3C working draft / Malhotra A. et al. (eds.). 2001, 29 Oct. http://www.w3.org/TR/2004/WD-xpath-functions-20041029/

39. Kiselyov O. On parent pointers in SXML trees. 2003, 12 Feb. http://www.okmij.org/ftp/Sclieme/parent-pointers.txt

40. Lehti P. Design and Implementation of a Data Manipulation Processor for a XML Query Language : Ph.D. thesis. 2001, Aug. http://www.ipsi.fraunliofer.de/~lehti/

41. Kay M. XSLT and XPath Optimization : Proc. conf. XML Europe, Amsterdam, Netherlands, 18-21 Apr., 2004.http://idealliancc.org/papcrs/dxxmle04/papers/02-03-02/02-03-02.pdf

42. Gl. Mishra P., Eich M.H. Join processing in relational databases // ACM Computing Surveys. -New York: ACM Press, 1992 Vol. 24, issue 1. - pp. G3-113. - ISSN 03G0-0300. http://portal.acm.org/citation.cfm?id=1287Gl

43. G5. Кнут Д.Э. Искусство программирования, том 3. Сортировка и поиск. 2-е изд., испр. и доп. - Пер. с аигл. Тертышпыи В.Т., Красиков II.В.; под ред. Тригуб С.II. - М.: Вильяме, 2004. - 832 е.: ил. - ISBN 5-8159-0082-4 (рус).

44. G6. Stephen G.A. String Search : Technical report TR-92-gas-01. School of Electronic Engineering Science. - 1992, October, littp: //ei.es. vt .cd u/~cs5G04/f95/cs5G04cnSS/TR92.html

45. G7. Hudak P. Conception, evolution, and application of functional programming languages // ACM Computing Surveys. New York: ACM Press, 1989. - Vol. 21, issue 3. - pp. 359-411. -ISSN 03G0-0300.littp://portal. acm.org/citation.cfm?id=72554