3.2. Нормализация на примерах

Пусть имеется схема отношения:

СТУДЕНТ2 (№_зачетки, Фамилия, Группа, Факультет, Семестр, Сессия)

где Сессия={Предмет, Преподаватель, Вид_работы, Оценка} представляет собой составной атрибут.

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

Представленная схема не соответствует требованиям первой нормальной формы, поскольку атрибут Сессия является множеством. После несложных преобразований приводим отношение к первой нормальной форме. Пусть имя нового имени отношения будет СТУДЕНТ:

СТУДЕНТ (№_зачетки, Фамилия, Группа, Факультет, Семестр, Предмет, Преподаватель, Вид_Работы, Оценка)

Отношение СТУДЕНТ (его фрагмент представлен на рис. 45) находится в первой нормальной форме, т. к. все составляющие его элементы атомарны.

№_за-четкиФамилияГруппа ФакультетСеместрПредмет ПреподавательВид_работыОценка
01ПановГ1Ф11ХимияСомовЭкзОтл
01ПановГ1Ф11ФизикаПетровЭкзОтл
01ПановГ1Ф11ИсторияЛьвовЭкзОтл
02ТуровГ2Ф11ХимияСомовЭкзХор
02ТуровГ2Ф11ФизикаПетровЭкзОтл
02ТуровГ2Ф11ИсторияЛьвовЭкзХор

Рис. 45. Исходное отношение в первой нормальной форме.

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

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

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

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

F1 = №_зачетки Фамилия, Группа, Факультет,
F2 = №_зачетки, Семестр, Предмет Преподаватель, Вид_Работы, Оценка,
F3 = №_зачетки, Семестр, Предмет Фамилия, Группа, Факультет,
F4 = №_зачетки, Семестр, Предмет Оценка,
F5 = Предмет Преподаватель,
F6 = Семестр, Предмет Вид_Работы,
F7 = Группа Факультет.

Рис. 46. Постулированные зависимости для отношения СТУДЕНТ (рис. 45)

Отметим, что в данном учебном пособии рассматривается упрощенный алгоритм нормализации, не нарушающий принципов теории нормализации. В качестве первоисточников рекомендуется обратиться к литературе [1, 2, 3, 6, 13, 18], где указывается, что теоретически каждый рассмотренный ниже этап процесса нормализации, относится к так называемым NP-полным задачам.

Так, например, алгоритм оптимального синтеза реляционной модели [2] базы данных оценивается величиной:

K = N * n + N2 * n + N * n2 + N2S,               (2)

где n - количество атрибутов, N - количество функциональных и многозначных зависимостей, S - количество атрибутов модели, входящих только в левые части зависимостей.

Этап 0. Определение возможных ключей

Применяя аксиомы для ФЗ (см. п. 2.3) или алгоритм определения реляционного ключа (см. п. 2.4), можно убедиться, что реляционным ключом в отношении СТУДЕНТ (рис. 45) является группа атрибутов: {№_зачетки, Семестр, Предмет}.

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

Этап 1. Приведение отношения к 2НФ

Для определения 2НФ необходимо выявить полные функциональные зависимости. Если такие зависимости присутствуют, то их следует представить в виде отдельных проекций.

Функциональная зависимость F3 (рис. 46) является неполной, т.к. набор атрибутов {Фамилия, Группа, Факультет}, в соответствии с F1, функционально зависит от атрибута №_зачетки, входящего в состав атрибутов левой части функциональной зависимости F3.

Функциональные зависимости F1, F2, F4, F5, F6 (рис. 46) являются полными функциональными зависимостями.

Отметим, что зависимости F2, F3, F4 являются зависимостями набора атрибутов схемы отношения от ключа отношения.
Следовательно, отношение СТУДЕНТ (рис. 45) не находится во второй нормальной форме. Используя правило декомпозиции, приведем отношение СТУДЕНТ ко второй нормальной форме. В результате декомпозиции получатся две проекции:

R1 (№_зачетки, Фамилия, Группа, Факультет) и
R2 (№_зачетки, Семестр, Предмет, Преподаватель, Вид_Работы, Оценка).

