Эффективные модели поиска в базах полуструктурированных данных на основе иерархии схем документов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Горелов, Сергей Сергеевич

• Горелов, Сергей Сергеевич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Горелов, Сергей Сергеевич

Введение

Актуальность.

Цели работы.

Методы.

Научные результаты.

Научная новизна.

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

Доклады и научные публикации.

1 Задачи, связанные с поиском в базах полуструктурированных данных

1.1 Модель OEM-данных.

1.2 Модель XML-данных.

1.3 Методы сокращения времени поиска в OEM-данных.

1.4 Методы сокращения веремни поиска в XML-данных.

1.5 Выводы.

2 Поиск в базах OEM-документов

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.3.4 Сравнительный анализ.

2.4 Выводы.

3 Поиск в наборе однотипных документов при заранее неизвестной модели данных

3.1 Формальная модель поиска и индексирования.

3.1.1 Поиск.

3.1.2 Индексирование.

3.1.3 Стоимость индекса

3.1.4 Построение оптимальных индексов.

3.1.5 Построение индексов по потоку документов.

3.2 Модель поиска в наборах XML-документов по XPath-запросам.

3.2.1 Вероятностное пространство запросов

3.2.2 Алгоритмы, реализующие интерфейсы модулей «документ», «схема», «запрос»

3.2.3 Свойства алгоритмов.

3.3 Оценки сложностей алгоритмов поиска и индексирования.

3.4 Выводы.

4 Программная система и тестовые испытания

4.1 Требования к программной системе.

4.2 Архитектурно-технологические решения.

4.2.1 Компоненты системы.

4.2.2 Интерфейсы компонент системы.

4.3 Эксперименты с использованием программной системы поиска и индексирования полуструктурированных документов.

4.3.1 Эксперименты с вычислением запросов.

4.3.2 Эксперименты с построением иерархий схем.

4.4 Выводы.

Введение диссертации (часть автореферата) на тему «Эффективные модели поиска в базах полуструктурированных данных на основе иерархии схем документов»

Актуальность

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

В последнее десятилетие в области хранения, обмена и обработки информации широкое распространение получили технологии, использующие понятие полуструктурированных данных [21]. Такой подход обладает большей гибкостью по сравнению с традиционными, в плане моделей описания данных, поскольку не требует наличия единой структуры у однотипных (относящихся к одной предметной-области) документов. Полуструктурированные данные могут использоваться при объединении разнородных информационных источников в единую систему [46], для поиска информации в Интернет или в корпоративных информационных хранилищах [2]. Известные на настоящее время формальные модели описания полуструктурированных данных [30, 21] и языков запросов, которые основываются на понятии регулярного путевого запроса [14], приводят к необходимости решения вычислительно трудных задач [55]. Под моделью полуструктурированных данных в диссертационной работе понимается Object Exchange Model (OEM) [56].

Документами в контексте настоящей работы будем называть объекты, содержащие данные в некотором заранее определенном формате. Базой данных будем именовать набор изолированных документов, подразумевая что при поиске данных результат вычисления запроса на отдельном документе не зависит от данных, содержащихся в других документах базы. Далее используются понятия OEM, XML, HTML-документов, однако наибольшее внимание в контексте целей данной работы уделяется OEM-модели. В качестве запросов для OEM-документов рассматриваются регулярные путевые запросы и конъюнктивные регулярные путевые запросы, для XML и HTML-документов рассматриваются ХРаШ-выражения. В действительности документы могут быть взаимосвязаны, например, для формата данных HTML такие взаимосвязи задаются гиперссылками. Их учет — предмет отдельного исследования [9], которое находится вне целей настоящей работы. В подходе, который используется в данной работе, такие взаимосвязи учитываться не будут. Вычисление запроса будем понимать как поиск всех документов базы, которые удовлетворяют условиям запроса.

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

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

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

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

Цели работы

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

• формализация понятия эффективности поиска документов в полуструктурированных базах данных с использованием индексов;

• разработка алгоритмов построения эффективных индексов для наборов полуструктурированных документов;

• разработка алгоритмов эффективного перестраивания индексов при добавлении полуструктурированных документов в базу;

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

Методы

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

• математическая логика, включая исчисление предикатов, теория алгоритмов;

• дискретная математика, в том числе комбинаторика, теория графов, теория автоматов и регулярных языков;

• теория вероятности.

Научные результаты

В диссертационной работе получены следующие результаты.

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

• Для поиска в наборах OEM-документов представлены алгоритмы, позволяющие оценивать эффективность индексов с позиции временных затрат на вычисление конъюнктивных регулярных путевых запросов.

• Для поиска в наборах XML-документов представлены алгоритмы, позволяющие оценивать эффективность индексов с позиции временных затрат на вычисление XPath-запросов.

• Разработан алгоритм построения эффективных индексов для поиска данных в наборах полуструктурированных документов. Разработан алгоритм построения эффективных индексов для поиска данных в потоках полуструктурированных документов.

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

