Нормальная форма Бойса-Кодда

Нормализация таблиц БД. Первая, вторая и третья нормальные формы

При проектировании структуры БД естественным желанием бывает минимизировать количество таблиц, а в идеальном случае сосредоточить все данные в одной таблице. Однако это оказывается неудобным при поддержке БД, то есть при выполнении трех основных операций с таблицами: обновления информации в записях, включения новых записей и удаления записей. Выяснилось, что структуру таблиц желательно выбирать в соответствии с определенными правилами. Такое проектирование (или перестройку) структуры таблиц стали называть нормализацией. Были определены этапы нормализации, в результате выполнения которых таблицы приводились к некоторым так называемым нормальным формам (НФ).

К 1970 году были введены первая, вторая и третья НФ. В 1974 году были сделаны предложения по улучшению третьей НФ. Так появилась НФ Бойса-Кодда.

В 1976 году были введены четвертая и пятая НФ. Если четвертая НФ имеет некоторое практическое значение, то пятая НФ в основном вызывает лишь теоретический интерес.

Первая НФ требует, чтобы таблица содержала атомарные значения, то есть на пересечении строки и столбца находилось единственное значение, а не список либо вложенная таблица. Атомарность значений соответствует сложившейся технологии обработки таблиц. Дейстительно, имея в поле список значений, необходимо обладать средствами выделения и поиска определенного значения. Таблицы, находящиеся в первой НФ, называются нормализованными. Следует отметить, что некоторые СУБД принципиально ориентированы на работу с ненормализованными таблицами.

Введем понятие функциональной зависимости для атрибутов отношения. Пусть X и Y- множества атрибутов отношения R. Говорят, что Y функционально зависит от X, если при фиксированных значениях атрибутов X однозначно определяются значения атрибутов Y. Такая функциональная зависимость обозначается как F: X → Y или Y=F(X). Понятие функциональной зависимости для отношений аналогично соответствующему понятию в математическом анализе.

Рассмотрим для примера отношениe или таблицу поставок некоторых изделий R (Sn, Scity, Cstatus, Pn, Q). В скобках указаны наименования атрибутов: Sn – шифр поставщика, Scity – город проживания поставщика, Сstatus – статус города, выраженный целым числом в зависимости от его населения и административного значения, Pn – шифр изделия, Q – объем поставки изделия Pn поставщиком Sn. Здесь можно выделить следующие функциональные зависимости:

· Sn → Scity;

· Scity → Cstatus;

· Sn, Pn → Q.

Однако Q не зависит функционально ни от Sn, ни от Pn по отдельности, т.к. поставщик Sn может поставлять разные изделия и в разных количествах, а изделие Pn может поставляться разными поставщиками.

В то же время существует функциональная зависимость Sn, Pn → Cstatus, поскольку для поставщика Sn однозначно находится статус города, где он живет, хотя атрибут Pn в этой зависимости не играет никакой роли.

Полной функциональной зависимостью F: X → Y считают такую функциональную зависимость, в которой Y зависит от всех атрибутов множества X, а не от какой-то их части. Рассмотренная выше функциональная зависимость Sn, Pn → Cstatus является неполной, т.к. существует зависимость Sn → Cstatus.

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

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

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

Наконец, при изменении наименования изделия придется заносить новое название во все записи, связанные с поставкой этого изделия.

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

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

Основным способом приведения отношения ко второй НФ является декомпозиция исходного отношения на два или более новых отношений. Так отношение R можно декомпозировать на отношения S (Sn, Scity, Cstatus) и SP (Sn, Pn, Q). В отношении S возможными ключами являются Sn и Sname, а в отношении SP имеется единственный составной ключ Sn, Pn.

Отношение S по-прежнему не лишено недостатков. При удалении единственного поставщика из некоторого города теряется информация о статусе города, а она может понадобиться в будущем. При изменении же статуса города придется корректировать записи обо всех поставщиках из этого города.

Проблемы возникают вследствие транзитивной функциональной зависимости Scity → Cstatus, то есть последовательности зависимостей Sn → Scity → Cstatus.

