Функциональная зависимость полей файла

 

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

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

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

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

Рассмотрим уже знакомый пример. Пусть в ИФ имеются поля:

 

 

Поле «ТЕЛЕФОН» находится в функциональной зависимости от полей «ДОЛЖНОСТЬ» и «ФАМИЛИЯ» (считаем, что в данном файле не будет храниться информация о сотрудниках-однофамильцах, имеющих одинаковые должности). Понятно, что один и тот же номер рабочего телефона могут иметь несколько сотрудников, т.е. по значению поля «ТЕЛЕФОН» нельзя однозначно определить должность и фамилию сотрудника.

Пусть X состоит из нескольких полей. Говорят, что Y находится в полной функциональной зависимости от X, если Y функционально зависит от Х ифункционально не зависит от любого подмножества X', не совпадающего с Х (Х' Х) [54].

В условиях предыдущего примера поле «ТЕЛЕФОН» находится в полной функциональной зависимости от совокупности полей «ДОЛЖНОСТЬ» и «ФАМИЛИЯ», поскольку оно не зависит функционально ни от поля «ДОЛЖНОСТЬ», ни от поля «ФАМИЛИЯ» по отдельности.

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

 

Пусть имеются три непересекающиеся совокупности полей исходного файла: H, J, К. Если К функционально зависит от J, то проекции proj [H, J] (ИФ) и proj [J, К] (ИФ) образуют полную декомпозицию ИФ.

Докажем это утверждение. Введем вспомогательный файл

 

 

Покажем, что каждая запись ИФ присутствует в ИФ1, и наоборот.

1. Возьмем произвольную запись исходного файла: (h, j, к). Очевидно, что ее часть (h, j) принадлежит первой проекции, (j, k) — второй проекции ИФ. По определению операции соединения можно утверждать, что запись (h, j, k) должна присутствовать в файле ИФ1.

2. Возьмем произвольную запись вспомогательного файла (h', j', k'). Согласно определению файла ИФ1, можно записать: proj [H, J] (ИФ1) = proj [H, J] (ИФ). Следовательно, в файле ИФ должна находиться хотя бы одна запись типа (h', j', k"), где k" пока не определено. По аналогии можно записать: proj [J, К] (ИФ1) = proj [J, K] (ИФ). Следовательно, в файле ИФ должна находиться хотя бы одна запись типа (h", j', k'), где h" пока не определено.

Таким образом, в ИФ должны содержаться записи (h', j', k") и (h", j', k'). Но поскольку K функционально зависит от J, можно заключить, что k" = k' и, следовательно, в ИФ имеется запись (h', j', k'), которую мы определили как произвольную запись ИФ1. Доказательство закончено.

Вернемся к примеру. Пусть в ИФ имеются поля:

 

 

Так как поле «ТЕЛЕФОН» находится в функциональной зависимости от полей «ДОЛЖНОСТЬ» и «ФАМИЛИЯ», можно заключить, что полную декомпозицию ИФ следует искать в виде проекций:

 

ПФ1 = proj [ДЕЖУРСТВО, ДОЛЖНОСТЬ, ФАМИЛИЯ] (ИФ);

ПФ2 = proj [ДОЛЖНОСТЬ, ФАМИЛИЯ, ТЕЛЕФОН] (ИФ).

 

Для этого примера можно обозначить: Н= [ДЕЖУРСТВО]; J = [ДОЛЖНОСТЬ, ФАМИЛИЯ]; К = [ТЕЛЕФОН].

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

 

Нормальные формы файла

 

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

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

Еще раз подчеркнем основное достоинство механизма нормализации файлов с помощью исследования функциональной зависимости полей файла: возможность проведения этой операции на этапе проектирования БД.

Перечислим основные НФ файлов в соответствии с [54].

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

Например, принципиально существует возможность хранить информацию о профессорско-преподавательском составе кафедры в следующем виде:

 

 

Однако такой файл не находится в 1 НФ (так как поле «ФАМИЛИЯ» не является атомарным).

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

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

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

Можно показать [54], что рассмотренные НФ подчиняются правилу вложенности по возрастанию номеров, т.е. если файл находится в 5 НФ, он находится и в 3 НФ, 2 НФ, 1 НФ, и наоборот (рис. 6.1).

 

 

Помимо описанных выше нормальных форм, используется 4 НФ, основанная на понятии обобщенной функциональной зависимости [46]. На практике, приведя все файлы к нормальной форме Бойса — Кодда, можно с большой долей уверенности утверждать, что они находятся и в 5 НФ, т. е. что нормализация файлов БД завершена.

Отметим, что существующие СУБД (например, широко распространенная СУБД Access из пакета MS Office) содержат средства для автоматического выполнения операций нормализации (подобные мастеру по анализу таблиц), хотя качество этого анализа зачастую требуют последующего вмешательства разработчика БД [16, 59].

Необходимость нормализации файлов БД (кроме решения уже рассмотренных проблем исключения дублирования и потери присоединенных записей) определяется еще по крайней мере двумя обстоятельствами [43]: во-первых, разумным желанием группировать данные по их содержимому, что позволяет упростить многие процедуры в БД — от организации разграничения доступа до повышения оперативности поиска данных; во-вторых, стремлением разработать БД в виде множества унифицированных блоков, что может облегчить модернизацию отдельных частей базы, а также использовать таблицы одной БД в других.

Важным направлением совершенствования СУБД является их интеллектуализация, что подробнее будет рассмотрено в разд. IV.