Вычисление замыканий.

1. Вычисление для множества является весьма трудоемкой задачей, т.к. множество может быть весьма большим, даже при малом .

В общем случае: . Тогда включает все функциональные зависимости , где подмножество множества . Т.к. множеств 2ⁿ, то огромно.

2. Вычисление для данного множества атрибутов несложно, т.к. количество вычислений по времени пропорционально мощности множества .

Алгоритм вычисления:

Дано: конечное множество атрибутов , множество функциональных зависимостей F на и .

1˚ ;

2˚

множество атрибутов таких, что в F существуют функциональные зависимости , где и . Т.к. и – конечно, то мы должны в итоге достичь такого , что . Отсюда следует признак конца вычислений: . Тогда .

Выполняем 2) до тех пор, пока не рассмотрим все функциональные зависимости.

Пример: Найти замыкание множества атрибутов относительно замыкания функциональных зависимостей.

1. 

2.

3. Рассмотрим функциональные зависимости:

Декомпозиция схем отношений.

Декомпозиция схем отношений является важным элементом проектирования БД. Декомпозицией схемы отношений называется замена ее совокупностью схем подмножеств таких, что ; не обязательно При построении декомпозиции желательно выполнение двух свойств:

1. свойство соединения без потерь:

,

где является естественным соединением его проекций на все .

Метод, проверяющий сохраняется ли свойство соединения без потерь:

Строится таблица с n столбцами и k строками. Столбец j соответствует атрибуту , а i-я строка отношению . На пересечении строки i и столбца j поместим символ a_j, если . В противном случае туда поместим символ b_ij.

Повторно рассматриваем каждую из зависимостей в до тех пор, пока в таблице невозможно будет сделать какие-либо изменения. Всякий раз, рассматривая зависимости , мы ищем строки, которые совпадают по всем столбцам, соответствующим атрибутам из X. При обнаружении двух таких строк отождествляем их символы в столбцах, соответствующих атрибутам из Y. Если при этом один из отождествляемых символов = a_j, приравниваем и другому a_j. В том случае, когда они равны b_lj и b_lj, делаем их оба равными b_lj или b_lj по своему усмотрению.

После модификации строк таблицы может обнаружиться, что некоторая строка стала равной . Тогда декомпозиция обладает свойством соединения без потерь. В противном случае она не обладает таким свойством.

Пример:

	N	A	T	C
R1	a1	a2	b13	b14 a4
R2	a1	b22 a2	a3	a4

• декомпозиция обладает свойством соединения без потерь.

2. множество зависимостей для должно быть выводимо из проекций на схемы отношений .

Формально проекцией на множество зависимостей в таких, что ( не обязательно ). Будем говорить, что декомпозиция сохраняет множество зависимостей , если из: логически следуют все зависимости, принадлежащие .

Это следует из того, что рассматриваются как ограничения целостности. Т.к. если бы из спроецированных зависимостей не следовало бы , то мы могли бы обнаружить такие текущие значения , представляющего отношение в декомпозиции, которые не удовлетворяют .

Может выполняться только одно из свойств. Декомпозиция может сохранять , не обладая свойством соединения без потерь. Например, . И, наоборот.

Для того чтобы привести схему отношения к какой-то декомпозиции существуют алгоритмы.