II.5. Функционални зависимости — Разширена писмена разработка
Разширена писмена разработка. II.5. Функционални зависимости
Подробен авторски текст за подготовка по конспекта на СУ. Краткият вариант е запазен на основната страница на темата. За преговор използвай плана; за обосновка — определенията и разработените примери. Това не е официален изпитен образец.
Кратка разработка и уроци по темата · План за изпита · Покритие · Източници
Обхват от конспекта
Функционални зависимости. Определение за функционална зависимост. Ключове на релациите. Суперключове. Откриване на ключовете в релациите. Правила за функционалните зависимости. Правило за разделяне/ комбиниране. Тривиални функционални зависимости. Правила на транзитивността. Покриващи множества на функционалните зависимости. Проекция на функционалните зависимости.
Покритие на конспекта
Всяка подточка води към съответния раздел на разработката.
- Функционални зависимости — 1. Какво твърди функционалната зависимост
- Определение за функционална зависимост — 1. Какво твърди функционалната зависимост
- Ключове на релациите — 2. Ключове и алгоритъм за затваряне
- Суперключове — 2. Ключове и алгоритъм за затваряне
- Откриване на ключовете в релациите — 2. Ключове и алгоритъм за затваряне
- Правила за функционалните зависимости — 3. Правила за извод
- Правило за разделяне/ комбиниране — 3. Правила за извод
- Тривиални функционални зависимости — 3. Правила за извод
- Правила на транзитивността — 3. Правила за извод
- Покриващи множества на функционалните зависимости — 4. Покрития и минимално покритие
- Проекция на функционалните зависимости — 5. Проекция на зависимости
Кратък план за изпита
- Семантика и формална дефиниция на функционална зависимост.
- Суперключ, кандидат-ключ, затваряне и намиране на ключове.
- Правила за извод и ограниченията на разделянето.
- Еквивалентни и минимални покрития.
- Проекция на зависимости при декомпозиция.
1. Какво твърди функционалната зависимост
Функционалната зависимост (ФЗ) е ограничение върху допустимите екземпляри на релационна схема. За множества атрибути X и Y записът X → Y означава: за всяка двойка кортежи t и u, ако t[X] = u[X], то t[Y] = u[Y]. При еднакви стойности на определящите атрибути са задължителни еднакви стойности на определяните. Стрелката обозначава зависимост, а не посока за навигация в ER диаграма.
Например КодКурс → ИмеКурс изразява правилото, че всеки код обозначава един курс с едно текущо име. Не следва обратното: различни курсове могат да имат еднакви имена. Зависимостта не означава и че името никога не се променя във времето; тя ограничава всеки отделен допустим екземпляр при избрания модел за текущи данни.
Един контрапример от два реда с еднакво X и различно Y опровергава ФЗ за конкретните данни. Липсата на контрапример в малка таблица не доказва общото бизнес правило. Празна релация или релация с един ред удовлетворява всяка ФЗ, но от това не следва, че всяко множество атрибути е предвидено като ключ на схемата. Зависимостите се извеждат от семантиката, а данните служат и за проверка за нарушения.
2. Ключове и алгоритъм за затваряне
Суперключ X определя всички атрибути на схемата R. Кандидат-ключ е суперключ, минимален по включване: никое негово собствено подмножество не е суперключ. „Минимален“ не означава непременно най-малкия брой атрибути сред всички кандидат-ключове. От кандидат-ключовете може да се избере първичен; останалите са алтернативни. Добавянето на атрибути към суперключ запазва свойството, но обикновено премахва минималността.
Затварянето X⁺ спрямо F е множеството атрибути, които логически следват от X чрез F. Започваме с X. Докато има зависимост U → V с U в текущото множество, добавяме V. Спираме, когато няма нов атрибут. Тъй като схемата е крайна, алгоритъмът завършва. X е суперключ точно когато X⁺ съдържа всички атрибути.
R(A, B, C, D), F = { A → B, B → C, AC → D }
A⁺: {A} → {A,B} → {A,B,C} → {A,B,C,D}Следователно A е суперключ. При тези зависимости празното множество не определя A, затова A е кандидат-ключ. Атрибутът A не се появява отдясно на никоя зависимост и не може да се получи от други атрибути; всеки ключ трябва да го съдържа. Понеже самото A вече е ключ, това е единственият кандидат-ключ. По принцип атрибутите, които не се срещат отдясно, са задължителни кандидати за включване, но това наблюдение не замества проверката със затваряне.
За систематично търсене разширяваме такива задължителни атрибути и проверяваме затваряния. След намиране на ключ не е необходимо да проверяваме неговите надмножества за минималност. В общия случай броят кандидат-ключове може да е голям, затова няма основание да се предполага единствен ключ.
3. Правила за извод
Аксиомите на Армстронг дават коректна и пълна система за логически извод на ФЗ: рефлексивност — ако Y е подмножество на X, то X → Y; разширяване — от X → Y следва XZ → YZ; транзитивност — от X → Y и Y → Z следва X → Z. Пълнота означава, че всяка ФЗ, която е логическо следствие от F, може да се изведе чрез тези правила.
Зависимостта X → Y е тривиална, когато Y ⊆ X. Например AB → A е вярна независимо от конкретните данни. При нетривиална зависимост поне един атрибут отдясно не присъства вляво. Тривиалността е свойство на записаните множества, а не оценка за практическа важност.
Правилото за разделяне позволява от X → YZ да изведем X → Y и X → Z. Обратно, при еднаква лява страна тези две зависимости се обединяват в X → YZ. Разделянето се отнася за дясната страна: от AB → C не следват A → C или B → C. Например оценката зависи от курсист и курс заедно, но не непременно от всеки поотделно.
От разширяване и транзитивност следва и псевдотранзитивност: X → Y и YZ → W дават XZ → W. В примера по-горе A → C, следователно A → AC, а заедно с AC → D получаваме A → D. В изводите буквите означават множества атрибути; AB е обединението им, а не произведение на стойности.
4. Покрития и минимално покритие
Затварянето F⁺ на множество зависимости включва всички негови логически следствия; то е различен обект от затварянето X⁺ на множество атрибути. F и G са еквивалентни покрития, ако F⁺ = G⁺. Проверяваме двустранно следване: всяка зависимост от F чрез G и всяка от G чрез F. За X → Y е достатъчно да проверим дали Y ⊆ X⁺ спрямо другото множество.
Минимално покритие може да се получи с единичен атрибут отдясно, без излишни атрибути отляво и без излишни зависимости. Първо разделяме десните страни. За излишен атрибут A в лявата страна X на X → B проверяваме дали B се получава от X без A чрез текущото множество. За излишна цяла зависимост временно я премахваме и проверяваме дали останалите още я извеждат. Промените се правят последователно с нова проверка след всяка, а не чрез независимо изтриване на всичко, което изглежда излишно в първоначалния набор.
За {A → B, B → C, AC → D} атрибутът C в AC → D е излишен: A вече определя C. Получаваме {A → B, B → C, A → D}. Ако към този набор е добавена A → C, тя е излишна по транзитивност. Минималното покритие не е задължително единствено. Обединяването на еднакви леви страни е удобен компактeн запис, но тогава десните страни вече не са единични.
5. Проекция на зависимости
Проекцията на F върху подмножество атрибути S съдържа всички зависимости от F⁺, чиито две страни са в S. Не е достатъчно просто да задържим изрично записаните зависимости, които споменават само S.
R(A, B, C), F = { A → B, B → C }
Проекция върху S(A, C): A → CA → C се извежда чрез атрибута B, който липсва от проектираната схема. Тя все пак е ограничение върху S. Един общ метод разглежда подмножествата X на S, намира X⁺ спрямо оригиналното F и извежда X → (X⁺ ∩ S); след това премахва тривиалните и излишните записи. Броят подмножества прави този пряк метод скъп при много атрибути, но той ясно показва правилното определение. Проекциите са основа за проверка на нормалните форми и за това дали зависимостите се запазват след декомпозиция.
Литературна опора и граници на сверяването
Официална библиография на СУ — номерата по-долу са от нея.
- СУ 11 — Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom, Database Systems: The Complete Book, 2. изд., Prentice Hall, 2008. Пълен текст, наличен в проекта и използван за сверка.
- Точно четене: §3.1–3.2.8; печатни 67–83 / PDF 104–120. PDF страниците са поредни от началото на локалния файл; в това копие печатната страница + 37 дава PDF страницата.
- Страница на авторите за второто издание. Примерите тук са авторски. Означенията са обяснени в текста; SQL уточненията са разграничени от класическия модел.
Текстът и примерите са авторска учебна разработка, а не официален отговор или указание на изпитна комисия на СУ. Номерацията на разделите в плана е авторска. Препратките показват опората за понятията, а не че примерите са преписани от учебник.