Алгоритмы эффективного вычисления конъюнктивных регулярных путевых запросов в базах полуструктурированных данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Афонин, Сергей Александрович

• Афонин, Сергей Александрович
• кандидат физико-математических наук
• 2007

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

Введение

ГЛАВА 1. Конъюнктивные регулярные путевые запросы

1.1. Основные понятия и обозначения

1.2. Модель данных и язык запросов.

1.2.1. Структура данных.

1.2.2. Язык запросов.

1.2.3. Ограничения целостности.

1.3. Вычисление запроса как поиск подграфа в графе.

1.4. Методы оптимизации CRPQ-запросов.

1.4.1. Индексные структуры.

1.4.2. Вычисление при наличии представлений.

1.4.3. Эквивалентность и вложенность запросов.

1.4.4. Усечение запроса с использованием схемы.

1.5. Выводы.

ГЛАВА 2. Базовые методы вычисления запросов

2.1. Стратегии вычисления запросов.

2.1.1. Вычисление элементарного запроса.

2.1.2. Стратегии вычисление CRPQ запроса.

2.1.3. Сравнение стратегий

2.2. Эвристики

2.2.1. Эвристики обхода вершин запроса.

2.2.2. «Обращение» ребер.

2.2.3. Порядок обхода исходящих ребер.

2.2.4. Наложение локальных ограничений.

2.2.5. Вычисление запроса с учетом эвристик.

2.3. Декомпозиция запросов.

2.3.1. Разложение CRPQ запросов.

2.3.2. Разложение элементарных запросов.

2.4. Выводы.

ГЛАВА 3. Оценка сложности элементарного запроса

3.1. Сложность запроса и меры сложности регулярных языков.

3.2. Мера сложности путевого запроса.

3.2.1. Определение меры сложности путевого запроса.

3.2.2. Вычисление сложности путевого запроса.

3.2.3. Свойства меры сложности путевого запроса.

3.3. Оценка сложности элементарного запроса.

3.3.1. Синтаксическая сложность элементарного запроса.

3.3.2. Оценка мощности результата элементарного запроса

3.3.3. Использование статистики базы данных.

3.4. Результаты тестирования.

3.5. Выводы.

ГЛАВА 4. Построение плана вычисления запроса

4.1. Понятие плана вычисления запроса.

4.2. Определение сложности плана.

4.2.1. Информативность вершины запроса.

4.2.2. Информативность ребра запроса.

4.2.3. Сложность плана

4.3. Алгоритм построения плана

4.4. Результаты применения планов.

4.5. Выводы.

ГЛАВА 5. Архитектура реализованного программного комплекса

5.1. Подсистема вычисления запросов

5.2. Подсистема хранения данных.

5.3. Подсистема оптимизации запросов.

5.3.1. Построение перезаписи элементарного запроса с учетом представлений

5.3.2. Построение плана вычисления запроса.

5.3.3. Оценка сложности плана.

5.4. Выводы.

Введение диссертации (часть автореферата) на тему «Алгоритмы эффективного вычисления конъюнктивных регулярных путевых запросов в базах полуструктурированных данных»

Актуальность темы. Необходимость интеграции данных из автономных, независимо администрируемых, информационных источников естественным образом приводит к задаче управления данными с неоднородной, часто изменяющейся или частично неизвестной структурой. Такие данные принято называть полуструктурированными. Примерами возникновения полуструктурированных данных являются системы интеграции данных в Интернет или в крупных корпоративных или государственных информационных системах. Отдельные компоненты (сайты или ведомственные информационные системы) могут содержать строго структурированные данные (общая структура HTML и единая структура базы данных, соответственно), однако при объединении информации из нескольких таких источников данные, описывающие одни и те же объекты реального мира, могут иметь существенно различающуюся структуру. Необходимость поиска информации одновременно в нескольких источниках приводит к задаче поиска данных с неоднородной структурой. В работе 2005 года [42] было предложено еще более общее направление исследований — переход от баз данных к «пространствам данных». Авторы этой работы рассматривают задачу поиска разнородной информации в очень широкой постановке (в качестве примера рассматривается поиск по всем файлам рабочей станции — электронным таблицам, текстовым документам, локальным базам данных и т.д.) и предлагают «программу исследований», направленную на достижение этой цели. Одним из таких направлений является обработка запросов к полуструктурированным данным. В частности, в этой работе отмечается, что применение методов управления полуструктурированными данными позволяет проводить структурированный поиск, но при этом не требует строгого сопоставления схем данных информационных источников.

