Содержание к диссертации
Введение
ГЛАВА 1. Конъюнктивные регулярные путевые запросы 13
1.1. Основные понятия и обозначения 13
1.2. Модель данных и язык запросов 18
1.2.1. Структура данных 18
1.2.2. Язык запросов 20
1.2.3. Ограничения целостности 27
1.3. Вычисление запроса как поиск подграфа в графе 35
1.4. Методы оптимизации CRPQ-запросов 38
1.4.1. Индексные структуры 38
1.4.2. Вычисление при наличии представлений 42
1.4.3. Эквивалентность и вложенность запросов 44
1.4.4. Усечение запроса с использованием схемы 47
1.5. Выводы 50
ГЛАВА 2. Базовые методы вычисления запросов 52
2.1. Стратегии вычисления запросов 53
2.1.1. Вычисление элементарного запроса 53
2.1.2. Стратегии вычисление CRPQ запроса 54
2.1.3. Сравнение стратегий 56
2.2. Эвристики 58
2.2.1. Эвристики обхода вершин запроса 58
2.2.2. «Обращение» ребер 59
2.2.3. Порядок обхода исходящих ребер 60
2.2.4. Наложение локальных ограничений 61
2.2.5. Вычисление запроса с учетом эвристик 62
2.3. Декомпозиция запросов 64
2.3.1. Разложение CRPQ запросов 64
2.3.2. Разложение элементарных запросов 65
2.4. Выводы 71
ГЛАВА 3. Оценка сложности элементарного запроса 73
3.1. Сложность запроса и меры сложности регулярных языков 73
3.2. Мера сложности путевого запроса 77
3.2.1. Определение меры сложности путевого запроса 77
3.2.2. Вычисление сложности путевого запроса 79
3.2.3. Свойства меры сложности путевого запроса 85
3.3. Оценка сложности элементарного запроса 86
3.3.1. Синтаксическая сложность элементарного запроса 86
3.3.2. Оценка мощности результата элементарного запроса 88
3.3.3. Использование статистики базы данных 90
3.4. Результаты тестирования 94
3.5. Выводы 95
ГЛАВА 4. Построение плана вычисления запроса 97
4.1. Понятие плана вычисления запроса 98
4.2. Определение сложности плана 99
4.2.1. Информативность вершины запроса 100
4.2.2. Информативность ребра запроса 103
4.2.3. Сложность плана 104
4.3. Алгоритм построения плана 105
4.4. Результаты применения планов 106
4.5. Выводы 110
ГЛАВА 5. Архитектура реализованного программного комплекса 111
5.1. Подсистема вычисления запросов 112
5.2. Подсистема хранения данных 114
5.3. Подсистема оптимизации запросов 115
5.3.1. Построение перезаписи элементарного запроса с учетом представлений 116
5.3.2. Построение плана вычисления запроса 118
5.3.3. Оценка сложности плана 120
5.4. Выводы 121
Заключение
- Модель данных и язык запросов
- Стратегии вычисление CRPQ запроса
- Вычисление сложности путевого запроса
- Построение перезаписи элементарного запроса с учетом представлений
Введение к работе
Актуальность темы. Необходимость интеграции данных из автономных, независимо администрируемых, информационных источников естественным образом приводит к задаче управления данными с неоднородной, часто изменяющейся или частично неизвестной структурой. Такие данные принято называть полуструктурированными. Примерами возникновения полуструктурированных данных являются системы интеграции данных в Интернет или в крупных корпоративных или государственных информационных системах. Отдельные компоненты (сайты или ведомственные информационные системы) могут содержать строго структурированные данные (общая структура 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» I/ Proceedings of the «Finnish Data Processing Week Conference (FDPW-2005)», стр. 8-19, 2006
Афонин C.A. «Алгоритмы эффективного вычисления конъюнктивных регулярных путевых запросов» // Вычислительные технологии, 12(2), 23-32, 2007.
Структура работы. Диссертационная работа состоит из введения, четырех глав и приложения. В первой главе приводится формальная постановка задачи поиска полуструктурированных данных, описываются основные модели данных и языки запросов, проводится анализ известных методов вычисления и оптимизации конъюнктивных регулярных путевых запросов.
Во второй главе рассматриваются основные алгоритмы, стратегии и эвристики, влияющие на эффективность вычисления запросов, приводятся экс-перементальные данные, позволяющие провести сравнительный анализ эффективности различных стратегий. В этой главе приводится решение задачи представления регулярного путевого запроса в виде конкатенации (композиции) двух запросов. Результаты, представленные в этой и последующих главах, получены автором в рамках настоящей диссертационной работы.
В третьей главе представлено предложенное автором решение задачи оценки сложности элементарного запроса. Для этого вводится новый метод определения сложности регулярного языка, который основывается на модели вычисления регулярного путевого запроса относительно древовидной базы данных.
В четвертой главе формализуется понятие плана вычисления конъюнктивного регулярного путевого запроса, описывается алгоритм построения оптимального плана. Приводятся результаты тестирования разработанных алгоритмов.
В заключительной пятой главе приводится архитектура разработанного пргораммного комплекса вычисления регулярных путевых запросов и описываются детали его реализации.
Общий объем работы составляет 130 страниц (включая список использованной литературы). Список литературы содержит 72 наименования.
Модель данных и язык запросов
Структура данных Для графового представления полуструктурированных данных стандартом де-факто является так называемая Object Exchange Model или OEM-модель, которая разрабатывалась для обеспечения унифицированного представления сложных информационных объектов в системе интеграции данных LORE [53]. В соответствии с этой моделью сложные структуры данных представляются в виде ориентированного графа с помеченными ребрами. Вершины графа соответствуют элементам первоначальной структуры данных, а ребра представляют отношения между ними. Представление данных в виде ориентированного графа с помеченными ребрами является достаточно универсальным. В рамках этой модели естественным образом реализуются конструкторы множества и кортежа, а данные, представленные в таком виде являются самоопределяющими, то есть содержат не только собственно данные, но и их структуру.
Приведем формальное определение полуструктурированного документа, которое будет использоваться в дальнейшем.
Определение 1.1. Полуструктурированным документом называется ориентированный граф с помеченными ребрами Ъ = (V,E,E, Vo), где V — множество вершин графа, Е — конечное множество меток ребер, Е С V х Е х V — множество Т,-помеченных ребер, Vo С V - корневые вершины.
Корневые вершины отражают деление документа на составные части, что позволяет не делать различия между отдельным документом и коллекцией документов, а именно, —базой данных. В дальнейшем понятия полуструктурированный документ и база полуструктурированных данных будут использоваться как синонимы.
Встречается несколько вариаций данного определения, которые в основном сводятся к следующему.
Множество Е может быть конечным или бесконечным. Например, Е может включать действительные числа. Формально это противоречит определению алфавита, однако как будет ясно в дальнейшем, такое расширение не является существенным для вычисления запросов, поскольку база данных является конечным объектом и всегда можно рассматривать лишь конечное подмножество возможных меток.
В некоторых случаях вместо произвольных ориентированных графов рассматривают упрощенные структуры, например, ацикличные графы или деревья.
Вершинам базы данных могут быть приписаны дополнительные метки. Этот подход является альтернативой включения множества допустимых значений атомарных объектов в алфавит Е.
Представление XML-документов в виде полуструктурированных данных. OEM-модель, обладая гибкостью представления различных данных, не может быть напрямую применена для представления XML-документов. Основными различиями между XML и полуструктурированными данными являются отсутствие порядка в OEM-модели (исходящие ребра неупорядочены) и наличие атрибутов у элементов XML (исходящие ребра в OEM однотипны и отличаются только метками).
Возможными способами представления XML-документов в рамках ОЕМ-модели являются [67]: отказ от порядка дочерних элементов и от различия между атрибутами и дочерними элементами в XML документе; представление атрибутов и порядковых номеров элементов за счет введения дополнительных элементов в алфавит меток и дополнительных вершин в графе.
Язык запросов Языки запросов к базам полуструктурированных данных проектируются с учетом главной особенности таких данных — отсутствием единой, строго определенной, схемы. Семантически одинаковые фрагменты базы данных могут иметь различную структуру данных. Язык запросов должен содержать специальные механизмы, обеспечивающие получение «осмысленного» результата даже при несоответствии структуры данных в различных фрагментах базы данных.
В основе языка запросов должна лежать (образующая алгебру) совокупность базовых операций над объектами, включающая операции поиска (фильтрации) данных и построения новых объектов. Классическим примером такой системы является реляционная алгебра Кодда. Для различных моделей полуструктурированных данных известно несколько таких систем операций [10,53,61,72]. В данной работе будем рассматривать только одну, наиболее трудоемкую операцию — поиск данных, удовлетворяющих заданным условиям. Вопросы построения новых объектов, преобразования и изменения данных, которые в случае OEM модели сводятся к преобразованию графов (например, [34]), затрагиваться не будут.
Стратегии вычисление CRPQ запроса
Вычисление элементарного запроса является наиболее часто выполняемой операцией, так как она соответствует проверке смежности вершин графа. Приведем алгоритм вычисления элементарного запроса, который использовался при тестировании (рис. 2.1).
Решалась задача в следующей постановке: для заданного помеченного графа G, определенного на Е регулярного выражения а, и некоторой вершины v определить множество Ra(v) вершин G, таких что Viu Є Ra{vo)Bvi,...,Vk : (vi,«x+i) E Е,ы = v,vk = w и цепочка e(vi,vi+i) удовлетворяет a.
Данная задача решается методом, аналогичным волновому алгоритму определения всех вершин, достижимых из заданной вершины в ориентированном графе. Предварительно по заданному регулярному выражению а строится недетерминированный конечный автомат М — (Q, Е, 8, % F). Через 8м обозначим функцию перехода, которая выполняет замыкание относительно пустых переходов.
Для каждой вершины, принадлежащей фронту волны, известно текущее состояние конечного автомата. Волна переходит только в те вершины, которые связаны с данным ребром, помеченным допустимым относительно текущего состояния НКА символом. Если при переходе мы попадаем в уже известную пару (vi,q), то вершина v,- не добавляется к новому фронту поскольку повторное ее прохождение при том же состоянии НКА не может расширить результирующее множество. При каждом новом переходе НКА проверяется на достижении заключительного состояния, что означает нахождение искомой вершины.
Данный алгоритм требует 0(Q V) затрат памяти. Временные затраты составляют 0{QVA{%)\og2{Q)hg{V)), где А(Ъ) обозначает максимальную степень вершины в базе данных Ъ.
Стратегии вычисление CRPQ запроса Рассмотрим основные стратегии вычисления CRPQ запросов. Первая стратегия, исчерпывающий поиск, является по сути алгоритмом поиска подграфа. Вторая стратегия предполагает вычисление элементарных запросов и последующее слияние результатов.
Исчерпывающий поиск Очевидная стратегия вычисления запроса состоит в последовательном, исчерпывающем поиске допустимых образов для переменных xi,...,xn. Поиск начинается с корня базы данных, для которого вычисляется множество достижимых относительно Лі вершин. Для каждого допустимого образа х\ рекурсивно производится поиск допустимых образов Ж2 и так далее до тех пор, пока не будут рассмотрены все переменные.
Изложенная стратегия соответствует применению алгоритма Ульмана (рис. 1.1 на стр. 36) с «переопределенным» отношением инцидентности. Её очевидным недостатком является потенциальная возможность быстрого разрастания дерева перебора. Такое свойство обусловлено тем, что для некоторых регулярных выражений число достижимых вершин может быть велико. Описанный далее метод вычисления запросов позволяет более эффективно использовать структуру запроса для уменьшения возможного перебора.
Проверка того, являются ли две вершины базы данных смежными относительно заданного регулярного выражения, требует полиномиального (относительно размера базы данных и регулярного выражения) времени и требует, вообще говоря, обхода всей базы данных.
Слияние результатов Другой возможной стратегией является вычисление каждого встречающего в запросе выражения вида yRz, и последующее слияние результатов (см. рис. 2.2). Вычисление запроса данным методом можно разделить на следующие три этапа.
На первом этапе для каждого встречающего в запросе регулярного выражения xRy производится вычисление множества iVXj, всех пар вершин базы данных, удовлетворяющих R.
Второй этап состоит в построении и последовательном уточнении множества допустимых значений Dx для переменных хо,...,хп. Вершина v базы данных может считаться допустимым значением для некоторой переменной х, если для каждой смежной с ней переменной у найдется такое допустимое значение w, что пара (и, w) удовлетворяет языку L(aq(x,y)). В алгоритме, представленном на рис. 2.2, f(Nxy) и s(Nxy) обозначает множество всех первых или вторых элементов соответственно.
Заключительная стадия — перебор возможных значений XQ, ..., хп и проверка их соответствия запросу. На этом этапе может использоваться алгоритм перебора с отсечением. Перебор значений необходим, поскольку не каждый набор допустимых значений соответствует запросу.
Метод слияния результатов позволяет использовать (по крайней мере частично) информацию обо всех регулярных выражениях запроса до начала перебора. Однако сложность поиска всех пар вершин, удовлетворяющих выражению R, составляет 0(V2 \R\). Использование индексных структур для регулярных путевых запросов (см. 1.4.1.) позволяет повысить эффективность вычисления всех пар вершин, соответствующих языку, однако в худшем случае приводит к таким же затратам.
Вычисление сложности путевого запроса
Вычисление сложности путевого запроса Регулярный язык С называется префиксным кодом, если он не содержит слов, являющихся собственным префиксом другого слова этого языка. Определение 3.2. Порождающим (префиксным) кодом регулярного языка L С Е назовем префиксный код С С Е такой, что: l.CC L;
2. для любого слова и из L язык С содержит либо это слово, либо некоторый его собственный префиксуй Є L 3w, w Є Е :w Є C,u = ww .
Утверждение 3.1. Для любого регулярного языка L С Е существует единственный порождающий код, который мы будем обозначать GC(L).
Доказательство. Предположим, что Сі и Сг — различные порождающие коды для L. Для определенности будем считать, что найдется такое слово w Є Сі, что w . Сг. По определению Сі С L, а значит w Є L. Так как Сг — порождающий код языка L и w . Сг, то Сг содержит некоторый собственный префикс гі/о слова w, причем гУо Є L. Из этого следует, что и Сі содержит WQ или его префикс, однако это противоречит определению префиксного кода, так как WQ есть префикс w, a w Є Сі. Полученное противоречие опровергает предположение о наличии различных порождающих кодов.
Докажем теперь, что для любого языка L существует порождающий код. Обозначим множество всех префиксных кодов в алфавите Е через VC . Рас смотрим множество VC-,{L) = {С Є ТСъ : С С L} префиксных кодов, содержащихся в языке L. Для любого линейно упорядоченного (по включе нию) подмножества А С VCz(L) объединение всех элементов А принадлежит VCz(L). В соответствии с леммой Цорна множество VCY,{L) имеет точную верхнюю грань. Утверждение 3.2. Для любого регулярного языка L его мера совпадает с мерой порождающего кода GC(L): /ІЗД = цТр(ССЩ). Доказательство. Пусть w есть некоторое слова из L,&w — соответствующее ему слово порождающего кода GC(L). Очевидно, что если дерево Т (для некоторого значения п) имеет путь w, то оно имеет и более короткий путь w . То есть Р{ш {Т, г)ф0\ w(T, г) 0} = 1.
Следующее утверждение позволяет получить эффективный алгоритм вычисления порождающего кода регулярного языка.
Утверждение 3.3. Пусть A = (Q, #о, , 8, F) — детерминированный автомат, соответствующий языку L С Е . Тогда автомат A! = (Q, qo, Е, S , F), где 6 {q,a)= 5(q,a), q$F 0, qeF соответствует порождающему коду GC(L).
Доказательство. Покажем сначала, что V — L(A ) — префиксный код. Пусть и/ — некоторый собственный префикс слова w Є V. Если w Є І/, то qow = f для некоторого заключительного состояния f Є F автомата А . Поскольку А — ДКА, а заключительные состояния не имеют допустимых переходов, то из этого следует, что w . L , а значит V — префиксный код.
Включение языка L(A ) С L{A) следует из построения автомата А . Оста лось доказать, что для любого слова w Є L язык V содержит либо само слово w, либо некоторый его префикс. Так как А — ДКА, то для любого слова ги є L(A) длины т существует единственная последовательность со стояний q qij,. .,ftTO ( = 0, qim Є F), переходы которой образуют слово w. Если эта последовательность не содержит заключительных состояний (за исключением qim), то по построению автомата A w Є L(A ). Если же найдет ся такое р т, что д,р Є F и qi} F для всех j р, то в автоматах А к А есть путь Фп ф2» і 7ір, а значит язык V содержит префикс w = сцх... afp_x слова w. О
Таким образом, задача вычисления fjTp(L) сводится к вычислению nTp(GC(L)). Далее будем предполагать, что L — префиксный код. Пусть A = (Q, 0) Е, 5, F) — детерминированный автомат, соответствующий языку L и удовлетворяющий условию Vg,q Є Q \{a Є E : %, a) = q }\ 1. (3.2)
Это условие означает, что в графе переходов автомата А между любой парой состояний найдется не более одного ребра. Такой автомат всегда существует. Например, его можно получить из минимального автомата для L путем разделения состояний q , которые не удовлетворяют условию 3.2. Обозначим через Lq язык L(Aq)2, а через Cq — его сложность fiT(Lq). Рассмотрим процедуру вычисления элементарного запроса L относительно дерева Тр. Предположим, что в процессе вычисления запроса «волна» оказалась в вершине і дерева при состоянии q автомата А. Так как L = GC(L), то S(f,a) = 0 для любого заключительного состояния / Є F и любого символа а Є Е, а язык L(Af) содержит только пустое слово. Следовательно, С/ = 1 для всех / Є F. Пусть теперь q F. Это означает, что найдется такой символ а Є Е, что S(q, а) ф 0. Пусть S(q, а) = q , а для всех символов а Є Е \ {a} 6(q, а) = 0. В этом случае вершина t дерева имеет допустимое продолжение с первым символом а с вероятностью paCs(q,a), а, значит, Cq = PoQ(9,a)- Рассмотрим случай, когда состояние q имеет более одного исходящего ребра. Для каждого исходящего ребра q - q автомата вероятность того, что вершина t дерева не имеет допустимого продолжения с первой буквой а есть, очевидно, 1 — paCs(qA)-
Построение перезаписи элементарного запроса с учетом представлений
Данная подсистемы бала реализована в среде системы символьных вычислений Mathematica (с частичным использованием внешних вычислительных модулей для работы с конечными автоматами, которые реализованы на C++). Выбор системы символьных вычислений в качестве языка реализации связано с использованием в алгоритмах определения сложности элементарного запроса аппарата производящих функций и разложений в ряд Тейлора. Применение численных методов для решения подобных задач может привести к значительным вычислительным погрешностям и получении ошибочных результатов.
Построение перезаписи элементарного запроса с учетом представлений Реализованы два алгоритма построения перезаписи запроса: построение максимальной точной перезаписи (рис. 5.4) и решения линейного языкового уравнения с регулярными коэффициентами (рис. 5.5).
Реализация алгоритма построения максимальной перезаписи регулярного путевого запроса в точности следует работе [65]. Сначала производится минимизация автомата, представляющего запрос. Минимальный автомат сохраняется в переменной da. После этого строится недетерминированный автомат al, состояниями которого являются состояния автомата da, а между состояниями і и j существует переход, помеченный символом, соответствующим языке е из заданного набора представлений Е, если в автомате da найдется путь между состояниями і и j, метки которого образуют слов из е. Вычисление этого условия осуществляется путем проверки пустоты пересечения регулярных языков е и SetlnitialFinalFA[da, {і}, {j}]. Последний язык задается автоматом da с измененными начальными и заключительными состояниями. Заключительным шагом алгоритма является построения допол нение автомата al.
Отметим, что в работе [65]доказывается экспоненциальная нижняя оценка алгоритмической сложности задачи вычисления максимальной перезаписи, а значит приведенный алгоритм является оптимальным.
Алгоритм поиска оптимального плана вычисления запроса приводится на рис. 5.7. В этой реализации используется встроенная функция TimeConstrained системы Mathematica, которая производит вычисление выражения, заданного в качестве ее первого аргумента с заданными ограничениями на время его выполнения. Если вычисления дляться больше указанного интервала времени (на рис. 5.7 используется значение 120 секунд), то возвращается значение, которое является третьим аргументом функции TimeConstrined.
Основная часть алгоритма поиска оптимального плана является первым аргументом функции TimeConstrained. В этой части кода производится построение заданного количества случайных планов вычисления запроса, причем на каждой итерации производится сравнение сложности текущего плана со сложностью лучшего из ранее рассмотренных планов. Если текущий план оказывается более эффективным, то изменяется значение переменной brp (best randpom plan). Семантика функции TimeConstrained гарантирует, что на поиск плана будет затрачено определенное количество времени. Если за этот промежуток система не успеет проверить требуемое количество случайных планов (в данном случае, 50), то результатом работы функции будет тот план, который удалось найти за отведенное время.
Основными результатами являются следующее. Описанные в диссертационной работе алгоритмы построения плана вычисления запроса реализованы в системе символьных вычислений Mathematica. Вычислительно трудная задача вычисления конъюнктивного регулярного путевого запроса реализована с использованием системы автоматического динамического распараллеливания программ OpenTS, что позволяет проводить вычисление как на однопроцессорных вычислительных системах, так и на многопроцессорных комплексах с разделяемой памятью.
Подсистема хранения документов во внешней памяти реализована таким образом, что функция вычисления запроса получает прозрачный доступ к данным на диске.
Поскольку система Mathematica является интерпретатором языка высокого уровня описанная в настоящей главе реализация программного комплекса вычисления конъюнктивных регулярных путевых запросов имеет макетный характер. Часть алгоритмов может быть реализована на традиционных языках программирования, что позволит существенно повысить производительность работы подсистемы построения плана вычисления запросов.
В рамках настоящей работы автором были получены следующие результаты. На основании проведенных численных экспериментов предложен ряд оригинальных эвристик, повышающих эффективность алгоритма вычисления конъюнктивных регулярных путевых запросов. Предложен новый метод вычисления регулярных путевых запросов с учетом материализованных представлений, основанный на решении языковых уравнений с регулярными коэффициентами. Предложен новый подход к определению сложности регулярного путевого запроса. Формализовано понятие плана вычисления конъюнктивного регулярного путевого запроса, сложности плана и предложен алгоритм построения эффективного плана вычисления конъюнктивных регулярных путевых запросов. Реализован программный комплекс для вычисления конъюнктивных регулярных путевых запросов, который может работать на многопроцессорных вычислительных системах с разделяемой памятью. Проведено тестирование, результаты которого подтверждают эффективность разработанного комплекса.
