Ульман Дж. Базы данных на Паскале (стр. 4 )

3.7.2. ВТОРАЯ НОРМАЛЬНАЯ ФОРМА

Как пояснялось в разд. 1.2.3, первичным ключом принято называть наиболее удобный для доступа в записям файла ключ-кандидат. Например, фирма <Типико> в качестве первичного ключа файла КЛИЕНТЫ использует поле НОМЕР_КЛИЕНТА.

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

В частности, файл ЗВЕРИ_В_НЕВОЛЕ из разд. 3.2 не может быть отнесен ко второй нормальной форме, поскольку поле ЗОНА_ОБИТАНИЯ функционально зависит от поля ЖИВОТНОЕ и тем самым не находится в полной функциональной зависимости

от первичного ключа, образуемого парой ЗООПАРК, ЖИВОТНОЕ.

Описанный в разд. 3.3.1 файл ПОСТАВЩИКИ_ТОВАРОВ, напротив, удовлетворяет определению второй нормальной формы, так как его поля НАЗВАНИЕ, НОМЕР_ТЕЛЕФОНА функционально полностью зависят от первичного ключа, которым служит ШИФР_ТОВАРА.

Первичный ключ файла ЗАКАЗЫ из разд. 3.6.1 состоит из двух полей: НОМЕР_ЗАКАЗА и ШИФР_ТОВАРА. В то время как поле КОЛИЧЕСТВО находится в полной функциональной зависимости от первичного ключа, поле ОПИСАНИЕ просто

зависит от него, и поэтому файл ЗАКАЗЫ не представлен во второй нормальной форме.

