Теория экономических информационных систем


Теория экономических информационных систем - стр. 43


 

§ 2.1.5. Ациклические базы данных

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

В отношении R(A, B ,C) существует многозначная зависимость (МЗ)

А -> -> В, если для любого а, являющегося значением атрибута А im(BC)a = im(B)a ° im(C)a, где °  - знак декартова произведения множеств.

Положение атрибутов В и С равноценно, поэтому одновременно справедливо А -> -> С, т.е. многозначные зависимости всегда встречаются парами.

Отношение R(A,B,C) с многозначной зависимостью А -> ->

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

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

Для определения понятия ациклической схемы БД введем граф соединений на множестве отношений {Sl,S2,...,Sk). Вершинами графа соединений являются имена существующих отношений SI, S2,...,Sk. Дуга графа <Si,Sj> существует, если в структуре отношений Si и Sj имеются общие атрибуты. Обозначим их для определенности через A(i,j) и назовем весом дуги. Путь на графе соединений называется А-путем, если атрибут А содержится в структуре каждого отношения, лежащего на пути. В графе соединений требуется, чтобы для каждой пары отношений Si, Sj с общим атрибутом A(ij) существовал A(ij)- путь между Si и Sj.

Если граф можно превратить в дерево с помощью исключения некоторых дуг при сохранении названного требования, то база данных с отношениями {Sl,S2,...,Sk} является ациклической.

Например, база данных, представленная на рис. 7 является циклической.

 

 

 

 

 

 

 

 


Рис. 7. Циклическая база данных

Существует простой алгоритм проверки базы данных на ацикличность. Он состоит из двух шагов:

1 шаг. Если некоторый атрибут встречается только в одном отношении, вычеркнуть данный атрибут из этого отношения.




Начало  Назад  Вперед



Книжный магазин