автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Алгоритмы эффективного вычисления конъюнктивных регулярных путевых запросов в базах полуструктурированных данных

Московский государственный университет им М В Ломоносова

На правах рукописи

Афонин Сергей Александрович

Алгоритмы эффективного вычисления конъюнктивных регулярных путевых запросов в базах полуструктурированных данных

Специальность 05 13 11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

иилиьиз?1

Москва — 2007 год

003060971

Работа выполнена в Институте механики Московского государственного университета им М В Ломоносова

Научный руководитель

доктор физико-математических наук, профессор

Васенин Валерий Александрович

Официальные оппоненты

доктор технических наук, профессор

Кузнецов Сергей Дмитриевич

кандидат физико-математических наук, доцент

Валединский Владимир Дмитриевич

Ведущая организация

Институт математики СО РАН

Защита диссертации состоится « 29 » июня 2007 г в 15 часов на заседавши диссертационного совета Д 002 087 01 в Институте Системного Программирования РАН по адресу 109004, Москва, ул Б Коммунистическая, д 25, конференц-зал

С диссертацией можно ознакомиться в библиотеке Института Системного Программирования РАН

Автореферат разослан « » /Ч&Я 2007 г

Ученый секретарь диссертационного совета Д 002 087-кандидат физ-мат наук

С П Прохоров

Общая характеристика работы

Актуальность темы. Необходимость интеграции данных из автономных, независимо администрируемых, информационных источников естествен ным образом приводит к задаче управления данными с неоднородной, часто изменяющейся или частично неизвестной структурой Такие данные принято называть полуструктурированными Примерами возникновения полуструктурированных данных являются системы интеграции данных в Интернет или в крупных корпоративных или государственных информационных системах Отдельные компоненты могут содержать строго структурированные данные, однако при объединении информации из нескольких таких источников однотипные со смысловой точки зрения данные могут иметь существенно различающуюся структуру Применение методов управления полуструктурированными данными позволяет проводить структурированный поиск, но при этом не требует строгого сопоставления схем данных1

Наиболее распространенными математическими моделями представления полуструктурированных данных являются ориентированные графы с помеченными ребрами, помеченные деревья и деревья с упорядоченными элементами Для каждой модели данных применяются соответствующие языки запросов (например, регулярные путевые запросы, XPath, XQuery) В качестве модели в данной работе выбрана одна из разновидностей графового представления данных Гибкость такого представления данных (другие модели могут быть сведены к графовому представлению) компенсирует большую, по сравнению с другими моделями, алгоритмическую сложность задач обработки запросов Следует отметить, что эффективность применения той или иной модели данных зависит от предметной области, в которой будет использоваться система управления полуструктурироваными данными Например, модель данных, основанная на упорядоченных деревьях, которая в настоящее время находится в центре внимания специалистов по базам данных, ориентирована в первую очередь на работу с XML-документами Для других задач, в которых возникают графовые структуры данных, эта модель менее эффективна

Вычисление конъюнктивных регулярных путевых запросов в графовой

lM Franklin, A Halevy, D Maier, Prom databases to dataspaces a new abstraction for information management, SIGMOD Rec , 34(4), 27-33, ACM Press, 2005

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

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

Научная новизна. В работе впервые рассматривается задача построения эффективного плана вычисления запроса Ранее подобная задача рас-

2М F Fernandez, D Suciu, Optimizing Regular Path Expressions Using Graph Schemas // Proc 14th Int Conf on Data Engineering, 14-23, IEEE Computer Society, 1998

3Calvanese, D , De Giacomo, G , Ьепгепш, M , and Vardi, M Rewriting of regular expressions and regular path queries // Journal Comp and Sys Sei, 64, 443^465, 2002

4S Abiteboul, V Vianu, Regular path queries with constraints // Proc 17th ACM Sym on Principles of Database Systems (PODS), 122-133,1997

G Grahne, A Thomo, Query containment and rewriting using views for regular path queries under constraints Ц Proc 21th ACM Sym on Principles of Database Systems (PODS), 111-122, 2003

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

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

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

