Язык модификации данных формата XML функциональными методами

Д.А. Лизоркин
Труды Института системного программирования РАН

Назад Содержание

8. Будущие исследования

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

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

Изолированность транзакций на уровне отсутствия чтения “грязных данных” [22] может быть реализована с помощью механизма блокировок древовидных структур [23] или мониторов Хоара. Целью текущих исследований является разработка таких методов изоляции транзакций, которые бы гарантировали отсутствие неповторяющихся чтений и проблемы фантомов, и которые бы в минимальной степени влияли на параллелизм транзакций.

9. Заключение

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

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

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

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

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

Список литературы

1. Когаловский М.Р. Глоссарий по стандартам платформы XML. Версия 7 (17-12-2006). // Электронные библиотеки. – М.: ИРИО, 2006.
2. The World Wide Web Consortium (W3C). XQuery 1.0: An XML Query Language : W3C Recommendation / Boag S. et al. (eds.). – 2007, 23 Jan.
3. The World Wide Web Consortium (W3C). XQuery Update Facility 1.0 : W3C Working Draft / Chamberlin D. et al. (eds.). – 2007, 28 Aug.
4. Лизоркин Д.А., Лисовский К.Ю. SXML: XML-документ как S-выражение // Электронные библиотеки. – М.: ИРИО, 2003. – Т. 6, вып. 2. – ISSN 1562-5419 = Russian digital libraries journal.
5. The World Wide Web Consortium (W3C). XML Information Set : W3C recommendation / Cowan J., Tobin R. (eds.). – 2nd edition. – 2004, 4 Feb.
6. Kiselyov O. SXML specification / Rev. 3.0. – ACM SIGPLAN Notices. – New York: ACM Press, 2002. – Vol. 37, N 6. – pp. 52-58. – ISSN 0362-1340.
7. Kiselyov O. A better XML parser through functional programming : Proc. Practical Aspects of Declarative Languages: 4th int. symposium, PADL'2002, Portland, 19-20 Jan., 2002 // Lecture Notes in Computer Science / Krishnamurthi S., Ramakrishnan C.R. (eds.). – Springer-Verlag Heidelberg, 2002. – Vol. 2257. – pp. 209-224. – ISSN: 0302-9743.
8. Лизоркин Д.А. Оптимизация вычисления обратных осей языка XML Path при его реализации функциональными методами // Сборник трудов Института системного программирования РАН / Под ред. чл.-корр. РАН Иванникова В.П. – М.: ИСП РАН, 2004. – Т. 8, ч. 2. – 214 c. – с. 93-119. – ISBN 5-89823-026-2.
9. Abelson H., Sussman G.J., Sussman J. Structure and Interpretation of Computer Programs. – 2nd ed. – London; New York: The MIT Press; McGraw Hill, 1996. – 657 pp. – ISBN 0-262-01153-0.
10. Boehm H.-J. Space efficient conservative garbage collection : Proc. conf. on Programming Language Design and Implementation (SIGPLAN'93), Albuquerque, NM, Jun. 1993 // ACM SIGPLAN Notices. – New York: ACM Press, 1993. – Vol. 28(6). – pp. 197-206; New York: ACM Press, 2004. – Vol. 39, issue 4. – pp. 490-501. – ISSN 0362-1340.
11. Lehti P. Design and Implementation of a Data Manipulation Processor for a XML Query Language : Ph.D. thesis. – 2001, Aug.
12. Консорциум W3C. Язык XML Path (XPath) версия 1.0 = XML Path Language (XPath) Version 1.0 : Рекомендация Консорциума W3C / Под ред. Clark J., DeRose S.; пер. с англ. Усманов Р. – 1999, 16 ноя.
13. S. S. Chawathe, A. Rajaraman, H. Garcia-Molina and J. Widom. Change Detection in Hierarchically Structured Information. Technical report; detailed version of paper appearing in SIGMOD 1996.
14. Igor Tatarinov, Zachary G. Ives, Alon Y. Halevy, Daniel S. Weld. Updating XML : Proc. ACM SIGMOD int. conf. on Management of Data (SIGMOD'01), Santa Barbara, California, 21-24 May, 2001 // SIGMOD Conference / Aref W.G. (ed.). – New York: ACM Press, 2001. – pp. 413-424. – ISBN 1-58113-332-4.
15. Лизоркин Д.А., Лисовский К.Ю. Язык XML Path (XPath) и его функциональная реализация SXPath // Электронные библиотеки. – М.: ИРИО, 2003. – Т. 6, вып. 4. – ISSN 1562-5419 = Russian digital libraries journal.
16. A. Laux, L. Martin. XUpdate update language : XML:DB Working Draft. – 14 Sep, 2000.
17. Лизоркин Д.А., Лисовский К.Ю. Реализация XLink – языка ссылок XML – с помощью функциональных методов // Программирование. – М.: Наука, 2005. – N 1. – С. 52-72. – ISSN 0361-7688 = Programming and computer software.
18. Лизоркин Д.А. Язык запросов к совокупности XML-документов, соединенных при помощи ссылок языка XLink // Сборник трудов Института системного программирования РАН / Под ред. чл.-корр. РАН Иванникова В.П. – М.: ИСП РАН, 2004. – Т. 8, ч. 2. – 214 c. – с. 121-153. – ISBN 5-89823-026-2; Программирование. – М.: Наука, 2005. – N 3. – ISSN 0361-7688 = Programming and computer software.
19. The World Wide Web Consortium (W3C). Extensible Markup Language (XML) 1.0 (Fourth Edition) : W3C Recommendation / Bray T. et al. (eds.). – 2006, 16 Aug.
20. Лизоркин Д.А., Лисовский К.Ю. Пространства имен в XML и SXML // Электронные библиотеки. – М.: ИРИО, 2003. – Т. 6, вып. 3. – ISSN 1562-5419 = Russian digital libraries journal.
21. Лизоркин Д.А. Функциональные методы обработки XML-данных / Ph.D. thesis = Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 05.13.11. – 2005, 11 ноя.
22. Кузнецов С.Д. Современные технологии баз данных : Годовой курс для студентов 3-го курса. – Центр Информационных Технологий.
23. Гарсиа-Молина Г., Ульман Дж.Д., Уидом Дж. Системы Баз Данных. Полный курс / Пер. с англ. Варакина С.А.; под ред. Слепцова А.В. – М,: Вильямс, 2003. – 1088 с.: ил. – ISBN 5-8459-0384-X (рус.)
24. Гринев М., Кузнецов С.Д, Фомичев А. XML-СУБД Sedna: технические особенности и варианты использования // Открытые системы. – 2004, вып 8.

---

Назад Содержание