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

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

Если 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 решает задачу информационного поиска , если Вводится сложность информационного графа. Предикат истинный на x, если x проходит в вершину β, и ложный в противном случае, называется функцией фильтра вершины β. Сложностью информационного графа U на запросе называется числогде R – множество вершин информационного графа U, P – множество переключательных вершин U, – количество ребер, исходящих из вершины β. Эта величина равна числу функций, вычисленных алгоритмом поиска, определяемым информационным графом U, на запросе x.

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

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

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

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

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

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

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