Поиск в базах данных с заранее неизвестной структурой. Теория.Практика.Приложения. Горелов С.С. МГУ им. М.В. Ломоносова механико-математический факультет.

Структура доклада 1.Теория Базовые понятия подхода Идеи алгоритмов Оценки сложности 2.Практика Тестирование на OEM-документах Тестирование на XML-документах 3.Приложения Поиск в XML-данных Прочие приложения

Что понимается под поиском в базе данных? Что понимается под индексом базы данных? За счет чего осуществляется сокращение времени поиска при использовании индекса? Как сравнивать индексы баз данных? Каким образом можно строить индексы близкие по свойствам к оптимальным? Введение

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

Основные понятия Определение Документ элемент наперед заданного множества D. База данных DB конечное множество документов. Запрос элемент наперед заданного множества Q. Определение Функция поиска документа отображение Qd : D х Q {0,1}. Если Qs(D, Q) = 1, то это значит, что документ D соответствует запросу Q, и Qs(D, Q) = 0 в противном случае. Определение Схема S объект, задающий множество документов (обозначим его [S]). Схема S1 называется более общей чем S2, если [S2] [S1]. Также будем обозначать это отношение S1S2.

Индекс Определение Индексом (иерархией схем) I для базы данных D назовем такое дерево схем, что каждая схема является более общей, чем любая из ее дочерних схем. Определение Функция поиска по схеме отображение Qs : S x Q {0,1}. При этом Qs(S, Q) = 1, если существует такой D, соответствующий S, что Qd(D,S)=1 и Qs(S, Q) = 0, если такого D не существует. Алгоритм, позволяющий сокращать время поиска в общем случае. На каждом шаге алгоритма для рассматриваемой вершины S индекса I проверяем соответствие схемы и запроса. Если условие не выполняется, то «отсекаем» рассматриваемую ветвь индекса со всеми соответствующими документами; если нет, то переходим к проверке дочерних схем.

Пример индекса

Оптимальность индекса Определение Стоимость вычислений на схеме |S| - средняя сложность вычислений запросов по схеме S. Определение Вероятность схемы {S} - вероятность события, что Qs(Q,S)=1. Математическое ожидание стоимости усечения пространства поиска по данному индексу / коротко назовем стоимостью индекса /. Математическое ожидание стоимости равно: M(I) = S I P{ Ŝ}*|S|. Определение Оптимальный индекс / 0 - такой, что для любого другого индекса I М(I) > М(I 0 ).

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

Модель поиска. Компоненты: D,Q,S, вероятностное пространство Функции: построение схемы по документу - S(D): D->S; вычисление размера схемы - |S|: S->R; отношение на схемах - S 1 >S 2 : SxS->{0,1}; объединение схем - S 1 +S 2 : SxS->S; вычисление вероятности схемы - P{S}: S->R; вычисление запроса на документе - Qd(D,Q): DxQ->{0,1}; вычисление запроса на схеме - Qs(S,Q): SxQ->{0,1}; проверка соответствия документа схеме – S>D: SxD->{0,1}. Свойства: отношения S 1 >S 2, S>D и операция S 1 +S 2 соответствуют некоторому изоморфизму S и подмножества 2 D ; если верно Qs(S,Q)=1, то существует D S: Qd(D,S)=1; если верно Qs(S,Q)=0, то для любого D S: Qd(D,S)=0. функции P{S} и |S| соответствуют своим определениям для вероятностного пространства.

Оценки сложности алгоритмов. Пусть база данных состоит из N документов. Пусть сложность вычисления |S| оценивается, как C |S|, сложность вычисления P {S} как C P{S}, а сложность вычисления S 1 +S 1 как C S1+S2. Разработано два алгоритма со следующими оценками сложности: 1.Стандартный - O(NC |S| +N 2 (C S1+S2 +C P{S} )+N 3 ln(N)). 2.По потоку документов - O(N(C |S| +C S1+S2 +C P{S} )+N 2 ln(N)). 3.Упрощенный - O((C S1+S2 +C P{S} )Nln(N)).

D=множество OEM документов. Q=множество CRP запросов. S=множество графовых схем. Тестирование системы поиска в OEM-документах.

Тест1. Зависимость времени индексации от размера базы.

Тест2. Зависимость стоимости индекса от размера базы.

Тест3. Тестирование поиска.

Тестирование системы поиска в XML-документах. D=XML документ. Q=XQuery запрос. S=схема DTD.

Тест1. Зависимость времени индексации от размера базы.

Тест2. Зависимость стоимости индекса от размера базы.

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

Поиск в XML. Поиск в OEM. Создание поисковых систем документов нестандартных типов по нестандартным запросам. Вероятные направления использования.

XML - человеко-ориентированный формат; XML - универсальный формат; XML имеет строго определённый синтаксис, что позволяет ему быть простым, эффективным и непротиворечивым; XML. Что это такое?

как универсальный формат для обмена структурированными данными между приложениями в сети Интернет 1996й год - утверждение спецификации XML, сочетающего простоту HTML и логику SGML для обработки XML данных были созданы XPath, XSL, XQuery Зачем создавался XML?

Применение. Для обмена данными между приложениями. XHTML,SOAP, etc. В качестве исходных данных для шаблонизаторов при выдаче XHTML пользователю. Для хранения исходных данных и их последующей обработке. Плюсы и минусы, отмечаемые разработчиками при выборе технологий связанных с XML. + Гибкость перехода от проекта к проекту и низкая стоимость перехода. + Отчуждаемость - Малое количество квалифицированных специалистов и как следствие высокая стоимость единичной разработки. - Низкая производительность Как применяют XML.

Отобраны: Свободно распространяемые СУБД. Поддерживаемые в настоящее время. С реализацией XQuery. Тестовая база: База библиотеки – 1млн записей, 400МБ XML файл. Запрос 1: Запрос книги по ключу. Запрос 2: Запрос книг, на которые ссылается Заданная. Native XML-СУБД. Небольшое тестирование.

Использование Native XML-СУБД. Время загрузки1 запрос2 запрос3 запрос Exist1час, 20 мин4мин 4мин, 20сек 7мин, 32сек SEDNA9 мин 1мин, 23cек 2мин, 55сек 3мин, 48сек SEDNA_I?63cек 1мин, 20cекFAILED dbxml2 мин18сек2мин, 2секFAILED MonetDb3 мин1сек 2мин, 47секFAILED

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

Выводы В настоящее время использование XML-технологий для хранения и обработки больших объемов данных представляется непрактичным, в силу отсутствия соответствующих средств. Теоретически пространство для развития как в целом XML-технологий, так и конкретно решаемой задачи – огромное. Начиная от конкретных реализаций поиска в XML-данных и заканчивая разработкой новых поисковых систем для нестандартных типов данных. Но на сегодняшний день подобные задачи стоят слишком далеко от тех массовых задач, которые непосредственно решаются на практике.