Научная новизна

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

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

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

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

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

Доклады и научные публикации

Основные результаты диссертации докладывались на конференциях: «Ломоносовские чтения» 2005 г.; на Третьей международной конференции по проблемам управления 2006 г. На семинарах: «Проблемы современных информационно-вычислительных систем» под руководством проф. В. А. Васенина на механико-математическом факультете МГУ имени М. В. Ломоносова в 2007 и 2008 г.; на семинаре под руководством проф. С. Д. Кузнецова в Институте системного программирования РАН в 2008г.; на семинаре Московской секции ACM SIGMOD под руководством проф. Л. А. Калиниченко в 2009 г.

ПО ТЕМЕ ДИССЕРТАЦИИ опубликовано 6 печатных работ, из которых 3 [1-3] в списке журналов, рекомендованных в ВАК РФ.

1. С.С. Горелов, В.А. Васенин. Усечение пространства поиска в полуструктурированных базах данных при помощи иерархии схем документов. Журнал «Программирование». Вып. 6, 2005, стр.41-55. (С.С. Горелову принадлежат доказательства теорем 1 и 2).

2. С.С. Горелов. Оптимальные иерархии схем для поиска по конъюнктивным регулярным путевым запросам в полуструктурированных базах данных. Журнал «Программирование». Вып. 4, 2006, стр.38-56.

3. С.С. Горелов. Модели и алгоритмы для систем поиска в наборах документов. Журнал «Информационные технологии». Вып. 1, 2009, стр.61-66.

4. С.С. Горелов. Построение иерархии схем по потоку полуструктурированных документов. Сборник «Информационные технологии и программирование», Вып. 3(12), 2004, стр.45-64.

5. Gorelov S.S., Vasenin V.A. Search Optimization in Semistructured Databases Using Hierarchy of Document Schemas Programming and Computer Software, MAIK Nauka/Interperiodica, vol. 31, no. 6, pp. 321-331, 2005. (C.C. Горелову принадлежат доказательства теорем 1 и 2).

6. Gorelov S.S. Optimal schema hierarchies in searching semistructured databases by conjunctive regular path queries. Programming and Computer Software, MAIK Nauka/Interperiodica, vol. 32, no. 4, pp. 215-227, 2006.

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

Заключение диссертации по теме «Теоретические основы информатики», Горелов, Сергей Сергеевич

4.4. Выводы

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

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

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

Заключение

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

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

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

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

Разработан алгоритм построения эффективных индексов для поиска данных в наборах полуструктурированных документов. Разработан алгоритм построения эффективных индексов для поиска данных в потоках полуструктурированных документов.

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

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

1. Афонин С. А. Алгоритмы эффективного вычисления конъюнктивных регулярных путевых запросов // Вычислительные технологии. — 2007. — Т. 12, № 2. — С. 23-32.

2. Васенин В. А., Афонин С. А., Коршунов А. А. К созданию концепции интегрированной системы распределённых информационных ресурсов Московского государственного университета им. М.В. Ломоносова. — М.: Изд-во МГУ, 2001.— С. 112.

3. Вирт Н. Алгоритмы и структуры данных. — Москва «МИР», 1989.— С. 286-301.

4. Горелов С. С. Построение иерархии схем по потоку полуструктурированных документов // Информационные технологии и программирование. — 2004. — Т. 12, № 3. — С. 4564.

5. Горелов С. С. Оптимальные иерархии схем для поиска по конъюнктивным регулярным путевым запросам в полуструктурированных базах данных // Программирование. — 2006. Т. 4. - С. 38-56.

6. Горелов С. С., Васенин В. А. Усечение пространства поиска в полуструктурированных базах данных при помощи иерархии схем документов // Программирование. — 2005. — Т. 6.-С. 41-55.

7. Гринев М., Кузнецов С., Фомичев А. XML-СУБД Sedna: технические особенности и варианты использования // Открытые системы. — 2004. — Т. 4. — С. 36-43. http: //www.citforum.ru/database/articles/sedna/.

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

9. Козлов Д. Д., Белова А. А. Исследование эффективности применения методов совместного анализа текстов и гиперссылок для поиска тематических сообществ // Интернет-математика 2005: автоматическая обработка веб-данных.— 2005.— Т. 5, № 1.— С. 250-271.

10. Липаев В. В. Программная инженерия. Методологические основы. — М.: изд-во ТЕИС, 2006.-С. 609.

11. Марков А. А., Нагорный Н. М. Теория алгоритмов. — Наука, 1984.— С. 304.

12. Новак JJ. Г., Кузнецов С. Д. Свойства схем данных XML // Труды Института системного программирования. — 2003. — Т. 4.

13. Смит Б. Методы и алгоритмы вычислений па строках. — Вильяме, 2006. — С. 496.

14. Abiteboul S., Vianu V. Regular path queries with constraints // 16th ACM Symposium on Principles of Database Systems. — 1997. — Pp. 122-133. cite-seer.ist.psu.edu/abiteboul98regular.html.

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

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

