Изучение основных алгоритмов теории реляционных баз данных, страница 2

Содержание и порядок выполнения работы

1.  Изучить и реализовать в виде программных процедур (функций) следующие алгоритмы:

алгоритмы LRED, LRED1 - построение редуцированного слева покрытия множества ФЗ;

алгоритм PRED - построение редуцированного справа покрытия множества ФЗ.

Описание данных алгоритмов приведено в прил.4.

Таблица 3.2

Номер

примера

Исходные данные:

F - неизбыточное множество ФЗ

Результат:

F" - редуцированное покрытие

1

F = {A → B, AB → BC}

F" = {A → ВС}

2

F = {А → ВС, В → С, АВ → D}

F" =  {А → B, B → C, A → D}

3

F = {АВ → С, ВС → А,  А → В, С → В}

F" = {A → C, C → A, C → В}

4

F = {0 → АВ, А → ВС}

F" = {0 → AB, 0 → C}

5

F = 0

F" = 0

6

F = (А → В, В → С}

F" = F

Таблица 3.3

Номер

примера

Исходные данные:

R - множество атрибутов;

F - неизбыточное множество ФЗ

Результат:

К - множество ключей

1

R  = ABC,

F = 0

К = {АВС}

2

R  = ABC,

F = {A → В)

К = {АС}

3

R  = ABCD,

F = (AB → C, C → AD}

К = {АВ, ВС}

4

R  = ABCD,

F = {A → B, B → A, AC → D}

K = {АС, ВС}

2.  Разработать программу редуцирования множества ФЗ. Считать, что исходное множество ФЗ является неизбыточным. Процесс редуцирования реализовать так:   сначала выполнить редуцирование слева с использованием алгоритма LRED1, а затем справа - с помощью алгоритма   PRED, причем в качестве исходного множества ФЗ взять результат редуцирования слева.

3.  Проверить корректность работы программы на контрольных примерах из табл.3.2.

4.  С помощью программы редуцирования найти один из ключей для заданных в табл.3.3 множества атрибутов R и множества ФЗ F.  Редуцированию  следует   подвергнуть  множество ,  где . После редуцирования ФЗ RN преобразуется к виду KN,