II.7. Многозначни зависимости — Разширена писмена разработка
Разширена писмена разработка. II.7. Многозначни зависимости
Подробен авторски текст за подготовка по конспекта на СУ. Краткият вариант е запазен на основната страница на темата. За преговор използвай плана; за обосновка — определенията и разработените примери. Това не е официален изпитен образец.
Кратка разработка и уроци по темата · План за изпита · Покритие · Източници
Обхват от конспекта
Многозначни зависимости. Независимост на атрибут и следващото от това излишество. Определение за многозначна зависимост. Причини за многозначните зависимости. Четвърта нормална форма. Декомпозиция в четвърта нормална форма. Връзка между нормалните форми.
Покритие на конспекта
Всяка подточка води към съответния раздел на разработката.
- Многозначни зависимости — 1. Независимостта също може да създава излишества
- Независимост на атрибут и следващото от това излишество — 1. Независимостта също може да създава излишества
- Определение за многозначна зависимост — 2. Формално определение
- Причини за многозначните зависимости — 1. Независимостта също може да създава излишества
- Четвърта нормална форма — 3. Четвърта нормална форма
- Декомпозиция в четвърта нормална форма — 4. Декомпозиция в 4NF
- Връзка между нормалните форми — 5. Връзка между нормалните форми
Кратък план за изпита
- Независими множества факти и излишества.
- Формално определение на многозначна зависимост.
- Тривиалност, допълване и връзка с ФЗ.
- 4NF и беззагубна декомпозиция.
- BCNF, 3NF и граници на нормализацията.
1. Независимостта също може да създава излишества
Функционалните зависимости не описват всички причини за повторения. Нека СЛУЖИТЕЛ(Номер, Език, Умение) записва езиците и професионалните умения на служителите. Бизнес правилото е, че езиците и уменията са независими: не записваме „умение, упражнявано на определен език“, а два отделни списъка способности.
За служител С01 с езици български и английски и умения SQL и Python широката релация трябва да съдържа всички четири комбинации:
(С01, български, SQL) (С01, български, Python) (С01, английски, SQL) (С01, английски, Python)
Номер не определя един-единствен Език или едно-единствено Умение. При тези правила може да няма нетривиална ФЗ с несуперключ отляво и схемата да е в BCNF, но повторението остава. Добавяне на нов език изисква по ред за всяко умение. Пропусната комбинация може погрешно да подскаже, че независимостта не е вярна. При k езика и m умения са нужни k·m реда вместо k + m факта в две отделни релации.
Причината не е наличието на множество стойности само по себе си, а смесването на независими многозначни факти в една схема. Ако служителят владее SQL само на български, а Python само на английски, комбинацията има собствено значение и независимостта е невярна. Тогава не трябва да създаваме липсващите двойки или да декомпозираме по несъществуваща зависимост.
2. Формално определение
За схема R разделяме атрибутите на неприпокриващи се множества X, Y и Z, където Z са останалите атрибути. Многозначната зависимост (МЗ) X ↠ Y означава: за всяка двойка кортежи t и u с еднакви стойности върху X съществуват и кортежите, получени чрез размяна на Y и Z частите. Тоест трябва да присъстват комбинациите (t[X], t[Y], u[Z]) и (t[X], u[Y], t[Z]).
Еквивалентно: при фиксирана стойност x на X допустимите Y и Z се комбинират като декартово произведение. Множеството от Y стойности зависи само от x, а не от конкретната Z стойност. За общ запис с припокриващи се X и Y се разглежда Y без X.
В примера Номер ↠ Език изисква всички езици на служителя да се комбинират с всички негови умения. По правилото за допълване следва и Номер ↠ Умение. От (С01, български, SQL) и (С01, английски, Python) се изискват и останалите два реда. Тези редове са следствие от изричното бизнес правило, а не от предположение на дизайнера.
МЗ X ↠ Y е тривиална, ако Y ⊆ X или X ∪ Y = R. Последният случай обяснява защо в двуатрибутна схема X,Y зависимостта X ↠ Y не поставя съдържателно ограничение върху независимост от трета група атрибути. Всяка ФЗ X → Y води до МЗ X ↠ Y, но обратното не е вярно: при МЗ могат да съществуват няколко Y стойности за едно X.
Правилата за ФЗ не могат безусловно да се пренасят към МЗ. По-специално X ↠ YZ не позволява механично разделяне на X ↠ Y и X ↠ Z: групата YZ може да е независима от останалото, но вътре в нея Y и Z да са свързани. Това разграничение е съществено при доказателства.
3. Четвърта нормална форма
Релационна схема е в 4NF спрямо зададените зависимости, когато за всяка нетривиална МЗ X ↠ Y, която следва от тях, X е суперключ. Суперключът тук се определя чрез функционално определяне на всички атрибути. Самото наличие на МЗ с лява страна X не прави X ключ.
В СЛУЖИТЕЛ(Номер, Език, Умение) зависимостта Номер ↠ Език е нетривиална: Език не е част от Номер и има останал атрибут Умение. Номер не е суперключ, защото за него има няколко реда. Следователно схемата не е в 4NF. При правилото за независимост и липса на други ФЗ ключът е цялата тройка. Това е пример за BCNF схема, която не е в 4NF.
4. Декомпозиция в 4NF
При нарушаваща нетривиална МЗ X ↠ Y разделяме R на R₁ = X ∪ Y и R₂ = X ∪ (R − (X ∪ Y)). МЗ гарантира, че естественото съединение на двете проекции възстановява точно първоначалната релация: допустимите комбинации са именно всички комбинации, които съединението образува при еднакво X.
ЕЗИЦИ(Номер, Език) УМЕНИЯ(Номер, Умение) (С01, български) (С01, SQL) (С01, английски) (С01, Python)
Съединението по Номер дава четирите оригинални реда. Сега нов език се записва веднъж независимо от броя умения. Алгоритъмът повтаря разделянето върху получените схеми, докато не останат нарушения, като работи с валидните зависимости за всяка подcхема. Беззагубността се запазва по стъпки; не се обещава непременно запазване на всички зависимости като локални проверки.
Без правилото за независимост същото съединение би добавило фиктивни факти. Беззагубността се доказва спрямо ограниченията, а не само чрез удачно подбран пример. Декомпозицията също не решава сама как да се пази служител без никакъв език или умение: за неговото независимо съществуване е нужна основна релация СЛУЖИТЕЛИ(Номер, …). Тя представя същността, а двете многозначни релации — отделните способности.
5. Връзка между нормалните форми
При стандартните определения 4NF ⇒ BCNF ⇒ 3NF. За първото следствие използваме, че всяка ФЗ е и МЗ. Ако нетривиална ФЗ нарушава BCNF, определящата страна не е суперключ; съответната МЗ е нетривиална и нарушава 4NF. Ако ФЗ определя всички останали атрибути, лявата страна вече е суперключ и нарушение няма.
Обратните следствия не са общовалидни: независимите езици и умения дават BCNF без 4NF, а зависимост към ключов атрибут може да е допустима в 3NF, но да нарушава BCNF. Следователно при анализ първо се заявяват зависимостите, после се намират ключовете и се проверява конкретното определение. „Повече таблици“ не е цел само по себе си. Целта е точно представяне на фактите с по-малко аномалии; производителността и удобството на заявките се оценяват отделно.
Литературна опора и граници на сверяването
Официална библиография на СУ — номерата по-долу са от нея.
- СУ 11 — Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom, Database Systems: The Complete Book, 2. изд., Prentice Hall, 2008. Пълен текст, наличен в проекта и използван за сверка.
- Точно четене: §3.6.1–3.6.6; печатни 105–113 / PDF 142–150. PDF страниците са поредни от началото на локалния файл; в това копие печатната страница + 37 дава PDF страницата.
- Страница на авторите за второто издание. Примерите тук са авторски. Означенията са обяснени в текста; SQL уточненията са разграничени от класическия модел.
Текстът и примерите са авторска учебна разработка, а не официален отговор или указание на изпитна комисия на СУ. Номерацията на разделите в плана е авторска. Препратките показват опората за понятията, а не че примерите са преписани от учебник.