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

• Автор: Афонин, Сергей Александрович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 130 с. : ил.

ОГЛАВЛЕНИЕ
Введение

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

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

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

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

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

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

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

1.4. Методы оптимизации СР3запросов

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

1.4.2. Вычисление при наличии представлений.
1.4.3. Эквивалентность и вложенность запросов.
1.4.4. Усечение запроса с использованием схемы
1.5. Выводы
ГЛАВА 2. Базовые методы вычисления запросов
2.1. Стратегии вычисления запросов
2.1.1. Вычисление элементарного запроса.
2.1.2. Стратегии вычисление СИРС запроса.
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. Разложение СР3 запросов.
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. Выводы
Заключение
СПРСОК ИЛЛЮСТРАЦИЙ
1.1 Алгоритм поиска подграфа в графе
2.1 Алгоритм поиска вершин, достижимых относительно заданного
регулярного языка.
2.2 Построение допустимых образов методом слияния результатов .
2.3 Окрестность вершины запросы.
2.4 Тестовый запрос для оценки эффективности эвристик.
2.5 Декомпозиция запроса
3.1 Построение автомата из автомата А,.
3.2 Зависимость разности хг от р.
3.3 Результаты оценки сложности запроса.
4.1 Выразительные возможности плана.
4.2 Примеры тестовых конъюнктивных запросов
5.1 Архитектура разработанного программного комплекса
5.2 Алгоритм вычисления запроса МаМетайса
5.3 Алгоритм вычисления запроса по заданному плану
МаШетайса
5.4 Алгоритм построения максимальной перезаписи МаетаНса.
5.5 Алгоритм решения линейного языкового уравнения
МаЛетаНса
5.6 Алгоритм построения случайного плана МаМетайса.
5.7 Алгоритм поиска оптимального плана МаМетаса.
5.8 Алгоритм вычисления сложности плана МаШетаЫса
СПИСОК ТАБЛИЦ
1.1 Локальные ограничения.ЗО
2.1 Характеристики тестовых запросов
2.2 Время выполнения в секундах тестовых запросов.
2.3 Среднее время вычисления сек тестовых запросов при различных планах
4.1 Сравнительная эффективность планов вычисления запросов
5 , п 5.
4.2 Сравнительная эффективность планов вычисления запросов 3 0
ВВЕДЕНИЕ
Актуальность


На основании проведенных численных экспериментов предложен ряд оригинальных эвристик, повышающих эффективность алгоритма вычисления конъюнктивных регулярных путевых запросов. Предложен новый метод вычисления регулярных путевых запросов с учетом материализованных представлений, основанный на решении языковых уравнений с регулярными коэффициентами. Предложен новый подход к определению сложности регулярного путевого запроса. Формализовано понятие плана вычисления конъюнктивного регулярного путевого запроса, сложности плана и предложен алгоритм построения эффективного плана вычисления конъюнктивных регулярных путевых запросов. Реализован программный комплекс для вычисления конъюнктивных регулярных путевых запросов, который может работать на многопроцессорных вычислительных системах с разделяемой памятью. Проведено тестирование, результаты которого подтверждают эффективность разработанного комплекса. Научная новизна. В работе впервые рассматривается задача построения эффективного плана вычисления запроса. Ранее подобная задача рассматривалась только в контексте территориально распределенных данных [,]. Предлагается новый метод определения сложности регулярного языка, который позволяет оценить сложность вычисления регулярного путевого запроса. Впервые формализовано понятие плана вычисления конъюнктивного регулярного путевого запроса, предложен метод оценки сложности плана и алгоритм построения эффективного плана. Предложен новый подход к проблеме вычисления регулярных путевых запросов с использованием материализованных представлений. Существующие методы решения данной задачи основываются на построении максимальной перезаписи запроса, которая может обладать значительной избыточностью. Предлагаемый подход основан на решении языковых уравнений с регулярными коэффициентами и позволяет находить более эффективные перезаписи. Практическая ценность. Результаты работы могут быть использованы при разработке систем управления полуструктурированными данными, основанных на графовой модели данных, в частности, в системах интеграции данных и информационно-поисковых системах, учитывающих логическую структуру документов. Разработаный в рамках данной работы прототип программного комплекса оптимизации и вычисления конъюнктивных регулярных путевых запросов является частью Автоматической Системы Информационного Обеспечения (АСИО), которая создается в НИИ Механики и Институте проблем информационной безопасности МГУ им. М.В. Ломоносова. Доклады и публикации. Основные положения работы докладывались на -ой международной конференции М1Р0-, Опатия, Хорватия ( г. Всероссийской научной конференции «Научный сервис в сети Интернет», Новороссийск ( г. Всероссийская конференция «Высокопроизводительные вычисления и технологии», Ижевск ( г. Всероссийской конференции «Мальцевские чтения», Новосибирск ( г. Программные системы: теория и приложения», ИПС РАН, г. Переславль-Залесский ( г. Developments in Language Theory», Палермо, Италия ( г. Semigroups and Languages», Лиссабон, Португалия ( г. Finnish Data Processing Week», Петрозаводск ( г. МГУ им. М. В. Ломоносова на семинаре «Проблемы современных информационновычислительных систем» под руководством проф. В. А. Васенина ( г. ИСП РАН ( г. Московской секции SIGMOD ( г. Афонин С. А. «Стратегии вычисления регулярных путевых запросов» // Информационные технологии и программирование. Сборник статей. Вып 5, стр. ММГИУ, . S. Afonin, A. Shundeev, V. Афонин С. А., «Параллельное вычисление запросов к базам иолуструк-турированных данных» // Сборник трудов Всероссийской конференции «Высокопроизводительные вычисления и технологии», Ижевск , стр. Васенин В. А., Афонин С. А. «К разработке моделей эффективного поиска информации в сети Интернет», Сборник трудов Всероссийской научной конференции «Научный сервис в сети Интернет », стр. Васенин, В. А., Афонин, С. А., Козицын А. С., Шундеев А. С. «Поиск в сверхбольших хранилищах данных и высокопроизводительные системы с массовым параллелизмом» // Труды международной конференции «Программные системы: теория и приложения», ИПС РАН / Под редакцией С. М. Абрамова. Том 1, стр. М.: Физматлит, . S. Afonin, Е.