Теория баз данных и информационного поиска Информационно-графовая модель данных




НазваниеТеория баз данных и информационного поиска Информационно-графовая модель данных
Дата конвертации17.02.2013
Размер445 b.
ТипЗадача


Теория баз данных и информационного поиска

  • Информационно-графовая модель данных


Содержание

  • Метод управляющих систем в теории информационного поиска

  • Поиск идентичных объектов

  • Интервальный поиск

  • Включающий поиск

  • Задача информационного поиска

  • Поиск идентичных объектов 2

  • Базовое множество

  • Пример базового множества

  • Информационный граф

  • Решение задачи информационного поиска

  • ИГ, решающий задачу поиска

  • Алгоритм, соответствующий ИГ

  • Сложность информационных графов

  • Поиск идентичных объектов 3

  • Включающий поиск 2

  • Интервальный поиск 2

  • Литература



Метод управляющих систем в теории информационного поиска

  • Шаг 1. Определяется понятие задачи информационного поиска и функции ответа, реализуемой этой задачей.

  • Шаг 2. Вводится специальная схема (называемая информационным графом), которая моделирует алгоритм поиска и реализует функцию ответа.

  • Шаг 3. Вводятся сложностные характеристики информационного графа (число ребер графа, время поиска в среднем и худшем случае).

  • Шаг 4. Находятся нижние оценки временной сложности для рассматриваемых задач информационного поиска.

  • Шаг 5. Строится информационный граф, реализующий функцию ответа и имеющий сложность, близкую к нижней оценке.



Поиск идентичных объектов

  • Y=[0,1] - множество записей.

  • X=[0,1] - множество запросов.

  • V - база данных.

  • Поиск идентичных объектов: для любого x найти y такую, что x



Интервальный поиск

  • .Y=[0,1] – множество записей.

  • .X множество запросов.

  • .V база данных.

  • Интервальный поиск: для

  • любого запроса u

  • перечислить все те и

  • только те записи , y

  • которые u



Включающий поиск

  • .Y - множество записей.

  • X - множество запросов.

  • .V - база данных.

  • Включающий поиск: для любого запроса

  • x

  • перечислить все те и только те записи

  • y

  • которые



Задача информационного поиска

  • - множество записей.

  • - множество запросов.

  • < - вероятностное пространство, где - алгебра подмножеств , - вероятностная мера на .

  • - бинарное отношение.

  • - тип информационного поиска.

  • Если и , то - задача информационного поиска типа .

  • Задача информационного поиска : для произвольного запроса перечислить те и только те записи , для которых .



Поиск идентичных объектов



Базовое множество

  • - множество запросов.

  • - предикат.

  • - переключатель.

  • - множество предикатов.

  • - множество переключателей.

  • - базовое множество.



Пример базового множества

  • - мн-во запросов.

  • - мн-во предикатов.

  • ,

  • - множество переключателей.

  • - базовое множество.



Информационный граф



Решение ЗИП

  • Проводимость предикат. ребра :

  • Проводимость переключательного ребра :

  • Проводимость пути C из ребер :

  • Функция фильтра вершины :Х

  • Характеристическая функция записи Xдля отношения

  • ИГ решает ЗИП если для любого запроса выполнено

  • Теорема ИГ решает ЗИП точно тогда, когда для любой записи выполнено



Характеристические функции включающего поиска



ИГ, решающий задачу включающего поиска

  • а



ИГ, решающий задачу интервального поиска



Алгоритм, соответствующий ИГ

  • Устанавливаем ответ корень ИГ помечаем и включаем в вспомогательное множество A.

  • Для каждой вершины , выполняем следующее:

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


Алгоритм, соответствующий ИГ

  • а



Алгоритм, соответствующий ИГ



Сложность ИГ

  • Q(U) – число ребер ИГ U.

  • . - число ребер, исходящих из вершины ; - множество вершин ИГ U; - множество переключательных вершин U; если f - предикат, определенный на X, то

  • Сложность ИГ U на запросе x:

  • Сложность ИГ U в худшем случае:

  • - множество ИГ над , решающих ЗИП I.

  • - вероятностное пространство над X.

  • Сложность ИГ U в среднем: T(U)=ET(U,x), т.е.

  • Сложность ЗИП I для базового множества и объема q:

  • Сложность ЗИП I для :



Сложность ИГ, решающего задачу включающего поиска

  • .

  • .

  • .



Сложность ИГ, решающего задачу интервального поиска



