II.5. Функционални зависимости — Разширена писмена разработка

Разширена писмена разработка. II.5. Функционални зависимости

Подробен авторски текст за подготовка по конспекта на СУ. Краткият вариант е запазен на основната страница на темата. За преговор използвай плана; за обосновка — определенията и разработените примери. Това не е официален изпитен образец.

Кратка разработка и уроци по темата · План за изпита · Покритие · Източници

Обхват от конспекта

Функционални зависимости. Определение за функционална зависимост. Ключове на релациите. Суперключове. Откриване на ключовете в релациите. Правила за функционалните зависимости. Правило за разделяне/ комбиниране. Тривиални функционални зависимости. Правила на транзитивността. Покриващи множества на функционалните зависимости. Проекция на функционалните зависимости.

Покритие на конспекта

Всяка подточка води към съответния раздел на разработката.

  1. Функционални зависимости — 1. Какво твърди функционалната зависимост
  2. Определение за функционална зависимост — 1. Какво твърди функционалната зависимост
  3. Ключове на релациите — 2. Ключове и алгоритъм за затваряне
  4. Суперключове — 2. Ключове и алгоритъм за затваряне
  5. Откриване на ключовете в релациите — 2. Ключове и алгоритъм за затваряне
  6. Правила за функционалните зависимости — 3. Правила за извод
  7. Правило за разделяне/ комбиниране — 3. Правила за извод
  8. Тривиални функционални зависимости — 3. Правила за извод
  9. Правила на транзитивността — 3. Правила за извод
  10. Покриващи множества на функционалните зависимости — 4. Покрития и минимално покритие
  11. Проекция на функционалните зависимости — 5. Проекция на зависимости

Кратък план за изпита

  1. Семантика и формална дефиниция на функционална зависимост.
  2. Суперключ, кандидат-ключ, затваряне и намиране на ключове.
  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 → C

A → 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 уточненията са разграничени от класическия модел.

Текстът и примерите са авторска учебна разработка, а не официален отговор или указание на изпитна комисия на СУ. Номерацията на разделите в плана е авторска. Препратките показват опората за понятията, а не че примерите са преписани от учебник.

Обратно към кратката разработка и уроците