Алгоритмы построения однословной перезаписи регулярных путевых запросов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Хазова, Елена Евгеньевна

• Хазова, Елена Евгеньевна
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Хазова, Елена Евгеньевна

Введение

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

Список литературы диссертационного исследования кандидат физико-математических наук Хазова, Елена Евгеньевна, 2009 год

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.