Апробация работы и публикации. Основные положения работы докладывались на 26-ой международной конференции MIPRO-2003, Опатия, Хорватия (2003 г), на Всероссийской научной конференции «Научный сервис в сети Интернет», Новороссийск (2003 г), на Всероссийская конференция «Высокопроизводительные вычисления и технологии», Ижевск (2003 г ), на Всероссийской конференции «Мальцевские чтения», Новосибирск (2003 г ), на международной конференции «Программные системы теория и при-

5D Sucra, Distributed query evaluation on semistructured data // ACM Trans Database Syst, 27(1), 1-62, 2002

Z Miao, D Stefanescu, A Thomo, Gnd-Aware Evaluation of Regular Path Queries on Spatial Networks jI Proc of the IEEE 21st Int Ccmf on Advanced Information Networking and Applications, 158-1S5, IEEE Computer Society, 2007

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

По теме диссертации опубликовано 9 печатных работ

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

Краткое содержание работы

Во введении описываются цели и задачи работы, обосновывается ее актуальность, научная новизна и практическая значимость Во введении также приводится краткое содержание работы

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

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

Определение. Полуструктурированным документом называется ориентированный граф с помеченными ребрами Ъ = (V, £, Е, Vo), где V — множество вершин графа, £ — конечное множество меток ребер, ECVxSx V — множество S-помеченных ребер, Vq С V - корневые вершины

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

Определение. Конъюнктивным регулярным путевым запросом называется ориентированный помеченный граф <2 = {X, Ед, Х0), где X — множество вершин запроса (переменных), обозначает множество всех регулярных языков над алфавитом Д, Вд С I х х X — множество помеченных ребер, Хо С X — корневые вершины запроса

Определим теперь семантику С11Р(3 запросов, а именно, — понятие результата вычисления запроса относительно базы данных

Определение. Инъективное отображение ¿и . X V вершин запроса <2 = {X, К^(Д), Хо) в вершины базы данных Ъ = {V, Е, Щ) удовлетворяет запросу, если

1 образы различных вершин запроса различаются,

2 корневые вершины запроса отображаются в корневые вершины базы,

3 смежные вершины запроса, соединенные ребром с меткой Д 6 Ле§(Д), отображаются в вершины базы, соединенные по крайней мере одним путем, метки которого образуют слово из языка И, а именно, —

(хи Я, х}) еЕя=> Ь{/,МАХз))(Ъ) ПД/0,

где обозначает регулярный язык, порожденный в графе

Ъ вершинами ц,{хг) и р,{х3)

Если на множестве X = {х\, Х2, , Хи) вершин запроса С,] введено отношение порядка <, то каждому упорядоченному набору вершин {ун ,ьг2, , базы Ъ можно сопоставить отображение /х X —> V, заданное правилом х3 Уь

Определение. Результатом вычисления запроса С} = [X, Г1е§(Д), Ед, Х^) относительно базы Ъ = (V, 1!, Е, ^о) будем называть множество Я(Ъ) С всех упорядоченных наборов вершин Ъ таких, что соответствующие им отображения \1 X —> V удовлетворяют запросу

Важными частными случаями запросов являются элементарные и тривиальные запросы Элементарным называется запрос вида Ц — Х\КХ2 (без корневых вершин) Результатом его выполнения относительно графа Ъ является множество

<2(2) - {(и, V) е V х V | и ф ь Л ЬМ{Ъ) ПНф0)

