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

• Барашев, Дмитрий Валерьевич
• кандидат физико-математических наук
• 2003

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

1 Введение

1.1 Слабоструктурироваиные данные

1.1.1 Формат XML.

1.1.2 XML и базы данных.

1.1.3 Поддержка платформы XML производителями СУБД

1.1.4 Основные термины.

1.2 Языки формулировки запросов слабоструктурированиых данных.

1.3 Задача выполнения поиска по регулярному выражению

2 Родственные работы

2.1 Реляционные схемы

2.1.1 STORED.

2.1.2 XISS.

2.2 Многомерные схемы.

2.2.1 XPath Accelerator.

2.3 Схемы на основе Trie-структур.

2.3.1 Index Fabric.

3 Построение распределенного документа и выполнение в нем запросов

3.1 Высокоуровневые требования к системе и к ее компонентам

3.2 Модель распределенного XML документа.

• 3.2.1 Префиксное PATRICIA дерево . ■.

3.2.2 Нумерация вершин PATRICIA дерева.

3.2.3 Правило нумерации.

3.2.4 Решение проблемы выяснения родства.

3.2.5 Тины связей между сетевыми узлами.

3.3 Эффективность алгоритма выполнения запроса.

3.4 Выполнение запроса.

3.4.1 Поиск в слабо связанной системе.

3.4.2 Поиск в силыю связанной системе.

3.5 Реализация локального хранилища.

3.6 Выводы.

4 Экспериментальные результаты

4.1 Спецификация эталонного теста RegXPBench.

4.1.1 Архитектура среды выполнения теста.

4.1.2 Генерация тестовых данных.

4.1.3 Выполнение теста: часть первая.

4.1.4 Выполнение теста: часть вторая.

4.2 Реализация тестовой системы.

4.3 Эксперименты и анализ результатов.

4.4 Выводы .G

Введение диссертации (часть автореферата) на тему «Оптимизация выполнения запросов в распределенных неоднородных системах»

Распределенные базы данных активно изучаются с середины 70-х годов. Различным аспектам распределенных БД, таким как выявление тупиков [24], моделирование производительности [41], посвящено множество работ. Однако, по многим техническим и маркетинговым причинам, распределенные БД до недавнего времени не были широко востребованы. Сейчас интерес к распределенным БД возрождается. Для этого есть несколько причин [33]:

1. Стоимость кластера из большого количества персональных компьютеров обычно ниже, чем стоимость большого мэйнфрейма, при одинаковой производительности.

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

3. Новые приложения, основывающиеся на распределенных технологиях, такие как системы управления документооборотом или приложения электронной коммерции.

4. Рынок, требующий от компаний более гибкой структуры их бизнеса.

Сеть World Wide Web предоставила удобную инфраструктуру для создания распределенных баз данных, однако для хранения данных в настоящее время используется множество форматов, далеко не всегда совместимых между собой и удобных для запросов. Так, например, информация о цепах на компьютерные комплектующие может быть представлена в виде набора генерируемых базой данных HTML страниц на специальном сайте, в виде документов Microsoft Excel па сайтах компаний, торгующих комплектующими; описания и пресс-релизы могут существовать в форматах HTML, PDF и прочих; вся эта информация разбросана но десяткам сайтов. Формулирование и выполнение запросов в такой среде крайне затруднено. Единый формат хранения данных решил бы проблему, однако, требовать перевода всей информации в какой-то единый формат уже практически невозможно; настолько же невозможно требовать, чтобы все данные удовлетворяли какой-то единой структурированной метамодели. Появившийся в середине 90-х годов термин слабоструктурированные данные [64, 73], обозначающий данные, не имеющие четко определенной структуры, но являющиеся вместо этого самоописывающими, предоставил новую абстракцию для интеграции разрозненной информации. Исследования в этой области привели к созданию многих вариантов модели данных, формата хранения и языков запросов [75]. В настоящее время стандартами de-facto являются формат XML и языки запросов XPath и XQuery. Появилась "мечта" об универсальном представлении распределенной, разнородной, но семантически схожей информации в виде виртуального XiML документа, который поддерживается совместно участниками распределенной БД и позволяет выполнять XPath или XQuery запросы [23]. Данная работа посвящена исследованию возможности построения таких документов и выполнению в них запросов в виде регулярных выражений.