Состав проекций R1 и R2 приведен на рис. 47 и 48 соответственно.

№_зачеткиФамилияГруппа Факультет
01ПановГ1Ф1
02ТуровГ2Ф1

Рис. 47. Проекция R1


№_зачеткиСеместрПредмет ПреподавательВид_работыОценка
011ХимияСомовЭкзОтл
011ФизикаПетровЭкзОтл
011ИсторияЛьвовЭкзОтл
021ХимияСомовЭкзХор
021ФизикаПетровЭкзОтл
021ИсторияЛьвовЭкзХор

Рис. 48. Проекция R2

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

Для отношения R1 (рис. 47) реляционным ключом будет атрибут (с именем) №_зачетки, а для отношения R2 (рис. 48) множество, состоящее из атрибутов {№_зачетки, Семестр, Предмет}. Если применить к этим проекциям предложение языка SQL (являющегося эквивалентным операции эквисоединения реляционной алгебры):

SELECT *
FROM R1, R2
WHERE R1.№_зачетки=R2.№_зачетки;
то исходное отношение будет восстановлено. При этом следует помнить, что проведенная операция даст истинный результат только в том случае, если один из операндов участвующих в операции, является в отношении-операнде реляционным ключом, а не просто входит в него. В нашем случае атрибут №_зачетки является первичным ключом в отношении R1 (рис. 47).

Далее необходимо проверить, находится ли каждая полученная проекция во второй нормальной форме.

Отношение R1 находится в первой нормальной форме, первичным ключом является атрибут №_зачетки. Каждый непервичный атрибут отношения R1 функционально полно зависит от ключа, следовательно, оно находится во второй нормальной форме. Заметим, что отношение всегда находится во второй нормальной форме, если первичный ключ этого отношения атомарен.

Отношение R2 (рис. 48) находится в 1НФ и его ключом является набор атрибутов {№_зачетки, Семестр, Предмет}. Однако оно не находится в 2НФ в силу неполной функциональной зависимости непервичного атрибута Преподаватель от ключа отношения (функциональная зависимость F5 (рис. 46) привносит неполноту) и неполной функциональной зависимости атрибута Вид_Работы от ключа отношения (функциональная зависимость F6 (рис. 46)). Учитывая указанные функциональные зависимости, отношение со схемой R2 должно быть, представлено в виде трех проекций R3 (рис. 49), R4 (рис. 50) и R5 (рис. 51):

№_зачеткиСеместрПредмет Оценка
011ХимияОтл
011ФизикаОтл
011ИсторияОтл
021ХимияХор
021ФизикаОтл
021ИсторияХор

Рис. 49. Проекция R3

ПредметПреподаватель
ФизикаПетров
ИсторияЛьвов
ХимияСомов
СеместрПредмет Вид_работы
1ФизикаЭкз
1ИсторияЭкз
1ХимияЭкз
Рис. 50. Проекция R4 Рис. 51. Проекция R5

Из полученной совокупности проекций R3, R4, R5, может быть восстановлено отношение R2 (рис. 48), если эквисоединение будет производится по ключам указанных отношений (рис. 52).

R3 (№_зачетки, Семестр, Предмет, Оценка),
R4 (Предмет, Преподаватель),
R5 (Семестр, Предмет, Вид_Работы).

Рис. 52. Промежуточный набор отношений

Как всегда, реляционные ключи в схемах отношений подчеркнуты. Полученные проекции R3, R4, R5 проверяются на предмет их нахождения во второй нормальной форме. Учитывая, что в указанных проекциях отсутствуют неполные функциональные зависимости, эти отношения находятся во второй нормальной форме.

Результатом этапа будет совокупность отношений во второй нормальной форме (рис. 53):

R1 (№_зачетки, Фамилия, Группа, Факультет),
R3 (№_зачетки, Семестр, Предмет, Оценка),
R4 (Предмет, Преподаватель),
R5 (Семестр, Предмет, Вид_Работы).

Рис. 53. Набор отношений в 2НФ

