Алгоритмы нахождения первичного ключа

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

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

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

Аналогично универсальный первичный ключ функционально определяет все атрибуты U всех отношений базы данных.

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

Используя понятие замыкания атрибутов, можно дать формальное определение первичного ключа отношения и указать простой способ, с помощью которого можно проверить, является ли заданный набор атрибутов первичным ключом отношения или нет [1], [6].

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

Пример 17. Пусть база данных состоит из четырех отношений (первичные ключи выделены):

Post (PN, PIM, GOR)

Det (DN, DIM, CENA)

PD (PN, DN, KOL)

Gorod(GOR, ST).

Эти отношения получены декомпозицией отношения PPD примера 1 из раздела 1.1. Все множество атрибутов базы данных определяется как

U = PN, PIM, ST, GOR, DN, DIM, CENA, KOL.

В разделе 1.3.1 были определены функциональные зависимости, которые справедливы на данном множестве атрибутов:

F = {PN ® PIM, PN ® GOR, PN ® ST, GOR ® ST, DN ® DIM, DN ® CENA, (PN,DN) ® KOL}.

Легко видеть, что для отношения Post справедливо множество зависимостей:

F_Post = {PN ® PIM, PN ® GOR}.

Атрибут PN действительно является первичным ключом отношения Post, так как

PN⁺ = PN, PIM, GOR (все множество атрибутов отношения Post).

Аналогично для отношения Det: F_Det = {DN ® DIM, DN ® CENA} и DN - первичный ключ отношения Det, так как DN⁺ = DN, DIM, CENA.

Для отношения PD: F_PD = {(PN, DN) ® KOL} и (PN, DN)⁺ = PN, DN, KOL.

Для отношения Gorod: F_Gorod = {GOR ® ST} и GOR⁺ = GOR, ST.

Универсальным первичным ключом в рассматриваемой базе данных является набор атрибутов (PN, DN), так как замыкание этого набора по множеству F равно полному набору атрибутов U:

(PN, DN) ⁺ = PN, DN, PIM, GOR, ST, DIM, CENA, KOL = U.

В рассматриваемом примере универсальный ключ совпадает с первичным ключом отношения PD. В общем случае это необязательно.

В настоящее время известны два алгоритма нахождения первичных ключей:

1. Алгоритм, основанный на последовательном исключении атрибутов из полного набора атрибутов отношения и проверке полученного набора на ключ;

2. Алгоритм, основанный на полном переборе претендентов на первичный ключ, начиная с одного, затем пар атрибутов и так далее.

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

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

Пример 18. Найдем первичный ключ отношения R = ABCDE, на котором справедливо множество функциональных зависимостей:

F = {A ® C, B ® C, C ® D, DE ® C, CE ® A}.

Алгоритм 1.

Выбираем первого претендента на первичный ключ, представляющего собой полный набор атрибутов отношения U= ABCDE. Обозначим этот набор X = ABCDE. Удаляем из него один атрибут, например A, и вычисляем замыкание полученного нового набора:

(X \ A)⁺ = (BCDE)⁺ = BCDEA = U.

Здесь символ “\” обозначает операцию вычитания атрибута A из набора X.

Поскольку замыкание указанного набора атрибутов дает все атрибуты U, то набор BCDE может быть ключом схемы отношения R, если никакое его подмножество, в свою очередь, не может быть ключом. Проверим это.

Итак, следующим претендентом на ключ является набор X = BCDE. Удаляем из него, например, атрибут B и вычисляем замыкание атрибутов нового набора:

(X \ B)⁺ = (CDE)⁺ = CDEA ≠ U.

Следовательно, набор CDE не может быть первичным ключом. Возвращаем атрибут B и удаляем из набора X атрибут C. Вычисляем замыкание нового набора атрибутов:

(X \ C)⁺ = (BDE)⁺ = BDECA = U.

Следовательно, набор BDE может быть первичным ключом. Проверим его на минимальность.

Итак, следующим претендентом на ключ является набор BDE, т.е. X = BDE. Удаляем из него атрибут D и вычисляем замыкание полученного набора атрибутов:

(X \ D)⁺ = (BE)⁺ = BECAD = U.

Следовательно, набор BE может быть первичным ключом. Проверим его на минимальность.

Итак, X = BE. После удаления атрибута E получим (X \ E)⁺ = B⁺ = BC ≠ U, а после удаления атрибута B получим (X \ B)⁺ = E⁺ = E ≠ U. Отсюда следует, что атрибуты B и E не могут быть первичными ключами. Поэтому в качестве первичного ключа можно взять последнего претендента - набор атрибутов BE. При этом мы не можем гарантировать минимальность найденного ключа, так как при другой последовательности исключения атрибутов возможно нахождение ключа с меньшим количеством атрибутов.

Алгоритм 2.

Сначала проверяем на ключ одиночные атрибуты

A⁺ = ACD ≠ U; B⁺ = BCD ≠ U; C⁺ = CD ≠ U; D⁺ = D ≠ U; E⁺ = E ≠ U.

Отсюда следует, что ни один одиночный атрибут отношения R = ABCDE не может выступать в роли первичного ключа этого отношения.

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

AB⁺ = ABCD ≠ U; AC⁺ = ACD ≠ U; AD⁺ = ADC ≠ U; AE⁺ = AECD ≠ U;

BC⁺ = BCD ≠ U; BD⁺ = BDC ≠ U; BE ⁺ = BECDA = U;

Таким образом, BE – минимальный первичный ключ исходного отношения.

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