Возможный ключ и детерминант

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

Детерминант. Если А -> В есть ФЗ и В не зависит функционально от любого подмножества А, то говорят, что А представляет собой детерминант В.

Из рис.10 можно заключить, что отношение УСПЕВАЕМОСТЬ имеет только один возможный ключ, а именно набор атрибутов <Сном, Дисциплина, Семестр >. Этот вывод получен путем нахождения минимального набора значений атрибутов, которые, если они известны, определяют значение всех других атрибутов кортежа. С помощью ФЗ, представленных на рис.10, легко видеть, что один номер Сном  определяет Сфам, Кном, Тном и для определения оценки должен быть известен весь набор Сном, Дисциплина и Семестр.

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

Детерминантами в отношении УСПЕВАЕМОСТЬ являются левые части всех ФЗ в отношении. Детерминантами здесь являются <Сном, Дисциплина, Семестр >, <Сном>, <Кном> и <Тном>.

Детерминанты заключены в угловые скобки для того, чтобы в данном случае выделить четыре различных детерминанта. Следует заметить, что взаимные зависимости дают два детерминанта.

Коддом доказано, что большинство потенциальных аномалий в БД будет устранено в случае должной декомпозиции каждого отношения в  нормальную форму Бойса-Кодда  (НФБК), которая определяется следующим образом:

Отношение находится в НФБК, если каждый детерминант отношения является возможным ключом.

Отношение УСПЕВАЕМОСТЬ не находится в НФБК. Это легко обнаружить, если расположить рядом перечень всех детерминантов и перечень всех возможных ключей и посмотреть, является ли каждый детерминант возможным ключом.

Возможные ключи Детерминанты

<Сном,Дисц,Семестр> <Сном,Дисц,Семестр>

<Сном>

<Тном>

<Кном>

Поскольку не каждый детерминант в отношении УСПЕВАЕМОСТЬ является возможным ключом, следовательно оно не находится в НФБК и его необходимо подвергнуть декомпозиции.

Общий подход к декомпозиции

В общем виде алгоритм проектирования БД может выглядеть следующим образом:

1. Разработка универсального отношения для БД.

2. Определение всех ФЗ между атрибутами отношения.

3. Определение того, находится ли отношение в НФБК. Если да, проектирование завершается; если нет, отношение должно быть разложено на два отношения.

4. Повторение шагов 2 и 3 для каждого нового отношения, полученного в результате декомпозиции. Проектирование завершается, когда все отношения будут находится в НФБК.

Предложенный алгоритм не определяет, как осуществлять декомпозицию отношения, не приведенного к НФБК, на два отношения. Это осуществляется с помощью ФЗ следующим образом.

Пусть отношение R(A,B,C,D,E,...) не приведено к НФБК. Определяется ФЗ, например, С -> D, про которую известно, что она является причиной того, что отношение R не находится в НФБК (С является детерминантом, но не является возможным ключом).

Создается два новых отношения: R1(A,B,C,E,...) и R2(C,D), где зависимостная часть ФЗ была выделена из R и опущена при формировании отношения R1 и ФЗ была использована полностью при формировании отношения R2. Теперь необходимо проверить, находятся ли в НФБК отношения R1 и R2. Про отношение R2(C,D) говорят, что одно является  проекцией  отношения R. Этот тип декомпозиции называется  декомпозицией без потерь  при естественном соединении. Указанный метод декомпозиции может быть использован на шаге 3 приведенного выше алгоритма проектирования.

В качестве примера использования метода выполним декомпозицию отношения УСПЕВАЕМОСТЬ. Обращаясь вновь к детерминантам и возможным ключам отношения УСПЕВАЕМОСТЬ, видим, что имеются три детерминанта, не являющихся возможными ключами: <Сном>, <Тном> и <Кном>

Кандидатами среди ФЗ для осуществления проекции являются: Сном -> Кном; Сном -> Тном; Кном -> Тном и Тном -> Кном.

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

Простым правилом выбора ФЗ для проекции может служить поиск "цепочки" вида А -> В -> С с последующим использованием для проекции крайней правой зависимости. В нашем случае такой "цепочкой" является Сном -> Кном -> Тном и "конец цепочки" Кном -> Тном порождает первую проекцию. Полученные в итоге отношения R1 и R2 приведены на рис.11 вместе со связанными с ними ФЗ.

R1(Cном, Дисц, Семестр, Сфам, Кном, Оценка)

Возможные ключи  Детерминанты

<Сном, Дисц, Семестр> < Сном, Дисц, Семестр >

< Сном >

R2(Кном, Тном)

Возможные ключи  Детерминанты

< Кном > < Кном >

< Тном > < Тном >

Рис.11. Отношения R1 и R2 получены в результате проекции Кном <-> Тном из отношения УСПЕВАЕМОСТЬ.

Отношение R2(Кном, Тном) находится в НФБК, поскольку все его детерминанты являются возможными ключами и оно не нуждается более в декомпозиции. Первичным ключом отношения R2 могут быть как Кном, так и Тном. Отношение R1 не находится в НФБК, т.к. детерминант <Сном> не является возможным ключом.

Следовательно отношение R1 необходимо подвергнуть дальнейшей декомпозиции.

Детерминант <Сном> имеет два зависимых от него атрибута Сном -> Сфам, Сном -> Кном, что можно рассматривать в качестве единичной ФЗ с составной правой частью Сном -> Сфам, Кном.

Проекция отношения R1, порождаемая этой ФЗ приводит к получению отношений R3 и R4, показанных на рис.12. Эти два отношения находятся в НФБК и вместе с отношением R2 могут использоваться при формировании БД для учета успеваемости.

R3(Сном, Дисц, Семестр, Оценка)

Возможные ключи Детерминанты

<Сном,Дисц.,Семестр> < Сном,Дисц.,Семестр >

R4(Сном, Сфам, Кном)

Возможные ключи Детерминанты

<Сном> <Сном>

Рис.12. Отношение R3 и R4 полученные в результате проекции

На рис.13 представлен окончательный вид отношений для такой БД (названной УСПЕХИ), а также экземпляры каждого отношения с данными, совпадающими с использованными для исходного отношения УСПЕВАЕМОСТЬ. Заметим, в частности, что в процессе декомпозиции автоматически произошло разбиение исходного отношения УСПЕВАЕМОСТЬ на три логических компонента: R2, в котором содержится информация о комнатах и телефонах; R3, в котором содержится информация об учебных дисциплинах и полученных студентами оценках; R4, в котором содержится информация о студентах. Такое логическое разбиение является прямым результатом использования в процессе декомпозиции заложенной в ФЗ информации, детализирующей то, как различные атрибуты в исходном отношении соотносятся друг с другом.

R2(Кном, Тном)

R3(Сном, Дисц, Семестр, Оценка)

R4(Сном, Сфам, Кном)

а)

УСПЕХИ

R3 R2

Сном	Дисц	Сем	Оценка		Кном	Тном
111	ВМ	3	2		120	2135
111	ТМ	2	4		211	3257
111	Физика	3	5		301	3589
222	ВМ	3	4		201	3290
222	Химия	1	5		401	5452
222	ВТ	4	4	R4
333	ТМ	2	5	Сном	Сфам	Кном
110	ВМ	1	4	111	Серов	120
				222	Перов	211
				333	Иванов	301
				110	Поляков	201
				444	Белов	401

б)

Рис.13. а - база данных УСПЕХИ; б - экземпляр БД в котором используются данные, приведенные на рис.8,а