Этап 2. Приведение отношения к 3НФ

Определение 3НФ запрещает наличие транзитивных зависимостей между непервичными атрибутами, поэтому анализу подлежит только отношение R1 (№_зачетки, Фамилия, Группа, Факультет), в котором присутствует несколько непервичных атрибутов. Все оставшиеся отношения по определению находятся в 3НФ.

Наличие функциональной зависимости F7 = Группа Факультет в отношении R1, приводит к транзитивной зависимости №_зачетки Группа Факультет, от которой следует избавиться, оставив атрибут Группа в качестве внешнего ключа в отношении R1. В результате получатся две проекции (рис. 54):

R11 ( №_зачетки, Фамилия, Группа),
R12 ( Группа, Факультет).

Рис. 54. Устранение транзитивной зависимости


Этап 3. Приведение к БКНФ

Все полученные отношения (рис. 55):

R11 (№_зачетки, Фамилия, Группа),
R12 (Группа, Факультет),
R3 (№_зачетки, Семестр, Предмет, Оценка),
R4 (Предмет, Преподаватель),
R5 (Семестр, Предмет, Вид_Работы).

Рис. 55. Состав отношений в БКНФ

находятся в нормальной форме Бойса-Кодда, потому что каждая функциональная зависимость из множества F = {F1, . . . , F7} (рис. 46) является (подразумевается) потенциальным ключом.

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

Пусть объект ПРЕПОДАВАТЕЛЬ наделяется администратором базы следующими свойствами ПРЕПОДАВАТЕЛЬ (Шифр, Фамилия, Должность, Оклад) (рис. 57) и для него фиксируются следующие зависимости (рис. 56):

F8: Шифр Фамилия,
F9: Шифр Должность,
F10: Шифр Оклад,
F11: Должность Оклад.

Рис. 56. Функциональные зависимости в объекте ПРЕПОДАВАТЕЛЬ

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

Для преподавателя также вводится отношение истории его работы:

ИСТОРИЯ_РАБОТЫ (Шифр, Предмет, Год, Должность),

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

Пусть исходные состояния фрагментов отношений R6 – ПРЕПОДАВАТЕЛЬ и R7 – ИСТОРИЯ_РАБОТЫ таковы, как это представлено на рис. 57 и 58 соответственно.

ШифрФамилия ДолжностьОклад
01ПетровПрепод.2100
02ЛьвовАссистент1700
03СомовДоцент2500
04ИвановДоцент2500
05СидоровДоцент2500


ШифрПредмет ДолжностьГод
01Числ.методыДоцент2000
01Теория алгор.Доцент2000
02Числ.методыАссистент2000
02Теория алгор.Ассистент2000
01Числ.методыДоцент2001
01Теория алгор.Доцент2001
02Числ.методыПрепод.2001
02Теория алгор.Препод.2001
Рис. 57. Проекция R6 - ПРЕПОДАВАТЕЛЬ Рис. 58. Проекция R7 - ИСТОРИЯ_РАБОТЫ

В отношении R6 (рис. 57) в качестве ключа используется атрибут Шифр и оно имеет транзитивную зависимость между непервичными атрибутами:

ШифрДолжность Оклад,
поэтому его необходимо привести к 3НФ, избавившись от транзитивности, используя общее правило декомпозиции (см. п. 2.5.2). Зависимость ШифрОклад является транзитивной. Учитывая функциональную зависимость ШифрДолжность, отношение ПРЕПОДАВАТЕЛЬ (рис. 57) можно получить естественным соединением двух проекций R8 и R9:

SELECT *
FROM R8, R9
WHERE R8.Шифр = R9.Шифр;

При этом с помощью языка описания схем DDL [30] построенные проекции должны получить в описании соответствующие определения ключей;

CREATETABLER8
ШифрCHAR(2)NOT NULL,
ФамилияCHAR(17)NOT NULL,
ДолжностьCHAR(15)NOT NULL,
 PRIMARY KEY (Шифр);

и

