Первая, вторая и третья нормальные формы

Диаграммы ФЗ

Пусть дана переменная-отношение R и пусть к ней применимо некоторое неприводимое множество функциональных зависимостей I. Удобнее всего представить это множество ФЗ в виде диаграммы функциональных зависимостей (диаграммы ФЗ). На рис. 4.5 представлены диаграммы ФЗ для переменных-отношений S, SP и P соответственно.

Рис. 11.3. Диаграмма ФЗ для переменных-отношений S, SP, P

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

ФЗ – это особый вид ограничений целостности, а потому они, несомненно, являются понятием семантическим. Распознавание ФЗ представляет собой часть процесса выяснения смысла тех или иных данных.

Замечание: При изложении материала данного раздела предполагается, что переменная-отношение имеет в точности один потенциальный ключ, который является первичным ключом.

Следует отметить, что сами по себе нормальные формы 1НФ, 2НФ и 3НФ не имеют особого значения и должны рассматриваться лишь как промежуточные этапы на пути построения НФБК (и форм более высокого уровня). Вначале дадим неформальное определение 3НФ для того, чтобы в общих чертах обрисовать основную цель изложения. После этого приведем описание процедуры перевода произвольной переменной-отношения к эквивалентному набору переменных-отношений в 3НФ.

Третья нормальная форма (неформальное определение). Переменная-отношение находится в 3НФ тогда и только тогда, когда ее неключевые атрибуты (если они вообще есть) являются:

а) взаимно независимыми;

б) неприводимо зависимыми от первичного ключа.

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

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

Теперь вернемся к описанию процедуры нормализации и дадим определение первой нормальной формы.

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

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

