Функциональные зависимости Нормализация отношений

Пример плохого отношения Название фирмы АдресТелефонТоварЦена (руб.) Чижиков & CoУткин проезд, Винт большой3 Чижиков & CoУткин проезд, Винт маленький5 Винты-гайкиУл.Ленина, Винт4 Чижиков & CoУткин проезд, Гайка1 СтройтоварыСтройбаза Саморез2 Чижиков & CoУткин проезд, Саморез3 Фирма-товар

Недостатки Избыточность Аномалии изменения Аномалии удаления Аномалии добавления

Решение - декомпозиция Название фирмыАдресТелефон Чижиков & CoУткин проезд, Винты-гайкиУл.Ленина, СтройтоварыСтройбаза Название фирмыТоварЦена (руб.) Чижиков & CoВинт большой3 Чижиков & CoВинт маленький5 Винты-гайкиВинт4 Чижиков & CoГайка1 СтройтоварыСаморез2 Чижиков & CoСаморез3 Фирма Товар

Декомпозиция R {A 1, A 2, … A n } S {B 1, B 2, … B m }T {C 1, C 2, … C k } 1) {A 1, A 2, … A n }= {B 1, B 2, … B m } {C 1, C 2, … C k } 2) S= B1, B2, … Bm (R) 3) T= C1, C2, … Ck (R)

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

Функциональные зависимости R {A 1, A 2, … A n } X, Y {A 1, A 2, … A n } X Y если любому значению X соответствует в точности одно значение Y X Y | Y ( X=x (R))| 1 Название фирмы Адрес, телефон. Название фирмы, товар Цена

A 1, A 2, … A n B 1, B 2, … B m ФЗ бывают: Тривиальные {B 1, B 2, … B m } {A 1, A 2, … A n } Нетривиальные {B 1, B 2, … B m } {A 1, A 2, … A n } {A 1, A 2, … A n } {B 1, B 2, … B m } Полностью нетривиальные {A 1, A 2, … A n } {B 1, B 2, … B m } =

Ключ Ключ – набор атрибутов, который функционально определяет все остальные F – множество функциональных зависимостей, заданных на отношении R A C называется транзитивной, если существует такой атрибут B, что имеются функциональные зависимости A B и B C и отсутствует функциональная зависимость C A

Замыкание множества атрибутов R {A 1, A 2, … A n } {B 1, B 2, … B m } {A 1, A 2, … A n } F – мн-во ФЗ Z={B 1, B 2, … B m } + – Z 0 := {B 1, B 2, … B m } – B i B j C – Z 1 :=Z 0 C {B 1, B 2, … B m } + = {A 1, A 2, … A n } {B 1, B 2, … B m } - ключ

Пример R {A, B, C, D, E, F} S = {A D, AB E, BF E, CD F, E C} {AE} + ?

Пример R {A, B, C, D, E, F} S = {A D, AB E, BF E, CD F, E C} {AE} + = ACDEF

Аксиомы Армстронга если B A, то A B рефлексивность; если A B, то AC BC пополнение; если A B и B C, то A C транзитивность.

Правила вывода (из аксиом Армстронга) 1. Объединение Если X Y и X Z, то X YZ. X Y + А2 = X XY, X Z + A2 = YX YZ + A3 = X YZ 2. Псевдотранзитивность X Y и WY Z, то WX Z. X Y +A2 = WX WY. WY Z + A3 = WX Z. 3. Декомпозиция Если X Y и Z Y, то X Z. А1 + А3.

Замыкание множества функциональных зависимостей F + - множество всех зависимостей, которые можно вывести из F, называют замыканием множества ФЗ F Любое множество функциональных зависимостей, из которого можно вывести все остальные ФЗ, называется базисом Если ни одно из подмножеств базиса базисом не является, то такой базис минимален

Замыкание множества функциональных зависимостей R {A 1, A 2, … A n } F – мн-во ФЗ B 1, B 2, … B m C (B 1, B 2, … B m C) F +, if C {B 1, B 2, … B m } +

Пример: R (A, B, C, D) AB C, C D, D A Найти все нетривиальные ФЗ, которые следуют из заданных Возможные ключи

Покрытие множества функциональных зависимостей Множество ФЗ F 2 называется покрытием множества ФЗ F 1, если любая ФЗ, выводимая из F 1, выводится также из F 2. F 1 + F 2 + F 1 и F 2 называются эквивалентными, если F 1 + = F 2 +.

Минимальное покрытие множества функциональных зависимостей правая часть любой ФЗ из F является множеством из одного атрибута (простым атрибутом); удаление любого атрибута из левой части любой ФЗ приводит к изменению замыкания F + ; удаление любой ФЗ из F приводит к изменению F +.

ДЕКОМПОЗИЦИЯ Декомпозиция – это разбиение на множества, может быть пересекающиеся, такие, что их объединение – это исходное отношение. Восстановить исходное отношение можно только естественным соединением. Говорят, что декомпозиция обладает свойством соединения без потерь, если для любого отношения r = R1 (r) R2 (r)... Rn (r).

А что происходит с зависимостями при декомпозиции? Можно определить Z (F): X Y XY Z Декомпозиция сохраняет множество зависимостей, если из объединения всех проекций зависимостей логически следует F.

Проектирование реляционных отношений 1 нормальная форма (НФ)– значения не являются множествами и кортежами. Атрибут называется первичным, если входит в состав любого возможного ключа. 2 нормальная форма – 1 НФ + любой атрибут, не являющийся первичным, полностью зависит от любого его ключа, но не от подмножества ключа. Фирма, Адрес, Телефон, Товар, Цена

3 НФ Транзитивная зависимость: пусть A, B, C – атрибуты, A B, B C, A не зависит от B и B не зависит от C. Тогда говорят, что C транзитивно зависит от A. 3 нормальная форма – если отношение находится во 2 нормальной форме и любой атрибут, не являющийся первичным, нетранзитивно зависит от любого возможного ключа.

Примеры: Универмаг, Товар, Номер отдела, Заведующий Город, Индекс, Адрес

Примеры: 3 нормальная форма – (Город, Индекс, Адрес) 2 нормальная форма, но не 3 нормальная форма – (Универмаг, Товар, Номер отдела, Заведующий) УТ Н, УН З, ключ – УТ.

НФ Бойса-Кодда Нормальная форма Бойса–Кодда – если X A, A X, то X ключ R. (Город, Индекс, Адрес) – 3 нормальная форма, но не форма Бойса–Кодда. Если разобьем на две (Город, Индекс), (Индекс, Адрес), пропадает зависимость Город, Адрес Индекс.

НФ Бойса-Кодда (Город, Индекс, Адрес) – 3 нормальная форма, но не форма Бойса–Кодда. Если разобьем на две (Город, Индекс), (Индекс, Адрес), пропадает зависимость Город, Адрес Индекс.

Вывод: Каждая схема отношений может быть приведена к форме Бойса–Кодда, так что декомпозиция обладает свойством соединения без потерь. Любая схема может быть приведена к 3 нормальной форме с соединением без потерь и с сохранением функциональной зависимости. Но не всегда можно привести к форме Бойса– Кодда с сохранением функциональных зависимостей.

Шаги при декомпозиции 1.Находим минимальное покрытие множества функциональных зависимостей 2.Выделяем зависимость, нарушающую НФ X Y (и нет атрибутов, зависящих от Y). 3.Находим зависимости с такой же левой частью. X W, X Z 4.Выделяем в отдельное отношение XYWZ 5.Из исходного отношения удаляем YWZ

Пример S Студент G Группа H Время R Аудитория C Предмет T Преподаватель