Основными математическими моделями представления полуструктурированных данных являются ориентированные графы с помеченными ребрами [53], помеченные деревья [10] и деревья с упорядоченными элементами [72]. Для каждой модели данных применяются соответствующие языки запросов например, регулярные путевые запросы, XPath, XQuery). Следует отметить, что эффективность применения той или иной модели данных зависит от предметной области, в которой будет использоваться система управления полу-структурироваными данными. Например, модель данных, основанная на упорядоченных деревьях, которая в настоящее время находится в центре внимания специалистов по базам данных, ориентирована в первую очередь на работу с XML-документами. Для других задач, таких как поиск текстов с учетом онтологий [3,6,60], управление содержанием web-сайтов или интеграция данных [7,70], эта модель менее эффективна, поскольку в этих приложениях естественным образом возникают графовые структуры данных.

Вычисление конъюнктивных регулярных путевых запросов в графовой модели данных может быть сведено к классической NP-полной задаче поиска подграфа в графе и известные алгоритмы вычисления запросов представляют собой модификации алгоритмов такого поиска. Основные работы, направленные на создание эффективных алгоритмов вычисления запросов, связанны с разработкой различных методов оптимизации запросов и построения индексных структур специального вида. Методы оптимизации регулярных путевых запросов включают такие направления, как усечение запросов с использованием схем данных [37], вычисление запросов с использованием материализованных представлений [65] и перезапись запроса с учетом ограничений целостности [18,45], и позволяют получить запрос, который эквивалентен исходному, но вычисление которого может быть проведено более эффективно. В частности, для некоторых методов усечения запросов доказывается оптимальность получающегося запроса. Перечисленные методы позволяют снизить размерность задачи, однако вычисление оптимизированного запроса сводится к решению задачи поиска подграфа. В тоже время «прямолинейное» сведение задачи вычисления запросов к поиску подграфа не учитывает ее характерных особенностей, связанных со структурой составляющих запрос регулярных языков. С учетом изложенного проблема разработки алгоритмов эффективного вычисления конъюнктивных регулярных путевых запросов и инструментальных средств их реализации является актуальной.

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

• реализация основных методов обработки конъюнктивных регулярных путевых запросов;

• экспериментальное определение множества параметров, влияющих на эффективность вычисления запросов;

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

• формализация понятия плана вычисления запроса и разработка алгоритмов построения планов, обеспечивающих эффективное вычисление запросов;

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

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

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

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

• Предложен новый подход к определению сложности регулярного путевого запроса.

• Формализовано понятие плана вычисления конъюнктивного регулярного путевого запроса, сложности плана и предложен алгоритм построения эффективного плана вычисления конъюнктивных регулярных путевых запросов.

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

Научная новизна. В работе впервые рассматривается задача построения эффективного плана вычисления запроса. Ранее подобная задача рассматривалась только в контексте территориально распределенных данных [55,68]. Предлагается новый метод определения сложности регулярного языка, который позволяет оценить сложность вычисления регулярного путевого запроса. Впервые формализовано понятие плана вычисления конъюнктивного регулярного путевого запроса, предложен метод оценки сложности плана и алгоритм построения эффективного плана.

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

Практическая ценность. Результаты работы могут быть использованы при разработке систем управления полуструктурированными данными, основанных на графовой модели данных, в частности, в системах интеграции данных и информационно-поисковых системах, учитывающих логическую структуру документов. Разработаный в рамках данной работы прототип программного комплекса оптимизации и вычисления конъюнктивных регулярных путевых запросов является частью Автоматической Системы Информационного Обеспечения (АСИО), которая создается в НИИ Механики и Институте проблем информационной безопасности МГУ им. М.В. Ломоносова.

