50. Намиране на всички кандидатни ключове

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

Цел: да използваш затваряне за достатъчност и отделна проверка за минималност.

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

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

X е суперключ, ако X⁺ съдържа всички атрибути на схемата. За кандидатен ключ е нужно и никой атрибут да не може да бъде премахнат, без да се загуби достатъчността. Минималност означава по включване, не непременно най-малък брой атрибути сред всички ключове.

За малки схеми проверяваме множествата по размер и спираме да разглеждаме надмножества на вече намерен ключ. Атрибут, който не се среща вдясно в нито една нетривиална зависимост от дадената основа, не може да бъде добавен от алгоритъма: трябва да присъства във всеки ключ.

Това е помощ за търсене, не достатъчно условие за ключ. Дори когато всички атрибути се срещат вдясно, може да има ключове; търсенето трябва да провери и останалите възможности.

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

В R(A,B,C) с A → B и B → A, C не се получава от никакво правило. Значи всеки ключ съдържа C. {A,C}⁺ и {B,C}⁺ съдържат и трите атрибута, а C⁺={C}. Двата кандидатни ключа са {A,C} и {B,C}.

Нито A, нито B сам определя C. {A,B,C} е суперключ, но не кандидатен ключ, защото съдържа по-малък ключ.

Достатъчност плюс минималност: R(A,B,C): A → B и B → A; C задължително присъства; {A,C} и {B,C}: минимални суперключове
Достатъчност плюс минималност. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.

Точно четене

СУ 11: Garcia-Molina, Ullman и Widom, Database Systems: The Complete Book, второ издание. §3.2.4 и карето „Closures and Keys“ на с. 80; печатни страници 75, 76, 77, 80 / PDF страници 112, 113, 114, 117. Номерата на PDF страниците са тези в сваления файл с 1240 страници; броят включва началните страници. Чети посочените раздели и примери, без съседните упражнения извън обхвата на урока. Това не са страници от първото издание.

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

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

Условие

Дадена е R(A, B, C, D) и основата A → B, B → A, C → D. Други правила освен следствията им не се предполагат; няма NULL. X⁺ е затварянето на множество атрибути. Кандидатен ключ е минимално по включване множество, чието затваряне е цялата схема. При проверката на минималност премахваме по един атрибут.

Дадени зависимости: R(A,B,C,D); A → B; B → A; C → D; Търсим всички минимални множества с пълно затваряне
Дадени зависимости. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.
  1. Кой атрибут задължително присъства във всеки кандидатен ключ и защо?
  2. Намери всички кандидатни ключове и покажи достатъчността им.
  3. Защо {A,B,C} не е кандидатен ключ?
  4. Защо {C,D} не е суперключ?

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

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

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

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

C. Той не се среща вдясно в дадената основа и не може да бъде получен, ако не е в началното множество.

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

{A,C} и {B,C}. От A получаваме B, от B получаваме A, а от C — D. И двете затваряния са {A,B,C,D}. Премахването на C губи C и D; премахването на A или B съответно оставя само {C,D}. Всички ключове трябва да съдържат C и поне един от A,B, затова списъкът е пълен.

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

То е суперключ, но съдържа и двата по-малки ключа {A,C} и {B,C}. Можем да махнем A или B.

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

{C,D}⁺={C,D}. Нито A, нито B се получава без поне единия от тях.

Пълният списък на ключовете: {A,C}⁺ = {A,B,C,D}; {B,C}⁺ = {A,B,C,D}; C е задължителен; необходим е поне един от A,B
Пълният списък на ключовете. Учебна схема на данни или разсъждение, не ER диаграма. Отвори в пълен размер.