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.
Точно четене
СУ 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⁺ се изчислява спрямо изрично посоченото множество. Еквивалентност означава еднакви допустими състояния.
- Следва ли всяка зависимост на G от F?
- Намери B⁺ спрямо G. Следва ли B → C от G?
- Еквивалентни ли са F и G?
- Дай два реда, които спазват 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.