Дипломы, курсовые, рефераты, контрольные...
Срочная помощь в учёбе

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

РефератПомощь в написанииУзнать стоимостьмоей работы

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

Полнота для информационных графов (реферат, курсовая, диплом, контрольная)

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

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

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

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

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

где fij 6 FuG.

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

Пусть нам дана произвольная ЗИП I = (XyVyp)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. Если fujG (то есть fuj = где д € С, а п 6 N), то вершину /?, из которой исходит j-e ребро i-й цепи, объявим переключательной припишем ей переключатель д) j-му ребру г-й цепи припишем число гг, из вершины Р выпустим еще г — 1 ребро, где г — мощность области значений переключателя д> и сопоставим им взаимно однозначно числа из множества {1,г} {п}.

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

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

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

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

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

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

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

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

Упражнения.

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

ь

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

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

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

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

Показать весь текст
Заполнить форму текущей работой