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

ЗАДАЧИ ПОИСКА НА ЧАСТИЧНО-УПОРЯДОЧЕННЫХ МНОЖЕСТВАХ ДАННЫХ

Задачи поиска на конечных частично-упорядоченных множествах данных

Задачи поиска, в которых отношение поиска, является отношением частичного порядка, встречаются практически во всех системах баз данных и в зависимости от интерпретации носят название включающего поиска [95], дескрипторного поиска [87, 103, 106], поиска по ключевым словам [56], задачи о доминировании [64, 86] и т. п.

В данном разделе мы приведем некоторые свойства отношений частичного порядка, полезные в том случае, когда эти отношения используются в качестве отношений поиска. Результаты, приведенные в данном разделе, были опубликованы в [31, 158]. Мы будем рассматривать типы задач поиска, в которых в качестве отношения поиска выступает отношение частичного порядка, а именно рассмотрим следующий тип SPart = (X, X, У)у где X — некоторое конечное множество, У — некоторое отношение частичного порядка на X х X, под которым будем понимать отношение, для любых х, у, z € X удовлетворяющее условиям

• рефлексивности х У х;

• транзитивности (х У у) & (у У z) -» (х У z);

• антисимметричности (х У у) & (у У х) —> = у).

Пусть а € X, Ка функция, действующая из X в {0,1} такая, что N^a = € X: х У а}. Отметим, что Ка(х) есть характеристическая функция записи а. Пусть

где N — множество натуральных чисел.

Справедливы следующие свойства.

Свойство 1. Если a, b G X и Кь(а) = 1, то 1^ка Я Nкь

Доказательство. Так как Кь{а) = 1, то а У 6. Для любого с € Nxa справедливо с У а У Ь. Отсюда следует, что с У 6 и, следовательно, с € TVtfb. Что и требовалось доказать.

Свойство 2. Ясли а е X, f € М и f(a) = l,mo N^a С TV/.

п

Доказательство. Пусть / = V ^а<- Так как /(а) = 1, то су-

»=1

ществует Kai такое, что Kai(a) = 1, но тогда согласно свойству 1 Нка Я Мка{ и> следовательно, TV/<-e С TV/. Что и требовалось доказать.

п

Свойство 3. Пусть а ? X и V /« = где fi € М. Тогда _ *=1

существует такое i € {1,п}, что /* = Ка.

Доказательство. Так как KQ(a) = 1, то существует такое г, что fi(a) = 1. Тогда согласно свойству 2 имеем TVjfe С TV/., но из условия следует, что TV/< С TV*Q, следовательно, TVxe = TV/., т. е. Яа = /»• Что и требовалось доказать.

п

Свойство 4. Ясли а е X, f = Д /», где fi € М и f(a) = 1, mo С TV/.

п

Доказательство. TV/ = f| TV/,. Так как а € TV/, то a G TV/, для

t=i

любого г = 1,...,п. Отсюда согласно свойству 2 имеем Nxa Я Nft

п

для любого i = 1 Следовательно, TV/<-a С f| TV/. = TV/. Что

i=l

и требовалось доказать.

Точку а € R С X назовем нижней единицей множества Я, если не существует точки 6 G Я {а} такой, что а У Ь.

п п

Доказательство. TV/ = f) TV/,. Допустим, что f] Nf. ф 0, т.е.

»=i i=i

/ ф 0. Просмотрим все точки множества Nf (а их конечное число) и для каждой проверим, является ли она нижней единицей? Пусть М = {ai,...,am} — множество всех нижних единиц множества TV/, которое мы в результате получили. Легко видеть, что для любой точки a 6 TV/ либо a 6 М, либо существует a* € М такое, что а У а,-. Из того, что а >: di следует Ка.(а) = 1 => а € NKai • Следовательно,

т

Nf С (J Мка С другой стороны, согласно свойству 4 (используем *=1

то, что /(а*) = 1) для любого г Е {1,...,ш} имеем Nxai С N/.

т

Следовательно, Nf = (J Nxa. и, значит, / ? Л4, что и требовалось *=1

доказать.

Пусть базовое множество имеет вид Т = (Л4,0). Пусть U — ПИГ над базовым множеством Т. Подмножество {ft,..., /Зт} вершин ПИГ U назовем характерным, если существует такая запись а 6 X, что

m

V (РА = Ка-

1 = 1

Пусть U — ПИГ над базовым множеством Т = (Л4,0). Пусть Б = = {ft,...,/?m} — характерное подмножество вершин ПИГ С/ такое,

т

что V (рр{ = Ка. Если в ПИГ U существует цепь, ведущгся из корня *=1

в какую-либо вершину множества В такая, что проводимость этой цепи равна Ка, то эту цепь назовем главной цепью характерного множества В.

Теорема 21 (о существовании главных цепей). Пусть Uпроизвольный ПИГ над базовым множеством Т = , 0). Пусть В — произвольное характерное подмножество вершин ПИГ U. Тогда в ПИГ U существует главная цепь множества В.

Доказательство. Рассмотрим некоторую цепь С графа U. Обозначим через fc проводимость цепи С. Пусть С такая цепь, что ^ = 0. Так как fc равна конъюнкции нагрузок ребер цепи С, то согласно свойству 5 имеем fc ? М. Пусть С в — множество цепей, ведущих из корня в вершины множества В. Так как В — характерное множество, то существует такая запись а € X, что V Фр = V fc — ^а-

рев сесв

Отсюда, согласно свойству 3 существует цепь С' 6 С в такая, что fc' = = Ка. Эта цепь С' и есть главная цепь множества В. Что и требовалось доказать.

Пусть U — ПИГ над базовым множеством Т = (Л4,0), разрешающий некоторую ЗИП I = (X, V, >;) типа Spart• Пусть у 6 Г. Если в графе U существует цепь, ведущая из корня в какую-либо вершину множества Ьц(у) такая, что проводимость этой цепи равна Xy,t> то эту цепь назовем главной цепью записи у.

Следствие 10. Пусть I = (X, V, >:) — ЗИП типа SpartПусть UПИГ над базовым множеством Т = (Л4,0), разрешающий ЗИП I. Тогда для любой записи у 6 V в графе U существует главная цепь записи у.

Доказательство. В силу свойства рефлексивности отношения У 0(у, h) Ф 0- Так как ПИГ U разрешает ЗИП 7, то V ^Ра — Ху,у =

<*€?v(y)

= К у согласно теореме 1. Следовательно, множество Ьц(у) есть характерное множество, и согласно теореме 21 в графе U существует главная цепь множества Lu(y). Что и требовалось доказать.

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