51. Защо затварянето е надеждна проверка
Специализирана тема С5 · Подготовка по програма № 19, СУ / ФМИ, 2026/2027 г. Авторски урок, пример и задача; не са официални отговори на СУ.
Цел: да обясниш защо алгоритъмът нито измисля, нито пропуска следваща зависимост.
Около 10–20 минути с четенето и задачата. Примерите и решенията тук са авторски и са съобразени с посочения източник.
Основната идея
Проверката за X → A чрез затваряне има две страни. Коректност: всеки добавен атрибут е обоснован. В началото X определя себе си. Ако вече определя лявата страна Y на правило Y → B, определя и B.
Пълнота: ако A не е в X⁺, можем да построим състояние, което спазва дадените зависимости, но нарушава X → A. Избираме два реда, еднакви по X⁺ и различни по всички други атрибути. За този аргумент работим в абстрактния модел на функционални зависимости, без допълнителни ограничения на домейните.
Защо тези редове спазват всяко правило Y → B от основата? Ако съвпадат по Y, цялото Y е в X⁺. Тогава алгоритъмът вече би добавил B в X⁺, така че редовете съвпадат и по B. За X → A обаче имаме еднакво X и различно A — контрапример.
Пример с обяснение
При R(A,B,C) и F={A → B}, A⁺={A,B}. Двата реда (a,b,c1) и (a,b,c2), с c1≠c2, спазват A → B, но нарушават A → C. Следователно A → C не следва от F. Това е различно от твърдението, че A → C никога не може да е вярна в отделно състояние.
Точно четене
СУ 11: Garcia-Molina, Ullman и Widom, Database Systems: The Complete Book, второ издание. §3.2.5; печатни страници 77, 78, 79 / PDF страници 114, 115, 116. Номерата на PDF страниците са тези в сваления файл с 1240 страници; броят включва началните страници. Чети посочените раздели и примери, без съседните упражнения извън обхвата на урока. Това не са страници от първото издание.
Учебникът и официалната библиография · Учебен речник.
Самостоятелна задача — около 5–10 минути
Условие
Дадена е R(A,B,C,D) с основа F={A → B, B → C}. Няма други ограничения и няма NULL. Всеки домейн допуска поне две различни стойности. X⁺ е затварянето по F. Конкретните символи a, b, c, d1 и d2 са допустими стойности в съответните колони, като d1≠d2. Контрапример трябва да спазва всички зависимости във F, но да нарушава проверяваната зависимост.
- Изчисли A⁺.
- Следва ли A → D от F?
- Построй два реда, които доказват отговора ти.
- Защо наличието на D извън A⁺ не означава, че A → D е невъзможна във всяко отделно състояние?
Изпрати отговорите по номера в разговора. За самопроверка отвори картите поотделно.
Отговори за преговор — разгъвай поотделно
Авторски примерни отговори, затворени по подразбиране. Tab до заглавието, после Enter или Space.
Покажи отговор 1
A⁺={A,B,C}: добавяме B, после C. За D няма приложимо правило.
Покажи отговор 2
Не. D не е в A⁺. Това означава, че дадените правила не гарантират A → D.
Покажи отговор 3
(a,b,c,d1) и (a,b,c,d2). Те съвпадат по A,B,C и спазват A → B и B → C, но имат различно D при еднакво A. Това е необходимият контрапример.
Покажи отговор 4
Например състояние само с един ред удовлетворява A → D, както и много други зависимости. „Не следва от F“ означава „не е гарантирана за всички състояния, удовлетворяващи F“, а не „не може да се случи“.