Работа организована следующим образом: в разделе 1.1 приводится введение в слабоструктурированные данные и XML; разделы 1.2 и 1.3 посвящены запросам слабоструктурированных данных вообще и запросам в виде регулярных выражений в частности. В главе 2 дай обзор методов храпения и индексирования слабоструктурировапиых данных, использующих существующие наработки. В главе 3 онисаиы модель данных, алгоритмы и варианты реализации структур данных для выполнения поиска по регулярному выражению в распределенном документе, а в главе 4 при веде и ы э кс и ери м е и тал ы i ы е резул ьтаты.

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

З.б Выводы

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

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

4 Экспериментальные результаты

В этой главе представлены описание и результаты практических экспериментов по реализации локального хранилища и алгоритма отсечения веток В-дерева, описанных в разделе 3.5. Целью экспериментов являлась проверка гипотезы о том, что использование В-дерева в качестве хранилища данных и алгоритма отсечения веток дает преимущества в скорости выполнения запросов, несущих в себе требуемую для алгоритма информацию. В качестве объекта сравнения была выбрана популярная свободная система выполнения запросов к XML документам Kweelt [2].

4.1 Спецификация эталонного теста RegXPBench

В настоящее время известно несколько эталонных тестов производительности XML баз данных: [56, 44, 15, 14]. Для тестирования хранилища RegXP совместно со студентом Сергеем Малеванным был разработан эталонный тест RegXPBench [72], являющийся модификацией известного теста XMach-1 [14].

4.1.1 Архитектура среды выполнения теста

Эталонный тест производительности XML баз данных XMach-1 [14] основан на веб-приложении, которое моделирует типичную работу пользователей с XML СУБД. Архитектура среды выполнения данного теста показана на рис. 14. Среда выполнения состоит из четырех компонент: XML СУБД, HTTP-сервера, загрузчиков документов в СУБД и виртуальных клиентов, имитирующих работу пользователей с веб-браузером. Тестовый набор данных состоит из большого количества относительно небольших по размеру докумс?тов-продукгпов (предполагается, что они были загружены с различных интернет-источников при помощи программ-загрузчиков) и одного большого, по сравнению с остальными документа

Тестируемая система

База данных

Поисковый механизм О

API базы данных каталог

Документы продукты

HTTP сервер

Servlet

Виртуальные клиенты О

Протокол HTTP

Загрузчики документов

Рис. 14: Архитектура среды выполнения эталонного теста RegXPBench ми, документа-каталога, содержащего в себе информацию о документах-продуктах. Каждый документ-продукт имеет уникальный идентификатор (URI), который вместе с метаданными об этом документе, хранится в документе-каталоге.

Во время работы теста виртуальные клиенты устанавливают соединения с HTTP-сервером и посылают информацию о запросах, которые они хотели бы выполнить. Поскольку предметом теста является эффективность выполнения запросов внутри СУБД, то время, затрачиваемое на общение клиентов и HTTP-сервера не учитывается при вычислении времени обработки запросов. Временем вычисления запроса считается интервал между моментом поступления запроса на HTTP-сервер и отправкой результатов запроса клиенту. Метрикой производительности считается количество выполненных запросов за единицу времени.

4.1.2 Генерация тестовых данных

Оригинальная процедура генерации тестовых данных теста XMach-1 сохранилась неизменной в RegXPBench. Генератор создает заданное количество документов-продуктов, назначает каждому из них уникальный идентификатор и помещает запись о документе в каталог. Документы-продукты внешне напоминают обычные статьи и относятся к классу тпексто-ориеитированных (document centric) документов. Базовое DTD документа-продукта показано на рис. 15. Поскольку маловероятно, что XML документы, пришедшие с различных веб-источников, будут иметь одинаковое DTD, то генератор XMach-1 порождает разнообразные DTD, модифицируя базовое путем приписывания целых чисел к каждому из имен элементов, кроме элементов author и link. Так, DTD N-ro документа будет иметь элементы с именами: documentN, chapterN, author, sectionN и т.д. Наличие в экземпляре докумепта-иродукта необязательных элементов DTD, глубина вложенности элементов section, а также некоторые другие характеристики определяются случайным образом по заданной таблице вероятностей. Содержимое символьных секций документов-продуктов генерируется но закону Зипфа [57] из словаря, содержащего 10000 слов английского языка.

