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

Если нам дана ЗИП I = (X_yV_yp) и базовое множество Т = (F, G), то возникает вопрос, а можно ли построить информационный граф над базовым множеством Т, решающий эту задачу /? Если для любой записи у;? V = {yi,… , ук} Ху"р € F, то ответ на этот вопрос положительный, и граф, изображенный на рисунке 2.5, решает задачу /.

В данном разделе дается более полный ответ на этот вопрос. Пусть нам дан тип S = (X_yY_yp)_y где X — множество запросов, Y — множество записей, р — отношение поиска, заданное на X х У, и базовое множество Т = {F_yG).

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

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

Теорема 10. Пусть заданы множества запросов X, записей Y, отношение поиска р на X х Y и базовое множество Т — (F_yG), такое, что предикат тождественная 1 принадлежит множеству F. Тогда Т будет полным для типа S = {Х_у Y, р) тогда и только тогда, когда для любой записи у 6 Y такой, что 0(у_ур) ф 0, функцию Ху, р{^х) можно представить формулой вида

где fij 6 FuG.

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

Пусть нам дана произвольная ЗИП I = (X_yV_yp)_y где V = {yi >••?•" Уk} Q Y. По предположению каждую из функций.

Xyi, p (^x) (i = 1, А:) можно представить формулой где fuj Е FUG, I = l, k.

Без ограничения общности можно считать, что каждая конъюнкция ДТЦ flij (^x) содержит предикат из F, причем этот предикат стоит первым в конъюнкции. В противном случае мы всегда можем добавить предикат тождественная 1.

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

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

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

Если 0(yi, p) ф 0, то проведем из корня в лист сц щ ориентированных цепей, причем г-я цепь (г = 1, п/) будет состоять из гпц ребер. Теперь для каждого г (г Е {1,п/}) проделаем следующее. Если flij € F, то j-e ребро г-й цепи объявим предикатным и припишем ему предикат fuj. Если fuj € G (то есть fuj = где д € С, а п 6 N), то вершину /?, из которой исходит j-e ребро i-й цепи, объявим переключательной припишем ей переключатель д₎ j-му ребру г-й цепи припишем число гг, из вершины Р выпустим еще г — 1 ребро, где г — мощность области значений переключателя д> и сопоставим им взаимно однозначно числа из множества {1,г} {п}.

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

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

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

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

Так как Т полно, то существует ИГ U, решающий ЗИП I =.

(X, У, р). Рассмотрим множество Ьц (у) листьев ИГ U, которым соответствует запись у. Так как U решает задачу /, то согласно теореме 9

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

Упражнения.

• 2.25. Пусть S = (Х_} Х,=) — тип поиска идентичных объектов, базовое множество имеет вид Т — (0, С), где множество переключателей G задается соотношением (2.8). Будет ли полно базовое множество Т для типа 5?
• 2.26. Задача включающего поиска, описанная в упражнении 2.14,

ь

может быть задана типом Sbooi = (В^п_уВ^ПуУ), где В^п — п-мерный ь

булев куб, У — отношение поиска на В^п х В^п, определяемое следующим соотношением.

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