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.
Точно четене
СУ 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 в AB → C? С кое правило се обосновава отговорът?
- След съкращаването на лявата страна и премахване на повторението излишна ли е A → C?
- Запиши полученото минимално покритие.
- Как проверяваш, че в него никое цяло правило не е излишно?
Изпрати отговорите по номера в разговора. За самопроверка отвори картите поотделно.
Отговори за преговор — разгъвай поотделно
Авторски примерни отговори, затворени по подразбиране. 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 не се получава. Левите страни са единични и празното множество не определя съответните десни атрибути по тези правила.