17. Borgelt C., Berthold M. R. Mining molecular fragments: Finding relevant substructures of molecules // ICDM '02: Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02). —Washington, DC, USA: IEEE Computer Society, 2002. — P. 51.

18. Buneman P. Semistructured data // 16th ACM Symposium on Principles of Database Systems.— 1997.— Pp. 117-121. citeseer.ist.psu.edu/buneman97semistructured.html.

19. Chen Q., Lim A., Ong K. W. D(k)-index: An adaptive structural summary for graph-structured data 11 SIGMOD. — 2003. Pp. 134-144.

20. Chung C., Min J., Shim K. Apex, an adaptive path index for xml data // SIGMOD. — 2002. — Pp. 121-132.

21. Clark J. XSL Transformations (XSLT) Version 1.0. — 1999. http://www.w3.org/TR/xslt.

22. Clark J., DeRose S. XML Path Language (XPath) Version 1.0.— 1999. http://www.w3.org/TR/xpath.

23. Clark J., Murata M. RELAXNG Tutorial, OASIS Working Draft. — 2001. http://www.oasis-open.org/committees/relax-ng/tutorial.html.

24. Cowan J., Tobin R. XML Information Set. — 2001. http://www.w3.org/TR/xml-infoset/.

25. Deutsch A., Fernandez M., Suciu D. Storing semistructured data with stored // SIGMOD '99: Proceedings of the 1999 ACM SIGMOD international conference on Management of data. — New York, NY, USA: ACM, 1999. Pp. 431-442.

26. Exploiting local similarity for efficient indexing of paths in graph structured data / R. Kaushik, P. Shenoy, P. Bohannon, E. Gudes // ICDE. — 2002. cite-seer.ist.psu.edu/kaushik02exploiting.html.

27. Bray Т., Paoli J., Sperberg-McQueen С. M. et al. Extensible Markup Language (XML) 1.0 (Fourth Edition). — 16 August 2006. http://www.w3.org/TR/2006/REC-xml-20060816/.

28. A fast index for semistructured data / B. Cooper, N. Sample, M. J. Franklin et al. // The VLDB Conference. — 2001. — Pp. 341-350. citeseer.ist.psu.edu/cooper01fast.html.

29. Fernandez M., Malhotra A., Marsh J. XQuery 1.0 and Xpath 2.0 Data Model.— 2003. http://www.w3.org/TR/xpath-datamodel/.

30. Fernandez M. F., Suciu D. Optimizing regular path expressions using graph schemas // ICDE. — 1998. — Pp. 14-23. citeseer.ist.psu.edu/fernandez98optimizing.html.

31. Florescu D., Kossmann D. A performance evaluation of alternative mapping schemes for storing XML data in a relational database: Tech. rep.: 1999. cite-seer.ist.psu.edu/florescu99performance.html.

32. Gorelov S. S. Optimal schema hierarchies in searching semistructured databases by conjunctive regular path queries // Programming and Computer Software. — 2007. — Vol. 32, no. 4. — Pp. 215-227.

33. Gorelov S. S., Vasenin V. A. Search optimization in semistructured databases using hierarchy of document schemas // Programming and Computer Software. — 2006.— Vol. 31, no. 6.— Pp. 321-331.

34. Henzinger M. R., Henzinger Т. А., Корке P. W. Computing simulations on finite and infinite graphs // IEEE Symposium on Foundations of Computer Science. — 1995.— Pp. 453-462. citeseer.ist.psu.edu/henzinger96computing.html.

35. High Performance MySQL / Z. Peter, S. Baron, T. Vadim et al. — O'Reilly, 2008. — P. 708.

36. IBM DB2 9 New Features / P. Zikopoulos, G. Baklarz, L. Katsnelson, C. Eaton. — McGraw-Hill Professional, 2007. — P. 422.

37. Inokuchi A., Washio Т., Motoda H. An apriori-based algorithm for mining frequent substructures from graph data. // PKDD. — 2000.— Pp. 13-23.

38. IS О/IE С 19757-3:2004. Document Schema Definition Languages (DSDL). — 2004. http://dsdl.org/.

39. Kawaguchi K. W3C XML Schema Made Simple.— 2001. http: //www.xml.com/pub / a /2001/06/06/schemasimple.html.

40. Kuramochi M., Karypis G. Frequent subgraph discovery // ICDM. — 2001.— Pp. 313-320. citeseer.ist.psu.edu/kuramochi01frequent.html.

41. Kwong A., Gertz M. Schema-based optimization of XPath expressions.— 2002. cite-seer.ist.psu.edu/kwong02schemabased.html.

42. Lore: A database management system for semistructured data / J. McHugh, S. Abiteboul, R. Goldman et al. // SIGMOD Record1997.- Vol. 26, no. 3.— Pp. 54-66. cite-seer.ist.psu.edu/mchugh9 71or e .ht ml.47