Материал: 500_Goncharov_S._A._Informatsionnye_tekhnologii_v_mediaindustrii_Upravlenie_dannymi_

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

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

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

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

– кандидатом. У файла могут быть несколько таких ключей. Рассмотрим пример файла (отношения).

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

№_служащего имя_служащего з/пл №_проекта Дата_окончания

Рисунок 6.9 – Функциональные зависимости файла служащий

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

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

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

41

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

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

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

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

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

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

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

proj Зоопарк, Зона_обитания (Зоопарки_мира) proj Животное, Зона_обитания (Зоопарки_мира) даст следующий набор записей:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

43

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

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

(ИФ) 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 (ИФ) образуют полную декомпозицию исходного файла.

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

44