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

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

ии^4Б1752

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

Хазова Елена Евгеньевна

АЛГОРИТМЫ ПОСТРОЕНИЯ однословной ПЕРЕЗАПИСИ РЕГУЛЯРНЫХ ПУТЕВЫХ ЗАПРОСОВ

Специальность 05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Л,

Москва - 2009 <%

'-У

003461752

Работа выполнена в Научно-исследовательском институте механики

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

Научный руководитель: доктор физико-математических наук,

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

Официальные оппоненты: доктор физико-математических наук,

профессор Алешин Станислав Владимирович (Московский государственный университет имени М.В. Ломоносова)

доктор технических наук, профессор Кузнецов Сергей Дмитриевич (Институт системного программирования Российской Академии Наук)

Ведущая организация: Институт математики имени С.Л. Соболева

Сибирского отделения РАН

Защита диссертации состоится 25 февраля 2009 г. в 16 ч. 45 мин. на заседании диссертационного совета Д.501.002.16 при Московском государственном университете имени М.В.Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В.Ломоносова, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 22 января 2009 г.

Ученый секретарь

диссертационного совета Д.501.002.16 при МГУ доктор физико-математических наук

/^А.А. Корнев

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

Актуальность темы. Современное общество, которое принято именовать информационным, характеризуется тем, что эффективные технологии обработки данных во многом определяют успехи в области материального производства, в научно-технической, социально-экономической и в политической сферах деятельности человека. В условиях быстрого развития сетевой инфраструктуры и объемов, сосредоточенных в ней данных, методы их поиска, систематизации и анализа на сегодня отстают от возрастающих еще более высокими темпами потребностей общества. Одна из причин сложностей, возникающих на пути их удовлетворения, связана с существенно неоднородным характером подлежащей обработке информации, как с позиции поддерживающей ее аппаратно-программной платформы, так и в плане модели представления этих данных. На сегодня сложно представить себе случай, когда интересующие пользователя практически значимые данные могут находиться под управлением традиционной реляционной СУБД, какой либо другой модели их описания (модели данных) или системы. Для того, чтобы удовлетворять такие потребности, необходимо интегрировать данные из автономных, независимо администрируемых информационных источников, как правило, слабо связанных между собой или обладающих разной моделью описания данных. Как следствие, задача управления данными с неоднородной, перманентно изменяющейся или частично неизвестной структурой становится практически важной и актуальной. Такие данные принято называть слабоструктурированными или полуструктурированными. Далее чаще используется второе из этих определений.

Одним из результатов в задаче поиска информации по разнородным источникам данных является новая абстракция управления информацией, именуемая пространством данных1'2'3. Цель поддержки пространства данных состоит в обеспечении базового набора функций над всеми источниками данных. Понятие пространства данных предполагает поддержку нескольких уровней доступа к информации, отличающихся степенью детальности описания данных. На самом нижнем уровне поддерживается поиск по клю-

аМ. FVanklin, A. Halevy, D. Maier, From databases to dataspaces: A new abstraction for information management // SIGMOD Rec., 34(4), 27-33, ACM Press, 2005

2M. Franklin, A. Halevy, D. Maier, Principies of dataspace systems // Proc. of the 25th SIGMOD symp. on Principies of database systems, 1-9, ACM Press, 2006

3M.A. Vaz Salles, J.-P. Dittrich, S. Karakashian et al, iTrails: pay-as-you-go information integration in dataspaces // Proc. of the 33rd int. conf. on Very large data bases, 663-674, VLDB Endowment, 2007

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

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

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

1. Формализуется понятие ограничения на структуру перезаписей и разрабатывается алгоритм построения однословной перезаписи при наличии дополнительного ограничения.

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

3. Разрабатываются алгоритмы построения всех возможных однословных перезаписей запроса.

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

Научная новизна. С учетом введенного в диссертации понятия однословной перезаписи регулярных путевых запросов и формулировки основной задачи в терминах полугрупп регулярных языков, научной новизной обладают следующие ее результаты. Решена задача принадлежности регулярного языка рациональному подмножеству полугруппы регулярных языков, что является обобщением результатов Хашигучи4. Сформулировано условие конечности полугруппы и рационального множества регулярных языков, которое существенно сильнее критериев конечности5'6, справедливых для произвольных полугрупп. Исследована структура полугрупп регулярных языков, доказана регулярность класса эквивалентности. Доказано, что полугруппы регулярных языков над однобуквенным алфавитом являются рациональными, автоматными и полугруппами Клини.

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