Поиск идентичных объектов

  • X=Y=(0,1]. - тип поиска идентичных объектов.

  • Теорема Пусть вероятностная мера P задана функцией плотности вероятности I , , |V|=k , - базовое множество, заданное (1)-(4); тогда I

  • и существует такой ИГI , что



Включающий поиск

  • Если y то O

  • Если I - ЗИП, то R

  • S - тип включающего поиска.

  • - множество всех монотонных конъюнкций от n переменных.

  • - множество монотонных булевых функций от n переменных.

  • Теорема Пусть F - базовое множество, где

  • F , x для любого x ; тогда

  • T для любой ЗИП I и существует

  • такая ЗИП I что T ,

  • где as



Пример включающего поиска

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .



Интервальный поиск

  • X - множество запросов.

  • Теорема Пусть вероятностная мера P задается функцией плотности вероятности I , - задача интервального поиска, - базовое множество (1)-(5), тогда I



Литература

  • Гасанов Э.Э. Теория сложности информационного поиска. Изд-во МГУ, Москва, 2005.

  • Гасанов Э.Э., Кудрявцев В.Б. Теория хранения и поиска информации. Физматлит, Москва, 2002.

  • Гасанов Э.Э. Об одной математической модели информационного поиска. Дискретная математика (1995) 3, N 2, 69-76.

  • Гасанов Э.Э. Об одномерной задаче интервального поиска. Дискретная математика (1995) 7, N 2, 40-60.

  • Гасанов Э.Э. Мгновенно решаемые задачи поиска. Дискретная математика (1996) 8, N 3, 119-134.

  • Гасанов Э.Э. Нижняя оценка сложности информационных сетей для одного отношения частичного порядка. Дискретная математика (1996) 8, N 4, 108-122.

  • Гасанов Э.Э. Нижняя оценка сложности включающего поиска в классе древовидных схем. Дискретная математика (1998) 10, N 1, 63-72.

  • Гасанов Э.Э., Кузнецова И.В. О функциональной сложности двумерной задачи интервального поиска. Дискретная математика (2002) 14, N 1, 114-141.



Похожие:

Теория баз данных и информационного поиска Информационно-графовая модель данных iconОсновы теории баз данных реляционная модель данных
База данных – поименованная и организованная совокупность взаимосвязанных данных, которые отражают состояние объектов конкретной...
Теория баз данных и информационного поиска Информационно-графовая модель данных iconЛекция Корпус как особый тип информационно-поисковой системы В. П. Захаров Санкт-Петербургский государственный университет Основные понятия информационного поиска
Ипс) это упорядоченная совокупность документов (массивов документов) и информационных технологий, предназначенных для хранения и...
Теория баз данных и информационного поиска Информационно-графовая модель данных iconЯзыки и методы конструирования программ
...
Теория баз данных и информационного поиска Информационно-графовая модель данных iconВведение Администрирование баз данных – что это такое?
База данных (БД) однозначно идентифицируемый массив данных заданной структуры, размещаемый на машиночитаемых носителях
Теория баз данных и информационного поиска Информационно-графовая модель данных iconПрограммирование II модели данных и базы данных
Гарсиа-Молина Г., Ульман Дж. Д., Уидом Д. Системы баз данных. Полный курс. М.: Издательский дом "Вильямс". 2003
Теория баз данных и информационного поиска Информационно-графовая модель данных iconМетоды и средства построения интеллектуальных агентов для продукционных систем и. А. Бессмертный Предмет исследования: Продукционная модель знаний
Предложенные методы позволяют подвергать предметную область декомпозиции и вычислять информативность баз знаний на разных уровнях...
Теория баз данных и информационного поиска Информационно-графовая модель данных iconРеляционная модель данных. Нормализация. Формы. 1НФ, 2 нф, 3НФ, нфбк, 4НФ, 5НФ
Реляционная модель данных является приложением к задачам обработки данных таких разделов
Теория баз данных и информационного поиска Информационно-графовая модель данных iconАнализ данных Ранжирование и оценка информационного поиска План

Теория баз данных и информационного поиска Информационно-графовая модель данных iconПоиск данных. Постановка, организация, последовательность поиска Классификация средств поиска Интернет
Всемирной паутины в базах данных. Специальные программы-роботы периодически «обходят» Web-серверы Интернета, читают все встречающиеся...
Теория баз данных и информационного поиска Информационно-графовая модель данных iconАнализ данных Введение в информационный поиск План оставшихся лекций
Основная цель: получить представление и задачах и проблемах систем информационного поиска
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница