59. Последователна декомпозиция в BCNF
Специализирана тема С6 · Подготовка по програма № 19, СУ / ФМИ, 2026/2027 г. Авторски урок, пример и задача; не са официални отговори на СУ.
Цел: Да разделиш схема по нарушаваща зависимост и да продължиш проверката в получените части.
Около 15–20 минути с четенето и задачата. При нужда раздели четенето и решаването на две кратки стъпки.
Основни понятия
Алгоритъмът започва със схема R и функционални зависимости F. Ако R е в BCNF, спираме за нея. Иначе избираме нарушение X → Y и намираме X⁺ спрямо зависимостите на текущата схема. Създаваме R₁ = X⁺ и R₂ = X ∪ (R ∖ X⁺). Общата част е X.
Във всяка нова схема използваме проекцията на зависимостите: всички следствия на F, чиито атрибути са в тази схема. Не изхвърляме мислено всички правила, които не са изписани дословно в началния списък. Повтаряме, докато всяка част е в BCNF.
Изборът на нарушение може да доведе до различни правилни декомпозиции. Алгоритъмът гарантира възстановяване без загуба чрез JOIN; запазването на всички зависимости за локална проверка е отделен въпрос.
Практичен пример
За R(A, B, C, D) са дадени A → B, B → C, C → D. A е ключ. Избираме нарушението B → C; B⁺ = {B, C, D}. Получаваме R₁(B, C, D) и R₂(A, B). В R₁ остава нарушение C → D, защото C не определя B. Разделяме R₁ на (C, D) и (B, C). Краят е (A, B), (B, C), (C, D). Във всяка част определящият единичен атрибут е ключ.
Точно четене
СУ 11: Garcia-Molina, Ullman и Widom, Database Systems: The Complete Book, второ издание, §3.3.4, Algorithm 3.20, печатни 89–92 / PDF 126–129. Чети посочените раздели в тези страници; съседните упражнения са по желание. Примерите, условието, решенията и схемите тук са авторски.
Учебникът и официалната библиография.
Самостоятелна задача — около 5–10 минути
Условие
Дадена е схема R(Курс, Катедра, Ръководител, Кабинет) и пълен набор от определящи зависимости F = {Курс → Катедра, Катедра → Ръководител, Ръководител → Кабинет}, плюс техните следствия. Няма други зависимости и няма NULL. Записът X → Y означава функционална зависимост; X⁺ е затваряне.
Използвай алгоритъма: при нарушение с лява страна X вземи X⁺ и X ∪ (R ∖ X⁺); после провери всяка нова схема спрямо проектираните зависимости. За първа стъпка е избрана Катедра → Ръководител.
- Какво е {Катедра}⁺ в началната схема?
- Кои две схеми получаваме при първата стъпка?
- Коя зависимост още нарушава BCNF в по-голямата компонента?
- Запиши окончателните схеми в BCNF.
Изпрати отговорите по номера в разговора, после отвори картите за преговор.
Отговори за преговор — разгъвай поотделно
Авторски примерни отговори, затворени по подразбиране. Tab до заглавието, после Enter или Space.
Покажи отговор 1
{Катедра, Ръководител, Кабинет}; Кабинет се добавя чрез Ръководител → Кабинет. Курс не се определя от Катедра.
Покажи отговор 2
R₁(Катедра, Ръководител, Кабинет) и R₂(Курс, Катедра). Общият атрибут е Катедра.
Покажи отговор 3
Ръководител → Кабинет в R₁. Ръководител⁺ там е {Ръководител, Кабинет}, без Катедра, така че лявата страна не е суперключ.
Покажи отговор 4
(Курс, Катедра), (Катедра, Ръководител), (Ръководител, Кабинет). Ключовете им са съответно Курс, Катедра, Ръководител. Всяка нетривиална проектирана зависимост има суперключ отляво; двете стъпки са без загуба.