Синтез реляционных баз данных

База данных состоит из множества атрибутов и ключей. С точки зрения теоретико-множественного описания реляционной базой данных d называется такая совокупность отношений {R₁, R₂, ...,R_p}, в которой каждое отношение имеет вид R_i= (S_i,K_i), где S_i- множество атрибутов, а K_i - множество атрибутов образующих ключ.

Предположим на входе задано множество F- зависимостей F над R. С их помощью требуется создать базу данных R=( R₁, R₂, ...,R_p). Эта БД должна удовлетворять следующим требованиям:

1.

где К – выделенный ключ Ri}

2. Каждое отношение Ri находится в третьей нормальной форме.

3. Не существует базы данных с меньшим числом отношений, удовлетворяющим пунктам 1 и 2.

4. Соединение всех полученных отношений Ri дает исходное отношение R.

Алгоритм порождающий базу данных из заданных F-зависимостей называется алгоритмом синтеза.

Определение. Если R – база данных и на ней задано множество F-зависимостей G, то в ней существует по крайней мере |E_G| отношений. Это означает, что в R столько же отношений, сколько и классов эквивалентности. Из этого следует следующее.

Пусть F - множество F – зависимостей. Любая база данных должна иметь |E_F’| отношений, где F’ неизбыточное покрытие для F.

Исходя из этого строится способ построения структуры базы данных.

Сначала находится неизбыточное покрытиеF’ для F и в E_F’ вычисляем классы эквивалентности. Для каждого E_F’(X) строим отношение, состоящее из всех атрибутов, появляющихся в E_F’(X). При этом атрибуты левой части каждого класса эквивалентности образуют выделенный ключ.

Реализация этого способа позволяет получить алгоритм SYNTHESIZE

Вход: множество F – зависимостей F над R.

Выход: полная схема баз данных для F.

1. Наити для F редуцированное минимальное покрытие G.

2. Для каждой CF – зависимости (X₁,X₂,…,X_k) Y из G построить отношение R_j= X₁X₂…X_kY с выделенными ключами K={X₁,X₂,…X_k).

3. Вернуться к п. 2.

Пример.

A B₁B₂C₁C₂DEI₁I₂I₃J

B₁B₂C₁ AC₂DEI₁I₂I₃J

B₁B₂C₂ AC₁DEI₁I₂I₃J

E I₁I₂I₃

C₁D J C₂D J

I₁I₂ I₃ I₂I₂ I₁ I₁I₃ I₂

И пусть R= AB₁B₂C₁C₂DEI₁I₂I₃J

Множество минимально, но не редуцировано. Редуцируя F , получим

F’= {A B₁B₂C₁C₂DE E I₁I₂

B₁B₂C₁ A B₁B₂C₂ A

C₁D J C₂D J

I₁I₂ I₃ I₂I₂ I₁ I₁I₃ I₂}

Образуя классы эквивалентности имеем

G={ (AB₁B₂C₁ ,B₁B₂C₂) DE

(E) I₁I₂

(C₁D) J (C₂D) J

(I₁I₂, I₂I₂, I₁I₃)}

Преобразуя каждую CF – в отношения с выделенными ключами, получим

R₁=AB₁B₂C₁C₂DE K₁= {AB₁B₂C₁ ,B₁B₂C₂}

R₂= EI₁I₂ K₂={E}

R₃= C₁DJ K₃={C₁D}

R₄= C₂DJ K₄={C₂D}

R₅= I₁I₂I₃ K₅={ I₁I₂, I₂I₂, I₁I₃}

Окончательная схема БД будет R=( R₁, R₂, R₃, R₄ ,R₅)