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

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

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

Из рис.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

Сном	Дисц	Сем	Оценка		Кном	Тном
	ВМ
	ТМ
	Физика
	ВМ
	Химия
	ВТ			R4
	ТМ			Сном	Сфам	Кном
	ВМ				Серов
		Перов
	Иванов
	Поляков
	Белов

б)

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

Анализ исходных аномалий

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

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

Обновление. В исходном отношении УСПЕВАЕМОСТЬ попытка изменить номер телефона Серова, проживающего в комнате 120 может привести к тому, что в БД появится два различных телефонных номера, установленного в комнате 120. В БД УСПЕХИ телефонные номера располагаются в отношении R2 и каждая комната может иметь только один телефонный номер. Следует помнить, что Кном является первичным ключом отношения R2, а значения первичного ключа по определению должны быть уникальными. Для изменения телефонного номера Серова следует в кортеже отношения R2, в котором Кном=120, изменить номер Тном. При этом будет изменен номер телефона для всех студентов, живущих в этой комнате. Таким образом, исходная аномалия обновления устраняется с помощью НФБК-проектирования.

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

Удаление. Когда отношение УСПЕВАЕМОСТЬ использовалось в качестве БД, удаление кортежа включавшего значения Сном=110 и Дисц. ВМ, привело к исчезновению из БД студента с номерами 110. Этого не может произойти в случае БД УСПЕХИ, поскольку информация о студентах общего характера разнесена в два различных отношения (R3 и R4). При исключении из отношения R3 кортежа <110,ВМ,1,4>, общая информация о студенте, хранимая в R4, останется.

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