52. Еквивалентни множества зависимости и покритие

Специализирана тема С5 · Подготовка по програма № 19, СУ / ФМИ, 2026/2027 г. Авторски урок, пример и задача; не са официални отговори на СУ.

Цел: да сравняваш смисъла на два списъка правила, а не само броя им.

Около 10–20 минути с четенето и задачата. Примерите и решенията тук са авторски и са съобразени с посочения източник.

Основната идея

Множество зависимости G е еквивалентно на F, когато двете допускат едни и същи състояния. Проверяваме и двете посоки: всяка зависимост на F следва от G и всяка зависимост на G следва от F.

Учебникът нарича еквивалентното представяне basis — основа. Тук използваме „еквивалентно покритие“ за същата идея. Само еднопосочното следване не е достатъчно за еквивалентност. За всяка проверявана X → Y изчисляваме X⁺ по другото множество.

Обозначението F⁺ означава множеството от всички функционални зависимости, следващи от F. Това е различен тип обект от X⁺: X⁺ съдържа атрибути, а F⁺ — зависимости. Равенството F⁺=G⁺ изразява еквивалентност.

Пример с обяснение

За R(A,B,C) нека F={A → B, B → C}, а G={A → B, B → C, A → C}. Допълнителната зависимост в G вече следва по транзитивност от F. G не е по-строго от F: двете множества са еквивалентни.

Но H={A → B, A → C} не е еквивалентно на F. От H не следва B → C: два различни A могат да имат едно и също B и различни C.

Добавено следствие не променя правилата: F: A → B; B → C; G: A → B; B → C; A → C; F и G допускат едни и същи състояния
Добавено следствие не променя правилата. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.

Точно четене

СУ 11: Garcia-Molina, Ullman и Widom, Database Systems: The Complete Book, второ издание. §3.2.1 и §3.2.7; печатни страници 73, 80, 81 / PDF страници 110, 117, 118. Номерата на PDF страниците са тези в сваления файл с 1240 страници; броят включва началните страници. Чети посочените раздели и примери, без съседните упражнения извън обхвата на урока. Това не са страници от първото издание.

Учебникът и официалната библиография · Учебен речник.

Самостоятелна задача — около 5–10 минути

Условие

В схемата R(A,B,C) сравняваме F={A → B, B → C} и G={A → B, A → C}. Няма други ограничения, няма NULL и всички означени стойности са допустими. X⁺ се изчислява спрямо изрично посоченото множество. Еквивалентност означава еднакви допустими състояния.

Сравни в двете посоки: F: A → B; B → C; G: A → B; A → C; Провери всяко правило чрез другото множество
Сравни в двете посоки. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.
  1. Следва ли всяка зависимост на G от F?
  2. Намери B⁺ спрямо G. Следва ли B → C от G?
  3. Еквивалентни ли са F и G?
  4. Дай два реда, които спазват G, но нарушават F.

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

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

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

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

Да. A → B е обща, а A → C следва от F по транзитивност.

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

B⁺ по G е {B}. Нито едно правило в G не започва само от известни атрибути, така че C не се добавя; B → C не следва.

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

Не. F налага всички ограничения на G, но обратното не е вярно. Състоянията, разрешени от F, са подмножество на тези, разрешени от G.

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

(a1,b,c1) и (a2,b,c2), с a1≠a2 и c1≠c2. Различните A не нарушават A → B или A → C; еднаквото B с различни C нарушава B → C от F.

Едната посока не стига: F налага G; G не налага B → C; (a1,b,c1), (a2,b,c2) спазват само G; Следователно F и G не са еквивалентни
Едната посока не стига. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.