C2, … Ck}
1) {A1, A2, … An}= {B1, B2, …
Bm}∪ {C1, C2, … Ck}2) S=π B1, B2, … Bm (R)
3) T=π C1, C2, … Ck (R)
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Функциональные зависимости. Нормализация отношений
Содержание
- 1. Функциональные зависимости. Нормализация отношений
- 2. Пример плохого отношенияФирма-товар
- 3. НедостаткиИзбыточностьАномалии измененияАномалии удаленияАномалии добавления
- 4. Решение - декомпозицияФирмаТовар
- 5. ДекомпозицияR {A1, A2, … An}S {B1,
- 6. Ограничения на значения:семантические, т.е. корректность отдельных значений
- 7. Функциональные зависимостиR {A1, A2, … An}X, Y
- 8. A1, A2, … An → B1, B2,
- 9. КлючКлюч – набор атрибутов, который функционально определяет
- 10. Замыкание множества атрибутовR {A1, A2, … An}{B1,
- 11. ПримерR {A, B, C, D, E, F} S = {A→D, AB→E, BF→E, CD→F, E→C} {AE}+ ?
- 12. ПримерR {A, B, C, D, E, F}
- 13. Аксиомы Армстронгаесли B⊂A, то A→B рефлексивность;если
- 14. Правила вывода (из аксиом Армстронга)1. Объединение Если
- 15. Замыкание множества функциональных зависимостейF+ - множество
- 16. Замыкание множества функциональных зависимостейR {A1, A2,
- 17. Пример:R (A, B, C, D)AB →C, C
- 18. Покрытие множества функциональных зависимостейМножество ФЗ F2 называется
- 19. Минимальное покрытие множества функциональных зависимостейправая часть любой
- 20. ДЕКОМПОЗИЦИЯДекомпозиция – это разбиение на множества, может
- 21. А что происходит с зависимостями при декомпозиции?Можно
- 22. Проектирование реляционных отношений1 нормальная форма (НФ)–
- 23. 3 НФТранзитивная зависимость: пусть A, B, C
- 24. Примеры: Универмаг, Товар, Номер отдела, ЗаведующийГород, Индекс, Адрес
- 25. Примеры: 3 нормальная форма – (Город, Индекс,
- 26. НФ Бойса-КоддаНормальная форма Бойса–Кодда – если X→A,
- 27. НФ Бойса-Кодда(Город, Индекс, Адрес) – 3 нормальная
- 28. Вывод:Каждая схема отношений может быть приведена к
- 29. Шаги при декомпозицииНаходим минимальное покрытие множества функциональных
- 30. ПримерS Студент G ГруппаH ВремяR АудиторияC ПредметT Преподаватель
- 31. Скачать презентанцию
Пример плохого отношенияФирма-товар
Слайды и текст этой презентации
Слайд 5
Декомпозиция
R {A1, A2, … An}
S {B1, B2, … Bm} T {C1,
C2, … Ck}
Bm}∪ {C1, C2, … Ck}2) S=π B1, B2, … Bm (R)
3) T=π C1, C2, … Ck (R)
Слайд 6Ограничения на значения:
семантические, т.е. корректность отдельных значений (год рождения больше
нуля);
ограничения на значения, которые зависят только от равенства или неравенства
значений (совпадают ли компоненты двух кортежей); наиболее важные ограничения называются функциональной зависимостью.
Слайд 7Функциональные зависимости
R {A1, A2, … An}
X, Y ⊂ {A1, A2,
… An}
X → Y если любому значению X соответствует в
точности одно значение YX → Y ⇔ |πY(σX=x(R))|≤1
Название фирмы → Адрес, телефон.
Название фирмы, товар → Цена
Слайд 8A1, A2, … An → B1, B2, … Bm ФЗ
бывают:
Тривиальные
{B1, B2, … Bm } ⊂ {A1, A2, …
An } Нетривиальные {B1, B2, … Bm } ⊄ {A1, A2, … An } {A1, A2, … An } ∩ {B1, B2, … Bm } ≠∅
Полностью нетривиальные {A1, A2, … An } ∩ {B1, B2, … Bm } =∅
Слайд 9Ключ
Ключ – набор атрибутов, который функционально определяет все остальные
F –
множество функциональных зависимостей, заданных на отношении R
A→C называется транзитивной, если
существует такой атрибут B, что имеются функциональные зависимости A→B и B→C и отсутствует функциональная зависимость C→A
Слайд 10Замыкание множества атрибутов
R {A1, A2, … An}
{B1, B2, … Bm
} ⊂ {A1, A2, … An }
F – мн-во ФЗ
Z={B1,
B2, … Bm }+ Z0 := {B1, B2, … Bm }
BiBj → C
Z1:=Z0∪C
{B1, B2, … Bm } += {A1, A2, … An } ⇒ {B1, B2, … Bm } - ключ
Слайд 13Аксиомы Армстронга
если B⊂A, то A→B
рефлексивность;
если A→B, то AC→BC
пополнение;
если
A→B и B→C, то A→C
транзитивность.
Слайд 14Правила вывода
(из аксиом Армстронга)
1. Объединение
Если X→Y и X→Z, то X→YZ.
X→Y
+ А2 = X→XY, X→Z + A2 = YX→YZ +
A3 = X→YZ2. Псевдотранзитивность 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.
Слайд 15Замыкание множества
функциональных зависимостей
F+ - множество всех зависимостей, которые можно
вывести из F, называют замыканием множества ФЗ F
Любое множество
функциональных зависимостей, из которого можно вывести все остальные ФЗ, называется базисомЕсли ни одно из подмножеств базиса базисом не является, то такой базис минимален
Слайд 16Замыкание множества
функциональных зависимостей
R {A1, A2, … An}
F – мн-во
ФЗ
B1, B2, … Bm → C
(B1, B2, … Bm
→ C) ∈F+ , ifC∈{B1, B2, … Bm }+
Слайд 17Пример:
R (A, B, C, D)
AB →C, C →D, D→A
Найти все
нетривиальные ФЗ, которые следуют из заданных
Возможные ключи
Слайд 18Покрытие множества функциональных зависимостей
Множество ФЗ F2 называется покрытием множества ФЗ
F1, если любая ФЗ, выводимая из F1, выводится также из
F2.F1+∈F2+
F1 и F2 называются эквивалентными, если F1+ = F2+.
Слайд 19Минимальное покрытие множества функциональных зависимостей
правая часть любой ФЗ из F
является множеством из одного атрибута (простым атрибутом);
удаление любого атрибута из
левой части любой ФЗ приводит к изменению замыкания F+;удаление любой ФЗ из F приводит к изменению F+.
Слайд 20ДЕКОМПОЗИЦИЯ
Декомпозиция – это разбиение на множества, может быть пересекающиеся, такие,
что их объединение – это исходное отношение.
Восстановить исходное отношение можно
только естественным соединением.Говорят, что декомпозиция обладает свойством соединения без потерь, если для любого отношения r = πR1(r)▷◁ πR2(r) ▷◁ ... ▷◁ πRn(r).
Слайд 21А что происходит с зависимостями при декомпозиции?
Можно определить πZ(F): X→Y
XY⊆Z
Декомпозиция сохраняет множество зависимостей, если из объединения всех проекций зависимостей
логически следует F.
Слайд 22Проектирование
реляционных отношений
1 нормальная форма (НФ)– значения не являются множествами
и кортежами.
Атрибут называется первичным, если входит в состав любого возможного
ключа.2 нормальная форма – 1 НФ + любой атрибут, не являющийся первичным, полностью зависит от любого его ключа, но не от подмножества ключа.
Фирма, Адрес, Телефон, Товар, Цена
Слайд 233 НФ
Транзитивная зависимость: пусть A, B, C – атрибуты, A→B,
B→C, A не зависит от B и B не зависит
от C. Тогда говорят, что C транзитивно зависит от A.3 нормальная форма – если отношение находится во 2 нормальной форме и любой атрибут, не являющийся первичным, нетранзитивно зависит от любого возможного ключа.
Слайд 25Примеры:
3 нормальная форма – (Город, Индекс, Адрес)
2 нормальная форма,
но не 3 нормальная форма – (Универмаг, Товар, Номер отдела,
Заведующий)УТ→Н, УН→З, ключ – УТ.
Слайд 26НФ Бойса-Кодда
Нормальная форма Бойса–Кодда – если X→A, A∉X, то X⊇ключ
R.
(Город, Индекс, Адрес) – 3 нормальная форма, но не форма
Бойса–Кодда.
Если разобьем на две (Город, Индекс), (Индекс, Адрес), пропадает зависимость Город, Адрес→Индекс.
Слайд 27НФ Бойса-Кодда
(Город, Индекс, Адрес) – 3 нормальная форма, но не
форма Бойса–Кодда. Если разобьем на две (Город, Индекс), (Индекс, Адрес),
пропадает зависимость Город, Адрес→Индекс.
Слайд 28Вывод:
Каждая схема отношений может быть приведена к форме Бойса–Кодда, так
что декомпозиция обладает свойством соединения без потерь.
Любая схема может быть
приведена к 3 нормальной форме с соединением без потерь и с сохранением функциональной зависимости.Но не всегда можно привести к форме Бойса–Кодда с сохранением функциональных зависимостей.
Слайд 29Шаги при декомпозиции
Находим минимальное покрытие множества функциональных зависимостей
Выделяем зависимость, нарушающую
НФ
X → Y (и нет атрибутов, зависящих от Y).
Находим зависимости
с такой же левой частью.
X → W, X → ZВыделяем в отдельное отношение XYWZ
Из исходного отношения удаляем YWZ
Теги
