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

Рис. 5.2

Приложение 6

Синтез В – схемы

По теореме 5 из раздела 1 для любого множества ФЗ F, заданного на конечном множестве атрибутов R , всегда существует В-схема, то есть декомпозиция ρ = {R_i,  i = 1,..., m}, обладающая свойствами:

1)    соединения   без   потерь   информации   относительно    F (F |= *[ρ]);

2)    сохранения всех ФЗ из F  ;

3)    ЗНФ относительно F .

Эта декомпозиция может быть построена с помощью алгоритма SYNTES (рис. 6.1).

Примечание к шагу 7 алгоритма SYNTES .

Для нахождения ключа алгоритмы редуцирования применяются ко множеству F' {R→ N},

где R→ N есть фиктивная ФЗ и . После редуцирования ФЗ R→ N преобразуется к виду

K→ N, где К -ключ множества R относительно F'.

Алгоритм SYNTES имеет конечное число шагов, все они выполняются с полиномиальной сложностью.

Алгоритм  SYNTES (R, F)

Вход: R - множество атрибутов,

          F - множество ФЗ над R .

Выход: ρ = {R_i, i = 1,..., m} - искомая В-схема.

Описание алгоритма

1.  Редуцирование F с использованием алгоритмов, представленных в прил.4. Этот шаг гарантирует ЗНФ для ρ. Пусть F' = {X_i→Y_i | X_i, Y_i } - результат редуцирования.

2.  Проверка условия: существует ли ФЗ   такая, что ? 

3.  Если да, то процесс построения искомой В - схемы завершён и она имеет вид ρ = {R} , то есть множество R не подлежит разложению на две и более схемы.

4.  Если нет, то выполняется синтаксическое разложение R по ФЗ из F' следующим образом:

ρ' = {,..., } , то есть каждой ФЗ  соответствует схема R_i с атрибутами  (i = 1,..., m). Этот шаг гарантирует выполнение выводимости

 и, следовательно, эквивалентности F' ≡ F .

5.  Проверка свойства F' = *[ρ'] методом прогонки табло. Здесь выводимость F' = *[ ρ'] эквивалентна выводимости F' = *[ρ'] поскольку F' ≡ F.

6.  Если метод прогонки табло завершился успешно, то по теореме 8 из раздела 1 имеет место выводимость F' = *[ρ '] и искомая В-­схема определяется так: ρ'= ρ.

7.  Если нет, то выполняется поиск ключа для множества R относительно F' с использованием алгоритмов редуцирования, представленных в прил.4.

8.  Искомая В-схема определяется так: , то есть к ρ' добавляется схема, содержащая все атрибуты найденного ключа К. Это гарантирует выполнение свойства F^’ |= *[ρ] (см. теорему 7 из раздела 1).

Приложение 7.

Исходные данные для практических задач

Вариант 1. РАСПИСАНИЕ ЭКЗАМЕНОВ.

Таблица 7.1

Имя атрибута	Семантика
D1	Код дисциплины
D2	Название дисциплины
P1	Табельный номер преподавателя
P2	Ф. И. О. преподавателя
E1	Дата экзамена
E2	Время экзамена
E3	Место проведения экзамена
G	Номер группы
Функциональная зависимость	Семантика
D1 → D2	Код дисциплины однозначно определяет ее название
P1 → P2	Табельный номер однозначно идентифицирует преподавателя
E1 E2 E3 → D1 P1 G	В указанный день и время в аудитории проводится экзамен только по одной дисциплине, одним преподавателем и в одной студенческой группе
D1 G → P1 P2	В каждой студенческой группе по каждой отдельной дисциплине принимает экзамен только один преподаватель
E1 E2 P1 → E3	Преподаватель одновременно может принимать экзамен только в одной аудитории
D1 P1 G → E1 E2 E3	Дата, время и место экзамена однозначно определяются номером группы, кодом дисциплины и табельным номером преподавателя
E1 E2 P1 → D1	Преподаватель одновременно может принимать экзамен только по одной дисциплине