Доклады и публикации. Основные положения работы докладывались на 26-ой международной конференции MIPRO-2003, Опатия, Хорватия (2003 г.), на Всероссийской научной конференции «Научный сервис в сети Интернет», Новороссийск (2003 г.), на Всероссийская конференция «Высокопроизводительные вычисления и технологии», Ижевск (2003 г.), на Всероссийской конференции «Мальцевские чтения», Новосибирск (2003 г.), на международной конференции «Программные системы: теория и приложения», ИПС РАН, г. Переславль-Залесский (2004 г.), на международной конференции «Developments in Language Theory», Палермо, Италия (2005 г.), на международной конференции «Semigroups and Languages», Лиссабон, Португалия (2005 г.), на международной конференции «Finnish Data Processing Week», Петрозаводск (2005 г.) на механико-математическом факультете МГУ им. М. В. Ломоносова на семинаре «Проблемы современных информационно-вычислительных систем» под руководством проф. В. А. Васенина (2005 г.), на семинаре ИСП РАН (2006 г.) и на семинаре Московской секции SIGMOD (2006 г.).

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

• Афонин С.А. «Стратегии вычисления регулярных путевых запросов» // Информационные технологии и программирование. Сборник статей. Вып 5, стр. 9-16 - М.:МГИУ, 2002.

• S. Afonin, A. Shundeev, V. Roganov, «Semistructured data search using dynamic parallelisation technology» // «Proceedings of the 26th International Convention MIPRO-2003», 152-157

• Афонин C.A., «Параллельное вычисление запросов к базам полуструктурированных данных» // Сборник трудов Всероссийской конференции «Высокопроизводительные вычисления и технологии», Ижевск 2003, стр. 202-205

• Васенин В.А., Афонин С.А. «К разработке моделей эффективного поиска информации в сети Интернет», Сборник трудов Всероссийской научной конференции «Научный сервис в сети Интернет 2003», стр. 252-255, Издательство МГУ, 2003

• Васенин, В. А., Афонин, С.А., Козицын А.С., Шундеев А.С. «Поиск в сверхбольших хранилищах данных и высокопроизводительные системы с массовым параллелизмом» // Труды международной конференции «Программные системы: теория и приложения», ИПС РАН / Под редакцией С. М. Абрамова. Том 1, стр. 211-228, М.: Физматлит, 2004.

• S. Afonin, Б. Khazova, «Membership and Finiteness Problems for Rational Sets of Regular Languages» // International Journal of Foundations of Computer Science, 17(3), 493-506, «World Scientific», 2006

• S. Afonin, «Language theoretic problems in modern database applications» // Proceedings of the «Finnish Data Processing Week Conference (FDPW-2005)», стр. 8-19, 2006

• Афонин C.A. «Алгоритмы эффективного вычисления конъюнктивных регулярных путевых запросов» // Вычислительные технологии, 12(2), 23-32, 2007.

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

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

5.4. Выводы

Основными результатами являются следующее.

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

• Предложен новый подход к определению сложности регулярного путевого запроса.

• Формализовано понятие плана вычисления конъюнктивного регулярного путевого запроса, сложности плана и предложен алгоритм построения эффективного плана вычисления конъюнктивных регулярных путевых запросов.

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

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

1. Афонин, С. А. Стратегии вычисления регулярных путевых запросов / С. А. Афонин // Информационные технологии и программирование. — 2002.-Т. 5, № 1.-С. 9-16.

2. Афонин, С. А. Параллельное вычисление запросов к базам полуструктурированных данных / С. А. Афонин // Тезисы докладов Всероссийской конференции «Высокопроизводительные вычисления и технологии».— Ижевск: 2003.- С. 202-205.

3. Афонин, С. А. Поиск текстовых документов с учетом их логической структуры / С. А. Афонин, А. С. Козицын // XII международная конференция по вычислительнй механике и современным прикладным про-грамным системам (ВМСППС). — 2003.

4. Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Д. Хопкрофт, Д. Ульман. — М.: Мир, 1979.

5. Бухараев, Р. Основы теории вероятностных автоматов / Р. Бухараев. — М.: Наука, 1985.