CREATETABLER9
ШифрCHAR(2)NOT NULL,
ОкладDECIMAL(8,2)NOT NULL,
 PRIMARY KEY (Шифр);

Рис. 59. Описание схемы на SQL

Напомним, что язык DDL является составной частью языка SQL.

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

Таким образом, исходное отношение ПРЕПОДАВАТЕЛЬ будет представлено двумя отношениями R8 (рис. 60) и R9 (рис. 61):

ШифрФамилия Должность
01ПетровПрепод.
02ЛьвовАссистент
03СомовДоцент
04ИвановДоцент
05СидоровДоцент
ШифрОклад
012100
021700
032500
032500
032500
Рис. 60. Проекция R8 Рис. 61. Проекция R9

Отметим, что исходное отношение ПРЕПОДАВАТЕЛЬ (рис. 57) может быть представлено и другой группой проекций (см. рис. 62 и 63), из которых также восстановимо исходное отношение.

ШифрФамилия Должность
01ПетровПрепод.
02ЛьвовАссистент
03СомовДоцент
04ИвановДоцент
05СидоровДоцент
ДолжностьОклад
Преподаватель2100
Ассистент1700
Доцент2500


Рис. 62. Проекция R10 Рис. 63. Проекция R11

Полученная совокупность проекций позволяет восстановить исходное отношение на основе следующего предложения языка SQL:

SELECT *
FROM R10, R11
WHERE R10.Должность = R11.Должность;

Результат разложения должен быть зафиксирован в описании схем отношений (рис. 64, а и 64, б):

CREATETABLER8
ШифрCHAR(2)NOT NULL,
ФамилияCHAR(17)NOT NULL,
ДолжностьCHAR(15)NOT NULL,
PRIMARY KEY (Шифр),
FOREIGN KEY (Должность) REFERENCES R11
ON UPDATE CASCADE;

Рис. 64, а. Схема отношения R10


CREATETABLER9
ДолжностьCHAR(15)NOT NULL,
ОкладDECIMAL(8,2)NOT NULL,
 PRIMARY KEY (Шифр);

Рис. 64, б. Схема отношения R11

Какое же решение должен принять алгоритм теории нормализации: включить в результирующую схему отношения R8, R9 или R10, R11 (указанные группы отношений находятся в 3НФ и нетрудно увидеть, что они находятся и в 4НФ).

Рассмотрим более подробно декомпозицию R10 и R11. Указанные проекции независимы друг от друга в следующем смысле: операции обновления данных в каждой из проекций могут быть выполнены совершенно независимо друг от друга [3] (отметим, что на практике это не так, но мы рассматриваем традиционную трактовку). Если такое обновление допустимо только в контексте данной проекции, т.е. не нарушается уникальность ключа в этой проекции, то соединение проекций R10 и R11 после обновления будет восстанавливать исходное отношение в новом его состоянии. Т.е. при соединении не будут нарушены ограничения, наложенные на ФЗ в отношении представленном на рис. 57.

Анализ декомпозиции R8 и R9 показывает, что обновление любой из этих проекций должно контролироваться системой, чтобы отслеживать нарушение зависимости ДолжностьОклад. Другими словами, обе проекции в декомпозиции не являются независимыми одна от другой и, кроме того, зависимость ДолжностьОклад становится ограничением между отношениями, хранимыми в базе данных. Такое ограничение уже явно не поддерживается в стандарте SQL и приходится писать программный код (триггеры, хранимые процедуры и т. п.).

Для декомпозиции R10, R11 такая необходимость отсутствует (не надо писать самим программный код), т.к. это становится прерогативой самой СУБД (для этого и используется ссылка REFERENCES R11 с опцией ON UPDATE CASCADE, см. рис. 64), которая опирается на правило уникальности первичных ключей отношения.

