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

Набор столбцов в реляционной базе данных

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

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

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

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

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

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

Пример

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

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

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

{А, Б}, {А, В}, {Б, В}, {А, В, В}, {А, В, Г}, {А, В, Г}, {Б, В, Г}, {А, В, Г}

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

{Б,В}, {Б,Г}, {Б,Г}, {А,Б,В}, {А,Б,Г}, {Б,В,Г}, {А,Б,В,Г}

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

{Б,В}, {А,Б,В}, {А,Б,Г}, {А,Б,В}, {Б,Б,В}, {А,Б,Б,В}

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

{Б,В}, {А,Б,Г}, {А,В,Г}

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

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

Определение потенциальных ключей

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

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

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

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

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

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

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

Смотрите также

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

Ссылки

1. Дата, Кристофер (2015). "Первые реляционные статьи Кодда: критический анализ" (PDF) . warwick.ac.uk . Получено 04.01.2020 . Обратите внимание, что извлечение позволяет "отношению" иметь любое количество первичных ключей, и, более того, такие ключи могут быть "избыточными" (лучше: приводимыми ). Другими словами, то, что в статье называется первичным ключом, позже (и лучше) стало известно как суперключ , а то, что в статье называется неизбыточным (лучше: неприводимым ) первичным ключом, позже стало известно как ключ-кандидат или (лучше) просто ключ .
2. "база данных - Может ли отношение иметь потенциальные ключи разной длины?". Stack Overflow . Получено 23.03.2023 .
3. Saiedian, H. (1996-02-01). "Эффективный алгоритм вычисления потенциальных ключей схемы реляционной базы данных". The Computer Journal . 39 (2): 124–132. doi :10.1093/comjnl/39.2.124. ISSN  0010-4620.
4. L. Lucchesi, Cláudio; Osborn, Sylvia L. (октябрь 1978 г.). «Кандидатные ключи для отношений». Журнал компьютерных и системных наук . 17 (2): 270–279. doi :10.1016/0022-0000(78)90009-0.

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

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

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