FIRST {S#, STATUS, CITY, P#, QTY}

PRIMARY KEY {S#, P#}

Кроме того, имеется и дополнительная ФЗ:

CITY ® STATUS

Данная ФЗ означает, что статус поставщика определяется его местоположением. Тогда диаграмма ФЗ будет иметь вид, представленный на рис. 4.6. В переменной-отношении FIRST нарушаются оба условия, указанные в приведенном выше определении 3НФ: не все неключевые атрибуты взаимно независимы, поскольку атрибут STATUS зависит от атрибута CITY, и не все неключевые атрибуты неприводимо зависимы от первичного ключа, поскольку атрибуты CITY и STATUS, каждый в отдельности, зависимы от атрибута S#.

Рис. 11.4. Диаграмма ФЗ переменной-отношения FIRST

Для иллюстрации дополнительных трудностей, порождаемых дополнительными стрелками на диаграмме ФЗ, приведен пример данных в переменной-отношении FIRST (см. рис. 11.5). Возникшая в результате избыточность очевидна, поскольку в каждом кортеже для поставщика с номером ‘S1’ атрибут CITY имеет значение ‘Москва’ и, кроме того, в каждом кортеже со значением ‘Москва’ в атрибуте CITY указано значение 20 для атрибута CITY.

FIRST

S#	STATUS	CITY	P#	QTY
S1		Москва	P1
S1		Москва	P2
S1		Москва	P3
S1		Москва	P4
S1		Москва	P5
S1		Москва	P6
S2		Смоленск	P1
S2		Смоленск	P2
S3		Смоленск	P2
S4		Москва	P2
S4		Москва	P4
S4		Москва	P5

Рис. 11.5. Пример данных в переменной-отношении FIRST

Избыточность в переменной-отношении FIRST приводит к разным аномалиям обновления, получившим такое название по историческим причинам. Под этим понимаются трудности, появляющиеся при выполнении операций обновления INSERT, DELETE и UPDATE. Рассмотрим избыточность вида «поставщик-город», соответствующую ФЗ S# ® CITY. Ниже приводятся описания проблем, которые могут возникнуть при выполнении каждой из указанных операций обновления.

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

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

Операция UPDATE. Название города для каждого поставщика повторяется в переменной-отношении FIRST несколько раз, и эта избыточность приводит к возникновению проблем при обновлении. Например, если поставщик с номером ‘S1’ переместится из Москвы в Тверь, то необходимо будет отыскать в переменной-отношении FIRST все кортежи, в которых значение ‘S1’ и ‘Москва’ связаны между собой (для внесения соответствующих изменений), иначе база данных окажется в противоречивом состоянии.

Для решения этих проблем необходимо заменить переменную-отношение FIRST двумя следующими переменными-отношениями:

SECOND {S#, STATUS, CITY}

SP {S#, P#, QTY}

Диаграммы ФЗ для этих двух переменных-отношений показаны на рис. 11.6а, а соответствующие наборы данных приведены на рис. 11.6.б.

(а)

SECOND

 

S#	STATUS	CITY
S1		Москва
S2		Смоленск
S3		Смоленск
S4		Москва

SP

 

S#	P#	QTY
S1	P1
S1	P2
S1	P3
S1	P4
S1	P5
S1	P6
S2	P1
S2	P2
S3	P2
S4	P2
S4	P4
S4	P5

(б)

Рис. 11.6. (а) ФЗ в переменных-отношениях SECOND и SP (б) данные, содержащиеся в переменных-отношениях SECOND и SP

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

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

Обе переменные-отношения (и SECOND,и SP) находятся во второй нормальной форме, тогда как переменная-отношение FIRST не находится в этой форме. Всякую переменную-отношение, которая находится в первой нормальной форме, но не находится во торой, всегда можно свести к эквивалентному множеству переменных-отношений, находящихся во 2НФ. Этот процесс заключается в преобразовании переменной-отношения в 1НФ подходящим набором проекций, эквивалентных исходной переменной-отношению в том смысле, что ее можно будет восстановить с помощью обратной операции соединения данных проекций.

Таким образом, первый этап процедуры нормализации состоит в создании проекций, которые позволяют исключить ФЗ, не являющиеся неприводимыми. Пусть дана переменная-отношение R, имеющая следующий вид:

R {A, B, C, D}

PRIMARY KEY {A, B}

/* Предполагается наличие ФЗ A ® D */

Процедура нормализации предусматривает замену этой переменной-отношения следующими двумя проекциями R1 и R2.

R1 {A, D}

PRIMARY KEY {A}

R2 {A, B, C}

PRIMARY KEY {A, B}

FOREIGN KEY {A} REFERENCES R1

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

Возвращаясь к нашему примеру, можно заметить, что структура переменных-отношений SECOND и SP все еще может вызвать некоторые проблемы. В переменной-отношении SECOND неключевые атрибуты все еще не являются взаимно независимыми. В частности, зависимость атрибута STATUS от атрибута S# хотя и является функциональной и действительно неприводимой, одновременно является и транзитивной (через атрибут CITY). Однако наличие транзитивных зависимостей может привести к возникновению описанных ниже аномалий обновления.

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

Операция DELETE. При удалении из переменной-отношения SECOND кортежа для некоторого города, представленного в ней этим единственным кортежем, будут удалены сведения не только о поставщике из данного города, но и информация о том, каким статусом обладал сам город.

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

Для решения этой проблемы необходимо заменить переменную-отношение SECOND двумя следующими проекциями:

SC {S#, CITY}

CS {CITY, STATUS}

Диаграммы ФЗ для этих переменных-отношений показаны на рис. 11.7а, а их содержимое – на рис. 11.7б.

(а)

SC

S#	CITY
S1	Москва
S2	Смоленск
S3	Смоленск
S4	Москва

CS

CITY	STATUS
Москва
Смоленск

(б)

Рис. 11.7. (а) ФЗ в переменных-отношениях SC и CS (б) данные, содержащиеся в переменных-отношениях SC и CS

Данное предобразование обратимо, так как переменная-отношение SECOND может быть получена посредством соединения переменных-отношений SC и CS по атрибуту CITY.

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

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

Переменные-отношения SC и CS находятся в третьей нормальной форме, причем первичными ключами в них являются атрибуты {S#} и {CITY} соответственно. Переменная-отношение SECOND не находится в третьей нормальной форме. Переменная-отношение, которая находится в 2НФ и не находится в 3НФ, всегда может быть преобразована в эквивалентный набор переменных-отношений в 3НФ. Этот процесс обратим, и, следовательно, никакая информация при подобном преобразовании не утрачивается.

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

R {A, B, C}

PRIMARY KEY {A}

/* Предполагается наличие ФЗ B ® C */

Процедура нормализации предусматривает замену этой переменной-отношения следующими двумя проекциями R1 и R2:

R1 {B, C}

PRIMARY KEY {B}

R2 {A, B}

PRIMARY KEY {A}

FOREIGN KEY {B} REFERENCES R1

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

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

Дата добавления: 2015-05-09