Принципы нормализации

Тема: Принципы нормализации.

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

Необходимы еще шаги нормализации.

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

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

Задавая отношение над элементами данных разработчик должен интересоваться тем, какие из атрибутов объекта являются зависимыми.

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

Дадим новое определение ключа. Ключ – кандидат определяется как минимальный набор полей (одного или нескольких), значения которых однозначно идентифицируют запись файла. Минимальность набора понимается в том смысле, что при изъятии из него любого поля он перестает быть ключом – кандидатом. У файла может иметься несколько таких ключей. Рассмотрим пример файла (отношения).

Служащий (№_служащего, имя_служащего, з/пл, №_проекта, дата_окончания). Функциональные зависимости файла можно представить с помощью диаграммы.

№_служащего

имя_служащего

з/пл

№_проекта

Дата_окончания

Рис. 29

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

Итак, файл имеет два поля F1 и F2. F2 не связано функциональной зависимостью с F1, так как значению в поле F1 соответствуют два различных значения поля F2. Можно сказать, что F1 функционально зависит от F2, если наряду с имеющимися записями. На файл наложено ограничение, запрещающее вводить в него такие новые записи, как например:

Атрибут может зависеть не от какого – то одного атрибута, а от целой группы атрибутов.

Если Х состоит из нескольких полей, то говорят, что У находится в полной функциональной зависимости от Х тогда и только тогда, когда:

a. У функционально зависит от Х;

b. У функционально не зависит от любого Х’, где X’ – такое подмножество Х, что по меньшей мере одно из Х не принадлежит Х’.

Приведем простой пример файла, который иллюстрирует данное определение. Файл «Заказы» содержит поля:

№_заказа

Шифр товара      {шифр, присвоенный заказанному товару}

Описание             {описание товара}

Количество                   {заказанное количество единиц товара}

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

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

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

В частности, приведем пример, демонстрирующий, как две проекции файла Зоопарки_мира:

Рис. 30

proj Зоопарк, Животное(Зоопарки_мира)

proj Животное, Зона_обитания (Зоопарки_мира)

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

С другой стороны, соединение проекций

proj Зоопарк, Зона_обитания (Зоопарки_мира)

proj Животное, Зона_обитания (Зоопарки_мира)

даст следующий набор записей:

Рис. 31

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

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

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

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

2. Определение правил выбора одной из двух альтернативных возможностей:

· хранить файл в его непосредственном виде или

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

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

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

Рис.32

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

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

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

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

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

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

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

Пусть 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НФ.

На практике, файл, приведенный к НФБК, как правило, находится в 5НФ, хотя этот факт всегда следует проверять.

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

Деятельность программиста.

№_программиста         

№_программы              

Имя программиста       

Имя программы            

Кол-во рабочих часов   

Рис. 36

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

Поэтому, следует файл представить в виде

№_программиста         

Имя программиста

Сведения о программисте

№_программы               

Имя программы

Сведения о программе

Вам также может быть полезна лекция "Эхокардиографические измерения".

№_программы                  

№_программиста              

Кол-во рабочих часов

Рис. 37

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