Апробация работы. Основные положения работы докладывались на международной конференции «Developments in Language Theory», Палермо, Италия (2005 г.), на международной конференции «Semigroups and Languages», Лиссабон, Португалия (2005 г.), на международной конференции «Automata and Formal Languages», Добогоко, Венгрия (2005 г.), на международной конференции «Актуальные проблемы вычислительной математики» посвященной памяти академика Н.С. Бахвалова (2006 г.), на механико-математическом факультете МГУ им. М. В. Ломоносова на семинаре «Проблемы современных информационно-вычислительных систем» под руководством проф. В. А. Васенина (2005 г., 2007 г.), на международной конференции «Automata and Formal Languages», Балатонфюред, Венгрия (2008 г.), на международной конференции «Мальцевские чтения», Новосибирск (2008 г.), на кафедре Математической теории интеллектуальных

4К. Hashiguchi, Representation theorems on regular languages // Journal of computer and system sciences, 27, 101-115, 1983

5A. de Luca, A. Restivo,Л finiteness condition for finitely generated semigroups // Semigroup forum 28, 123-134, 1984

6S. Varricchio, A finiteness condition for finitely generated semigroups // Semigroup Forum, 38(1), 331335, Springer New York, 1989

систем механико-математического факультета МГУ им. М. В. Ломоносова на семинаре «Дискретный анализ» под руководством проф. С. В. Алешина, проф. В. А. Буевича, с.н.с. М. В. Носова (2008 г.).

Публикации. По теме диссертации опубликовано 6 печатных работ, в том числе две из них [3,5] в журналах, внесенных в список ВАК.

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

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

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

3. Доказана регулярность класса эквивалентности конечно порожденной полугруппы регулярных языков. Разработан алгоритм, позволяющий построить регулярный язык, который соответствует классу эквивалентности полугруппы.

4. Исследованы свойства полугрупп регулярных языков над однобуквен-ным алфавитом, доказана их рациональность. Разработан алгоритм, выписывающий автоматную структуру для данных полугрупп.

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

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

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

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

Первая глава является вводной, в ней рассматриваются задачи, которые возникают при вычислении запросов с использованием представлений. К их числу относятся:

• выразимость запроса через набор представлений;

• эквивалентность перезаписей запросов;

• пустота пересечения множеств запросов;

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

• эквивалентность множеств запросов.

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

В главе также рассматриваются возможные области практического применения перечисленных выше задач. К их числу относятся: виртуальная интеграция в единую базу данных из источников с разными моделями их описания; семантическое кеширование, которое широко используется в клиент-серверных, OLAP-системах и мобильных вычислениях; дополнительные механизмы логического разграничения доступа к данным с целью обеспечения их конфиденциальности. Вводится модель полуструктурированных данных, описывается формальная математическая постановка задач, которые составляют содержание диссертации.

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

Ъ = (У,Е,у),

где V — вершины графа, соответствующие объектам, v — помечающая функция, которая сопоставляет каждому объекту его значение, Е С V X ЕхУ - отношение инцидентности, где £ — множество меток.

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

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

Каждому ребру, соединяющему вершины х, у, в графе Ъ сопоставлен некоторый символ а е Е, при этом {х, а, у) € Е. Таким образом, каждому пути

(хи аь х2), (х2, а2,23),..., (х„, а„, жп+1) е Е, (1)

соединяющему вершины х\,хп+1, приписано слово а\й2.. .ап в алфавите Е. Следовательно, в основу запросов к полуструктурированным данным можно положить ограничения, которые накладывются на слова, приписанные путям, соединяющим вершины графа, формализующего полуструктурированные данные.

В работе рассматриваются регулярные путевые запросы, в которых ограничения задаются регулярными выражениями. Пусть Ь С Е* — регулярный язык. Результатом данного запроса будут все возможные пары вершин х,у графа 25, для которых существует путь вида (1), где х = XI, у — £„+1 и слово а1а2 • • • чп принадлежит регулярному языку Ь. Регулярные выражения позволяют формулировать запросы, не имея полной информации о структуре данных. В ответ на запрос, представленный регулярным выражением вида аЕ*Ь, будут найдены пары вершин, которые соединены путями, начинающимися с буквы а и заканчивающиеся буквой Ь.

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

Введем определения. Пусть А и Е два непересекающихся конечных алфавита, которые будем называть алфавитом представлений и алфавитом базы данных, соответственно. Через Яед(1У) обозначим множество регулярных языков над алфавитом Е. Регулярная подстановка <р — это гомоморфизм Д+ —> Яед(Е). Таким образом, регулярная подстановка определяет полугруппу Зу, = ({<,р(£) | 6 е А)}).

Если породающие элементы конечно порожденной полугруппы запро-

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

Определение (Рациональное множество). Множество Л регулярных языков над Е называется рациональным, если существует конечный алфавит Д, регулярный язык К С Д+, и регулярная подстановка ip : Д+ —> Reg(E) такая, что

Ж = {cp(w) I wE К}.

Таким образом, рациональные множества являются рациональными подмножествами конечно порожденных полугрупп регулярных языков. Будем считать, что пара (К, <р) является представлением рационального множества и обозначать его через 31 = (К, ip).

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

