69. Четвърта нормална форма и декомпозиция

Специализирана тема С7 · Подготовка по програма № 19, СУ / ФМИ, 2026/2027 г. Авторски урок, пример и задача; не са официални отговори на СУ.

Цел: да отделяш независимите множества факти с възстановяване без загуба.

Около 10–20 минути с четенето и задачата. Примерите и решенията тук са авторски и са съобразени с посочения източник.

Основната идея

Схема е в четвърта нормална форма (4NF), когато за всяка нетривиална многозначна зависимост X ↠ Y, следваща от ограниченията, X е суперключ. Ключовете и суперключовете продължават да се определят чрез функционални зависимости.

Ако X ↠ Y нарушава 4NF, разлагаме R на R₁(X∪Y) и R₂(X∪Z), където Z са атрибутите извън X∪Y. В примерите X и Y са непресичащи се. Релациите съдържат проекциите на оригиналните редове, без дублиране.

Естественото съединение на двете проекции възстановява точно първоначалната релация: всички комбинации по едно X вече са изискани от многозначната зависимост. После проверяваме получените схеми за други нарушения. Не приемаме, че всяко произволно разделяне има тази гаранция.

Пример с обяснение

В R(Човек,Език,Хоби) независимостта Човек ↠ Език е нетривиална, а Човек не е суперключ, когато може да има няколко езика и хобита. Разлагаме на ЕЗИЦИ(Човек,Език) и ХОБИТА(Човек,Хоби).

За човек с два езика и три хобита запазваме 2+3 реда вместо 2×3. Съединението по Човек възстановява шестте комбинации. Ако няма други нетривиални зависимости в двете схеми, те са в 4NF.

Разделяне на независимите факти: R(Човек,Език,Хоби); ЕЗИЦИ(Човек,Език); ХОБИТА(Човек,Хоби); Съединението по Човек възстановява всички комбинации
Разделяне на независимите факти. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.

Точно четене

СУ 11: Garcia-Molina, Ullman и Widom, Database Systems: The Complete Book, второ издание. §3.6.4–3.6.5; печатни страници 110, 111, 112 / PDF страници 147, 148, 149. Номерата на PDF страниците са тези в сваления файл с 1240 страници; броят включва началните страници. Чети посочените раздели и примери, без съседните упражнения извън обхвата на урока. Това не са страници от първото издание.

Учебникът и официалната библиография · Учебен речник.

Самостоятелна задача — около 5–10 минути

Условие

Дадена е R(Човек,Език,Хоби) с независимост Човек ↠ Език. Няма нетривиални функционални зависимости и няма други нетривиални многозначни зависимости освен следствията от даденото правило. Няма NULL. Иван има точно български и немски и точно шах и бягане. Таблицата съдържа всички четири комбинации:

R — всички редове
ЧовекЕзикХоби
Иванбългарскишах
Иванбългарскибягане
Иваннемскишах
Иваннемскибягане

При разлагане ползваме проекция без повторения. Естествено съединение означава комбиниране на редове с еднакъв общ атрибут Човек.

Изходен случай: Иван: български и немски; Иван: шах и бягане; R съдържа всичките четири комбинации; Правило: Човек ↠ Език
Изходен случай. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.
  1. Нарушава ли дадената многозначна зависимост 4NF и защо?
  2. Запиши двете схеми и редовете след декомпозицията.
  3. Колко реда връща съединението и измисля ли нов факт спрямо оригинала?
  4. В 4NF ли са двете получени схеми според дадените ограничения?

Изпрати отговорите по номера в разговора. За самопроверка отвори картите поотделно.

Отговори за преговор — разгъвай поотделно

Авторски примерни отговори, затворени по подразбиране. Tab до заглавието, после Enter или Space.

Покажи отговор 1

Да. Човек ↠ Език е нетривиална в трите колони, а Човек не е суперключ. Отсъствието на нетривиални FD означава, че само цялото множество атрибути е кандидатен ключ на R.

Покажи отговор 2

ЕЗИЦИ(Човек,Език): (Иван,български), (Иван,немски). ХОБИТА(Човек,Хоби): (Иван,шах), (Иван,бягане). Това са проекции, затова повторенията са премахнати.

Покажи отговор 3

Четири реда — точно първоначалните. Правилото за независимост гарантира всички комбинации, следователно съединението не добавя несъществувала комбинация в тази допустима релация.

Покажи отговор 4

Да. Човек ↠ Език и Човек ↠ Хоби са тривиални в съответните двуколонни схеми. По условие няма други нарушения. Тривиалността не означава, че Човек е ключ.

Двете проекции и възстановяването: ЕЗИЦИ: Иван/български; Иван/немски; ХОБИТА: Иван/шах; Иван/бягане; 2 × 2 съвпадения по Иван = 4 първоначални реда
Двете проекции и възстановяването. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.