Легко показать, что любой файл, не отвечающий определению второй нормальной формы, не может находиться и в пятой нормальной форме. Предположим, что таким файлом является ИМЯФАЙЛА. Набор из одного или нескольких неключевых полей ИМЯФАЙЛА, функционально зависящих от первичного ключа, обозначим К, а подмножество полей первичного ключа, от которых К функционально зависит полностью, - J. Совокупность остальных полей ИМЯФАЙЛА, не входящих в К или J, назовем Н. Согласно теореме Хита, указанная функциональная зависимость влечет тождество: ИМЯФАЙЛА = proj Н, J (ИМЯФАЙЛА join proj J, К (ИМЯФАЙЛА).

Проекции в правой части тождества не имеют общего ключа-кандидата. Следовательно, ИМЯФАЙЛА не находится в пятой нормальной форме и подлежит поэтому нормализации. Имеется в виду, что его следует заменить полной декомпозицией, объединяющей проекции в пятой нормальной форме. Для файла ЗВЕРИ_В_НЕВОЛЕ такую декомпозицию можно составить, в частности, из проекций proj ЗООПАРК, ЖИВОТНОЕ (ЗВЕРИ_В_НЕВОЛЕ) и

proj ЖИВОТНОЕ, ЗОНА_ОБИТАНИЯ (ЗВЕРИ_В_ НЕВОЛЕ).

Нормализация файла ЗАКАЗЫ осуществляется путем разложения на проекции

proj НОМЕР_ЗАКАЗА, ШИФР_ТОВАРА, КОЛИЧЕСТВО (ЗАКАЗЫ) и

proj ШИФР_ТОВАРА, ОПИСАНИЕ (ЗАКАЗЫ).

3.7.3. ТРЕТЬЯ НОРМАЛЬНАЯ ФОРМА

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

Если ввести ограничение, запрещающее записывать в файл ПОСТАВЩИКИ_ТОВАРОВ из разд. 3.3.1 фирмы-поставщики с одинаковыми названиями, он потеряет третью нормальную форму, поскольку его поле НОМЕР_ТЕЛЕФОНА станет связано Функциональной зависимостью с полем НАЗВАНИЕ, не являющимся ключом. В то же время, благодаря тому, что поле АДРЕС файла АДРЕСА_КЛИЕНТОВ функционально не зависит от поля НАЗВАНИЕ, этот файл имеет третью нормальную форму.

Можно доказать, что любой файл ИМЯФАЙЛА, который не представлен в третьей нормальной форме, не может находиться в пятой нормальной форме. Для этого определим К как набор неключевых полей, обладающих функциональной зависимостью от другого набора неключевых полей, которое обозначим J. Введем также совокупность полей Н файла ИМЯФАЙЛА, не принадлежащих J или К. Наличие указанной функциональной зависимости согласно теореме Хита приводит к тождеству

ИМЯФАЙЛА = proj Н, J (ИМЯФАЙЛА) join proj J, К (ИМЯФАЙЛА).

Проекции в правой части тождества не имеют общего ключа - кандидата. Следовательно, ИМЯФАЙЛА не находится в пятой нормальной форме и его следует нормализовать, заменив этими проекциями. Так, например, файл ПОСТАВЩИКИ_ТОВАРОВ {разд 3.3.1) можно нормализовать, замещая его проекциями

proj ШИФР_ТОВАРА, НАЗВАНИЕ (ПОСТАВЩИКИ_ТОВАРОВ) и

proj НАЗВАНИЕ, НОМЕР_ТЕЛЕФОНА (ПОСТАВЩИКИ_TOBAРОB).

3.7.4. НОРМАЛЬНАЯ ФОРМА БОЙСА-КОДДА

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

к полной функциональной зависимости от ключа-кандидата.

Примером файла, который представлен в третьей нормальной форме но не имеет НФБК, может служить файл СТОРОЖА_ЗООПАРКОВ:

ЗООПАРК эйтон эйтон БИТОН БИТОН

ЖИВОТНОЕ КЕНГУРУ ВПГБЛЮД ЭМУ ВЕРБЛЮД

СТОРОЖ ПОНСОНБИ ПОНСОПБИ КАРУЗЕРС ГЕРДЛСТОН

Пара ЗООПАРК, ЖИВОТНОЕ составляет ключ-кандидат, от которого поле СТОРОЖ находится в полной функциональной зависимости. Однако из-за того, что поле ЗООПАРК, входящее в ключ-кандидат, функционально зависит от поля СТОРОЖ,

данный файл не находится в НФЬК.

Для того чтобы доказать, что любой файл, не имеющий НФБК, не может находиться в пятой нормальной форме, рассмотрим произвольный файл ИМЯФАЙЛА. Пусть К - набор полей этого файла, связанный полной функциональной зависимостью с другим набором полей J, который не является ключом-кандидатом. Как и в предыдущих случаях, введем совокупность полей Н, не принадлежащих J или К. В силу наличия функциональной зависимости из теоремы Хита следует, что

ИМЯФАЙЛА = proj Н, J (ИМЯФАЙЛА) join proj J, К (ИМЯ ФАЙЛА).

Две проекции в правой части тождества не содержат общего ключа-кандидата, ввиду чего можно утверждать, что ИМЯФАЙЛА не представлен в пятой нормальной форме и может быть нормализован путем разложения на свои проекции. Файл СТОРОЖА_ЗООПАРКОВ, например, можно нормализовать, заменив его проекциями

proj ЖИВОТНОЕ, СТОРОЖ (СТОРОЖА_ЗООПАРКОВ) и

proj СТОРОЖ, ЗООПАРК (СТОРОЖА_ЗООПАРКОВ).

3.8. УПРАЖНЕНИЯ

Анализируя файлы, заданные в каждом из упражнений 1-5, необходимо решить следующие задачи:

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

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

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

1. Дано содержимое файла, имеющего поля со следующими именами:

ПОМЕСТЬЕ ГЕЙБЛЗ ГЕЙБЛЗ КОЗИКОТ КОЗИКОТ

САДОВЫЕ_ЦВЕТЫ НАРЦИССЫ РОЗЫ КОЛОКОЛЬЧИКИ РОЗЫ

СЕЗОН_ЦВЕТЕНИЯ ВЕСНА ЛЕТО ВЕСНА ЛЕТО

2. Дано содержимое файла, имеющего поля со следующими именами:

ВИД_СПОРТА ПРЫЖКИ в ДЛИНУ БЕГ НА 100 М 100 М С БАРЬЕРАМИ ПРЫЖКИ С ШЕСТОМ

ПОБЕДИТЕЛЬ АРМСТРОНГ МАРШАЛЛ МАРШАЛЛ УИЛЬЯМС

ГОД_РОЖДЕНИЯ_ПОБЕДИТЕЛЯ 1972 1969 1969 1969

3. Дано содержимое файла, имеющего поля со следующими именами:

ФАМИЛИЯ АРМСТРОНГ АРМСТРОНГ ВЕК НАЙТ

НАПИТОК ВИСКИ ХЕРЕС ВИСКИ ХЕРЕС

КОЛИЧЕСТВО_ПОРЦИЙ 3 1 1 2

ЦЕНА_ЗА_ПОРЦИЮ 40 30 40 30

4. Дано содержимое файла, имеющего поля со следующими именами:

ВЛАДЕЛЕЦ_АВТОМОБИЛЯ	ДАТА_РОЖДЕНИЯ	N_РЕГИСТРАЦИИ	ДАТА_РЕГИСТРАЦИИ
АРМСТРОНГ	июнь 1960	АНС134Т	июнь 1979
АРМСТРОНГ	июнь 1960	BCY529	май 1980
ВЕК	май 1959	AHD339H	октябрь 1972
НАЙТ	июль 1961	ОУУ796Р	январь 1976

5. Дано содержимое файла, имеющего поля со следующими

именами:

НОМЕР_ДОРОГИ A3 A3 А4 А4

ПРОТЯЖЕННОСТЬ 352 352 219 219

ГОРОД АРБИ ТИТОН АРБИ ЭСФИЛД

НАСЕЛЕНИЕ 25632 62310 25632 25632

Для простоты можно считать, что в файле нет двух городов

G одинаковыми названиями.

3.9. ЧЕТВЕРТАЯ НОРМАЛЬНАЯ ФОРМА

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

так как в нем не содержится ответа на вопрос, образует ли данная пара проекций полную декомпозицию файла.

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

Сконструируем пример файла, который, будучи в НФБК, не находится в четвертой нормальной форме. Для этого несколько преобразуем структуру музыкального файла ИСПОЛНЕНИЯ так, чтобы в него можно было записывать номера всех сочинений (НОМСОЧ), исполнявшихся на каждом концерте. Кроме того,

заменим поле НОМАНС, в которое будут заноситься номера всех исполнителей, выступавших на каждом концерте. Сразу же можно отметить, что модернизированный файл не отвечает требованиям, предъявляемым к первой нормальной форме, поскольку его поля НОМСОЧ и НОМИСП могут содержать по нескольку значений.

ДАТА	ГОРОД	СТРАНА	НОММУЗ	НОМСОЧ	НОМИСП
	ТИТОН	ТИЛАНДИЯ	М9	С 1, СЗ, С5	Р8, Р9
и т. п.	АРБИ	ЭКСЛАНДИЯ	М1	СЗ, С4, С6	Р1, Р4, Р7

Можно получить эквивалентную нормальную форму (по крайней мере, первую), соединив два файла, которые назовем НАБОР_СОЧ НАБОР_ИСП. Первый из них должен содержать следующую информацию:

ДАТА	ГОРОД	СТРАНА	НОМСОЧ
	ТИТОН	ТИЛАНДИЯ	С1
	ТИТОН	ТИЛАНДНЯ	СЗ
	ТИТОН	ТИЛАНДИЯ	С5
	АРБИ	ЗКСЛАНДИЯ	СЗ
	АРБИ	ЭКСЛАНДИЯ	С4
	АРБИ	ЭКСЛАНДИЯ	С6

В этом файле (он имеет первую нормальную форму) указаны номера всех произведений, исполненных на каждом концерте. Файл НАБОР_ИСП, также представленный в первой нормальной форме, позволяет выяснить, что за исполнители участвовали в каждом концерте. Его содержимое таково:

ДАТА ГОРОД СТРАНА НОММУЗ НОМИСП

ТИТОН ТИЛАНДИЯ М9 Р8

ТИТОН ТИЛАНДИЯ М9 Р9

АРБИ ЭКСЛАНДИЧ М Р1

АРБИ ЭКСЛАНДИЯ М1 Р4

АРБИ ЭКСЛАНДИЯ MI Р7

и т. д.

Соединению файлов НАБОР_СОЧ и НАБОР_ИСП присвоим имя НОВИСПОЛНЕНИЯ. Операция соединения осуществляется по трем полям - ДАТА, ГОРОД и СТРАНА. Ключевыми полями файла НОВИСПОЛНЕНИЯ являются ДАТА, ГОРОД, СТРАНА,

НОМИСП и НОМСОЧ, так что он, очевидно, представлен в НФБК. Однако НОВИСПОЛНЕНИЯ не находится в четвертой нормальной форме, хотя его проекции НАБОР_СОЧ и НАБОР_ИСП образуют полную декомпозицию. Эти проекции имеют общие

поля ДАТА, ГОРОД и СЫГРАНА, которые составляют лишь часть ключа-кандидата, и поэтому любое сочетание значений этих трех полей может присутствовать в файле НОВИСПОЛНЕНИЯ произвольное число раз.

Файл, не представленный в четвертой нормальной форме, не имеет и пятой нормальной формы, ввиду чего может быть нормализован. По отношению к файлу НОВИСПОЛНЕНИЯ, например, это означает, что его следует заменить проекциями НАБОР_СОЧ и НАБОР_ИСП.

Для того чтобы можно было выявить принадлежность конкретного слайда к четвертой нормальной, форме, необходимо иметь способ определения полных декомпозиций. В тех случаях, когда файл, как в примере с НОВИСПОЛНЕНИЯ, либо уже записан, либо наверное может быть записан в виде соединения двух проекций, распознавание полной декомпозиции не составляет труда.

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

ровно двух проекций.

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

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

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

3.10. ОБЪЕКТЫ И АТРИБУТЫ

3.10.1. ФУНКЦИОНАЛЬНАЯ

ЗАВИСИМОСТЬ АТРИБУТОВ ОТ ОБЪЕКТОВ

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

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

НОМЕР_СЧЕТА

ДАТА_ПРЕДЪЯВЛЕНИЯ_СЧЕТА

НОМЕР_НАРЯДА

ШИФР_ТОВАРА

КОЛИЧЕСТВО_ЕДИНИЦ

ПЛАТА_ЗА_ДОСТАВКУ

ОБЩАЯ_СУММА

НОМЕР_КЛИЕНТА

ИМЯ_ПОКУПАТЕЛЯ

АДРЕС_ДЛЯ_РАСЧЕТОВ

ПРЕДЕЛЬНЫЙ_РАЗМЕР_КРЕДИТА

ТОРГОВАЯ_ЗОНА

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

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

предмета. Чаще всего файлы используются как носители информации об объектах и их атрибутах. В таких файлах неключевые поля являются атрибутами объектов, идентифицируемых первичными ключами. Примером могут служить поля файла АДРЕСА_КЛИЕНТОВ, обсуждавшегося в разд. 3.3.2: НАЗВАНИЕ и АДРЕС являются атрибутами клиентов, которые однозначно определяются значениями первичного ключа НОМЕР-КЛИЕНТА.

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

Проиллюстрируем эти положения на примере музыкальных файлов.

Файл АНСАМБЛИ содержит такие атрибуты каждого ансамбля, как его название, страна, где он был организован, его руководитель. Сами ансамбли представляют объекты, идентифицируемые первичным ключом НОМАНС. В файле МУЗЫКАНТЫ имя музыканта, дата его рождения и страна, где он родился,

представляют атрибуты музыканта, однозначно определяемого по первичному ключу НОММУЗ.

Файл ИСПОЛНИТЕЛИ описывает соотношения между двумя объектами, которые идентифицируются полями НОММУЗ и ИНСТРУМЕНТ. Поле ОЦЕНКА - это атрибут соотношения между музыкантом и его инструментом, принимающий значения

от СКВЕРНО до ОТЛИЧНО. Совместно поля НОММУЗ и ИНСТРУМЕНТ образуют ключ-кандидат файла ИСПОЛНИТЕЛИ. Желательно иметь еще один ключ-кандидат для перекрестных ссылок, в связи с чем файл ИСПОЛНИТЕЛИ дополнен полем

НОММУЗ, которое используется как первичный ключ.

Файл УЧАСТНИКИ_АНСАМБЛЕЙ также описывает соотношение между двумя типами объектов - исполнителями и ансамблями. Как можно выяснить из гл. 2, без этого файла трудно обойтись, хотя в нем и не содержится никаких атрибутов указанного соотношения. Их отсутствие означает, что оба поля файла УЧАСТНИКИ. АНСАМБЛЕЙ являются ключевыми.

Инструмент в музыкальных файлах выступает как объект, однако никаких атрибутов этого объекта хранить не предполагалось, в связи с чем специальный файл ИНСТРУМЕНТЫ не заводился.

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

объектами являются счета и клиенты.

Очевидно, поле НОМЕР_СЧЕТА может служить первичным ключом и использоваться для идентификации счетов. Поля ДАТА_ПРЕДЪЯВЛЕНИЯ_СЧЕТА, ПЛАТА_ЗА_ДОСТАВКУ, НОМЕР_КЛИЕНТА и ОБЩАЯ_СУММА следует рассматривать

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

ЗАГОЛОВКИ_СЧЕТОВ HOMEР_СЧЕТА ДАТА_ПРЕДЪЯВЛЕНИЯ_СЧЕТА HOMEР_КЛИЕНТА ПЛАТА_ЗА_ПОСТАВКУ ОБЩАЯ_СУММА

{Имя файла) {Первичный ключ файла} {Суммарная плата за доставку всехтоваров} {Общая сумма выплат по счету}

Второй тип объектов представляют клиенты, идентифицируемые первичным ключом НОМЕР_КЛИЕНТА. Данным объектам в списке соответствуют атрибуты ИМЯ_ПОКУПАТЕЛЯ, АДРЕС_ДЛЯ_РАСЧЕТОВ, ПРЕДЕЛЬНЫЙ_РАЗМЕР_КРЕДИТА и ТОРГОВАЯ_ЗОНА. Учитывая это, логично предложить следующую структуру для второго файла:

КЛИЕНТЫ {Имя файла)

НОМЕР_КЛИЕНТА

ИМЯ_ПОКУПАТЕЛЯ

АДРЕС_ДЛЯ_РАСЧЕТОВ

ПРЕДЕЛЬНЫЙ_РАЗМЕР_КРЕДИТА

ТОРГОВАЯ_ЗОНА

Можно заметить, что ни в один из файлов не вошло поле КОЛИЧЕСТВО_ЕДИНИЦ, которое должно играть роль атрибута. Не исключено, что любой из товаров фигурирует в нескольких счетах, причем всякий раз КОЛИЧЕСТВО_ЕДИНИЦ может

принимать различные значения. Следовательно, это поле функционально не зависит от поля ШИФР. ТОВАРА и вообще оно не может рассматриваться как атрибут какого-либо из объектов. Однако оно все же является атрибутом, но не объекта, а соотношения между двумя объектами - счетом и товаром. Еще одним атрибутом того же соотношения служит НОМЕР_НАРЯДА. Это поле идентифицирует наряд на продажу, в котором записан данный товар, вследствие чего последний и был включен в счет.

Принимая во внимание эти атрибуты, необходимо сформировать еще один файл следующей структуры:

СОДЕРЖАНИЕ_СЧЕТОВ {Имя файла}