Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ
Посмотреть оригинал

Полнота для информационных графов

Если нам дана ЗИП I = (X, V,p) и базовое множество Т = (F, G), то возникает вопрос: а можно ли построить информационный граф над базовым множеством Т, разрешающий эту задачу /? Если для любой записи yiV = {yi, • • • ,У*} имеем Xyitp € Е, то ответ на этот вопрос положительный, и граф, изображенный на рис. 1.5, разрешает задачу I.

В данном разделе дается более полный ответ на этот вопрос.

Пусть нам дан тип 5 = (X, У, р), где X — множество запросов, У — множество записей, р — отношение поиска, заданное на X х У, и базовое множество Т = (F,G).

Скажем, что базовое множество Т полно для типа S = (X, У, р), если для любой ЗИП I = (X,V,p) типа S существует ИГ U над базовым множеством Т, разрешающий ЗИП I.

Справедлив следующий результат, относящийся к проблеме полноты для ИГ [22, 23].

Теорема 2. Пусть заданы множества запросов X, записей Y, отношение поиска р на XxY и базовое множество Т = (F, G), такое что предикат тождественная 1 принадлежит множеству F. Тогда Т будет полным для типа S = (X, У, р) тогда и только тогда, когда для любой записи у G У такой, что 0(у,р) Ф 0, функцию Ху,р(х) можно представить формулой вида

Рис. 1.5. Информационный граф переборного алгоритма

где fij G F U G,

Доказательство. Достаточность.

Пусть нам дана произвольная ЗИП / = (X,V,p), где V = = Я Y. По предположению каждую из функций Хм,р(х)

(I = 1 ,к) можно представить формулой

где fujFUG, l = l,fc.

Без ограничения общности можно считать, что каждая конъюнкция Л7Д содержит предикат из F, причем этот предикат стоит

первым в конъюнкции. В противном случае мы всегда можем добавить предикат тождественная 1.

ИГ, разрешающий ЗИП /, будем строить следующим образом.

Сначала возьмем к + 1 вершину и объявим одну из них корнем, а остальные объявим листьями и мысленно перенумеруем, начиная с 1 до к. Затем для каждого I 6 {1, к} проделаем следующее.

Припишем I-му листу (обозначим его а/) запись г//.

Если 0(yi,p) ф 0, то из корня в лист а/ проведем щ ориентированных цепей, причем г-я цепь (г = 1 , п*) будет состоять из тц ребер. Теперь для каждого г (г € {1, п/}) проделаем следующее. Если flijF, то j-e ребро i-й цепи объявим предикатным и припишем ему предикат fHj. Если fuj G 6 (т.е. //у = где р € <7, а п € gN), то вершину 0, из которой исходит j-e ребро г-й цепи, объявим переключательной и припишем ей переключатель д, j-му ребру г-й цепи припишем число п, из вершины 0 выпустим еще г — 1 ребро, где г — мощность области значений переключателя д, и сопоставим им взаимно однозначно числа из множества {1,г} {п}.

Нетрудно видеть, что в этом случае

Поскольку это условие выполняется для всех листьев, то согласно теореме 1 построенный ИГ разрешает ЗИП I.

Необходимость.

Пусть Т полно для отношения р. Возьмем произвольную запись у 6 У такую, что 0(у, р) ф 0. Пусть V — любая библиотека, содержащая запись у.

Так как Т полно, то существует ИГ t/, разрешающий ЗИП I = = (X,V,p). Рассмотрим множество Lu{y) листьев ИГ U, которым соответствует запись у. Так как U разрешает задачу /, то согласно теореме 1

Поскольку каждая из функций y?Q(ar) есть функция проводимости от корня к листу а, а функция проводимости по определению есть дизъюнкция конъюнкций некоторых предикатов из F U G, то необходимость доказана, что и доказывает теорему.

Упражнения

1.15. Пусть S = (Х,Х,=) — тип поиска идентичных объектов, базовое множество имеет вид Т — (0, С7), где множество переключателей G задается соотношением (1.8). Будет ли полно базовое множество Т для типа 5?

1.16. Задача включающего поиска, описанная в упражнении 1.4, может

ь ъ

быть задана типом Sbooi = (Вп, Вп} >;), где Вп — n-мерный булев куб, У — отношение поиска на Вп х Вп, определяемое следующим соотношением

Приведите пример базового множества, полного для типа Sbooi? Приведите пример минимального по мощности базового множества, полного для типа Sbooi’

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы