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

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

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

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

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

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

 

ДЕЖУРСТВО

ДОЛЖНОСТЬ

ФАМИЛИЯ

ТЕЛЕФОН

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

206

однофамильцах, имеющих одинаковую должность). Понятно, что один и тот же номер рабочего телефона могут иметь несколько сотрудников, т.е. по значению поля «ТЕЛЕФОН» нельзя одно­значно определить должность и фамилию сотрудника.

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

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

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

 

ДОЛЖНОСТЬ

ФАМИЛИЯ

НОМЕР КА­БИНЕТА

МАРКА СЛУЖЕБНО-ГО_ АВТОМОБИЛЯ

Поле «НОМЕРКАБИНЕТА» находится в полной функцио­нальной зависимости от совокупности полей «ДОЛЖНОСТЬ» и «ФАМИЛИЯ», которые образуют ключ, а поле «МАРКА_СЛУ-ЖЕБНОГО АВТОМОБИЛЯ» не находится в полной функцио­нальной зависимости от совокупности этих же полей, поскольку это поле функционально зависит от поля «ДОЛЖНОСТЬ».

15.2. Теорема Хита

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

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

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

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

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

207

2. Возьмем произвольную запись вспомогательного файла: (А', У, к'). Согласно определению файла ИФ1 можно записать:

proj [ И, J] (ИФ1) = proj [Н, /] (ИФ).

Следовательно, в файле ИФ должна находиться хотя бы одна запись типа (А', /, к"), где к" пока не определено. По аналогии можно записать:

" proj [J, К] (ИФ1) = proj [/, K\ (ИФ).

Следовательно, в файле ИФ должна находиться хотя бы одна запись типа (h",j', k'), где h" пока не определено.

Таким образом, в ИФ должны содержаться записи (/г', j', к") ^и ik", j', к'). Однако поскольку К функционально зависит от /, можно заключить, что к" = к' и, следовательно, в ИФ имеется запись (А', У, к'), которую определяют как произвольную запись ИФ1. Доказательство закончено.

Еще раз рассмотрим ИФ с полями:

 

ДЕЖУРСТВО

ДОЛЖНОСТЬ

ФАМИЛИЯ

ТЕЛЕФОН

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

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

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

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

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

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

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

При проведении нормализации на каждом шаге проверяется принадлежность файла некоторой нормальной форме. Если он

208

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

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

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

 

ДОЛЖНОСТЬ	ФАМИЛИЯ
Заведующий кафедрой	Иванов, Петров
Профессор	Сидоров
Доцент	Фомин
Преподаватель	Семин, Савин, Федоров

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

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

Пример. Пусть ИФ имеет следующую организацию:

 

ДОЛЖНОСТЬ

ФАМИЛИЯ

НОМЕР КА­БИНЕТА

МАРКА СЛУЖЕБНО-ГО__ АВТОМОБИЛЯ

Первичным ключом файла является совокупность полей «ДОЛЖ­НОСТЬ» и «ФАМИЛИЯ». Поле «МАРКА_СЛУЖЕБНОГО__АВТОМОБИ-ЛЯ» не находится в полной функциональной зависимости от первично­го ключа (оно функционально зависит от поля «ДОЛЖНОСТЬ»). Обо­значим: #= [ФАМИЛИЯ, НОМЕР_КАБИНЕТА], /= [ДОЛЖНОСТЬ], К= [МАРКА_СЛУЖЕБНОГО_АВТОМОБИЛЯ]. Тогда ИФ следует пред­ставить в виде полной декомпозиции:

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

ПФ2 = proj [ДОЛЖНОСТЬ, МАРКА_СЛУЖЕБНОГО__АВТОМОБИЛЯ]

(ИФ).

209

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

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

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

Пример. Пусть ИФ имеет следующие поля: «СТУДЕНТ» — фамилия студента; «УЧЕРУППА» — номер учебной группы, в котором учится студент; «УЧЛИСЦИПЛИНА» — номер учебной дисциплины, кото­рую студент изучает:

 

УЧ_ГРУППА

СТУДЕНТ

УЧЛИСЦИПЛИНА

Ключом этого ИФ является совокупность всех трех полей. Если пред­положить, что в БД отсутствуют данные о нескольких учебных группах, обучающихся по одному и тому же учебному плану (т. е. изучающие одни и те же учебные дисциплины), можно заметить, что поле из состава первичного ключа «УЧЕРУППА» находится в функциональной зависи­мости от поля «УЧ^ДИСЦИПЛИНА» и, следовательно, файл не нахо­дится в НФ Бойса — Кодда, поэтому его можно представить в виде пол­ной декомпозиции по проекциям:

ПФ1 = proj [УЧ_ГРУППА, СТУДЕНТ] (ИФ); ПФ1 = proj [УЧ^ЕРУППА, УЧЛИСЦИПЛИНА] (ИФ).

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

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

Отметим, что существующие СУБД (например, широко рас­пространенная Access из пакета MS Office) содержат средства для

210

Рис. 15.1. Соотношение нормальных форм файла

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

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

ГЛАВА 16. АДРЕСАЦИЯ ДАННЫХ В ПАМЯТИ ЭВМ

ПО МЕСТУ

16.1. Адресная функция

Чтобы правильно использовать ЭВМ, необходимо не только хорошо представлять себе структурные отношения между дан­ными, но и знать способы представления таких структур в памя­ти машины и методы работы с ними. Основное различие форм представления структур данных в памяти ЭВМ определяется в первую очередь тем, как адресуются их элементы в памяти ма­шины. Различают два способа адресации: по месту и по содержи­мому.

При адресации по месту указываются логические или физиче­ские адреса данных, определяющие места расположения данных в памяти машины.

При адресации по содержимому размещение данных и их вы­борка осуществляются по известному значению ключа, т.е. опре­деляются содержимым самих данных.

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

1) последовательное распределение памяти;

2) связанное распределение памяти.

Наиболее простой формой хранения данных в памяти ЭВМ является одномерный линейный список.

Линейный список — это множество объектов (узлов) (Х(1), Х(2), ..., Х(п), п > 0), структурные свойства которых связаны только с ли­нейным (одномерным) относительным расположением узлов. Та­ким образом, линейный список реализует структуру, которую можно определить как линейное упорядочение элементов данных.

⇐ Предыдущая30313233343536373839Следующая ⇒

Поделиться: