Ключи схем отношений.

Рассматривая наборы объектов, мы предполагали, что существует ключ – набор атрибутов, однозначно определяющий объект. Аналогичное понятие существует и для отношения с заданным множеством функциональных зависимостей, то есть набор атрибутов, однозначно определяющий кортеж отношения.

Пусть задана схема отношения R=(U, F), XÍU;

Множество Х называют сверхключом схемы отношения R, если Х⁺=U, то есть зависимость Х—>U принадлежит F⁺ .

Минимальный по включению сверхключ называется ключом, то есть Х – ключ схемы R, если:

1) X⁺ = U;

2) ни для какого собственного подмножества YÌХ, Y⁺¹U.

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

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

Задача нахождения произвольного “первого попавшегося” ключа отношения решается довольно просто. Это можно сделать следующим образом: рассматривается все множество атрибутов U, из него вычеркивается любой атрибут, получаем множество V; если V⁺=U, то вычеркнутый атрибут так и остается вычеркнутым, иначе возвращаем его на место. Далее пытаемся вычеркнуть следующий атрибут, так продолжаем до тех пор, пока ни один атрибут нельзя будет вычеркнуть. Оставшийся набор атрибутов является ключом отношения.

Вычисление всех ключей отношения задача довольно трудоемкая, поскольку ключей может быть экспоненциально много, подробнее эта задача рассматривается ниже. Задачи нахождения минимального по количеству атрибутов ключа, а также проверки, является ли конкретный атрибут ключевым (первичным), относятся к классу NP-трудных, то есть не имеют алгоритмов решения с полиномиальной оценкой трудоемкости.

Пример.

Для схемы отношения R=(U, F), где U={А1, А2, …, А8},

F={А1¾>А2; А2—>АЗ; A3¾>А1; А2,АЗ—>А4; А4,А7¾>А6;

А6,А5—>А7; А7¾>А8} требуется найти все ключи, наборы первичных и непервичных атрибутов и сверхключ. В результате решения получаем.

Все ключи отношения:

К1={А1, А5, А6}, К2={А1, А5, А7}, КЗ={А2, А5, A6},

К4={А2, А5, А7}, К5={АЗ, А5, А6}, К6={АЗ, А5, А7}.

Множество первичных атрибутов: {А1, А2, АЗ, А5, А6, А7}.

Множество непервичных атрибутов: {А4, А8}.

Ясно, что сверхключом является любое множество атрибутов, содержащее ключ, например, в приведенном примере сверхключом является множество: {А1, А2, А5, А6}.