49. Затваряне на множество атрибути

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

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

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

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

Затварянето X⁺ спрямо F е множеството от всички атрибути, които X определя според зависимостите F. Започваме със самото X — то винаги определя собствените си атрибути.

Повтаряме: ако цялата лява страна на някоя зависимост вече е в текущото множество, добавяме дясната ѝ страна. Спираме, когато цял преглед на правилата не добави нищо. Не е достатъчно само едно преминаване през списъка.

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

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

Нека R(Курсист, Група, Зала, Етаж) има Курсист → Група, Група → Зала, Зала → Етаж. Започваме с {Курсист}; добавяме Група, после Зала, после Етаж. Получаваме {Курсист}⁺ = {Курсист, Група, Зала, Етаж}.

Ако добавим атрибут Ден, за който няма приложимо правило, Ден няма автоматично да попадне в затварянето. Наличието му в схемата не означава, че Курсист го определя.

Алгоритъмът добавя само обосновани атрибути: {Курсист}; {Курсист, Група}; {Курсист, Група, Зала}; {Курсист, Група, Зала, Етаж}
Алгоритъмът добавя само обосновани атрибути. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.

Точно четене

СУ 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 по тези зависимости, а → е функционална зависимост. Търси се затваряне на атрибути, не на конкретни стойности.

Вход за затваряне: Схема R(A, B, C, D, E); A → B; B → C; {C,D} → E; Начални множества за сравнение: {A} и {A,D}
Вход за затваряне. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.
  1. Изчисли A⁺, като покажеш стъпките.
  2. Можем ли да добавим E към A⁺ само защото вече сме получили C?
  3. Изчисли {A,D}⁺.
  4. Следва ли 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}⁺. Това е проверка за логическо следствие на правилата, а не наблюдение върху примерни редове.

Две различни затваряния: A⁺ = {A,B,C}; {A,D}⁺ = {A,B,C,D,E}; За CD → E са необходими и C, и D
Две различни затваряния. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.