Заметим, что алгоритмы теории нормализации – это чисто синтаксические правила и поэтому они не могут "чувствовать" семантику любых видов зависимостей (подобное замечание было высказано достаточно давно, см. например [1, 6].

Традиционный реляционный подход, опираясь на концепцию независимых проекций, предлагает использовать для нашего примера декомпозицию R10 и R11, исходя из следующего определения независимых отношений [3].

Определение. Проекции R1 и R2 независимы тогда и только тогда, когда:

  1. Каждая ФЗ в отношении R является логическим следствием функциональных зависимостей в проекциях R1 и R2;
  2. Общие атрибуты проекций R1 и R2 образуют потенциальный ключ, по крайней мере, в одной из них.

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

Еще раз подчеркнем, что декомпозиция типа: Преподаватель (Шифр, Фамилия, Оклад) и Оклады (Оклад, Должность), является недопустимой, поскольку она выполняется с потерей информации.
Таким образом, если существует отношение R (A, B, C), удовлетворяющее функциональным зависимостям A B и B C, то исходное отношение следует разбивать на проекции {A, B} и {B, C}.
Аналогичное правило распространяется и на многозначные зависимости A B и B C.

Все ниже приведенные отношения (рис. 65) находятся в БКНФ.

R11 (№_зачетки, Фамилия, Группа),
R12 ( Группа, Факультет),
R3 ( №_зачетки, Семестр, Предмет, Оценка),
R4 (Предмет, Шифр_Преподавателя),
R5 (Семестр, Предмет, Вид_Работы),
R10 (Шифр, Фамилия, Должность),
R11 (Должность, Оклад).

Рис. 65. Состав отношений в БКНФ   (Докажите!)


Этап 3. Приведение отношения к 4НФ

В качестве примера для рассмотрения данного этапа воспользуемся отношением ИСТОРИЯ_РАБОТЫ, представленным на рисунке 58. Для данного отношения существует следующий набор многозначных зависимостей:

F12:   Шифр Предмет,
F13:   Шифр Год, Должность.

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

ШифрПредмет
01Числ. методы
01Теория алгор.
02Числ. методы
02Теория алгор.
ШифрДолжность Год
01Доцент2000
02Ассистент2000
01Доцент2001
02Преподаватель2001
Рис. 66. Проекция R13 Рис. 67. Проекция R14

Проекции R13 и R14 находятся в 4НФ, так как отношения содержат только тривиальные многозначные зависимости. Исходное отношение, представленное на рис. 58, полностью восстановимо с помощью следующей конструкции языка SQL:

SELECT *
FROM   R13, R14
WHERE   R13.Шифр = R14.Шифр;

Напомним, что многозначная (как и функциональная) зависимость должна являться инвариантом предметной области.

В качестве упражнения ответьте на вопросы:

  1. Можно ли добавить кортеж вида: <02, Доцент, 2003> в отношение R14 (рис. 67)?
  2. Можно ли добавить кортеж вида: <02, Схемотехника> в отношение R13 (рис. 66)?

Таким образом, схема базы данных будет состоять из следующих отношений (рис. 68):

R11 (№_зачетки, Фамилия, Группа),
R12 ( Группа, Факультет),
R3 ( №_зачетки, Семестр, Предмет, Оценка),
R4 (Предмет, Шифр_Преподавателя),
R5 (Семестр, Предмет, Вид_Работы),
R10 (Шифр, Фамилия, Должность),
R11 (Должность, Оклад).
R13 (Шифр, Предмет),
R14 (Шифр, Должность, Год).

Рис. 68. Состав отношений в 4НФ (5НФ)


Для однозначности прочтения атрибутов отношений, имена некоторых атрибутов, указанных на рис. 62, необходимо видоизменить (рис. 69):

R11 (№_зачетки, Фамилия, Группа),
R12 ( Группа, Факультет),
R3 ( №_зачетки, Семестр, Предмет, Оценка),
R4 (Предмет, Шифр_Преподавателя),
R5 (Семестр, Предмет, Вид_Работы),
R10 (Шифр_Преподавателя, Фамилия, Должность),
R11 (Должность, Оклад).
R13 (Шифр_Преподавателя, Предмет),
R14 (Шифр_Преподавателя, Должность, Год).

Рис. 69. Уточненные имена атрибутов


[ Назад  Начало раздела  Далее  Содержание]