Алгоритмы построения однословной перезаписи регулярных путевых запросов

• Автор: Хазова, Елена Евгеньевна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 135 с. : ил.

Оглавление
Введение

1 Перезапись регулярных путевых запросов и полугруппы регулярных языков

1.1 Вычисление запросов с использованием представлений.

1.1.1 Базы данных, запросы, представления.

1.1.2 Области применения перезаписей запросов

1.2 Перезапись регулярных путевых запросов.

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

1.2.2 Модель полуструктурированных данных

1.2.3 Максимальная перезапись запросов.

1.2.4 Частичная перезапись запросов

1.2.5 Однословная перезапись запросов
1.3 Применение алгоритмических методов алгебры в задачах перезаписи запросов
1.3.1 Перезапись запросов как задача принадлежности для полугруппы регулярных языков.
1.3.2 Поиск перезаписи с дополнительными ограничениями.
1.3.3 Применение задачи равенства слов при перезаписи запросов.
1.3.4 Оценка выразительной силы набора представлений.
1.4 Полугруппы с эффективно решаемой задачей равенства слов
1.4.1 Автоматные полугруппы
1.4.2 Рациональные полугруппы
1.4.3 Полугруппы Клини.
1.5 Выводы.
2 Рациональные множества регулярных языков
2.1 Принадлежность полугруппе и рациональному множеству
2.1.1 Принадлежность рациональному множеству.
2.1.2 Анализ сложности алгоритма проверки принадлежности рациональному множеству .
2.2 Ядро полугруппы или класс эквивалентности
2.2.1 Регулярность класса эквивалентности полугруппы
2.2.2 Алгоритм построения класса эквивалентности
2.2.3 Оптимальная перезапись запроса
2.3 Конечность полугруппы и рационального множества
2.3.1 Конечность полугруппы .
2.3.2 Конечность рационального множества
2.3.3 Анализ сложности алгоритма проверки конечности рационального множества
2.4 Эквивалентность полугрупп и рациональных множеств
2.4.1 Алгоритм проверки вложенности полугрупп
2.4.2 Неразрешимость задачи эквивалентности рациональных множеств .
2.5 Выводы.
3 Задача равенства слов для полугрупп регулярных языков
3.1 К автоматности полугрупп регулярных языков.
3.1.1 Автоматность рациональных полугрупп.
3.1.2 Нерациональность конечно порожденной полугруппы регулярных языков
3.2 Случай однобуквенного алфавита.
3.2.1 Строение полугрупп в случае конечных порождающих элементов .
3.2.2 Строение полугрупп в случае произвольных порождающих элементов,
содержащих пустое слово.
3.2.3 Автоматность полугрупп регулярных языков
3.2.4 Клиновость, рациональность полугрупп регулярных языков.
3.3 Выводы
4 Реализация и тестирование алгоритмов
4.1 Реализованные алгоритмы.
4.1.1 Подсистема вычисления запроса
4.1.2 Построение максимальной перезаписи .
4.1.3 Построение однословной перезаписи
4.2 Эксперименты с перезаписью .
4.2.1 К задаче равенства слов
4.2.2 К константе Хашигучи.
4.3 Выводы
Заключение
Приложения
Литература


Показывается практическая значимость построения класса эквивалентности запроса. Результаты экспериментов показывают, что алгоритмы построения однословных перезаписей можно реализовать на практике. Основные положения данной работы докладывались на конференциях. Developments in Language Theory: 9th International Conference, DLT , Palermo, Italy, July 4-8, . International Conference on Semigroups and Languages. Lisbon, Portugal, July -, . International Conference on Automata and Formal Languages, AFI/, May -, , Dobogykx, Hungary. Международная конференция «Актуальные проблемы вычислительной математики» посвященная памяти академика Н. С. Бахвалова, . International Conference on Automata and Formal Languages, AFL’, May -, , Balatonfured, Hungary. Международная конференция «Алгебра, логика и приложения (Мальцевские чтения)», Новосибирск, г. Результаты, представленные в диссертации, проходили апробацию на механикоматематическом факультете МГУ им. М. В. Ломоносова на семинаре «Проблемы современных информационно-вычислительных систем» иод руководством проф. В. Л. Васенина (, гг. Математической теории интеллектуальных систем механико-математического факультета МГУ им. М. В. Ломоносова па семинаре «Дискретный анализ» под руководством проф. С. В. Алешина, проф. В. А. Буевича, с. М. В. Носова ( г. По теме диссертации опубликовано б печатных работ, в том числе две из них [3,5] в журналах, внесенных в список ВАК. О представлении регулярных языков в виде конкатенации заданных», Е. Е.Хазова // Информационные технологии и программирование: Межвузовский сборник статей. Вып. М.гМГИУ, . Membership and Finiteness Problems for Rational Sets of Regular Languages», Sergey Afonin and Elena Khazova, Lecture Notes in Computer Science // Springer-Verlag GmbH, -, . Membership and Finiteness Problems for Rational Sets of Regular Languages», Afonin S. Khazova E. International Journal of Foundations of Computer Science // World Scientific, (3), 3-6, . А note on finitely generated semigroups of regular languages», Afonin S, Khazova E, International Conference «Semigroups and Languages» // World Scientific, 1-8, . К вопросу об автоматпости полугрупп регулярных языков», Хазова Е. Вестник Московского университета, сер. Semigroups of regular languages over one letter alphabet arc rational », Afonin S. Khazova E. Proceedings of th International Conference on Automata and Formal Languages, AFL:, -, . В данной главе рассматриваются задачи, которые возникают при вычислении запросов с использованием представлений, а также возможные области их практического применения. Вводится модель полуструктурированных данных, описывается математическая постановка задач, которые составляют основное содержание диссертации. Настоящая диссертационная работа посвящена решению задач, которые появляются в ходе вычисления регулярных путевых запросов с использованием материализованных представлений. Задачи, связанные с использованием материализованных представлений могут рассматриваться вне зависимости от конкретного языка запросов или модели данных. В данном разделе приводятся общие постановки задач, которые в контексте данной работы исследуются применительно к модели полуструктурированных данных. Согласно определению, данному в (4], система баз данных — это компьютеризированная система, основное назначение которой заключается в хранении информации, в предоставлении пользователям средства для ее извлечения и модификации. Таким образом, система баз данных включает в себя собственно данные (сохраняемые в базе данных), аппаратное обеспечение, программное обеспечение (в частности, систему управления базами данных -СУБД), а так же пользователей (прикладные программы и конечные пользователи). Одной из важнейших операций, которые выполняются при работе с данными, является выборка хранящейся в базе данных информации. Для получения такой информации, пользователь составляет запрос к базе данных на языке запросов и в ответ получает’ результат его выполнения. Для повышения эффективности работы с данными, система может предоставлять возможность использования представлений.