49. Затваряне на множество атрибути
Специализирана тема С5 · Подготовка по програма № 19, СУ / ФМИ, 2026/2027 г. Авторски урок, пример и задача; не са официални отговори на СУ.
Цел: да намериш всичко, което едно множество атрибути определя чрез дадените зависимости.
Около 10–20 минути с четенето и задачата. Примерите и решенията тук са авторски и са съобразени с посочения източник.
Основната идея
Затварянето X⁺ спрямо F е множеството от всички атрибути, които X определя според зависимостите F. Започваме със самото X — то винаги определя собствените си атрибути.
Повтаряме: ако цялата лява страна на някоя зависимост вече е в текущото множество, добавяме дясната ѝ страна. Спираме, когато цял преглед на правилата не добави нищо. Не е достатъчно само едно преминаване през списъка.
При краен брой атрибути алгоритъмът спира. Правилата може да се прилагат в различен ред, но крайното затваряне е едно и също. X⁺ е множество имена на атрибути, не таблица с редове.
Пример с обяснение
Нека R(Курсист, Група, Зала, Етаж) има Курсист → Група, Група → Зала, Зала → Етаж. Започваме с {Курсист}; добавяме Група, после Зала, после Етаж. Получаваме {Курсист}⁺ = {Курсист, Група, Зала, Етаж}.
Ако добавим атрибут Ден, за който няма приложимо правило, Ден няма автоматично да попадне в затварянето. Наличието му в схемата не означава, че Курсист го определя.
Точно четене
СУ 11: Garcia-Molina, Ullman и Widom, Database Systems: The Complete Book, второ издание. §3.2.4; печатни страници 75, 76, 77 / PDF страници 112, 113, 114. Номерата на PDF страниците са тези в сваления файл с 1240 страници; броят включва началните страници. Чети посочените раздели и примери, без съседните упражнения извън обхвата на урока. Това не са страници от първото издание.
Учебникът и официалната библиография · Учебен речник.
Самостоятелна задача — около 5–10 минути
Условие
Дадена е R(A, B, C, D, E) с точно следната основа от зависимости: A → B, B → C, CD → E. Приемат се техните следствия; други правила не се предполагат. Няма NULL. CD означава {C,D}. X⁺ означава затварянето на X по тези зависимости, а → е функционална зависимост. Търси се затваряне на атрибути, не на конкретни стойности.
- Изчисли A⁺, като покажеш стъпките.
- Можем ли да добавим E към A⁺ само защото вече сме получили C?
- Изчисли {A,D}⁺.
- Следва ли AD → E от дадените зависимости?
Изпрати отговорите по номера в разговора. За самопроверка отвори картите поотделно.
Отговори за преговор — разгъвай поотделно
Авторски примерни отговори, затворени по подразбиране. Tab до заглавието, после Enter или Space.
Покажи отговор 1
{A} → {A,B} → {A,B,C}. Нито едно правило не добавя D; CD → E не е приложимо. Следователно A⁺ = {A,B,C}. Стрелките между множествата тук означават стъпки на алгоритъма.
Покажи отговор 2
Не. За CD → E трябва да имаме и C, и D. Само C не е достатъчно.
Покажи отговор 3
{A,D} → {A,B,D} → {A,B,C,D} → {A,B,C,D,E}. Следователно {A,D}⁺ съдържа всички атрибути.
Покажи отговор 4
Да. E принадлежи на {A,D}⁺. Това е проверка за логическо следствие на правилата, а не наблюдение върху примерни редове.