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 никога не може да е вярна в отделно състояние.

Контрапример за недоказана зависимост: Дадено: A → B; A⁺ = {A,B}; Ред 1: (a,b,c1); Ред 2: (a,b,c2), c1 ≠ c2; A → B е вярна; A → C е нарушена
Контрапример за недоказана зависимост. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.

Точно четене

СУ 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, но да нарушава проверяваната зависимост.

Условия за контрапримера: R(A,B,C,D); F={A → B, B → C}; Домейните позволяват различни стойности; Да се провери гарантирано ли е A → D
Условия за контрапримера. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.
  1. Изчисли A⁺.
  2. Следва ли A → D от F?
  3. Построй два реда, които доказват отговора ти.
  4. Защо наличието на 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“, а не „не може да се случи“.

Два реда са достатъчни: (a,b,c,d1); (a,b,c,d2), d1 ≠ d2; Еднакви A,B,C; различно D; Всички F са спазени, A → D е нарушена
Два реда са достатъчни. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.