Некоторые модификации алгоритма

Декомпозиционного метода

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

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

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

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

Пусть r – отношение со схемой R, w, x, y, z – подмножества R.

1-я аксиома вывода. Рефлексивность.

В r всегда имеет место Х ® Х (так как отношение всегда имеет не более одного кортежа).

2-я аксиома вывода. Пополнение.

Если r удовлетворяет Х ® Y, то r удовлетворяет F-зависимости XZ ® Y (Х ® Y влечет за собой XZ ® Y).

Например, дано отношение:

r	(A	B	C	D)
	a₁	b₁	c₁	d₁
	a₂	b₂	c₁	d₁
	a₁	b₁	c₁	d₂
	a₃	b₃	c₂	d₃

Отношение r удовлетворяет F-зависимости А ® В и, следовательно, функциональным зависимостям: АВ ® В, AC ® B, AD ® B, ABC ® B, ABD ® B, ACD ® B, ABCD ® В в силу второй аксиомы.

3-я аксиома вывода. Аддитивность (так же известна под названием – объединение).

Если отношение r удовлетворяет X ® Y и X ® Z, то r удовлетворяет F-зависимости Х ® YZ.

В рассматриваемом примере А ® В и А ® С, по третьей аксиоме А ® ВС.

4-я аксиома вывода. Проективность.

Если отношение r удовлетворяет X ® YZ, то r удовлетворяет X ® Y и X ® Z.

5-я аксиома вывода. Транзитивность.

Х ® Y и Y ® Z влечет за собой X ® Z.

6-я аксиома вывода. Псевдотранзитивность.

Если r удовлетворяет зависимостям X ® Y и YZ ® W, то r удовлетворяет XZ ® W.

Использование аксиом вывода при удалении

Избыточных зависимостей

Использование аксиомы пополнения

Использование аксиомы аддитивности

Если:

то:

Использование аксиомы проективности

Если:

то:

Использование аксиомы транзитивности

Исходный набор F-зависимостей:

исключаем A ® E, так как A ® C и C ® E:

исключаем B ® E, так как B ® C и C ® E:

исключаем A ® С так как A ® B и B ® C:

Получили неизбыточный набор функциональных зависимостей. Теперь, применив метод декомпозиции, можно получить набор НФБК – отношений.

Имеем отношение r (A, B, C, E).

Выделяя в отдельное отношение F-зависимость C ® E, разбиваем отношение r на r1 (C, E) и r2 (A, B, C).

Отношение r1 находится в НФБК, r2 – нет. Выделяя в отдельное отношение зависимость B ® C, разбиваем r2 на отношения r3 (B, C) и r4 (A, B). Полученные отношения находятся в НФБК.

Использование аксиомы псевдотранзитивности

Имеем F-зависимости: Преподаватель ® Курс; Время, Курс ® Аудитория; Преподаватель, Время ® Аудитория. Зависимость Преподаватель, Время ® Аудитория - избыточная псевдотранзитивная зависимость, ее можно удалить.

Использование нескольких аксиом

Исходный набор F-зависимостей:

Имеем: B ® D; B, C ® D. По аксиоме пополнения можно удалить B, C ® D. Получаем:

Зависимость A ® B, C заменяем на A ® B и A ® C (аксиома проективности):

По аксиоме транзитивности удаляем A ® D и A ® C:

В полученном наборе F-зависимостей нет больше избыточных зависимостей – преобразование закончено.

Следует обратить внимание на такой момент: избыточные F-зависимости необходимо удалять по одной, каждый раз заново анализируя получаемый набор функциональных зависимостей.

В рассмотренном примере удаление избыточных F-зависимостей можно было выполнить в ином порядке:

· удалить A ® D (аксиома транзитивности);

· удалить B, C ® D (аксиома пополнения);

· заменить A ® B, C на A ® B и A ® C (аксиома проективности);

· удалить A ® C.

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

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

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

Минимальное покрытие не всегда является уникальным.

Обратимся к БД «Консультант».

Исходный набор F-зависимостей:

По аксиоме транзитивности можно удалить как избыточную зависимость:

а) № студента ® № телефона;

б) № студента ® № комнаты.

В результате будут получены два минимальных покрытия (первое – при выполнении пункта а); второе – при выполнении пункта б), использование которых приведет к построению тех же самых двух БД, проектирование которых уже обсуждалось нами.

⇐ Предыдущая 3 4 5 6 789 10 11 12 Следующая ⇒