Элементарный запрос будем называть тривиальным, если образ Х\ фиксирован Если 1) — г, то результат вычисления такого запроса будем обозначать (¿(Ъьг)

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

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

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

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

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

• «Обращение» ребер Если в процессе вычисления запроса для некоторых вершин запроса х и у, образующих ребро (x,L,y), значения допустимых образов вычислены и требуется уточнить эти значения, учитывая данное ребро,

• Порядок обхода исходящих ребер В том случае, если на основании какой-либо дополнительной информации можно предположить, что вычисления элементарного запроса, соответствующего исходящему ребру текущей вершины, приведет к получению множества большой мощности данное ребро можно временно не рассматривать Например, если вершина запроса имеет два ребра, помеченных языками L\ = (о + b + с)* и ¿2 = (abc)4, то сначала следует рассматривать ребро,

(аЬ|ас)* о -Ю

3 (аЬ[аа):

-О

I* 4

-О

aabcdef 5

Рис 1 Тестовый запрос для оценки эффективности эвристик помеченное языком ¿2

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

Результаты применения описанных эвристик приведен в таблице 1 База данных содержала 100 вершин План, соответствующий просмотру вершин запроса в порядке возрастания их номеров обозначен буквой В Выполнение запроса с обращением всех ребер соответствует столбцу Я Обращение некоторых ребер соответствует столбцу .ОД Различные планы вычисления запросов (изменяются порядок просмотра вершин и направления просмотра ребер) обозначены символами Р\, Количество процессоров обозначе-

но через N

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

Во-вторых, важным является отсутствие, а возможно и снижение производительности при увеличении количества вычислительных узлов Это может быть связано с тем, что ответы равномерно распределены в дереве

В И БЛ Рг Р» Рз РА Ръ Рь

N=1 1069 1565 1237 21 8 771 58 60 4 64 1080 2

N = 2 696 1535 805 20 0 51 8 52 38 2 5 1 569 4

ЛГ = 4 429 1569 519 19 9 44 3 48 26 0 45 302 7

N=-8 348 1572 416 24 2 52 1 79 36 1 81 213 1

Таблица 1 Среднее время вычисления (сек) тестовых запросов при различных планах

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

В заключительном разделе главы предлагается метод вычисления элементарных запросов с использованием материализованных представлений, который основан на решении языковых уравнений Для заданных регулярных языков Ь и Е (запроса и представления) рассматривается уравнение Ь = ЕХ относительно неизвестного языка X Решение уравнения называется максимальным, если оно не содержится ни в каком другом решении Фундаментальным языком уравнения называется язык 0(Ь,Е), являющийся пересечением всех производных Ь по словам из Е

Теорема. Если уравнение Ь — ЕХ относительно X имеет решение, то фундаментальный язык И(Ь: Е) является его максимальным решением Максимальное решение может быть эффективно построено

Если язык М является решением уравнения Ь = ЕХ, то вычисление исходного запроса Ь(Ъ) сводится к вычислению М(Ъ, э), где э пробегает множество {у Е V | Зи € V (и, у) € Е(Ъ)} Приводятся примеры запросов, для которых предлагаемый алгоритм оказывается эффективнее существующих методов вычисления запросов с использованием материализованных представлений

В третьей главе представлено предложенное автором решение задачи оценки сложности элементарного запроса Для этого разрабатывается ме-

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

Построение оптимального плана вычисления запроса невозможно без предварительной оценки трудоемкости выполнения отдельных операций При вычислении конъюнктивных регулярных путевых запросов основной является операция вычисления элементарного запроса В качестве меры сложности запроса предлагается рассматривать мощность результата вычисления запроса В первом разделе главы рассматриваются такие меры сложности регулярных языков, как число состояний минимального автомата, энтропия, автоматность и статистика мотивов (метод оценки числа вхождений регулярного множества слов в случайной последовательности символов) Отмечается, что данные подходы не соответствуют понятию сложности элементарного запроса В последующих разделах главы предлагается мера сложности элементарного запроса, основанная на понятии случайной базы данных, и приводится алгоритм ее вычисления

Пусть £ — конечный алфавит, ар £ —» [0,1] — некоторое отображение Случайным детерминированным И-деревом с параметром р назовем дерево Тр, построенное по следующим правилам

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

• вероятность того, что нелистовая вершина дерева имеет исходящее ребро с меткой а 6 £ есть ра = р(а)

Определение. Вероятностной мерой сложности регулярного языка <2 С £* назовем число

мтр(д) = р{д(тр,г)^0}, (1)

где г обозначает корневую вершину дерева Тр

Теорема. Для любого действительного числа е > О, любого отображения р £ —► [0,1] и любого регулярного языка К значение может быть

вычислено с точностью е

Доказательство проводится ло следующей схеме Без ограничения общности можно считать, что Я является префиксным кодом, поскольку значение /¿ГР(Д) совпадает со значением для максимального префиксного

кода, вложенного в R Пусть А = {Q,q0,'L,S,F) есть детерминированный автомат, такой, что в его графе переходов между любой парой состояний найдется не более одного ребра и L(A) = R Такой автомат всегда существует Обозначим через Lq язык L(Aq), где Ач обозначает автомат, полученный из А смещением начального состояния в а через Cq — его сложность цТ(Ьд) Тогда

P{Lq(Tp) = 0} = 1 - Cq = П il~PaCS{q,a)) (2)

a€S J(S,o)j60

Это приводит к следующей системе соотношений между величинами Cq для всех q S Q

Сд = 1- П (1 - PaCS(<¡,a)) ,если q <£ F,

OES /о\

S(q,a)9¡0

Cq = 1 ,если q € F

Величина C9o соответствует искомому значению f¿T(L)

Далее доказывается, что отображение (3) является сжимающим в гиперкубе 0 ^ Cq < 1 (q € Q) для любых значений ра € [0,1] (а € £), a значит оно имеет единственную неподвижную точку, которую можно вычислить численными методами

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

1 для каждой буква алфавита Е каждая вершина графа имеет не более одного исходящего ребра, помеченного этой буквой,

2 вероятность того, что вершина графа имеет исходящее ребро с меткой а е Е есть ра,

3 конец исходящего ребра выбирается с равной вероятностью из множества вершин графа

Пусть Ф™ — случайная база данных, г — ее выделенная (корневая) вершина, а <5 — элементарный запрос Вычисление <3(Фр, г) можно рассматривать как вычисление запроса относительно, вообще говоря, бесконечного дерева Т°°(Ф£), которое получается из (Фр,г) в результате обхода Ф™ в ширину Можно заметить, что чем длиннее простые пути в Ф™, тем реже встречаются одинаковые поддеревья в дереве Т°° Поскольку математическое ожидание длины простого пути в Ф™ (математическое ожидание длины самонепересекающегося пути при случайном блуждании в полном графе Кп) растет с увеличением п справедливо следующее утверждение

Утверждение Для любого регулярного языка <2 С Е* и любого отображения р Е —» [0,1]

Таким образом, дерево Тр можно рассматривать как приближение Фр Поскольку под синтаксической сложностью запроса понимается некоторая его числовая характеристика, которая не зависит от конкретного экземпляра базы данных, то логичным представляется рассматривать деревья вида Тр, для которых р(а) = р для всех букв алфавита а £ Е Поскольку точное значение р неизвестно, то при определении синтаксической сложности запроса желательно провести некоторое усреднение по возможным значениям этого параметра Такой подход приводит к следующему определению

Определение. Синтаксической сложностью элементарного запроса <2 будем называть величину

Значение 5(<2) может быть получено с помощью численного интегрирования функции /<э(р) = /^Tp(Q) Предлагается метод уточнения значения Е(<2) с использованием материализованных представлений (решение языковых уравнений) и с учетом статистики экземпляра базы данных, которая представляется в виде вероятностного автомата

Тестирование метода определения сложности элементарного запроса проводилось по следующей схеме Для каждого из запросов (случайного регулярного языка) и тестовой базы данных вычислялось точное значение коли-

1ш1 Р{<Э(Ф» ф 0} = /хЭД)

п.—г

(4)

(5)

чества вершин, соответствующих запросу Полученные результаты сравнивались с ожидаемыми значениями, вычисленными на основании меры сложности элементарного запроса Запросы и базы данных генерировались случайным образом Для каждого из тестируемых запросов была проведена серия из 40 испытаний (для каждого испытания генерировалась новая база данных) и выбиралось среднее значение числа достижимых вершин Коэффициент корреляции между расчетными значениями 5(<2) и реальными данными составил 0 877, что подтверждает эффективность предложенной меры сложности регулярного путевого запроса

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

Определение. Ограничениями вершины х запроса С} будем называть набор 7г — (х,ЬС), где х € X, ЬС — подмножество множества инцидентных х ребер, то есть

ЬС С {(ж8, Ь, х3) € Дз ( хг = х или х3 = х} (6)

Порождающую вершину будем обозначать х(тт), & множество ребер — Е(тг) Планом вычисления запроса ф называется такая последовательность П = {Уъ > к к} ограничений, которая содержит все ребра запроса \/е £ Ед 3г ^ К е € 7гг

Вычисление запроса с использованием плана П осуществляется аналогично алгоритму поиска подграфа, со следующим дополнениями Во-первых, последовательность просмотра вершин запроса определяется планом П Первой просматривается вершина аг(7Г1), второй — х^ъ) и так далее Отметим, что вершины ж(7Гг) и х{щ+\) не обязательно являются смежными в графе <2 Во-вторых, одна и та же вершина может встречаться в последовательности (ж(7Гг), г ^ |П|} несколько раз В этом случае при повторном рассмотрении вершины х осуществляется проверка того, что текущий образ этой вершины, зафиксированный при первом ее прохождении, удовлетворяет новым ограничениям И, наконец, если множество Е(щ) содержит входящие относительно вершины х(тгг) ребра, то эти ребра обращаются

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

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

• при выборе смежной вершины запроса предпочтение следует отдавать вершинам с наиболее информативными входящими ребрами (из ранее просмотренных вершин запроса)

Далее предлагается формализация понятий информативности и сложности плана

В качестве информативности вершины запроса предлагается взять «вероятность появления наиболее вероятного дерева», удоветворяющего ограничениям вершины Это значение можно рассматривать как приближение вероятности того, что вершина базы данных может являться образом данной вершины запроса Поскольку конечное S-помеченное дерево может быть представлено в виде конечного языка над алфвитом Е (множество слов, приводящих в листовые вершины), то функция оценки частотности (вероятности) появления заданного дерева есть Еац Fm(£) —» [0,1] Индекс all означает, что в отличие от введенной ранее функции сложности регулярного языка 5, требуется вхождение всех слов из заданного языка Бац-Максимальным покрытием системы регулярных языков {Qi, , Qk} назовем такой конечный язык С £ Fm(E), что (1) Qt Л С Ф 0 для любого г = 1, , к, и (2) для любого конечного языка С" € Fm(E), удовлетворяющего предыдущему условию, выполняется неравенство Еац(С) ^ Зац(С')

Функцию Зац можно задать с использованием введенной ранее функции функции сложности запроса 3 Напрмер, если задан конечный язык F = {рзъДОг}, состоящий из двух слов с общим префиксом р, то в качестве

значения Еац(Г) можно выбрать Н({р})Е({51})Е({в2}) В общем случае такое определение приводит к рекурсивной формуле

Определение. Информативностью ограничения ж вершины х запроса <5 назовем число

/(*) = (2-ЕагКС"))(2-5а»(С+))1 (?)

где С~ и С+ — Нагг-максимальные покрытия множеств регулярных языков, приписанных входящим и исходящим ребрам вершины х, соответственно

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

Определение. Информативностью ребра е — (х,Ь,у) конъюнктивного регулярного путевого запроса будем называть величину

1Щ = 1-Е(1К), (8)

где Ья обозначает обращение языка Ь

Обозначим через п(г) первое вхождение вершины л запроса в плане П Определим на множестве вершин запроса отношение частичного порядка у -<11 2, которое означает, что в запросе есть ребро (у г) и вершина у встречается в плане раньше вершины г Обозначим через Ьху регулярный язык, приписанный в запросе С} ребру между вершинами а; и у, и определим информативность первого посещения вершины х запроса в рамках плана П как

У ~~ /

ш = /(Ф)) 1 + £ 1Ш) куя\ к уг1 (9)

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