Документ-каталог относится к классу структурно-ориентированных (data centric)1 документов. Его внутренние элементы имитируют дерево доменных имен и путей внутри каждого домена, а в листьях содержится небольшое количество метаипформации о документах-продуктах (рис. 16). Таким образом, документ-каталог является ветвистым деревом высотой 5-8 элементов без символьных секций. Пример каталога, содержащего 1 документ показан па рис. 17 термины тсксто-ориентированный и структурно-ориентированный противоречат встречающимся в русских переводах [GO] терминам документ, ориентированный па документ и документ, ориентированный на данные, однако, мы считаем маши термины более короткими и благозвучными и рассматриваем их как попытку дополнить русскую терминологию платформы XML [СУ]

ELEMENT document (title, chapter+)>

ATTLIST document author CDATA #IMPLIED doc.id ID #IMPLIED>

ELEMENT author (#PCDATA)>

ELEMENT title (#PCDATA)>

ELEMENT chapter (author?, head, section+)>

ATTLIST chapter id ID #REQUIRED>

ELEMENT section (head, paragraph+, section*)>

ATTLIST section id ID #REQUIRED>

ELEMENT head (#PCDATA)>

ELEMENT paragraph (#PCDATA I link)*>

ELEMENT link EMPTY>

ATTLIST link xlink:type (simple) #FIXED "simple" xlink:href CDATA #REQUIRED>

Рис. 15: Базовое DTD документа-продукта 4.1.3 Выполнение теста: часть первая

В первой части теста запускается виртуальный клиент, который поочередно отправляет на сервер запросы одного из трех типов, указанных в табл. 6. Эти запросы являются подмножеством запросов теста XMach-1, которое можно переписать, используя регулярные выражения. Количество генерируемых запросов каждого типа определяется перед началом тестового сеанса, а порядок генерации запросов определяется случайным образом. Запросы каждого тина выполняются при помощи регулярных выражений следующим образом:

Тип 1 Документы-продукты поочередно перебираются и на каждом их них выполняется запрос phrase/.*

ELEMENT directory (host+) > <!ELEMENT host (host+ I path+) > <!ATTLIST host name CDATA # REQUIRED > <!ELEMENT path (path+ I docinfo) > <!ATTLIST path name CDATA # REQUIRED > <!ELEMENT docinfo EMPTY > <!ATTLIST docinfо docid ID # REQUIRED loader CDATA # REQUIRED inserttime NMTOKEN # REQUIRED update.time NMTOKEN # IMPLIED >

Рис. 16: DTD документа-каталога

Если результатом запроса является непустое множество, то выполняется второй запрос */value-of(docid) который возвращает атрибут docid документа

Тин 2 Документы-продукты поочередно перебираются и па каждом их них выполняется запрос */docid =doc idpararneter который проверяет, совпадает ли docid очередного документа с искомым. Если результатом' является непустое множество, то выполняется второй запрос */section7mm&er/headmtm&er/value-of(. *) возвращающий требуемый результат directory> ahost name=5com'> bhost name='test-company'> <chost name='www'> apath name='products'> bpath name='overview.xml'> <docinfo docid='2' loader='robot1' inserttime='20000110152530'/> bpath> </apath> </chost> </bhost> </ahost> </directory>

Рис. 17: Пример доку мента-каталога

Тип 3 Запросы третьего типа применяются к документу-каталогу. Регулярное выражение запроса имеет общий вид: ahost / bhost / chost / apath/bpath / cpath /. *

Поскольку количество параметров данного запроса является переменным, что на практике означает, что отсутствующие в конкретном экземпляре запроса параметры' не определены, то неопределенные параметры пропускаются при составлении регулярного выражения. Так, запрос с тремя переданными параметрами ahost, bhost и apath записывается следующим образом: ahost / bhost /. */apath /. *

Тип Описание Параметры

1 Получить идентификаторы всех документов, содержащих данную фразу Фраза

2 Вернуть список элементов документа с заданным id, которые являются детьми элементов section с заданным номером Идентификатор документа и номер раздела

3 Выдать имена документов, URL которых соответствует заданному образцу От 1 до всех 6 компонент URL

5 Заключение

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

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

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

• Даны сильное и ослабленное определения эффективности алгоритмов выполнения запросов в виде регулярных выражений к распределенному документу.

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

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

• Реализован прототип локального хранилища слабоструктурировап-пых данных.

• Разработаны эталонные тесты производительности выполнения запросов в виде регулярных выражений. Тесты являются адаптированным подмножеством эталонных тестов производительности XML баз данных XMach-1.

• Проведена серия экспериментов по сравнению RegXP с системой выполнения запросов к XML документам Kweelt. Полученные результаты говорят об эффективности предложенного в RegXP алгоритма оптимизации выполнения запроса.

Список литературы диссертационного исследования кандидат физико-математических наук Барашев, Дмитрий Валерьевич, 2003 год

1. GNU Regexp Java Library.http://www.cacas.org/j ava/gnu/regexp/.2. Kweelt.http://kweelt.sourceforge.net.

2. Object Data Standard: ODMG 3.0. http://www.iso.org.4. Oracle XML DB.http://otn.oracle.com/tech/xml/techinfо.html.

3. SQL 1999 standard, http://www.iso.org.

4. G. The Unicode Standard, http://www.Unicode.org.

5. Serge Abiteboul. Querying semi-structured data. In Database Theory -ICDT '97, 6th International Conference, Delphi, Greece, January 8-10, 1997, Proceedings, volume 1186 of Lecture Notes in Computer Science, pages 1-18. Springer, 1997.

6. Serge Abiteboul, Dalian Quass, Jason McHugh, Jennifer Widom, and Janet L. Wiener. The Lorel query language for semistructured data. International Journal on Digital Libraries, l(l):68-88, 1997.

7. Apache Software Foundation. XIndice User Manual. http://xml.apache.org/xindice.

8. Francois Bancilhon. Object databases. ACM Computing Surveys (CSUR), 28(1): 137—140, 1996. http://doi.acm.org/10.1145/234313.234373.

9. Dmitry Barashev. Supporting regular expressions in queries to distributed XML documents. In Proceedings of the Fifth Russian Conference on Digital Libraries, 2003.http://rcdl2003.spbu.ru.

10. Dmitry Barashev, Michal Kratky, and Tomas Skopal. Modern approaches to indexing XML data. Sbornik vedeckych praci, 2003.

11. Dmitry Barashev and Boris Novikov. Indexing XML to support path expressions. In Proceedings of the Sixth East-European Conference on Advances in Databases and Information Systems, volume 2, 2002. http://www.dcs.elf.stuba.sk/adbis2002.

12. Timo B5hme and Erhard Rahm. XMach-1: A Benchmark for XML Data Management. In Datenbanksysteme in Biiro, Technik und Wissenschaft (BTW), 9. GI-Fachtagung, Oldenburg, 7.-9. Marz 2001, Proceedings, Informatik Aktuell. Springer, 2001.

13. Peter Buneman. Semistructured data. In Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 117-121. ACM Press, 1997.

14. Peter Buneman, Susan B. Davidson, Gerd G. Hillebrand, and Dan Suciu. A query language and optimization techniques for unstructured data. In Proceedings of the 1996 ACM SIGMOD International Conference on

15. Management of Data, Montreal, Quebec, Canada, June Jr6, 1996, pages 505-516. ACM Press, 1996.

16. Brian Cooper, Neal Sample, Michael J. Franklin, Gisli R. Hjaltason, and Moshe Shadmon. A fast index for semistructured data. In Proceedings of 27th International Conference on Very Large Data Bases, pages 341350. VLDB, 2001.

17. J. Robie D. D. Chamberlin and D. Florescu. Quilt: An XML Query Language for Heterogeneous Data Sources. In Proceedings of the 3rd ACM SIGMOD WebDB Workshop, pages 53-62, 2000.

18. Alin Deutsch, Mary Fernandez, Daniela Florescu, Alon Levy, and Dan Suciu. A query language for XML. Computer Networks, 31(11-16):1155-1169, 1999.

19. Alin Deutsch, Mary Fernandez, and Dan Suciu. Storing semistructured data with STORED. In Proceedings of the 1999 ACM SIGMOD international conference on Management of data, pages 431-442. ACM Press, 1999.

20. Paul F. Dietz. Maintaining order in a linked list. In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, pages 122-127, 1982.

21. Edd Dumbill. Distributed XML.http://www.xml.com/pub/a/ws/2000/09/06/distributed.html.

22. Ahmed K. Elmagarmid. A survey of distributed deadlock detection algorithms. ACM SIGMOD Record, 15(3):37-45, 1986.

23. R. J. Enbody and II. C. Du. Dynamic hashing schemes. ACM Computing Surveys (CSUR), 20(2):850-113, 1988.http://doi.acm.org/10.1145/46157.330532.

24. M. Fernandez, J. Simeon, P. Wadler, S. Cluet, A. Deutsch, D. Florescu, A. Levy, D. Maier, J. McHugh, J. Robie, D. Suciu, and J. Widom. XML query languages: Experiences and exemplars. 1999.http: //www-db. research. belllabs. com/user/simeon/xquery. ps.

25. Mary Fernandez, Daniela Florescu, Alon Levy, and Dan Suciu. A query language for a web-site management system. ACM SIGMOD Record, 26(3):4-ll, 1997.http://doi.acm.org/10.1145/262762.262763.

26. Daniela Florescu and Donald Kossmann. Storing and querying XML data using an RDMBS. IEEE Data Eng. Bull., 22(3):27-34, 1999.

27. Torsten Grust. Accelerating XPath location steps. In Proceedings of ACM SIGMOD 2002, June 4-6, Madison, USA, 2002.

28. Antonin Guttman. R-trees: A dynamic index structure for spatial searching. In Proceedings of ACM SIGMOD 1984, Annual Meeting, Boston, USA, pages 47-57. ACM Press, 1984.

29. IBM. XML Extender Brochure, 2000.http://www-3.ibm.com/software/data/db2/extenders/xmlext/.

30. David Konopnicki and Oded Shmueli. W3QS: A query system for the World-Wide Web. In VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland, pages 54-65. Morgan Kaufmann, 1995.

31. Donald Kossmann. The state of the art in distributed query processing. ACM Computing Surveys (CSUR), 32(4):422-469, 2000.http://doi.acm.org/10.1145/371578.371598.

32. Quanzhong Li and Bongki Moon. Indexing and querying XML data for regular path expressions. In Proceedings of 27th International Conference on Very Large Data Bases. Morgan Kaufmann, 2001.

33. Wen-Syan Li, Junho Shim, K. Selguk Candan, and Yoshinori Hara. WebDB: A web query system and its modeling, language, and implementation. In Proceedings of the IEEE Forum on Reasearch and Technology Advances in Digital Libraries, IEEE ADL '98, 1998.

34. David Lomet. The evolution of effective B-tree: page organization and techniques: a personal account. ACM SIGMOD Record, 30(3):64-69, 2001.

35. Jason McHugh, Serge Abiteboul, Roy Goldman, Dallas Quass, and Jennifer Widom. Lore: a database management system for semistructured data. ACM SIGMOD Record, 26(3):54-66, 1997.http://doi.acm.org/10.1145/262762.262770.

36. Alberto Mendelzon, George Mihaila, and Tova Milo. Querying the World Wide Web. International Journal on Digital Libraries, l(l):54-67, 1997.

37. M.Ley. How to mirror DBLP.http: //www. inf ormatik.uni-trier.de/-ley/db/about/instr.html.

38. Donald R. Morrison. PATRICIA Practical Algorithm To Retrieve Information Coded in Alphanumeric. J ACM, 15(4):514-534, 1968. http://doi.acm.org/10.1145/321479.321481.

39. Matthias Nicola and Matthias Jarke. Performance modeling of distributed and replicated databases. IEEE Transactions on Knowledge and Data Engineering, 12(4):645-672, 2000.

40. Yannis Papakonstantinou, Hector Garcia-Molina, and Jennifer Widom. Object exchange across heterogeneous information sources. In

41. Proceedings of the Eleventh International Conference on Data Engineering, March 6-10, 1995, Taipei, Taiwan, pages 251-260. IEEE Computer Society, 1995.

42. Jonathan Robie, Joe Lapp, and David Schach. XML Query Language (XQL). Technical report.http://www.w3.org/TandS/QL/QL98/pp/xql.html.

43. Albrecht Schmidt, Florian Waas, Martin L. Kersten, Michael J. Carey, Ioana Manolescu, and Ralph Busse. XMark: A Benchmark for XML Data Management. In Proceedings of 28th International Conference on Very Large Data Bases, VLDB'2002, 2002.

44. Dan Suciu. Management of semistructured data. ACM SIGMOD Record, 26(4) :4-7, 1997.

45. Dan Suciu. Distributed query evaluation on semistructured data. ACM Transactions on Database Systems (TODS), 27(l):l-62, 2002.

46. W3C. CSS. http://www.w3c.org/Style/CSS.49. W3C. XScliema.http://www.w3c.org/XML/Schema.50. W3C. XSL.http://www.w3c.org/Style/XSL.

47. W3C. Extensible Markup Language (XML) 1.0, 1998. http://www.w3.org/TR/REC-xml.

48. W3C. HTML 4.01 Specification, 1999. http://www.w3.org/TR/html4.

49. W3C. XML Path Language (XPath) Version 1.0, 1999. http://www.w3.org/TR/xpath.

50. W3C. XML Linking Language (XLink) Version 1.0, 2001. http://www.w3.org/TR/2001/REC-xlink-20010627/.

51. G. K. Zipf. The Psychobiology of Language. Houghton Miffin, Boston, 1935.

52. Альфред Ахо, Рави Сети, и Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Addison-Wesley Вильяме, 2001.

53. Дмитрий Барашев, Сергей Малеванный, н Борис Хвостиченко. RegXP.http://sourceforge.net/projects/regxp.

54. GO. Рональд Буро. XML и базы данных. Открытые системы, (10), 2000.http://www.osp.ru/os/2000/10/062.htm.

55. Даниэла Флорсску, Алон Леви, и Альберто Мендельсон. Технологии баз данных для World Wide Web: обзор. СУБД, (04-05), 1998.

56. Дж. Фридл. Регулярные выражения. Библиотека программиста. O'Reilly Питер, 2001.

57. Александр Фролов and Григорий Фролов. Базы данных в Интернете. Microsoft Press, Русская Редакция, 2000.

58. Максим Гринев. Системы управления полуструктурированными данными. Открытые системы, (5-6), 1999.http://www.osp.ru/os/1999/05-06/09.htm.

59. Джон Хопкрофт, Раджив Мотвани, и Джеффри Ульман. Введение в теорию автоматов, языков и вычислений. Addison-Wesley Вильяме, 2002.

60. Борис Хвостиченко. Индексирование путей в слабоструктурироваи-ных данных. Дипломная работа, СПбГУ, мат.-мех. факультет, кафедра информатики, 2003.

61. Борис Хвостиченко и Борис Новиков. Индексирование путей в слабоструктурированных данных. Труды четвертой всероссийской конференции 'Электронные Библиотеки', 2002.

62. Дональд Кнут. Все про ТеX. Вильяме, 2003.

63. Михаил Р. Когаловский. Глоссарий по стандартам платформы XML. http: //www. elbib.ru/index.phtml?page=elbib/rus/methodology/xmlbase.

64. Михаил Р. Когаловскии. XML: Возможности и перспективы. Директор И С, 2001.

65. Михаил Р. Когаловскии. Стандарты платформы XML и базы данных. Труды Третьей Всероссийской конференции 'Электронные Библиотеки\ 2001.

66. Сергей Малеванный. Реализация эталонного теста для XML СУБД, поддерживающих запросы с регулярными выражениями. Дипломная работа, СПбГУ, мат.-мех. факультет, кафедра информатики, 2003.

67. Дмитрий Палей. Моделирование квазиструктурированных данных. Открытые системы, (9), 2002.http://www.osp.ru/os/2002/09/057.htm.

68. Александр Печерский. Язык XML практическое введение, http://www.citforum.ru/internet/xml/index.shtml.

69. Андрей Суслов. Языки запросов для XML данных. Открытые системы, (2), 2001.http://www.osp.ru/os/2001/02/065.htm.

70. Джеффри Ульман, Гектор Гарсиа-Молина, и Дженнпфер Упдом. Систелш баз данных. Полный курс. Williams, 2003.

71. Джонатан Эйиджел. XML: время пришло. LAN/Журнал сетевых решений, 1999.http://www.citforum.ru/internet/articles/xml009.shtml.