ТОРА (9) - Семинар №4 - Синтез хорошей БД

Материал из Кафедра ИУ5 МГТУ им. Н.Э.Баумана, студенческое сообщество
Перейти к навигации Перейти к поиску

Синтез хорошей схемы БД

Из семинара 2: предметную область зададим следующую: "график полётов".

График = (пилот, рейс, дата, время), сокращённо: $$\rho=(A,B,C,D)$$

Итоговая $$F = (B\rightarrow D, D\rightarrow B, BC\rightarrow A)$$

Идём по алгоритму:

1)

строим условно-неизбыточное покрытие:
$$УНП = B\rightarrow D, D\rightarrow B, BC\rightarrow AD$$

2)

пропускаем, потому что есть $$BC\rightarrow AD$$

3)

$$B\rightarrow^? AD$$ нет
$$B:+ = BD$$, $$AD\nsubseteq B^+$$
$$C\rightarrow^? AD$$ нет
$$C:+ = C$$, $$AD\nsubseteq C^+$$
УНП остаётся без изменений.

4)

разбиваем на классы:
$$B\rightarrow D$$, $$D\rightarrow B$$, $$K_1 = BD$$
$$BC\rightarrow AD$$, $$K_2 = BCAD$$

5)

построить граф:

6)

7)

8)

пропускаем, потому что нет ФЗ с пустой правой частью.

9)

$$\rho = (BD, ABC) = (R_1, R_2)$$

10)

  • смотрим соединение без потерь:
$$A$$ $$B$$ $$C$$ $$D$$
$$R_1$$ $$b$$ $$a$$ $$b$$ $$a$$
$$R_1$$ $$a$$ $$a$$ $$a$$ $$b$$
$$A$$ $$B$$ $$C$$ $$D$$
$$R_1$$ $$b$$ $$a$$ $$b$$ $$a$$
$$R_1$$ $$a$$ $$a$$ $$a$$ $$a$$
Есть строка сплошь из $$a$$, значит схема обладает соединением без потерь.
  • смотрим сохранение ФЗ:
1-4) $$H = \varnothing$$, $$УНП = (B\rightarrow B\rightarrow D, BC\rightarrow AD, D\rightarrow B)$$
5) $$H$$ не пусто.
6)
$$BC\rightarrow^? D\in(B\rightarrow D, BC\rightarrow A, D\rightarrow B)^+$$
$$(BC)^+ = BCAD$$, $$D\in (BC)^+$$, значит, схема обладает сохранением ФЗ.

Таким образом, $$\rho$$ обладает соединением без потерь, сохранением ФЗ и находится в 3НФ.

ДЗ

Задание:

Проверить, находятся ли получившиеся $$R_1$$ и $$R_2$$ в НФБК?

Решение:

$$\rho = (BD, ABC) = (R_1, R_2)$$

$$F = (B\rightarrow D, BC\rightarrow A)$$

Отношение находится в НФБК, если для каждой нетривиальной и неприводимой ФЗ $$X\rightarrow Y$$ $$X$$ - ключ.

1. Выбираем ключи:

$$R_1$$:
1)
$$i = 0$$, $$X_0 = BD$$
$$(X_0 - D)^+ = B^+ = BD = R$$, $$i = 1$$, $$X_1 = B$$
$$(X_0 - B)^+ = D^+ = D\neq R$$
$$i$$ возросло.
2)
$$i = 1$$, $$X_1 = B$$
$$(X_1 - B)^+ = \varnothing^+ = \varnothing$$
$$i$$ не возросло, значит $$B$$ - ключ.
$$R_2$$:
1)
$$i = 0$$, $$X_0 = ABC$$
$$(X_0 - A)^+ = (BC)^+ = ABC = R$$, $$i = 1$$, $$X_1 = BC$$
$$(X_0 - B)^+ = (AC)^+ = AC\neq R$$
$$(X_0 - C)^+ = (AB)^+ = AB\neq R$$
$$i$$ возросло.
2)
$$i = 1$$, $$X_1 = BC$$
$$(X_1 - B)^+ = C^+ = C\neq R$$
$$(X_1 - C)^+ = B^+ = B\neq R$$
$$i$$ не возросло,значит $$BC$$ - ключ.

2. Проверяем:

$$R_1$$:
$$B\rightarrow D$$ - нетривиальная;
$$\varnothing\subset B$$, значит $$B\rightarrow D$$ - неприводимая;
$$B$$ - ключ, значит $$R_1$$ находится в НФБК.
$$R_2$$:
$$BC\rightarrow A$$ - нетривиальная;
$$B\subset BC$$, но $$B\nrightarrow A$$;
$$C\subset BC$$, но $$C\nrightarrow A$$;
выходит, $$BC\rightarrow A$$ ещё и неприводимая;
$$BC$$ - ключ, значит $$R_2$$ тоже находится в НФБК.