Ключ кандидата

В реляционной модели из базы данных , с ключом кандидата , или просто ключом , в виде отношения схемы является минимальным суперключи отношениями схемы. ^[1] Другими словами, это набор атрибутов, так что каждое отношение экземпляра схемы отношения не имеет двух отдельных кортежей с одинаковыми значениями для этих атрибутов (что означает, что набор атрибутов является суперключом), и существует нет надлежащего подмножества этих атрибутов, которое является суперключом схемы отношения (что означает, что набор минимален). Он определяет функциональную зависимость ограничение от ключа кандидата на все атрибуты схемы отношения.

Ключи-кандидаты также по-разному называются первичными ключами, вторичными ключами или альтернативными ключами.

Составляющие атрибуты называются основными атрибутами . И наоборот, атрибут, который не встречается в ЛЮБОМ кандидатном ключе, называется непервичным атрибутом .

Поскольку отношение не содержит повторяющихся кортежей, набор всех его атрибутов является суперключом, если значения NULL не используются. Отсюда следует, что каждое отношение будет иметь по крайней мере один ключ-кандидат.

Ключи-кандидаты отношения сообщают нам все возможные способы идентификации его кортежей. Как таковые, они являются важной концепцией при разработке схемы базы данных .

Пример [ править ]

Определение ключей-кандидатов можно проиллюстрировать следующим (абстрактным) примером. Рассмотрим переменную отношения ( relvar ) R с атрибутами ( A , B , C , D ), которая имеет только следующие два допустимых значения r1 и r2 :

Здесь r2 отличается от r1 только значениями A и D последнего кортежа.

Для r1 следующие наборы обладают свойством уникальности, т. Е. В экземпляре нет двух отдельных кортежей с одинаковыми значениями атрибутов в наборе:

{A, B}, {A, C}, {B, C}, {A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}, {A, B, C, D}

Для r2 свойство единственности имеет место для следующих множеств;

{B, C}, {B, D}, {C, D}, {A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}, {A, B, C, D}

Поскольку суперключи relvar - это те наборы атрибутов, которые имеют свойство уникальности для всех допустимых значений этой relvar, и поскольку мы предполагаем, что r1 и r2 - все допустимые значения, которые может принимать R , мы можем определить набор суперключей R с помощью на пересечении двух списков:

{B, C}, {A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}, {A, B, C, D}

Наконец, нам нужно выбрать те наборы, для которых нет подходящего подмножества в списке, а именно:

{B, C}, {A, B, D}, {A, C, D}

Это действительно кандидаты ключи relvar R .

Мы должны рассмотреть все отношения, которые могут быть присвоены relvar, чтобы определить, является ли определенный набор атрибутов ключом-кандидатом. Например, если бы мы рассматривали только r1, мы бы пришли к выводу, что {A, B} - это ключ-кандидат, что неверно. Однако из такого отношения мы могли бы заключить, что определенный набор не является ключом-кандидатом, потому что этот набор не имеет свойства уникальности (пример {A, D} для r1 ). Обратите внимание, что наличие надлежащего подмножества набора, обладающего свойством уникальности, не можетв целом может использоваться как доказательство того, что надмножество не является кандидатом ключа. В частности, обратите внимание, что в случае пустого отношения каждое подмножество заголовка имеет свойство уникальности, включая пустой набор.

Определение ключей-кандидатов [ править ]

Набор всех ключей-кандидатов может быть вычислен, например, из набора функциональных зависимостей . Для этого нам нужно определить закрытие атрибута для набора атрибутов . Набор содержит все атрибуты, которые функционально подразумеваются .${\ displaystyle \ alpha +}$${\ displaystyle \ alpha}$${\ displaystyle \ alpha ^ {+}}$${\ displaystyle \ alpha}$

Найти единственный кандидатный ключ довольно просто. Мы начинаем с набора атрибутов и пытаемся последовательно удалить каждый атрибут. Если после удаления атрибута закрытие атрибута остается прежним, то в этом атрибуте нет необходимости, и мы можем удалить его навсегда. Назовем результат . Если это набор всех атрибутов, то это ключ-кандидат.${\ displaystyle \ alpha}$${\ Displaystyle {\ текст {минимизировать}} (\ альфа)}$${\ displaystyle \ alpha}$${\ Displaystyle {\ текст {минимизировать}} (\ альфа)}$

Фактически мы можем обнаружить каждый ключ-кандидат с помощью этой процедуры, просто попробовав каждый возможный порядок удаления атрибутов. Однако существует гораздо больше перестановок атрибутов ( ), чем подмножеств ( ). То есть множество порядков атрибутов приведет к одному и тому же ключу-кандидату.${\ displaystyle n!}$${\ Displaystyle 2 ^ {п}}$

Существует фундаментальная трудность для эффективных алгоритмов вычисления ключей-кандидатов: определенные наборы функциональных зависимостей приводят к экспоненциальному количеству ключей-кандидатов. Рассмотрим функциональные зависимости , которая дает ключи кандидатов: . То есть лучшее, что мы можем ожидать, - это алгоритм, который эффективен в отношении количества ключей-кандидатов.${\ displaystyle 2 \ cdot n}$${\ displaystyle \ {A_ {i} \ rightarrow B_ {i}: i \ in \ {1, \ dots, n \} \} \ cup \ {B_ {i} \ rightarrow A_ {i}: i \ in \ {1, \ точки, n \} \}}$${\ Displaystyle 2 ^ {п}}$${\ displaystyle \ {A_ {1}, B_ {1} \} \ times \ dots \ times \ {A_ {n}, B_ {n} \}}$

Следующий алгоритм фактически работает за полиномиальное время по количеству ключей-кандидатов и функциональным зависимостям: ^[2]

 функция find_candidate_keys (A, F) / * A - это набор всех атрибутов, а F - набор функциональных зависимостей * / K [0]: = минимизировать (A); n: = 1; / * Количество ключей, известных на данный момент * / я: = 0; / * Текущий обрабатываемый ключ * / пока я <п делаю для каждого α → β ∈ F делаем / * Строим новый потенциальный ключ из предыдущего известного ключа и текущего FD * / S: = α ∪ (K [i] - β); / * Поиск, является ли новый потенциальный ключ частью уже известных ключей * /  найдено: = ложь; для j: = от 0 до n-1 сделать если K [j] ⊆ S, то найдено: = true; / * Если нет, добавляем if  если не найден тогда K [n]: = минимизировать (S); п: = п + 1; я: = я + 1 вернуть K

Идея алгоритма заключается в том, что при наличии ключа-кандидата и функциональной зависимости обратное применение функциональной зависимости дает набор , который также является ключом. Однако он может быть покрыт другими уже известными ключами-кандидатами. (Алгоритм проверяет этот случай с помощью переменной «найдено».) Если нет, то минимизация нового ключа дает новый ключ-кандидат. Ключевым моментом является то, что все ключи-кандидаты могут быть созданы таким образом.${\ displaystyle K_ {i}}$${\ displaystyle \ alpha \ rightarrow \ beta}$${\ Displaystyle \ альфа \ чашка (K_ {i} \ setminus \ beta)}$

См. Также [ править ]

• Альтернативный ключ
• Составной ключ
• Нормализация базы данных
• Первичный ключ
• Реляционная база данных
• Суперключ
• Главный импликант - это соответствующее понятие ключа-кандидата в логической логике.

Ссылки [ править ]

• Дата, Кристофер (2003). «5: Целостность». Введение в системы баз данных . Эддисон-Уэсли. С. 268–276. ISBN 978-0-321-18956-1.

Внешние ссылки [ править ]

• Системы управления реляционными базами данных - Дизайн баз данных - Техническое задание - Ключи : обзор различных типов ключей в РСУБД (Система управления реляционными базами данных).