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

3. ПРАКТИКУМ НА ЭВМ

...Если хотите научиться плавать —

нужно войти в воду, а если желаете

научиться решать задачи - решайте их.

Дж. Пойа

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

Таких задач в практикуме десять. Это соответствует десяти вариантам для каждого из заданий. Исходные данные для вариантов заданий приведены в табл. 7.1 - 7.10 прил. 7.

Задание 1

Неизбыточные покрытия

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

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

алгоритм SX⁺      - построение замыкания множества атрибутов над заданным множеством ФЗ F;

алгоритм PRF - проверка выводимости F  |=Х ─>Y;

алгоритм NРОК - построение неизбыточного покрытия для заданного множества ФЗ F.

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

Таблица 3.1

Номер примера	Исходные данные: R - множество атрибутов, F - множество ФЗ	Результат: F' - неизбыточное покрытие
1	R = ABC, F = 0	F'=0
2	R = ABC, F = {А →  А, В →  В, С → С, ABC → ВС }	F' = 0
3	R = AB, F= {A → 0, B → 0}	F '= 0
4	R = ABC, F={0 →  A, B → A}	F’ = {0 → A}
5	R = ABC, F = {А → В, В → С, А → С}	F' = {A → B, B → C}
6	R = ABC, F = {А → В, АВ → ВС}	F' = F

2.  Проверить корректность работы программы, реализующей алгоритм NPOK , на контрольных примерах из табл. 3.1.

3.  Найти неизбыточное покрытие исходного множества ФЗ для практической задачи, приведенной в прил.7 (номер таблицы исходных данных соответствует  номеру  варианта  задания).  Результаты обосновать, проверив их вручную с помощью правил вывода.

Содержание отчета

1.  Текст программы.

2.  Результаты выполнения программы на контрольных примерах.

3.  Результат решения практической задачи (неизбыточное покрытие).

Задание 2

Редуцированные покрытия. Нахождение ключа