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

Информационно-графовая модель данных – модель данных, основанная на представлении данных в виде функционально нагруженного графа, который, определяя по запросу вычислительный процесс, выдает нужный ответ.

Если X – множество символов запросов с заданным на нем вероятностным пространством , где σ – алгебра подмножеств множества X, P – вероятностная мера на σ; Y – множество символов данных (записей); ρ – бинарное отношение на X∙Y, называемое отношением поиска; то пятерка  называется  типом. Тройка , где V – некоторое конечное подмножество множества Y, называемое библиотекой, называется задачей информационного поиска типа S. Содержательно задача информационного поиска  состоит в перечислении для произвольно взятого запроса  всех и точно тех записей , что xρy. Если F и G – суть множества символов одноместных предикатов и переключателей соответственно, определенных на X, где переключатель – функция, областью значений к-рой является конечное подмножество натурального ряда, то пара  называется базовым множеством и описывает множество элементарных операций, используемых при решении задачи информационного поиска.

Над базовым множеством  определяется понятие  информационного графа. В конечной многополюсной ориентированной сети выбирается вершина – полюс, называемая корнем. Остальные полюса называются листьями и им приписываются записи из Y. Нек-рые вершины сети называются переключательными и им приписываются переключатели из G. Ребра, исходящие из каждой из переключательных вершин, нумеруются и называются переключательными ребрами. Ребра, не являющиеся переключательными, называются предикатными и им приписываются предикаты из множества F. Таким образом нагруженную многополюсную ориентированную сеть называют информационным графом над базовым множеством . Затем определяется  функционирование информационного графа. Предикатное ребро проводит запрос , если предикат ребра истинен на x; переключательное ребро под номером n проводит x, если переключатель начала этого ребра равен n на x; ориентированная цепочка ребер проводит x, если каждое ребро цепочки проводит x; запрос x проходит в вершину β информационного графа, если существует ориентированная цепь, ведущая из корня в вершину β, которая проводит x; запись y, приписанная листу α, попадает в ответ информационного графа на x, если x проходит в лист α. Ответом информационного графа U на запрос x называют множество записей, попавших в ответ U на x, и обозначают его . Эту функцию  считают результатом функционирования информационного графа U. Информационный граф наряду со структурой данных описывает алгоритм соответствующего поиска. Процесс поиска при заданном запросе начинается с корня и распространяется в зависимости от нагрузочных функций, возможно, сразу по нескольким направлениям. Если этот процесс на графе достигает элементов данных, то они включаются в ответ алгоритма.

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

Если каждая функция из  – измерима (относительно алгебры ), то для любого информационного графа  над  функция  измерима.  Сложностью информационного графа  называется математическое ожидание величины , равное  Она характеризует среднее время поиска.  В-сложностью информационного графа  называется число  Эта величина характеризует время поиска в худшем случае.  Объемом информационного графа  называется число  ребер . Он характеризует объем памяти, необходимый для хранения данных.

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

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

Рекомендуемая литература

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

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

[3] Гасанов  Э. Э. Информационно-графовая модель хранения и поиска данных.  Интеллектуальные системы (1998)  3,   3-4, 163-192.

           Э.Э.Гасанов.