Каноническая форма ИЛМ ПО

Каноническая форма ИЛМ предназначена для формализованного перехода к логической структуре БД. ИЛМ ПО представлена в канонической форме при выполнении следующих условий.

1. Все ИО описываются отношениями, находящимися, как минимум, в 3НФ.

2. Между ИО отсутствуют отношения типа “Многие-ко-многим”.

3. ИО расположены по уровням иерархии в соответствии с отношениями типа “Один-ко-многим”.

Иерархическое расположение ИО означает, что из двух ИО, например А и В, связанных отношением типа 1:М, на верхнем уровне иерархии будет ИО, находящийся на стороне “один” (А), а на нижнем – со стороны “много” (В). Оно обеспечивает проверку правильности структур данных: позволяет обнаружить циклы или контуры в структуре данных, повышает наглядность структуры ИЛМ ПО.

 

Рис.4.7 б. Преобразование много-многозначного отношения
двух ИО в одно-многозначные

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

Формализованный подход основан на использовании матрицы смежности – квадратной матрицы, количество строк (и столбцов) которой равно количеству ИО. Значения элементов матрицы X_ij = 1 (i – номер строки, j – номер столбца) определяются по формулам:

X_ij = 1, если ИО_i : ИО_j = 1 : М;

X_ij = 0, если ИО_i : ИО_j ¹ 1 : М.

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