Неприводимое множество зависимостей.

 

Пусть S1 и S2 – два множества функциональных зависимостей. Если S1⁺ = S2⁺ , то множества S1 и S2 – эквивалентны. Если S1 эквивалентно S2, то соблюдение СУБД ограничений, представленных зависимостями множества S2, автоматически обеспечит соблюдение ограничений, представленных зависимостями S1 и наоборот.

Можно найти множество функциональных зависимостей S2, которое эквивалентно S1 и неприводимо, не вычисляя замыкание.

Множество ФЗ называется неприводимым тогда и только тогда, когда оно обладает следующими свойствами:

- каждая функциональная зависимость этого множества имеет одноэлементную правую часть;

- если ни одна функциональная зависимость множества не может быть устранена без изменения замыкания этого множества, т.е. без утраты некоторой информации.

- если ни один атрибут не может быть устранен из левой части любой функциональной зависимости данного множества без изменения замыкания множества.

 

 

Пример4.Дана переменная-отношение S с функциональными зависимостями.

S# ―> SNAME

S# ―> STATUS

S# ―> CITY

Является ли множество функциональных зависимостей неприводимым?

 

Решение. Это множество функциональных зависимостей является неприводимым, так как:

1. Правая часть каждой функциональной зависимости содержит один атрибут.

2. Ни одна из этих зависимостей не может быть опущена без изменения замыкания множества, то есть без утраты некоторой информации.

3. Левая часть каждой функциональной зависимости является неприводимой (ее нельзя сократить).

Лекция9. Нормализация.

Процесс нормализации основывается на концепциях нормальных норм. Первая НФ (1НФ), вторая НФ (2НФ), третья НФ (3НФ) определены Коддом. Определение Кодда 3НФ приводит к некоторой неадекватности. Переработанное и более точное понятие 3НФ, данное Бойсом и Коддом является более строгим. Отношение в 3НФ по новому определению называют нормальной формой Бойса-Кодда (НФБК). Четвертая НФ (4НФ) и пятая НФ (5НФ) определены Фейгином (Fagin).

Говорят, что отношение находится в нормальной форме, если оно удовлетворяет заданному набору условий.

 

Декомпозиция без потерь.

Декомпозиция должна быть обратимой. Это значит, что она должна выполняться без потерь информации.

Рассмотрим переменную -отношение S.

S

S#	STATUS	CITY
S3		Paris
S5		London

 

а)

SST SC

S#	STATUS
S3
S5

 

 

STATUS	CITY
	Paris
	London

 

б)

SST

 

STS

S#	STATUS
S3
S5

STATUS	CITY
	Paris
	London

Рис. 1. Декомпозиция переменной- отношения S.

 

Следует отметить, что процесс декомпозиции – это операция проекции.

В случае а)информация не утрачивается (декомпозиция без потерь). При соединении переменных -отношений SST и SC будет получено исходное отношение S. В случае б) нельзя сказать в каком городе находится поставщик. При соединении переменных -отношений SST и STC получено исходное отношение S получено не будет, значит некоторая информация будет утрачена. В этом случае декомпозиция не является декомпозицией без потерь.

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

Каждая переменная-отношение S; SP; P имеет неприводимое множество функциональных зависимостей. Эти функциональные зависимости можно представить еще в виде диаграммы.

Рис.2. Диаграммы функциональных зависимостей для переменных - отношений S; SP; P.

Все переменные - отношения находятся в 3НФ.