Графическое представление функциональных зависимостей.

Для множества функциональных зависимостей F вида X→A, заданного на множестве атрибутов А1, А2, …, An можно построить направленный граф, имеющий два типа вершин.

1. Для каждого атрибута Aj строим вершину, помеченную Aj.

2. Для каждой функциональной зависимости Xj→Aj, где Х ={Aj1, Aj2, …, Ajm строим либо дугу, где m=1, либо дополнительную вершину, помечаем ее Xj, а в нее входят дуги от вершин Aj1 и так далее.

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

Пример ПОТОМ

Нормализация схем отношений.

Существуют два подхода к нормализации. Один основан на декомпозиции, а другой – на синтезе схемы.

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

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

Алгоритм декомпозиции.

Пусть задан граф функциональных зависимостей. Если схема отношения нарушает третью нормальную форму, то возможны следующие варианты:

1) Частичная зависимость.

R{K1, K2,X, Y}

X, Y – множество неключевых атрибутов,

К1, К2 – ключи

К2 → Х

Заменяем R на две схемы.

R1={K1, K2, Y}, R2={K1, X}

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

2) Транзитивная зависимость. Пусть R={K, X1, X2, X3}

K – ключевые атрибуты,

X1, X2, X3 – множество неключевых атрибутов.

K→X1→X

Заменяем R на две схемы: R1={K, X1, X3}, R2={X1, X2}

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

3) Сложнотранзитивная зависимость

Пусть R={K1, K12, X1, X2, X3}

K2X1→X2

CN → CName

PN → PName

SN → SName

PName → type

PName → color

CN, PN→SN

CN, PN, SN → Q

Имеется транзитивная зависимость SN → SName

Выделяем схему:

Остается:

Алгоритм синтеза.

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

1. Разбиваем множество функциональных зависимостей F на подмножество Fi так, чтобы в подмножестве были все функциональные зависимости с одинаковыми левыми частями.

2. Для каждого Fi строим реляционную схему, состоящую из всех атрибутов, участвующих в Fi. Эта схема будет в третьей нормальной форме, а ключ ее – в левой части Fi.

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

Многозначные зависимости.

Схема, находящаяся в НФБК, может иметь аномалии обновления. Например, имеется отношение «Студент».

В этом отношении нет функциональных зависимостей, а аномалии есть. Для каждого студента (номер зачетки) существует несколько предметов и несколько видов спорта, которые не зависят друг от друга.

Пример показывает, что недостаточно анализировать одни функциональные зависимости, которые не отражают факт независимости между атрибутами (предмет, спорт). Независимость в данном случае ведет к избыточности и аномалиям.

Для того, чтобы избежать избыточности вследствие независимости данных, необходимо изучать многозначные зависимости.

Определение. Пусть имеется схема отношения R={A1, A2, …., An}, а в ней непересекающиеся подмножества X и Y. Z=R - (X U Y). Тогда говорят, что существует многозначная зависимость из X в Y (X→→Y), если для каждого отношения r со схемой R справедливо, что для любых двух кортежей t1 и t2 из r с равными проекциями на х следует, что в r существует кортеж t3, такой что его проекция на х равна проекции на х t2, проекция t3 на y равна проекции на y t1, проекция t3 на z равна проекции на z t2.

То есть для любых двух кортежей t1 и t2, у которых t1(x)=t2(x), обязательно существует в r кортеж t3, такой, что <t1(x), t1(y), t2(z)>. Из соображений симметрии существует кортеж t4, такой, что <t1(x), t2(y), t1(z)>.

Например, в вышестоящей таблице действует многозначная зависимость НомерЗачетки →→Предмет

Поэтому, если взять два кортежа t1=<100, БД, Футбол> и t2=<100, ООП, Теннис>, то из определения многозначной зависимости следует существование еще двух кортежей: t3=<100, ООП, Теннис> и t4=<100, ООП, Футбол>.

Многозначная зависимость является свойством предметной области: то есть мы знаем, что если взять какой-то предмет (БД), который читает в t1 в аудитории a1 преподаватель p1 студенту s1 с оценкой m1 и, если этот же предмет читается в t2 в аудитории а2 преподавателем p2 студенту s2 с оценкой m2.

Тривиальная многозначная зависимость время, аудитория →→ аудитория.

Можно доказать, что выполнение функциональной зависимости X→Y влечет выполнение многозначной зависимости X→→Y. Если в отношении R={X, Y, Z} задана многозначная зависимость X→→Y, то справедливо и X→→Z, то есть многозначные зависимости всегда появляются парами (X→→Y|Z).

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

Теорема: R={X, Y, Z}, тогда декомпозиция R на (X, Y) и (X, Z) обладает свойством соединения без потерь, если на R задана многозначная зависимость X→→Y|Z.

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

Определение: Если для подмножества атрибутов X и Y задана многозначная зависимость X→→Y и все атрибуты из R функционально зависят от Х, это означает, что отношение находится в четвертой нормальной форме. Другими словами, в R должны быть только зависимости вида K→X, то есть функциональные зависимости от ключа к другим атрибутам: отношение находится в четвертой нормальной форме, если оно в НФБК и все многозначные зависимости являются функциональными, выходящими из ключа.