6. Васенин, В. А. К разработке моделей эффективного поиска информации в сети интернет / В. А. Васенин, С. А. Афонин // Сборник трудов Всероссийской научной конференции «Научный сервис в сети Интернет 2003». Абрау-Дюрсо: Издательство МГУ, 2003.- С. 252-255.

7. Васенин, В. А. К созданию концепции интегрированной системы распределенных информационных ресурсов Московского государственного университета им. М.В. Ломоносова / В. А. Васенин, С. А. Афонин,

8. A. А. Коршунов. — Издательство Московского университета, 2001.

9. Васенин, В. A. GRACE: распределенные приложения в Internet /

10. B. А. Васенин, В. А. Роганов // Открытые системы.— 2001.— Т. 5-6.-С. 29-33.

11. Горелов, С. С. Optimal schema hierarchies in searching semistructured databases by conjunctive regular path queries / С. С. Горелов // Программирование.- 2006.- Т. 32, № 4.- С. 215-227.

12. Гросс, М. Теория формальных грамматик / М. Гросс, А. Лантен. — М.: Мир, 1971.-Р. 294.

13. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. М.: Мир, 1982.

14. Кудрявцев, В. Б. Введение в теорию автоматов / В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин.— М.: Наука, 1985.

15. Афонин, С. А. О разложении регулярных языков. — Материалы докладов Всероссийской конференции «Мальцевские чтения». — 2003.

16. Проектирование и реализация параллельных алгоритмов вычисления и оптимизации запросов в системах управления полуструктурированными данными: Tech. rep. / А. Жижченко, С. Афонин, Н. Алексиадис, др.: ЦНТК РАН, 2003.

17. Трахтенброт, Б. А. Конечные автоматы (поведение и синтез) / Б. А. Трахтенброт, Я. М. Барздинь. — М.: Наука, 1970.

18. Abiteboul, S. Regular path queries with constraints / S. Abiteboul, V. Vianu // Proc. of the sixteenth ACM SIGACT SIGMOD SIGART Sym. on Principles of Database Systems (PODS 97).- 1997.- Pp. 122-133. citescer.nj.nec.com/abiteboul97regular.htmI.

19. Aboulnaga, A. Estimating the selectivity of XML path expressions for internet scale applications / A. Aboulnaga, A. R. Alameldeen, J. F. Naughton // The VLDB Journal.- 2001.- Pp. 591-600.citeseer.nj.nec.com/aboulnaga01estimating.html.

20. Afonin, S. Semistructured data search using dynamic parallelisation technology / S. Afonin, A. Shundeev, V. Roganov // Proceedings of the 26th International Convention MIPRO-2003, Opatija, Croatia.- 2003.-Pp. 152-157.

21. Answering regular path queries using views / D. Calvanese, G. D. Giacomo, M. Lenzerini, M. Y. Vardi // ICDE.- 2000.- Pp. 389-398.citeseer.nj.nec.com/calvanese99answering.html.

22. Brzozowski, J. A. Derivatives of regular expressions / J. A. Brzozowski // Journal of the ACM. 1964. - октябрь. - Vol. 11, no. 4. - Pp. 481-494.

23. Buneman, P. Path constraints in semistructured databases / P. Buneman, W. Fan, S. Weinstein // Journal of Computer and System Sciences.— 2000. Vol. 61, no. 2. — Pp. 146-193. citeseer.nj.nec.com/246597.html.

24. Buneman, P. UnQL: a query language and algebra for semistructured data based on structural recursion / P. Buneman, M. F. Fernandez, D. Suciu // VLDB Journal: Very Large Data Bases. 2000. - Vol. 9, no. 1. - Pp. 76110. citeseer.nj .nec.com/390455.html.

25. Cali, A. Local constraints in semistructured data schemas / A. Cali, D. Calvanese, M. Lenzerini // Proc. of the 8th Italian Conf. on Database Systems (SEBD 2000).- 2000.

26. Calvanese, D. What can knowledge representation do for semi-structured data? / D. Calvanese, G. De Giacomo, M. Lenzerini // Proc. of the 15th Nat. Conf. on Artificial Intelligence (AAAI'98).- 1998.- Pp. 205-210.

