53. Минимално покритие на зависимости

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

Цел: да премахваш излишни части от правила, без да променяш допустимите данни.

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

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

Минималното покритие е еквивалентна основа с един атрибут вдясно във всяко правило, без излишен атрибут вляво и без излишна зависимост. „Минимално“ не обещава единствен резултат или най-малкия възможен брой правила.

За да проверим излишен атрибут в Y → B, временно махаме този атрибут от Y и намираме затварянето на останалите по текущата основа. Ако то съдържа B, можем да съкратим лявата страна. За да проверим излишна зависимост, изваждаме цялото правило от основата и проверяваме следва ли то от останалите.

Тези две проверки не са една и съща операция. След промяна проверяваме отново; не изхвърляме едновременно две зависимости само защото всяка изглежда излишна при наличието на другата.

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

Нека F={A → B, AB → C, A → C}. В AB → C атрибутът B е излишен, защото A⁺ по F съдържа C. След замяната се получава повторение на A → C, което оставяме веднъж. G={A → B, A → C} е минимално покритие: никое от двете правила не следва само от другото.

Съкращението е допустимо заради всички дадени зависимости. Само AB → C не би ни позволило да махнем B.

Почистване без промяна на смисъла: A → B; AB → C; A → C; В AB → C: B е излишен при тези правила; Резултат: A → B; A → C
Почистване без промяна на смисъла. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.

Точно четене

СУ 11: Garcia-Molina, Ullman и Widom, Database Systems: The Complete Book, второ издание. §3.2.7 и Algorithm 3.12, стъпка 3; печатни страници 80, 81, 82 / PDF страници 117, 118, 119. Номерата на PDF страниците са тези в сваления файл с 1240 страници; броят включва началните страници. Чети посочените раздели и примери, без съседните упражнения извън обхвата на урока. Това не са страници от първото издание.

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

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

Условие

Дадена е R(A,B,C) с F={A → B, AB → C, B → C, A → C}. AB е {A,B}. Няма други ограничения и няма NULL. Търсим еквивалентна основа с единични десни страни, без съкратима лява страна и без правило, следващо от останалите.

Изходна основа за задачата: A → B; AB → C; B → C; A → C
Изходна основа за задачата. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.
  1. Излишен ли е A в AB → C? С кое правило се обосновава отговорът?
  2. След съкращаването на лявата страна и премахване на повторението излишна ли е A → C?
  3. Запиши полученото минимално покритие.
  4. Как проверяваш, че в него никое цяло правило не е излишно?

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

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

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

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

Да. B → C вече е дадена, така че B⁺ съдържа C и само B е достатъчно. AB → C може да се замени с B → C.

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

Да. От A → B и B → C следва A → C по транзитивност. Зависимостта може да се премахне след тази проверка.

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

G={A → B, B → C}. G извежда A → C и AB → C, а F съдържа правилата на G, затова двете основи са еквивалентни.

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

Без A → B затварянето на A е само {A}; B не се получава. Без B → C затварянето на B е само {B}; C не се получава. Левите страни са единични и празното множество не определя съответните десни атрибути по тези правила.

Минимално покритие: AB → C се заменя с наличното B → C; A → C следва от A → B и B → C; Остава: {A → B, B → C}
Минимално покритие. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.