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). Във всяка част определящият единичен атрибут е ключ.

Две стъпки, не едно механично разделяне
Две стъпки, не едно механично разделяне. Стрелките показват последователност на разглеждане, не ER кардиналност. Отвори в пълен размер.

Точно четене

СУ 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⁺); после провери всяка нова схема спрямо проектираните зависимости. За първа стъпка е избрана Катедра → Ръководител.

  1. Какво е {Катедра}⁺ в началната схема?
  2. Кои две схеми получаваме при първата стъпка?
  3. Коя зависимост още нарушава BCNF в по-голямата компонента?
  4. Запиши окончателните схеми в BCNF.

Изпрати отговорите по номера в разговора, после отвори картите за преговор.

Отговори за преговор — разгъвай поотделно

Авторски примерни отговори, затворени по подразбиране. Tab до заглавието, после Enter или Space.

Покажи отговор 1

{Катедра, Ръководител, Кабинет}; Кабинет се добавя чрез Ръководител → Кабинет. Курс не се определя от Катедра.

Покажи отговор 2

R₁(Катедра, Ръководител, Кабинет) и R₂(Курс, Катедра). Общият атрибут е Катедра.

Покажи отговор 3

Ръководител → Кабинет в R₁. Ръководител⁺ там е {Ръководител, Кабинет}, без Катедра, така че лявата страна не е суперключ.

Покажи отговор 4

(Курс, Катедра), (Катедра, Ръководител), (Ръководител, Кабинет). Ключовете им са съответно Курс, Катедра, Ръководител. Всяка нетривиална проектирана зависимост има суперключ отляво; двете стъпки са без загуба.

BCNF компоненти на учебната схема
BCNF компоненти на учебната схема. Стрелките показват последователност на разглеждане, не ER кардиналност. Отвори в пълен размер.