54. Проектиране на функционални зависимости
Специализирана тема С5 · Подготовка по програма № 19, СУ / ФМИ, 2026/2027 г. Авторски урок, пример и задача; не са официални отговори на СУ.
Цел: да намираш правилата за част от колоните, включително изведените през премахнати колони.
Около 10–20 минути с четенето и задачата. Примерите и решенията тук са авторски и са съобразени с посочения източник.
Основната идея
При проекция на R върху схема S запазваме избрани атрибути. Проекцията на зависимостите включва всички зависимости, които следват от първоначалната основа F и използват само атрибути на S.
Не е достатъчно да изтрием от списъка всяко правило с премахнат атрибут. Този атрибут може да е междинна стъпка в доказателство. За всяко X⊆S намираме X⁺ по пълната F, после запазваме следствията X → A за A в X⁺∩S. Можем да представим резултата с по-малко еквивалентно покритие.
Проекцията на данни е операция върху редове и колони; проекцията на зависимости е изчисление на гарантираните ограничения. Случайната уникалност в конкретна извадка не добавя ново правило.
Пример с обяснение
В R(Курсист, Група, Факултет) са дадени Курсист → Група и Група → Факултет. Ако запазим само (Курсист, Факултет), остава валидна Курсист → Факултет. Макар Група да не е в новата схема, тя участва в извода.
Затова при изчисляване на {Курсист}⁺ първо използваме и двете оригинални зависимости. Едва след това ограничаваме резултата до новите атрибути.
Точно четене
СУ 11: Garcia-Molina, Ullman и Widom, Database Systems: The Complete Book, второ издание. §3.2.8; печатни страници 81, 82, 83 / PDF страници 118, 119, 120. Номерата на PDF страниците са тези в сваления файл с 1240 страници; броят включва началните страници. Чети посочените раздели и примери, без съседните упражнения извън обхвата на урока. Това не са страници от първото издание.
Учебникът и официалната библиография · Учебен речник.
Самостоятелна задача — около 5–10 минути
Условие
Дадена е R(A,B,C,D) с основа F={A → B, B → C, C → D}. Няма други ограничения и няма NULL. Проектираме схемата върху S(A,C,D), тоест премахваме B. Проекцията на F съдържа всички нейни следствия, използващи само A,C,D. За затваряне използвай цялата F, включително правилата с B.
- Изчисли A⁺ по F и посочи следствията с лява страна A в новата схема.
- Кое нетривиално правило с лява страна C се запазва?
- Дай минимално покритие на проектираните зависимости.
- Защо само изтриване на правилата с B би дало непълен резултат?
Изпрати отговорите по номера в разговора. За самопроверка отвори картите поотделно.
Отговори за преговор — разгъвай поотделно
Авторски примерни отговори, затворени по подразбиране. Tab до заглавието, после Enter или Space.
Покажи отговор 1
A⁺={A,B,C,D}. В S следват A → C и A → D. A → B не е правило върху S, защото B липсва от нейната схема.
Покажи отговор 2
C → D. То е дадено и използва само атрибути на S. C⁺ по F е {C,D}.
Покажи отговор 3
{A → C, C → D}. То извежда A → D. D⁺={D}, а проверката на останалите подмножества не добавя независими правила; това е пълно покритие върху S.
Покажи отговор 4
Бихме оставили само C → D и пропуснали A → C. B участва в доказателството A → B → C, дори когато не присъства в резултатната схема.