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

Если нам дана ЗИП I = (X, V, p) и базовое множество Т = (F, G), то возникает вопрос: а можно ли построить информационный граф над базовым множеством Т, разрешающий эту задачу /? Если для любой записи yi € V = {yi, • • •, У*} имеем Xy_itp € Е, то ответ на этот вопрос положительный, и граф, изображенный на рис. 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, функцию Ху, р (^х) можно представить формулой вида

где fij G F U G,

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

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

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

где fuj € FUG, l = l, fc.

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

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

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

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

Если 0(yi, p) ф 0, то из корня в лист а/ проведем щ ориентированных цепей, причем г-я цепь (г = 1, п*) будет состоять из тц ребер. Теперь для каждого г (г € {1, п/}) проделаем следующее. Если flij € F, то j-e ребро i-й цепи объявим предикатным и припишем ему предикат f_Hj. Если 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'