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

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

Кандидатный ключ — это минимальный суперключ , т.е. суперключ, который не содержит меньший ключ. Следовательно, отношение может иметь несколько потенциальных ключей, каждый из которых имеет разное количество атрибутов.

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

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

Существует функциональная зависимость от ключа-кандидата ко всем атрибутам в отношении.

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

Пример

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

р1

А	Б	С	Д
а1	б1	с1	d1
а1	б2	с2	d1
а2	б1	с2	d1

р2

А	Б	С	Д
а1	б1	с1	d1
а1	б2	с2	d1
а1	б1	с2	d2

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

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

{A,B}, {A,C}, {B,C}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {А,Б,С,Г}

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

{B,C}, {B,D}, {C,D}, {A,B,C}, {A,B,D}, {A,C,D}, {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}

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

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

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

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

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

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

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

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

function find_candidate_keys(A, F)
    /* A is the set of all attributes and F is the set of functional dependencies */
    K[0] := minimize(A);
    n := 1; /* Number of Keys known so far */
    i := 0; /* Currently processed key */
    while i < n do
        for each α → β ∈ F do
            /* Build a new potential key from the previous known key and the current FD */
            S := α ∪ (K[i] − β);
            /* Search whether the new potential key is part of the already known keys */ 
            found := false;
            for j := 0 to n-1 do
                if K[j] ⊆ S then found := true;
            /* If not, add it */
            if not found then
                K[n] := minimize(S);
                n := n + 1;
        i := i + 1
    return K

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

См. также

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

Ссылки

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

Внешние ссылки

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