Определение. Пусть tp : Д+ —> Reg{Е) регулярная подстановка. Однословной перезаписью регулярного языка R G Reg(H) по подстановке <р называется слово w £ Д+ такое, что <p(w) = R.

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

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

7Lenzerini М., Data Integration: A Theoretical Perspective // Proc. of the 21th SIGMOD Conf., 233-246,

ACM, 2002

включает: глобальную схему данных, схемы источников данных и отображение между ними. Локальные схемы описывают структуру источников, где расположены реальные данные. Глобальная схема предоставляет согласованное виртуальное описание всех данных на ее основе.

Один из методов интеграции носит название LAV (local as view). Особенностью этого метода является тот факт, что локальные источники данных Li описываются как представления глобальной базы данных G. Если система интеграции получает запрос к глобальной базе данных, то необходимо его представить в терминах представлений локальных источников. Такое задание можно описать следующим образом: для каждого локального источника Li существует некоторый запрос Щ к глобальной базе данных такой, что верно Li = Ri(G). Для того, чтобы вычислить произвольный запрос М, поступивший извне, необходимо разложить его через запросы {Ri}. Если предположить, что доступна только одна операция над запросами, которую условно назовем композицией (о), то необходимо найти такой набор ¿i, ..i/t, что M — Rii о R^ ... о R[k) либо констатировать, что такого разложения не существует.

Вопрос перезаписи запросов возникает также в семантическом квитировании. Семантическое кеширование широко используется в клиент-серверных системах8, OLAP системах9, мобильных вычислениях10 и гетерогенных системах11. Семантическое кеширование отличается тем обстоятельством, что кешируются результаты запросов, а не строки базы данных или страницы. В данном случае кеш-память состоит из множества элементов, связанных семантическим описанием. Одним из этапов семантического кеширования является проверка того, можно ли поступивший запрос M выразить через те запросы {Ä,}, результаты вычисления которых уже известны и хранятся в кеш-памяти системы.

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

BShaul Dar, Michael J. ïYanklin, Björn T. Jónsson, Divesh Srivastava, Michael Tan, Semantic Data Caching and Replacement // VLDB '96: Proceedings of the 22th International Conference on Very, 330-341, 1996

'Prasad M. Deshpande, Karthikeyan Ramasamy, Amit Shukla, Jeffrey F. Naughton, Caching multidimensional queries using chunks, 259-270, 1998

l0Ken. C. K. Lee, H. V. Leong, Antonio Si, Semantic query caching in a mobile environment // SIGMOBILE Mob. Comput. Commun. Rev., 3(2), 28-36, 1999

"Parke Godfrey, Jarek Gryz, Semantic Query Caching for Hetereogeneous Databases // Knowledge Representation Meets Databases, 6.1-6.6,1997

принятой политике безопасности, не предназначены для него. Ответы на некоторые другие запросы, согласно положений той же политики, могут быть конфиденциальными и для этой категории пользователей. В таком случае описанные механизмы могут потребовать обоснования того, что раскрытые представления не дают информации, позволяющей вычислять такие конфиденциальные запросы. Здесь возникает задача по постановке и технике ее решения близкая к задачам интеграции и кеширования. Ее суть в том, чтобы уметь проверять, принадлежит ли какой-либо запрещенный запрос М множеству запросов, вычислимых на основании разрешенных представлений {Ri}n.

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

Задача. Пусть ip : Д+ ->- Reg(Е) — регулярная подстановка, R 6 Дед(Е) — произвольный регулярный язык. Существует ли алгоритм проверки принадлежности языка R полугруппе S^,, порожденной регулярной подстановкой tpl Можно ли найти слово w е Д+ такое, что верно у?(ги) = R?

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

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

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

"К. Hashiguchi, Representation theorems оп regulär languagea // Journal of Computer and system sciences, 27, 101-115, 1983

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

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