27. Calvanese, D. Modeling and querying semi-structured data / D. Calvanese, G. De Giacomo, M. Lenzerini // Network and Information Systems.— 1999. Vol. 2, no. 2. - Pp. 253-273.

28. Carrasco, R. C. Learning deterministic regular grammars from stochastic samples in polynomial time / R. C. Carrasco, J. Oncina // RAIRO

29. Theoretical Informatics and Applications).— 1999.— Vol. 33, no. 1.— Pp. 1-20.

30. Clark, J. Xml path language (xpath) version 1.0: Tech. rep. / J. Clark, S. DeRose: World Wide Web Consortium, 1999.http://www.w3c.org/TR/xpath/.

31. Constraints for semistructured data and XML / P. Buneman, W. Fan, J. Sin^on, S. Weinstein // SIGMOD Record (ACM Special Interest Group on Management of Data).— 2001.— Vol. 30, no. 1.— Pp. 47-54. citescer.nj .nec.com/489223.html.

32. Containment of conjunctive regular path queries with inverse / D. Calvanese, G. D. Giacomo, M. Lenzerini, M. Y. Vardi // KR.- 2000.

33. Counting twig matches in a tree / Z. Chen, H. V. Jagadish, F. Korn et al. // ICDE. — 2001. — Pp. 595-604. citeseer.ist.psu.edu/chen01counting.html.

34. Courcelle, B. Graph rewriting: An algebraic and logic approach / B. Courcelle // Formal Models and Sematics, volume В of Handbook of Theoretical Computer Science. — Elsevier, Amsterdam, 1990. — Pp. 193-242.

35. Deutsch, A. Optimization properties for classes of conjunctive regular path queries. — 2001. gunther.smeal.psu.edu/deutsch01optimization.html.

36. Eppstein, D. Subgraph isomorphism in planar graphs and related problems / D. Eppstein /I J. Graph Algorithms & Applications.— 1999.— Vol. 3, no. 3. Pp. 1-27.

37. Fernandez, M. Optimizating regular path expressions using graph schemas: Tech. rep. / M. Fernandez, D. Suciu: PENN Database Research Group., 1999.

38. Flavio Rizzolo, A. M. Indexing xml data with toxin. citeseer.nj.nec.com/rizzolo01indexing.html.

39. Fortune, S. The directed subgraph homeomorphism problem / S. Fortune, J. Hopcroft, J. Wyllie // Theoretical Computer Science. — 1980. — Vol. 10. — Pp. 111-121.

40. Franklin, M. From databases to dataspaces: a new abstraction for information management / M. Franklin, A. Halevy, D. Maier // SIGMOD Rec. 2005. - Vol. 34, no. 4. - Pp. 27-33.

41. Grahne, G. Algebraic rewritings for optimizing regular path queries / G. Grahne, A. Thomo // Theoretical Computer Science. — 2003. — March. — Vol. 296. P. 453.

42. Halevy, A. Y. Theory of answering queries using views / A. Y. Halevy // SIGMOD Record (ACM Special Interest Group on Management of Data). — 2000. — Vol. 29, no. 4. — Pp. 40-47. citeseer.nj.nec.com/halevy00theory.html.

43. Kanza, Y. Flexible queries over semistructured data / Y. Kanza, Y. Sagiv // Proceedings of the ACM PODS'Ol Conference. 2001.

44. Kari, L. On insertion and deletion in formal languages.— Ph.D. thesis, University of Turku, Finland. — 1991.

45. Kari, L. Maximal and minimal solutions to language equations / L. Kari, G. Thierrin // Journal of Computer and System Sciences.— 1996. — December- — Vol. 53. Pp. 487-496.

46. Kaushik, R. Exploiting local similarity for indexing paths in graph-structured data, citeseer.nj.nec.com/496617.html.

47. Lee, D. Counting relaxed twig matches in a tree.— 2002.citcseer.ist.psu.edu/lee02counting.html.

48. Li, Q. Indexing and querying XML data for regular path expressions / Q. Li, B. Moon // The VLDB Journal.- 2001.- Pp. 361-370.citeseer.nj .ncc.com/H01indexing.html.

