48. Транзитивност: зависимости по верига
Специализирана тема С5 · Подготовка по програма № 19, СУ / ФМИ, 2026/2027 г. Авторски урок, пример и задача; не са официални отговори на СУ.
Цел: да извеждаш ново правило по верига, без да обръщаш стрелките.
Около 10–20 минути с четенето и задачата. Примерите и решенията тук са авторски и са съобразени с посочения източник.
Основната идея
Транзитивност: ако X → Y и Y → Z, следва X → Z. За два реда с еднакво X първата зависимост налага еднакво Y, а втората — еднакво Z.
Стрелката е насочена. От X → Y не следва Y → X. За използване на втората зависимост трябва да знаем всички атрибути в нейната лява страна: A → B и BC → D сами по себе си не дават A → D.
Изведената зависимост е логическо следствие на правилата във всички допустими състояния. Не я обосноваваме само с това, че текущите два реда случайно съвпадат.
Пример с обяснение
В УЧАСТНИЦИ(Номер, Група, Зала) всеки участник има една група, а всяка група — една текуща зала. Дадени са Номер → Група и Група → Зала. Следва Номер → Зала. Залата може да се използва от различни групи в различни часове; обратната зависимост не е зададена.
Ако вместо Група → Зала знаехме само {Група, Час} → Зала, номерът без час нямаше да е достатъчен за зала.
Точно четене
СУ 11: Garcia-Molina, Ullman и Widom, Database Systems: The Complete Book, второ издание. §3.2.6; печатни страници 79, 80 / PDF страници 116, 117. Номерата на PDF страниците са тези в сваления файл с 1240 страници; броят включва началните страници. Чети посочените раздели и примери, без съседните упражнения извън обхвата на урока. Това не са страници от първото издание.
Учебникът и официалната библиография · Учебен речник.
Самостоятелна задача — около 5–10 минути
Условие
Дадена е релацията СЛУЖИТЕЛИ(Номер, Отдел, Ръководител). Всеки служител е в точно един отдел и всеки отдел има точно един текущ ръководител. Един отдел може да има много служители. Един ръководител може да ръководи повече от един отдел. Няма NULL. Дадени са Номер → Отдел и Отдел → Ръководител. → означава функционална зависимост. Всички текущи редове са:
| Номер | Отдел | Ръководител |
|---|---|---|
| С1 | О1 | Мария |
| С2 | О1 | Мария |
| С3 | О2 | Мария |
- Каква зависимост от Номер към Ръководител следва?
- Защо два реда с еднакъв Номер трябва да имат еднакъв Ръководител?
- Следва ли Отдел → Номер?
- Следва ли Ръководител → Отдел?
Изпрати отговорите по номера в разговора. За самопроверка отвори картите поотделно.
Отговори за преговор — разгъвай поотделно
Авторски примерни отговори, затворени по подразбиране. Tab до заглавието, после Enter или Space.
Покажи отговор 1
Номер → Ръководител, по транзитивност през Отдел.
Покажи отговор 2
Първо Номер → Отдел налага един и същ отдел. След това Отдел → Ръководител налага един и същ ръководител. Двете стъпки работят за всяко допустимо състояние.
Покажи отговор 3
Не. С1 и С2 са в О1. Обратната посока не следва и е опровергана от дадените редове.
Покажи отговор 4
Не. Мария ръководи О1 и О2, което е разрешено от условието.