X
Код презентации скопируйте его
Функциональные зависимости. Нормализация отношений
Скачать эту презентацию
Презентация на тему Функциональные зависимости. Нормализация отношений
Скачать эту презентациюCлайд 1
Функциональные зависимости Нормализация отношений
Cлайд 2
Пример плохого отношения Фирма-товар Название фирмы Адрес Телефон Товар Цена (руб.) Чижиков & Co Уткин проезд, 5 999-99-99 Винт большой 3 Чижиков & Co Уткин проезд, 5 999-99-99 Винт маленький 5 Винты-гайки Ул.Ленина, 1 333-33-33 Винт 4 Чижиков & Co Уткин проезд, 5 999-99-99 Гайка 1 Стройтовары Стройбаза № 1 444-44-44 Саморез 2 Чижиков & Co Уткин проезд, 5 999-99-99 Саморез 3
Cлайд 3
Недостатки Избыточность Аномалии изменения Аномалии удаления Аномалии добавления
Cлайд 4
Решение - декомпозиция Фирма Товар Название фирмы Адрес Телефон Чижиков & Co Уткин проезд, 5 999-99-99 Винты-гайки Ул.Ленина, 1 333-33-33 Стройтовары Стройбаза № 1 444-44-44 Название фирмы Товар Цена (руб.) Чижиков & Co Винт большой 3 Чижиков & Co Винт маленький 5 Винты-гайки Винт 4 Чижиков & Co Гайка 1 Стройтовары Саморез 2 Чижиков & Co Саморез 3
Cлайд 5
Декомпозиция R {A1, A2, … An} S {B1, B2, … Bm} T {C1, C2, … Ck} 1) {A1, A2, … An}= {B1, B2, … Bm} {C1, C2, … Ck} 2) S= B1, B2, … Bm (R) 3) T= C1, C2, … Ck (R)
Cлайд 6
Ограничения на значения: семантические, т.е. корректность отдельных значений (год рождения больше нуля); ограничения на значения, которые зависят только от равенства или неравенства значений (совпадают ли компоненты двух кортежей); наиболее важные ограничения называются функциональной зависимостью.
Cлайд 7
Функциональные зависимости R {A1, A2, … An} X, Y {A1, A2, … An} X Y если любому значению X соответствует в точности одно значение Y X Y | Y( X=x(R))| 1 Название фирмы Адрес, телефон. Название фирмы, товар Цена
Cлайд 8
A1, 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 } =
Cлайд 9
Ключ Ключ – набор атрибутов, который функционально определяет все остальные F – множество функциональных зависимостей, заданных на отношении R A C называется транзитивной, если существует такой атрибут B, что имеются функциональные зависимости A B и B C и отсутствует функциональная зависимость C A
Cлайд 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 } - ключ
Cлайд 11
Пример R {A, B, C, D, E, F} S = {A D, AB E, BF E, CD F, E C} {AE}+ ?
Cлайд 12
Пример R {A, B, C, D, E, F} S = {A D, AB E, BF E, CD F, E C} {AE}+ = ACDEF
Cлайд 13
Аксиомы Армстронга если B A, то A B рефлексивность; если A B, то AC BC пополнение; если A B и B C, то A C транзитивность.
Cлайд 14
Правила вывода (из аксиом Армстронга) 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.
Cлайд 15
Замыкание множества функциональных зависимостей F+ - множество всех зависимостей, которые можно вывести из F, называют замыканием множества ФЗ F Любое множество функциональных зависимостей, из которого можно вывести все остальные ФЗ, называется базисом Если ни одно из подмножеств базиса базисом не является, то такой базис минимален
Cлайд 16
Замыкание множества функциональных зависимостей R {A1, A2, … An} F – мн-во ФЗ B1, B2, … Bm C (B1, B2, … Bm C) F+ , if C {B1, B2, … Bm }+
Cлайд 17
Пример: R (A, B, C, D) AB C, C D, D A Найти все нетривиальные ФЗ, которые следуют из заданных Возможные ключи
Cлайд 18
Покрытие множества функциональных зависимостей Множество ФЗ F2 называется покрытием множества ФЗ F1, если любая ФЗ, выводимая из F1, выводится также из F2. F1+ F2+ F1 и F2 называются эквивалентными, если F1+ = F2+.
Cлайд 19
Минимальное покрытие множества функциональных зависимостей правая часть любой ФЗ из F является множеством из одного атрибута (простым атрибутом); удаление любого атрибута из левой части любой ФЗ приводит к изменению замыкания F+; удаление любой ФЗ из F приводит к изменению F+.
Cлайд 20
ДЕКОМПОЗИЦИЯ Декомпозиция – это разбиение на множества, может быть пересекающиеся, такие, что их объединение – это исходное отношение. Восстановить исходное отношение можно только естественным соединением. Говорят, что декомпозиция обладает свойством соединения без потерь, если для любого отношения r = R1(r) R2(r) ... Rn(r).
Cлайд 21
А что происходит с зависимостями при декомпозиции? Можно определить Z(F): X Y XY Z Декомпозиция сохраняет множество зависимостей, если из объединения всех проекций зависимостей логически следует F.
Cлайд 22
Проектирование реляционных отношений 1 нормальная форма (НФ)– значения не являются множествами и кортежами. Атрибут называется первичным, если входит в состав любого возможного ключа. 2 нормальная форма – 1 НФ + любой атрибут, не являющийся первичным, полностью зависит от любого его ключа, но не от подмножества ключа. Фирма, Адрес, Телефон, Товар, Цена
Cлайд 23
3 НФ Транзитивная зависимость: пусть A, B, C – атрибуты, A B, B C, A не зависит от B и B не зависит от C. Тогда говорят, что C транзитивно зависит от A. 3 нормальная форма – если отношение находится во 2 нормальной форме и любой атрибут, не являющийся первичным, нетранзитивно зависит от любого возможного ключа.
Cлайд 24
Примеры: Универмаг, Товар, Номер отдела, Заведующий Город, Индекс, Адрес
Cлайд 25
Примеры: 3 нормальная форма – (Город, Индекс, Адрес) 2 нормальная форма, но не 3 нормальная форма – (Универмаг, Товар, Номер отдела, Заведующий) УТ Н, УН З, ключ – УТ.
Cлайд 26
НФ Бойса-Кодда Нормальная форма Бойса–Кодда – если X A, A X, то X ключ R. (Город, Индекс, Адрес) – 3 нормальная форма, но не форма Бойса–Кодда. Если разобьем на две (Город, Индекс), (Индекс, Адрес), пропадает зависимость Город, Адрес Индекс.
Cлайд 27
НФ Бойса-Кодда (Город, Индекс, Адрес) – 3 нормальная форма, но не форма Бойса–Кодда. Если разобьем на две (Город, Индекс), (Индекс, Адрес), пропадает зависимость Город, Адрес Индекс.
Cлайд 28
Вывод: Каждая схема отношений может быть приведена к форме Бойса–Кодда, так что декомпозиция обладает свойством соединения без потерь. Любая схема может быть приведена к 3 нормальной форме с соединением без потерь и с сохранением функциональной зависимости. Но не всегда можно привести к форме Бойса–Кодда с сохранением функциональных зависимостей.
Cлайд 29
Шаги при декомпозиции Находим минимальное покрытие множества функциональных зависимостей Выделяем зависимость, нарушающую НФ X Y (и нет атрибутов, зависящих от Y). Находим зависимости с такой же левой частью. X W, X Z Выделяем в отдельное отношение XYWZ Из исходного отношения удаляем YWZ
Cлайд 30
Пример S Студент G Группа H Время R Аудитория C Предмет T Преподаватель
