Банк данных (стр. 11 )

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

Москва	Эму	Австралия
Стокгольм	Кенгуру	Австралия

Поэтому соединение этих проекций нельзя получить полную декомпозицию файла Зоопарки_мира.

К основным задачам реляционной теории нормализации относятся:

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

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

Рассмотрим задачу 2.

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

Шифр_товара	Название	№_телефона
АС15	Вектор	3-15-22
ВК79	Флора	4-10-73
ВР28	Гарант	2-17-38
СР12	Вектор	3-15-22
ТА54	Вектор	3-15-22
ТС43	Гарант	2-17-38

Рис.32

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

Проекции 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

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