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} е суперключ, но не кандидатен ключ, защото съдържа по-малък ключ.
Точно четене
СУ 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⁺ е затварянето на множество атрибути. Кандидатен ключ е минимално по включване множество, чието затваряне е цялата схема. При проверката на минималност премахваме по един атрибут.
- Кой атрибут задължително присъства във всеки кандидатен ключ и защо?
- Намери всички кандидатни ключове и покажи достатъчността им.
- Защо {A,B,C} не е кандидатен ключ?
- Защо {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 се получава без поне единия от тях.