Введение в банки данных (стр. 12 )

Считаем, что один вид товара поставляет только одна фирма, название фирмы уникально.

Проекции proj Шифр_товара, Название (Поставщик) и proj Название, №_телефона(Поставщик), совместно образуют полную декомпозицию. Многократное повторение телефонных номеров в исходном файле – один из примеров дублирования данных.

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

Устранить дублирование важно по двум причинам. Во-первых, можно добиться существенной экономии памяти. Во-вторых, если какой-то элемент дублируется n раз (например, телефон фирмы Вектор – 3 раза), то при корректировании данных необходимо менять содержимое всех n копий. Очевидно, что n – кратное повторение одной и той же операции – излишняя трата времени. В то время, как в проекции файла эти данные встречаются лишь однажды.

Итак, в некоторых случаях дублирование устраняется за счет перехода от самого файла к его полной декомпозиции. Однако, возможны такие ситуации, когда подобная замена не даст эффекта. Можно показать, что дублирование неизбежно, если проекции, порождающие полную декомпозицию, содержат общий для обеих ключ исходного файла. Итак, можно сделать вывод: если существует такая полная декомпозиция файла, которая образована проекциями, не имеющими общего ключа, то замена исходного файла этой декомпозицией исключает возможность дублирования информации. Сравните, например полную декомпозицию: proj Шифр_товара, №_телефона (Поставщик) и proj Шифр_товара, Название (Постащик) с предложенной ранее.

Решая вопрос о том, что целесообразнее хранить – файл как таковой или его полную декомпозицию, следует принимать в расчет проблему «присоединенных записей». Сначала рассмотрим пример подобной записи, а затем дадим точное определение. Предположим, что в файл Поставщики понадобилось внести телефон новой фирмы Глория 4-47-25, от которой не поступило еще никаких товаров. Так как поле Шифр_товара является ключом, то его нельзя оставлять пустым, иначе эту запись невозможно будет идентифицировать. Поэтому номер телефона в файл поставщики внести не удастся. Однако его можно записать в проекцию proj Название, №_телефона (Поставщики).

Название	№_телефона
Вектор	3-15-22
Гарант	2-17-38
Флора	4-10-73
Глория	4-47-25

Записи, подобные последней, называют присоединенными. Сформулируем общее определение:

Пусть R и S – наборы полей файла ИФ и выполняется условие ИФ = proj R (ИФ) join proj S (ИФ). Запись является присоединенной, если она занесена в проекцию proj S (ИФ), но не входит в состав какой – либо записи proj R (ИФ) join proj S (ИФ), поскольку с ней невозможно образовать конкатенацию ни одной из записей проекции proj R (ИФ).

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

Теперь можно сформулировать теорему Хита, которая устанавливает связь между функциональной зависимостью и полной декомпозицией файла. Рассмотрим файл ИФ, в котором выделим три набора полей: H, J и K таких, что каждое поле ИФ принадлежит лишь какому – то одному из этих трех наборов. Теорема Хита: если K функционально зависит от J, то справедливо тождество ИФ = proj H, J (ИФ) join proj J, K (ИФ).

Это означает, что при наличии функциональной зависимости K от J проекции proj H, J (ИФ) и proj J, K (ИФ) образуют полную декомпозицию исходного файла.

Процесс нормализации состоит в переходе от одной нормальной формы к другой. В основе перехода лежит теорема Хита. Рассмотрим поочередно эти формы.

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

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

Например, файл с рисунка 29 находится во 2НФ, а файл с рисунка 30 не находится во 2НФ, так как поле Зона_обитания функционально зависит от поля Животное, но не находится в полной функциональной зависимости от ключа Зоопарк, Животное.

В ряде случаев 2НФ порождает неудобства, поэтому переходят к третьей нормальной форме (3НФ). На этом шаге ликвидируется транзитивная зависимость. Пусть А, В и С – три набора полей файла R. Если при этом обратное соответствие неоднозначно, то есть А не зависит от В, или В не зависит от С, то С транзитивно зависит от А. Транзитивная зависимость устраняется с помощью применения теоремы Хита. Файл представлен в 3НФ, если он удовлетворяет определению 2НФ и ни одно из его неключевых полей не зависит от любого другого неключевого поля.

Например, файл Поставщики, с наложенным ограничением на название фирм не находится в 3НФ, но находится во 2НФ.

Таким образом, процесс нормализации состоит их трех шагов, которые представлены на рисунке 34.

 

Рис.34.1

٭

٭

٭

Приведение к 2НФ (устранение неполной зависимости).

٭

٭

A A A

преобразуется в

B B D

C C

D

٭

٭

٭

Приведение к 3НФ (устранение неполной зависимости).

преобразуется в

А А В

В В С

С

Рис.34.2

Это три основных, базовых нормальных формы. Существуют еще несколько видов НФ.

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

Зоопарк	Животное	Сторож
Москва	Кенгуру	Иванов
Москва	Верблюд	Кузнецов
Стокгольм	Эму	Шмидт
Стокгольм	Верблюд	Шмидт

Рис. 35

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

Файл представлен в 4НФ, если каждая его полная декомпозиция из двух проекций такова, что обе проекции не содержат общего ключа. Пример файла, который находится в НФБК, но не находится в 4НФ можно сконструировать из двух файлов: Набор_соч (Дата, Город, Страна, №_соч) и Набор_исп (Дата, Город, Страна, №_муз, №_соч). операция соединения выполняется по трем полям: Дата, Город, Страна. Ключевыми полями в новом файле являются Дата, Город, Страна, №_исп, №_соч, так, что он, очевидно, представлен в НФБК. Но он не находится в 4НФ, хотя его проекции образуют полную декомпозицию, они имеют общие поля Дата, Город, Страна, которые составляют часть ключа.

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

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