4. Нормальные формы

Все проводимые ниже рассуждения о нормальных формах (как, впрочем, и о проектировании схем баз данных) относятся к системам оперативной обработки транзакций OLTP и базовым отношениям. Для OLAP-систем, как и для виртуальных отношений OLTP-систем, характерной является как раз ненормализованность данных, связанная с избыточной формой их хранения и представления.

4.1. Функциональные зависимости (ФЗ)

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

Рассмотрим отношение, содержащее данные о результатах конкретной экзаменационной сессии (семестр и учебный год не указаны):

Сессия(№ ЗК, Ф, И, О, МнемоП, Оценка)

Атрибуты № ЗК (номер зачетной книжки) и МнемоП (мнемоническое обозначение предмета) образуют ключ этого отношения (так как в конкретную сессию в одну зачетку по одному предмету

поставить можно лишь не более одной оценки). Однако помимо ограничения уникальности, связанного с этим ключом, на отношение должно быть наложено то условие, что зачетка выдается одному конкретному лицу и, следовательно, в этом отношении кортежи с одинаковым номером зачетки должны содержать одинаковые значения атрибутов Ф, И, О (табл. 4.1). Поэтому, как говорят, атрибуты Ф, И, О функционально зависят от атрибута № ЗК.

Таблица 4.1.: Пример ненормализованного отношения

Таким образом, функциональная зависимость – это однозначная зависимость, затабулированная в базе данных. Термин «зависимость» не означает, что в данном случае по № ЗК (числу) можно без использования данных, хранимых в отношении, «вычислить» Ф, И, О. Он означает лишь, что одному значению № ЗК нельзя в отношении сопоставить два или более значений Ф, И или О.

Определение. Пусть X и Y – подсхемы схемы отношения S, определяющие над схемой S схему функциональной зависимости X ! Y (читается «X стрелка Y»). Определим ограничение функциональной зависимости invhX ! Y i как утверждение о том, что в отношении со схемой S любые два кортежа, совпадающие в проекции на подсхему X, должны совпадать и в проекции на подсхему

Y :

invhX ! Y ir(S) = 8t1; t2 2 r(t1[X] = t2[X] ) t1[Y ] = t2[Y ]); X; Y 2 S

В этом случае говорят, также, что X функционально определяет Y или что Y функционально зависит от X. В схеме функциональной зависимости X ! Y подсхема X называется левой частью, а Y – правой частью. На схему функциональной зависимости для краткости обычно ссылаются как на функциональную зависимость.

Конец определения.

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

Приведем примеры изображения функциональных зависимостей:

{№ ЗК} ! {Ф, И, О} {№ ЗК, МнемоП} ! {Оценка}

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

Сессия(№ ЗК, Ф, И, О, МнемоП, Оценка) primary key(№ ЗК, МнемоП)

{№ ЗК} ! {Ф, И, О}

которым отношение будет автоматически удовлетворять.

Теорема. Справедливы следующие правила, называемые правилами вывода Армстронга (часто называемые аксиомами):

ПВ1. ` X ! X рефлексивность

ПВ2. X ! Y ` X [ Z ! Y пополнение

ПВ3. X ! Y; Y [ W ! Z ` X [ W ! Z псевдотранзитивность

Здесь X, Y , Z, W – произвольные подсхемы схемы отношения S. Символ метаутверждения о выводимости «`» разделяет списки посылок и заключений. Посылки и заключения представлены в сокращенной форме обозначениями схем функциональных зависимостей. В расширенной форме им соответствуют ограничения функциональных зависимостей:

ПВ1. invhX ! Xir(S)

ПВ2. invhX ! Y ir(S) ) invhX [ Z ! Y ir(S)

ПВ3. invhX ! Y ir(S)&invhY [ W ! Zir(S) ) invhX [ W ! Zir(S)

Доказательство правила рефлексивности следует непосредственно из определения ограничения функциональной зависимости при подстановке X вместо Y . Это тавтология.

Доказательство правила пополнения. Пусть кортежи равны на X [ Z. Тогда они равны на X. Согласно посылке, они будут равны и на Y .

Доказательство правила псевдотранзитивности. Пусть кортежи равны на X [W . Тогда они равны и на X, и на W . Согласно посылке 1, они будут равны и на Y . Следовательно, они равны и на X, и на W . Отсюда, согласно посылке 2, они будут равны и на Z.

Конец теоремы.