49. Marx, M. Conditional XPath, the first order complete XPath dialect / M. Marx // Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. — Paris, France: 2004. — Pp. 13-22.

50. Miao, Z. Grid-aware evaluation of regular path queries on spatial networks / Z. Miao, D. Stefanescu, A. Thomo // aina. 2007. - Vol. 0. - Pp. 158-165.

51. Milo, T. Index structures for path expressions / T. Milo, D. Suciu // Lecture Notes in Computer Science.— 1999.— Vol. 1540.— Pp. 277-295. citeseer.nj.nec.com/milo97index.html.

52. Nicodeme, P. Motif statistics / P. Nicodeme, B. Salvy, P. Flajolet // Theoretical Computer Science. 2002. - Vol. 287.- Pp. 583-617.

53. Park, C.-W. An effective query pruning technique for multiple regular path expressions / C.-W. Park, C.-W. Chung // Journal of Systems and Software. 2002. - December. - Vol. 64. - Pp. 219-233.

54. Querying semistructured heterogeneous information / D. Quass, A. Rajaraman, Y. Sagiv et al. // Deductive and Object-Oriented Databases (DOOD '95).- LNCS no. 1013. Springer, 1995.- Pp. 319-344.

55. Querying the semantic web with RQL / G. Karvounarakis, A. Magganaraki, S. Alexaki et al. // Comput. Networks.- 2003.- Vol. 42, no. 5.- Pp. 617640.

56. A query language and optimization techniques for unstructured data / P. Buneman, S. Davidson, G. Hillebrand, D. Suciu // Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. — 1996. Pp. 505-516.

57. A query language and optimization techniques for unstructured data: Tech. Rep. 9 / P. Buneman, S. Davidson, G. Hillebrand, D. Suciu: PENN Database Research Group., 1996. ftp://ftp.cis.upenn.edu/pub/papers/db-research/sigmod96.ps.gz.

58. A query language for XML / A. Deutsch, M. Fernandez, D. Florescu et al. // Computer Networks (Amsterdam, Netherlands: 1999). — 1999. — Vol. 31, no. 11-16.— Pp. 1155-1169. citeseer.nj.nec.com/deutsch98query.html.

59. Rabin, M. Decidability of second-order theories and automata on infinite trees / M. Rabin // Transactions of the American Mathematical Society. — Vol. 141.- 1969.-Pp. 1-35.

60. Rewriting of regular expressions and regular path queries / D. Calvanese, G. De Giacomo, M. Lenzerini, M. Vardi // Journal of Computer and System Sciences. 2002. - May. - Vol. 64. - Pp. 443-465.

61. Shallit, J. Automaticity I: Properties of a measure of descriptional complexity / J. Shallit, Y. Breitbart // Journal of Computer and System Sciences.- 1996,-Vol. 53.- Pp. 10-25.

62. Shasha, D. Algorithmics and applications of tree and graph searching / D. Shasha, J. T.-L, Wang, R. Giugno // Symposium on Principles of Database Systems. — 2002. — Pp. 39-52. citeseer.nj.nec.com/501656.html.

63. Suciu, D. Distributed query evaluation on semistructured data / D. Suciu // ACM Trans. Database Syst. 2002. - Vol. 27, no. 1.- Pp. 1-62.

64. Ullmann, J. R. An algorithm for subgraph isomorphism / J. R. Ullmann // Journal of the ACM.- 1976. январь. - Vol. 23, no. 1.- Pp. 31-42.

65. Vasenin, V. A. To the problem of building an integrated system of university distributed information resources / V. A. Vasenin, S. A. Afonin // Proceedings of the Finnish Data Processing Week Conference FDPW-2001. — 2001.-Pp. 152-177.

66. View-based query answering and query containment over semistructured data / D. Calvanese, G. De Giacomo, M. Lenzerini, M. Y. Vardi // Proc. of the 8th Int. Workshop on Database Programming Languages (DBPL 2001).-2001.

67. Xquery: An query language for xml.: Tech. rep. / S. Boag, D. Chamberlin, M. F. Fernandez et al.: World Wide Web Consortium, 2007.http://www.w3c.org/TR/xquery/.