Задача. Пусть IR = (К, (р) — рациональное множество регулярных языков над Ей RE Reg(E) —• произвольный регулярный язык. Существует ли алгоритм проверки принадлежности языка R множеству Л? Можно ли найти слово w G Д+ такое, что оно принадлежит языку К и верно <p(w) = Д?

Решение данной задачи представлено во второй главе диссертации.

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

В общем случае, когда полугруппа задана определяющими соотношениями на порождающие элементы, а именно —

S = (Д | Vi = щ, Vi, щ в Д*, i £ [1,..., fc]},

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

14А. А. Марков, Н. М. Нагорный, Теория алгорифмов, Наука, 1984

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

в : Д+ х Д+ Д(2, $)*, где Д(2, $) = ((Д и {$}) х (Д и {$})) - {($, $)},

Определение. Пусть Ь 6 Нед(Д), <р : Д+ —> Кед{11) — регулярная подстановка такие, что <р(Ь) = §, где § — конечно порожденная полугруппа. Пара (Д, Ь) является автоматной структурой для если:

= {в(и, у) | и, V 6 Ь, <р(и) = регулярный язык в Д(2, $)*;

Ь& = {в(и, у) | и, у £ Ь, 1р(и5) = <р(ь)} регулярный язык в Д(2, $)* для любого 5 € Д.

Полугруппа называется автоматной, если она обладает автоматной структурой.

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

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

следующим образом:

V) - 6[)... (*„, 6'п+г) ...($, <и

если т < п.

если п < ш;

если т = п;

Задача. Пусть и §ф — две полугруппы, заданные регулярными подстановками ¡р : А1 —> /?ед(Е) и ф : Дг —» Де<?(Е). Можно ли проверить вложенность полугрупп?

В случае, когда верно вложение полугрупп С §,/,, система представлений заданная подстановкой ф обладает большей выразительной силой, чем система представлений заданная ¡р.

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

Задача. Пусть (К\, <р) и (К2, ф) — рациональные множества, заданные регулярными подстановками <р : Д1 —» Яед(Е), ф : Д2 —> Лед(Е) и регулярными языками Кх,К2 € Лед(А). Можно ли проверить вложенность рациональных множеств (Кг, ф) и (К2, ф)1

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

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

Задача, Пусть Л = (К, (р) — рациональное множество регулярных языков над Е, заданное регулярным языком К € Кед[А) и регулярной подстановкой <р : Д —» Яед(Е). Существует ли алгоритм проверки конечности рационального множества К = (К, >р)1

Разрешимость данной задачи доказывается во второй главе настоящей работы.

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

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

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

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

Теорема 1. Задача принадлежности регулярного языка R G Regijl) рациональному множеству Л = (К,<р) регулярных языков над Е разрешима.

Доказательство данной теоремы является конструктивным. В первом разделе главы приводится алгоритм проверки принадлежности регулярного языка рациональному множеству и анализируется сложность данного алгоритма.

Во втором разделе доказывается, что для любой полугруппы S регулярных языков и любого слова w £ S данной полугруппы верно утверждение: множество слов, равных w, является регулярным.

Теорема 2. Пусть <р : Д+ —> Reg(Е) — регулярная подстановка, Sv — конечно порожденная полугруппа регулярных языков, w — слово в алфавите Д. Множество

[tu] — {и G Д+ | tp(u) = ip(w)} является регулярным языком над Д.

Множество F — [ги] может быть построено с помощью следующего алгоритма (на вход подается слово w G Д+).

• Положить К = Д+, F = 0.

• Повторять следующие шаги пока tp(w) € (К, ip):

— найти самое короткое слово v 6 К такое, что <p(v) = <^(ги);

— добавить слово v в F;

— положить К — К \ E[v, До).

15К. Hashiguchi, Representation theorems оп regulär languages // Journal of Computer and system sciences, 27, 101-115, 1983

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

При последовательном поступлении эквивалентных запросов, являющихся словами над алфавитом представлений, полезно иметь возможность вычислять только один из них, а на второй уже выдавать результат не производя вычислений. Предложенный алгоритм поиска оптимальной перезаписи позволяет решать данную задачу. Он требует построения класса эквивалентности для каждого нового запроса и основывается на проверке ограниченности автомата расстояния. Эта задача, в свою очередь, является РБРАСЕ-полной. Более эффективный метод решения задачи эквивалентности запросов может основываться на решении задачи о равенстве слов в том случае, если она не является вычислительно сложной. Данный вопрос рассматривается в следующей главе.

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

Регулярный язык Ь обладает свойством конечной степени, если существует натуральное число А; £ N такое, что Ь* — В 1966 Брозовский поставил вопрос о разрешимости данной проблемы. Независимо друг от друга положительные ответы дали Хашигучи16 и Саймон17. Будем писать /рр(Ь) — р или /рр(Ь) < оо если Ь* = 1/, и /рр{Ь) = оо, если такого числа не существует.

18K. Hashiguchi, Limitedness Theorem on Finite Automata with Distance Functions 11 Journal of computer and system sciences, 24, 233-244, 1982

17I. Simon, Limited subsets of a free monoid J/ Proceedings of the 19st Annual Symposium on Foundations of Computer Science, 143-150,1978

Теорема 3. Пусть tp : Д+ -> Reg(Е) — регулярная подстановка. Конечно порожденная полугруппа конечна тогда и только тогда, когда для любого m-подмножества {Si,..., <5m} С Д (m = 1,..., |Д|):

fpp(ip(6iS2...Sm)) < оо.

Следует отметить, что полученное условие накладывает существенное ограничение на структуру соотношений в полугруппе. Так, например, полугруппа S, заданная представлением S = (Д | х3 = х2 для всех х 6 А*) является бесконечной, если алфавит содержит по крайней мере две буквы18. Однако, полугруппа регулярных языков, удовлетворяющих соотношению х3 — х2 конечна по Теореме 3 (из соотношения х2 — х3 следует, что /рр(<р(х)) = 2). Этот факт означает, что полугруппа регулярных языков должна удовлетворять дополнительным соотношениям, которые являются следствием структуры регулярных языков.

В третьем разделе данной главы также доказывается следующая теорема.

Теорема 4. Задача конечности рационального множества Л = {К, ф) разрешима.

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

В четвертом разделе второй главы доказывается следующая теорема.

Теорема 5. Задача вложенности рациональных множеств регулярных языков не разрешима.

Третья глава посвящена решению задачи о равенстве слов для полугрупп регулярных языков.

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

18 J.A Brzozowski, К. Culik, A. Gabrielian, Classification of noncounting events // Journal of computer and system sciences, 5, 41-53, 1971

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

Рассмотрим полугруппу § порожденную языками

х = (а + Ь)*а, у — е + а + Ь, и г ~ Ь*

над Е = {а, Ъ}. В работе доказывается, что полугруппа 8 является автоматной. Для этого строятся представление 5

(.х, у, г | ух = х, гх = х, г2 = г, хгу = хг, хукг — хг (к ^ 1))

и автоматы для Ь= и Ьх,Ьу,Ьг.

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

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

Несмотря на то, что автоматные структуры с помощью несложных рассуждений могут быть построены для некоторых полугрупп регулярных языков, это предположение не является тривиальным. Например, пусть § по-лугурппа конечных языков. Каждый конечный язык может быть разложен в конкатенацию простых языков, однако это разложение не единственно ({е, а, а2, о3} = {е, а}3 = {е, а}{е, а2}). Таким образом, простые факторы могут удовлетворять нетривиальным соотношениям. В общем случае, ситуация еще более сложна.

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

Теорема 6. Рациональная полугруппа является автоматной.

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

Теорема 7. Не все полугруппы, порожденные конечным множеством регулярных языков, являются рациональными.

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

Доказательство основано на том, что коммутативные группы Клини являются рациональными19, а полугруппа является конечно порожденной тогда и только тогда, когда распознаваемое множество является рациональным20.

Определение. Для любого языка L С А*, любой регулярной подстановки (р язык = {w 6 А* I Зи Е L : tp{u) — ¡p(w)} называется замыканием языка L.

В работе доказываются следующие теоремы.

Теорема 8. Для конечно порожденной полугруппы S и регулярной подстановки <р : Д+ —t S верно: если для любого регулярного языка L над алфавитом Д замыкание \L]V является регулярным языком, то полугруппа S является полугруппой Клини.

Теорема 9. Пусть |Е| = 1. Для конечно порожденной полугруппы §, для любого регулярного языка L С А* и регулярной подстановки tp : Д+ S замыкание является регулярным языком.

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

Ранее предполагалось, что произвольные коммутативные полугруппы являются автоматными21. Однако оказалось, что существует коммутативная полугруппа не являющаяся автоматной22. Существование иных соот-

19 С. P. Rupert, On commutative Klee ne monoids //Springer New York, Semigroup Forum, 43(2), 163-177, 1991

20R. Gilmer, Commutative Semigroup Rings // University of Chicago, Chicago, 1984

21Colin M. Campbell, Edmund F. Robertson, Nikola Ruäkuc, Richard M. Thomas, Automatic semigroups j/ Journal of Theoretical Computer Science, 250 (1-2), 365-391, 2001

"Michael Hoffmann, Richard M. Thomas, Automaticity and commutative semigroups // Glasgow Mathematical Journal, 44, 167-176, 2002

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

В четвертой главе описывается созданная автором на языке МаШета-1лса программная реализация алгоритмов, представленных в работе. Программные средства использовались в ходе тестовых испытаний разработанных алгоритмов.

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

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

• подсистема построения максимальной перезаписи запроса;

• подсистема построения однословной перезаписи запроса.

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

24*П3+П*1ОВ(П+2)+П

где п — это число состояний автомата расстояния. Константа Хашигучи ограничивает длину слов, которые могут являться однословной перезаписью запроса.

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

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

Благодарности

Автор глубоко благодарен научному руководителю — доктору физико-математических наук, профессору Васенину Валерию Александровичу и кандидату физико-математических наук Афонину Сергею Александровичу за постановку задач, обсуждение результатов и постоянное внимание к работе.

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

1. «О представлении регулярных языков в виде конкатенации заданных», Е.Е.Хазова // Информационные технологии и программирование: Межвузовский сборник статей. Вып. 3(8), 23-38, - М.:МГИУ, 2003.

2. «Membership and Finiteness Problems for Rational Sets of Regular Languages», Afonin S., Khazova E., Lecture Notes in Computer Science // Springer-Verlag GmbH, 88-99, 2005.

(Е.Е.Хазовой принадлежат доказательство теоремы 5 и техническая реализация теоремы 3)

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

4. «А note on finitely generated semigroups of regular languages», Afonin

5, Khazova E, International Conference «Semigroups and Languages» // World Scientific, 1-8, 2007.

(Результаты данной статьи являются плодом совместной работы С.А.Афонина и Е.Е.Хазовой, эти результаты не могут быть разделены.)

5. «К вопросу об автоматности полугрупп регулярных языков», Хазова Е., Вестник Московского университета, сер.1, математика, механика,

6, 55-59, 2007.

6. «Semigroups of regular languages over one letter alphabet are rational», Afonin S., Khazova E., Proceedings of 12th International Conference on Automata and Formal Languages, AFL'08, 61-73, 2008.

(Е.Е.Хазовой принадлежит доказательство основных теорем 2 и 3, представленных в данной статье.)

Издательство ЦПИ при механико-математическом факультете МГУ имени М. В. Ломоносова

Подписано в печать 20. О/ О9 Формат 60x90 1/16. Усл. печ. л. /,<?5 Тираж /#¿7 экз. Заказ О5

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

Введение

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 Выводы.

Актуальность темы

Современное общество, которое принято именовать информационным, характеризуется тем, что эффективные технологии обработки данных во многом определяют успехи в области материального производства, в научно-технической, социально-экономической и в политической сферах деятельности человека. В условиях быстрого развития сетевой инфраструктуры и объемов, сосредоточенных в пей данных, методы их поиска, систематизации и анализа на сегодня отстают от возрастающих еще более высокими темпами потребностей общества. Одна из причин сложностей, возникающих на пути их удовлетворения, связана с существенно неоднородным характером подлежащей обработке информации, как с позиции поддерживающей ее аппаратно-программной платформы, так и в плане модели представления этих данных. На сегодня сложно представить себе случай, когда интересующие пользователя практически значимые данные могут находиться под управлением традиционной реляционной СУБД, какой либо другой модели их описания (модели данных) или системы. Для того, чтобы удовлетворять такие потребности, необходимо интегрировать данные из автономных, независимо администрируемых информационных источников, как правило, слабо связанных между собой или обладающих разной моделью описания данных. Как следствие, задача управления данными с неоднородной, перманентно изменяющейся или частично неизвестной структурой становится практически важной и актуальной. Такие данные принято называть слабоструктурированными или полуструктурированными. Далее чаще используется второе из этих определений.

Одним из результатов в задаче поиска информации по разнородным источникам данных является новая абстракция управления информацией, именуемая пространством данных [34,41,47]. Цель поддержки пространства данных состоит в обеспечении базового набора функций над всеми источниками данных. Понятие пространства данных предполагает поддержку нескольких уровней доступа к информации, отличающихся степенью детальности описания данных. На самом нижнем уровне поддерживается поиск по ключевым словам. При обработке более сложных поисковых запросов, учитывающих структуру документов, могут применяться модели как полуструктурированных данных, рассматриваемые в настоящей диссертации, так и модели реляционных данных. При этом следует принимать во внимание, чем выше уровень, тем сложнее организация доступа к данным.

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

Цель и задачи работы

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

1. Формализуется понятие ограничения на структуру перезаписей и разрабатывается алгоритм построения однословной перезаписи при наличии дополнительного ограничения.

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

3. Разрабатываются алгоритмы построения всех возможных однословных перезаписей запроса.

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

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

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

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

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

3. Доказана регулярность класса эквивалентности конечно порожденной полугруппы регулярных языков. Разработан алгоритм, позволяющий построить регулярный,язык, который соответствует классу эквивалентности полугруппы.

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

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

Научная новизна работы

С учетом введенного в диссертации понятия однословной перезаписи регулярных путевых запросов и формулировки основной задачи в терминах полугрупп регулярных языков, научной новизной обладают следующие ее результаты. Решена задача принадлежности регулярного языка рациональному подмножеству полугруппы регулярных языков, что является обобщением результатов Хашигучи [44]. Сформулировано условие конечности полугруппы и рационального множества регулярных языков, которое существенно сильнее известных ранее критериев конечности полугруппы [29, 65]. Исследована структура полугрупп регулярных языков, доказана регулярность класса эквивалентности. Доказано, что полугруппы регулярных языков над однобуквенным алфавитом являются рациональными, автоматными и полугруппами Клини.

Практическая ценность

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

Структура и объем работы

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

4,3. Выводы

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

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

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

• Эксперименты, проведенные на автоматах до пяти состояний показывают, что верхняя оценка сложности алгоритма проверки ограниченности автомата расстояния, основанная на константе Хашигучи, возможно завышена. Максимальное значение степени языка, обладающего свойством конечной степени, равно 7, хотя оценка, основанная на константе Хашигучи, требует проверки до 8.89272 * 10154 степени.

Заключение

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

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

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

3. Доказана регулярность класса эквивалентности конечно порожденной полугруппы регулярных языков. Разработан алгоритм, позволяющий построить регулярный язык, который соответствует классу эквивалентности полугруппы.

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

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

1. Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. — Мир, 1978.

2. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. — Вильяме, 2000.

3. Вухштаб А. А. Теория чисел. — М.: Просвещение, 1966.

4. Дейт К. Д. Введение в системы баз данных. — М:Издательский дом Вильяме, 2001.

5. Критически важные объекты и кибертерроризм. Часть 1. Системный подход к организации противодействия. / О. О. Андреев, И. С. Батов, М. В. Большаков и др.; Ред. В. А. Васенин. — МЦНМО, Москва, 2008. — С. 398.

6. Критически важные объекты и кибертерроризм. Часть 2. Аспекты программной реализации средств противодействия. / О. О. Андреев, И. С. Астапов, С. А. Афонин и др.; Ред. В. А. Васенин. — МЦНМО, Москва, 2008. — С. 607.

7. Лаллеман Ж. Полугруппы и комбинаторные приложения. — Мир, 1985.

8. Марков А. А., Нагорный Н. М. Теория алгорифмов. — Наука, 1984.

9. Пентус А. Е., Пентус М. Р. Теория формальных языков. — М.: Изд-во ЦПИ при механико-математическом ф-те МГУ, 2004.

10. Хазова Е. Е. О представлении регулярных языков в виде конкатенации заданных // Сборник трудов молодых ученых. Издательство МГИУ. — Т. 3. — 2003. — С. 23-38.

11. Хазова Е. Е. К вопросу об автоматности полугрупп регулярных языков // Вестник Московского Университета, сер.1, математика, механика. — Т. 6. — 2007. — С. 55-59.

12. Afonin S., Khazova E. Membership and finiteness problems for rational sets of regular languages // International Journal of Foundations of Computer Science. — 2006. — Vol. 17, no. 3. — Pp. 493-506.

13. Afonin S., Khazova E. Semigroups of regular languages over one letter alphabet are rational // 12th International Conference on Automata and Formal Languages, AFL'08. — 2008. — Pp. 112.

14. Answering complex sql queries using automatic summary tables / M. Zaharioudakis, R. Cochrane, G. Lapis et al. // SIGMOD Rec. — 2000. — Vol. 29, no. 2, — Pp. 105-116.

15. Answering queries with aggregation using views / D. Srivastava, S. Dar, H. V. Jagadish, A. Y. Levy // The VLDB Journal.- 1996,- Pp. 318-329. citeseer.ist.psu.edu/srivastava96answering.html.

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

17. Automatic groups and amalgams / G. Baumslag, S. M. Gersten, M. Shapiro, H. Short. — Vol. 76. — 1991.- Pp. 229-316.

18. Brzozowski J., Culik K., Gabrielian A. Classification of noncounting events // Journal of computer and system sciences. — 1971. — Vol. 5. — Pp. 41-53.

19. Caching multidimensional queries using chunks / P. M. Deshpande, K. Ramasamy, A. Shukla, J. F. Naughton.— 1998. — Pp. 259-270. citeseer.ist.psu.edu/deshpande98caching.html.

20. Chang J.-y., Lee S.-g. Query reformulation using materialized views in data warehouse environment // DOLAP '98: Proceedings of the 1st ACM international workshop on Data warehousing and OLAP. — New York, NY, USA: ACM, 1998. — Pp. 54-59.

21. A chase too far? / L. Popa, A. Deutsch, A. Sahuguet, V. Tannen // SIGMOD Rec. — 2000. — Vol. 29, no. 2. — Pp. 273-284.

22. Chaudhuri S., Dayal U. An overview of data warehousing and olap technology // SIGMOD Rec. 1997. - Vol. 26, no. 1. — Pp. 65-74.

23. Conway J. Regular Algebra and Finite Machines. — Chapman and Hall, 1971.29. de Luca A., Restivo A. A finiteness condition for finitely generated semigroups // Semigroup forum. 1984. - Vol. 28. - Pp. 123-134.

24. Duschka О. M., Genesereth M. R. Answering recursive queries using views // PODS '97: Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. New York, NY, USA: ACM, 1997. — Pp. 109-116.

25. Duschka О. M., Genesereth M. R. Query planning in infomaster // SAC '97: Proceedings of the 1997 ACM symposium on Applied computing. — New York, NY, USA: ACM, 1997. — Pp. 109-111.

26. Extensible markup language (xml) 1.0.— 1998.— World Wide Web Consortium. http://www.w3c.org/.

27. Fine N., Wilf Herbert S. Uniqueness theorems for periodic functions. — Proc. Amer. Math. Soc., 1965. Vol. 16. - Pp. 109-114.

28. Franklin M., Halevy A., Maier D. From databases to dataspaces: a new abstraction for information management // SIGMOD Rec.— 2005.— Vol. 34, no. 4.— Pp. 27-33. http://portal.acm.org/citation.cfm7id-1107502.

29. Gilmer R. Commutative Semigroup Rings. — University of Chicago, Chicago, 1984.

30. Godfrey P., Gryz J. Semantic query caching for hetereogeneous databases // Knowledge Representation Meets Databases.— 1997.— Pp. 6.1-6.6. citeseer.ist.psu.edu/godfrey97sernantic.html.

31. Goldstein J., Larson P.-A. Optimizing queries using materialized views: a practical, scalable solution // SIGMOD Rec. 2001. - Vol. 30, no. 2. - Pp. 331-342.

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

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

34. Halevy A. Y. Answering queries using views: A survey // The VLDB Journal— 2001.— Vol. 10, no. 4. Pp. 270-294.

35. Halevy A., Franklin M., Maier D. Principles of dataspace systems // PODS '06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. — New York, NY, USA: ACM, 2006. — Pp. 1-9.

36. Harinarayan V., Rajaraman A., Ullman J. D. Implementing data cubes efficiently // SIGMOD Rec. 1996. - Vol. 25, no. 2. - Pp. 205-216.

37. Hashiguchi K. Limitedness theorem on finite automata with distance functions // Journal of computer and system sciences. — 1982. — Vol. 24. — Pp. 233-244.

38. Hashiguchi K. Representation theorems on regular languages // Journal of computer and system sciences. — 1983. — Vol. 27. — Pp. 101-115.

39. Kwok С. Т., Weld D. S. Planning to gather information // 13th AAAI National Conf. on Artificial Intelligence.— Portland, Oregon: AAAI / MIT Press, 1996.— Pp. 32-39. citeseer.ist.psu.edu/kwok96planning.html.

40. Lee К. С. K., Leong H. V., Si A. Semantic query caching in a mobile environment // SIGMOBILE Mob. Comput. Commun. Rev. — 1999. — Vol. 3, no. 2. — Pp. 28-36.

41. Leung H. Limitedness theorem on finite automata with distance functions: an algebraic proof// Theor. Comput. Sci. 1991. - Vol. 81, no. 1. — Pp. 137-145.

42. Pottinger R., Levy A. Y. A scalable algorithm for answering queries using views // The VLDB Journal. — 2000. — Pp. 484-495. citeseer.nj.nec.com/pottingerOOscalable.html.

43. Ren Q., Dunham M. H. Using semantic caching to manage location dependent data in mobile computing // Mobile Computing and Networking.— 2000.— Pp. 210-221.citeseer.ist.psu.edu/renOOusing.html.

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

45. Rupert С. On commutative kleene monoids // Semigroup Forum. — 1991. — Vol. 43, no. 2.— Pp. 163-177.

46. Salomaa A. Jewels of Formal Language Theory. — Computer science press, 1981.

47. Semantic data caching and replacement / S. Dar, M. J. Franklin, В. T. Jonsson et al. // VLDB '96: Proceedings of the 22th International Conference on Very Large Data Bases. — San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1996. — Pp. 330-341.

48. Simon I. Limited subsets of a free monoid // Proceedings of the 19st Annual Symposium on Foundations of Computer Science. — 1978.— Pp. 143-150.

49. Theodoratos D., Sellis Т. K. Dynamic data warehouse design // Data Warehousing and Knowledge Discovery.— 1999.— Pp. 1-10. citeseer.ist.psu.edu/theodoratos99dynamic.hljml.

50. Tsatalos 0. G., Solomon M. H., Ioannidis Y. E. The gmap: a versatile tool for physical data independence // The VLDB Journal. — 1996. — Vol. 5, no. 2. — Pp. 101-118.

51. Varricchio S. A finiteness condition for finitely generated semigroups // Semigroup Forum. — 1989.-Vol. 38, no. 1.- Pp. 331-335.

52. View-based query processing and constraint satisfaction / D. Calvanese, G- De Giacomo, M. Lenzerini, M. Y. Vardi // Proc. of the 15th IEEE Sym. on Logic in Computer Science (LICS 2000). 2000. - Pp. 361-371. • j

53. Word processing in groups / J. W. Cannon, D. B. A. Epstein, D. F. HolJ; et al. — j Jones and Bartlett Publishers, 1992.

54. Yang H. Z., Larson P.-A. Query transformation for psj-queries // VLDB '87: Proceedings of the 13th International Conference on Very Large Data Bases. — San Francisco,, CA, USA: Morgan Kaufmann Publishers Inc., 1987. — Pp. 245-254.