13. Нормализация реляционных отношений. Нормальная форма Бойса-Кодда.

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

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

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

С этими требованиями трудно не согласиться, выглядят они вполне разумно. Но еще труднее следовать им на практике, если они сформулированы столь туманно и неопределенно.

Всего в реляционной теории насчитывается 6 НФ:

1-я НФ (обычно обозначается также 1НФ).

2НФ.

3НФ.

НФ Бойса-Кодда (НФБК).

4НФ.

5НФ.

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

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

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

Эта нормальная форма вводит дополнительное ограничение по сравнению с 3НФ.

Определение нормальной формы Бойса-Кодда:

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

Ситуация, когда отношение будет находится в 3NF, но не в BCNF, возникает при условии, что отношение имеет два (или более) возможных ключа, которые являются составными и имеют общий атрибут. Заметим, что на практике такая ситуация встречается достаточно редко, для всех прочих отношений 3NF и BCNF эквивалентны.

14. Древовидная иерархическая структура базы данных. Рекурсивное дерево.

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

1) имеется единственная особая вершина, называемая корнем, в которую не заходит ни одно ребро;

2) во все остальные вершины заходит только одно ребро, а исходит произвольное (0, 1, 2, ..., n) количество ребер;

3) не имеется циклов.

В программировании используется другое определение дерева, позволяющее при решении задач рассматривать дерево как структуру, состоящую из меньших деревьев (или поддеревьев), т.е. как рекурсивную структуру.

Рекурсивно дерево определяется как конечное множество T, состоящее из одного или более узлов (вершин), таких, что:

1) существует один специально выделенный узел, называемый корнем дерева;

2) остальные узлы разбиты на m ? 0 непересекающихся подмножеств Т1 , Т2 , ..., Тm , каждое из которых в свою очередь является деревом.

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

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

Вершины дерева определения БД соответствуют введенным типам групп записей, с помощью которых выполнена интерпретация типов сущностей. Обычно допускают только простые типы групп, т.е. группа, представляющая вершину дерева определения, не должна включать составные и повторяющиеся группы, но их можно представить как самостоятельные вершины дерева определения. Корневой вершине дерева определения соответствует тип корневой группы, остальным вершинам - типы зависимых групп. Дуга дерева определения, соответствующая групповому отношению, представляет некоторый тип связи между рассматриваемыми типами сущностей (которые представлены соответствующими типами групп). Дуга исходит из типа родительской (исходной) группы и заходит в тип порожденной группы. Дуги обычно называют связью исходный - порожденный. Поскольку между двумя типами групп может быть не более одной такой связи, то на графической диаграмме схемы иерархической базы данных связи могут специально не помечаться. Тип зависимой группы можно идентифицировать соответствующей последовательностью связей исходный - порожденный. Иерархический путь в дереве определения представляется последовательностью групп, начинающейся типом корневой группы и заканчивающейся типом заданной группы.

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

----------