Отношение R находится в третьей НФ, если оно находится во второй НФ, и каждый неключевой зависит от любого возможного ключа нетранзитивно. Другими словами, у отношения R не должно быть функциональных зависимостей от неключевых атрибутов.

Действительно, в отношении S имеется единственный ключ Sn, а атрибут Cstatus функционально зависит от неключевого атрибута Scity.

Как и прежде, выходом является декомпозиция отношения S на отношения S1 (Sn, Scity, Cstatus) и S2 (Scity, Cstatus).

Приведем пример нормализации таблицы R (Sch, Adr, Cl, Teach, Subj, Sp_mark, Sp_date), содержащей сведения об успеваемости школьников. Здесь Sch – идентификация школьника, Adr – его адрес, Cl – класс, Teach – классный руководитель, Subj – учебный предмет, Sp_mark – список полученных оценок, Sp_date – даты получения оценок.

Для приведения таблицы R к первой НФ нужно атрибут списка оценок Sp_mark заменить атрибутом отдельной оценки Mark, а атрибут Sp_date атрибутом Date. В этом случае проще отслеживать определенные оценки (например, двойки и пятерки), проводить вычисления (например, считать средние баллы), рассматривать изменения успеваемости во времени и т. п. Вместо одной записи школьника по предмету придется включать столько записей, сколько есть оценок по этому предмету.

Ключом таблицы будет совокупность атрибутов Sch, Subj. Таблица не находится во второй НФ, т.к. атрибуты Adr, Cl, Teach зависят только от Sch, то есть от части ключа. Целесообразно создать новую таблицу с этими атрибутами и ключом Sch.

В этой таблице имеется транзитивная зависимость Sch → Cl → Teach. Для приведения к третьей нормальной форме необходимо создать еще одну таблицу с атрибутами Cl и Teach.

Подведем итоги. Исходная таблица R декомпозирована на таблицы R1 (Sch, Adr, Cl), R2 (Cl, Teach) и R3(Sch, Subj, Mark, Date).

Пусть в определенном выше отношении SP присутствует еще и имя поставщика Sname. Будем для удобства считать, что имя однозначно определяет поставщика. Тогда в отношении SP (Sn, Sname, Pn, Q) единственным неключевым атрибутом является Q. Имеются два возможных ключа

· Sn, Pn;

· Sname, Pn.

При изменении имени поставщика Sname должны корректироваться все записи, связанные с этим поставщиком.

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

Отношение R находится в НФ Бойса-Кодда (НФБК), если каждый детерминант является возможным ключем отношения.

Приведение к НФБК также подразумевает декомпозицию таблицы. В приведенном примере разумно выделить атрибуты Sn и Sname в отдельное отношение S3 (Sn, Sname), оставив в прежнем виде отношение SP (Sn, Pn, Q).

Заметим, что отношение R, находящееся в НФБК, находится также во второй и третьей НФ.

Приведение к НФБК может вызвать помимо достоинств и некоторые аномалии. Рассмотрим отношение R (City, Adr, Ind), содержащее сведения о почтовых адресах. Здесь City – название города, Adr - адрес без указания города, Ind – шестизначный почтовый индекс. Как известно, в городе каждое почтовое отделение имеет свой индекс.

В отношении R нет неключевых атрибутов, поэтому оно находится во второй и третьей НФ. Возможными ключами являются сочетания City, Adr или Adr, Ind. Имеются функциональные зависимости

· City, Adr → Ind;

· Ind → City.

Атрибут Ind является детерминантом для атрибута City, но не является возможным ключом, поэтому отношение R не находится в НФБК. Одним из вариантов декомпозиции является представление информации в двух отношениях R1 (Ind, City) с ключом Ind и R2 (Ind, Adr) с обоими ключевыми атрибутами.

Пусть требуется по заданным значениям атрибутов City и Adr определить Ind. Адресу может соответствовать множество индексов разных городов, поэтому придется для каждого индекса определять город и сравнивать его с тем, который требуется. Таким образом, после декомпозиции потеряна функциональная связь City, Adr → Ind. Другие варианты разложения отношения R приводят к аналогичным проблемам.

Дата добавления: 2014-01-07