Определение. Сложностью плана П = {тг1; , ттц} назовем величину

План П будем называть оптимальным, если для любого другого плана П' вычисления запроса 0 справедливо неравенство Сой£(П) > Сов1{П')

Домножение на убывающую функцию 1 / 1о§(г +1) придает больший вес первым элементам плана, а значит планы, в которых первыми рассматриваются вершины с более информативными ограничениями будут иметь меньшую сложность

Теорема Для любого конъюнктивного регулярного путевого запроса количество планов его вычисления конечно Существует алгоритм нахождения оптимального плана

При тестировании метода в качестве критерия эффективности плана рассматривается количество рекурсивных вызовов, которое делает алгоритм вычисления запроса при использовании заданного плана Тестирование проводилось на случайных запросах Случайный запрос представляет собой случайный граф (вероятность наличия ребра между двумя вершинами равнялась 2/п, где п — число вершин запроса), ребрам которого приписаны случайные регулярные языки над четырехбуквенным алфавитом Тестирование проводилось при п < 6 Для заданного случайного запроса строился оптимальный план его выполнения и сравнивалась эффективность оптимального плана с эффективностью случайных планов выполнения этого запроса Для каждого запроса строилось множество случайных баз данных, для каждой из которых проводилось вычисление запроса с использованием оптимального и нескольких случайных планов

Результаты тестирования показали, что в некоторых случаях существуют планы выполнения запроса, которые оказываются эффективнее построенного оптимального плана Однако в среднем (в общей сложности было выполнено 200 запросов) оптимальные планы оказываются более эффективными Отношение числа рекурсивных вызовов для оптимального плана к среднему значению этого параметра для случайных планов составило 0 55 При этом наблюдается снижение данного параметра при увеличении размера базы данных Для баз данных, содержащих 100 вершин, это отношение

(10)

составило 0 31 Также следует отметить, что около 20% данных лежит в диапазоне от 0 8 до 1 2, что означает наличие нескольких близких по эффективности планов Полученные результаты показывают, что предложенный метод повышает эффективность алгоритма вычисления CRPQ запросов В частности, для запроса, представленного на стр 8, алгоритм построения плана приводит к «почти оптимальному» плану (см табл 1)

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

Реализованный программный комплекс вычисления конъюнктивных регулярных путевых запросов включает следующие подсистемы (модули)

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

• Подсистема хранения данных во внешней памяти Данная подсистема позволяет добавлять и извлекать документы из хранилища и обеспечивает подсистеме вычисления запросов прозрачный доступ к информации во внешней памяти (виртуальная память)

• Подсистема анализа статистических характеристик базы данных

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

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

Подсистема вычисления конъюнктивных регулярных путевых запросов была реализована как в виде функций на языке Mathematica (в целях тестирования разработанных алгоритмов), так и в виде выполняемых файлов, работающих с использованием MPI в среде Linux Общий объем кода подсистемы для операционной системы Linux составляет около 3000 строк на языке С-1—!-

Для хранения документов в дисковой подсистеме применяется блочная организация файлов Каждый файл данных разбивается на блоки фиксированного размера (размер блока зависит от параметров операционной еисте-

Рис 2 Архитектура разработанного программного комплекса

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

Подсистемы оптимизации запросов и построения плана вычисления бала реализована в среде системы символьных вычислений МаЛета^са (с частичным использованием внешних вычислительных модулей для работы с конечными автоматами, которые реализованы на С++) Выбор системы символьных вычислений в качестве языка реализации подсистемы обусловлено использованием в алгоритмах определения сложности элементарного запроса аппарата производящих функций и разложений в ряд Тейлора Применение численных методов для решения подобных задач может привести к значительным вычислительным погрешностям и получению ошибочных результатов

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

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

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

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

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

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

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

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

Список опубликованных работ по теме диссертации

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

2 S Afonm, A Shundeev, V Roganov, «Semistructured data search usmg dynamic parallelisation technology» // «Proceedmgs of the 26th International Convention MIPRO-2003», 152-157

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

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

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

6 S Afonm, Е Khazova, «Membership and Fmiteness Problems for Rational Sets of Regular Languages» // Proc of the Developments m Language Theory, LNCS 3572 / С De Felice and A Restivo eds 88-99, Springer, 2005

7 S Afonm, E Khazova, «Membership and Fmiteness Problems for Rational Sets of Regular Languages» // International Journal of Foundations of Computer Science, 17(3), 493-506, «World Scientific», 2006

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

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

Подписано в печать 28 05 2007 Исполнено 28 05 2007 г Печать трафаретная

Заказ № 546 Тираж 100 экз

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш , (495) 975-78-56 www autoreferat ru

Введение

ГЛАВА 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 является интерпретатором языка высокого уровня описанная в настоящей главе реализация программного комплекса вычисления конъюнктивных регулярных путевых запросов имеет макетный характер. Часть алгоритмов может быть реализована на традиционных языках программирования, что позволит существенно повысить производительность работы подсистемы построения плана вычисления запросов.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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/.