ТОРА (9) - Семинар №4 - Синтез хорошей БД: различия между версиями
ILobster (обсуждение | вклад) |
ILobster (обсуждение | вклад) (ДЗ к пятому семинару, спасибо одному бойцу) |
||
Строка 94: | Строка 94: | ||
== ДЗ 1 == | == ДЗ 1 == | ||
<u>Задание:</u> | |||
Проверить, находятся ли получившиеся {{Формула|f=R_1}} и {{Формула|f=R_2}} в НФБК? | Проверить, находятся ли получившиеся {{Формула|f=R_1}} и {{Формула|f=R_2}} в НФБК? | ||
<u>Решение:</u> | |||
{{Формула|f=\rho = (BD, ABC) = (R_1, R_2)}} | |||
{{Формула|f=F = (B\rightarrow D, BC\rightarrow A)}} | |||
Отношение находится в НФБК, если для каждой нетривиальной и неприводимой ФЗ {{Формула|f=X\rightarrow Y}} {{Формула|f=X}} - ключ. | |||
1. Выбираем ключи: | |||
:{{Формула|f=R_1}}: | |||
::1) | |||
:::{{Формула|f=i = 0}}, {{Формула|f=X_0 = BD}} | |||
:::{{Формула|f=(X_0 - D)^+ = B^+ = BD = R}}, {{Формула|f=i = 1}}, {{Формула|f=X_1 = B}} | |||
:::{{Формула|f=(X_0 - D)^+ = D^+ = D\neq R}} | |||
:::{{Формула|f=i}} возросло. | |||
::2) | |||
:::{{Формула|f=i = 1}}, {{Формула|f=X_1 = B}} | |||
:::{{Формула|f=(X_1 - B)^+ = \varnothing^+ = \varnothing}} | |||
:::{{Формула|f=i}} не возросло, значит {{Формула|f=B}} - ключ. | |||
:{{Формула|f=R_2}}: | |||
::1) | |||
:::{{Формула|f=i = 0}}, {{Формула|f=X_0 = ABC}} | |||
:::{{Формула|f=(X_0 - A)^+ = (BC)^+ = ABC = R}}, {{Формула|f=i = 1}}, {{Формула|f=X_1 = BC}} | |||
:::{{Формула|f=(X_0 - B)^+ = (AC)^+ = AC\neq R}} | |||
:::{{Формула|f=(X_0 - C)^+ = (AB)^+ = AB\neq R}} | |||
:::{{Формула|f=i}} возросло. | |||
::2) | |||
:::{{Формула|f=i = 1}}, {{Формула|f=X_1 = BC}} | |||
:::{{Формула|f=(X_1 - B)^+ = C^+ = C\neq R}} | |||
:::{{Формула|f=(X_1 - C)^+ = B^+ = B\neq R}} | |||
:::{{Формула|f=i}} не возросло,значит {{Формула|f=BC}} - ключ. | |||
2. Проверяем: | |||
:{{Формула|f=R_1}}: | |||
::{{Формула|f=B\rightarrow D}} - нетривиальная; | |||
::{{Формула|f=\varnothing\subset B}}, значит {{Формула|f=B\rightarrow D}} - неприводимая; | |||
::{{Формула|f=B}} - ключ, значит {{Формула|f=R_1}} находится в НФБК. | |||
:{{Формула|f=R_2}}: | |||
::{{Формула|f=BC\rightarrow A}} - нетривиальная; | |||
::{{Формула|f=B\subset BC}}, но {{Формула|f=B\nrightarrow A}}; | |||
::{{Формула|f=C\subset BC}}, но {{Формула|f=C\nrightarrow A}}; | |||
:: выходит, {{Формула|f=BC\rightarrow A}} ещё и неприводимая; | |||
::{{Формула|f=BC}} - ключ, значит {{Формула|f=R_2}} тоже находится в НФБК. | |||
== ДЗ 2 == | == ДЗ 2 == | ||
Строка 103: | Строка 152: | ||
=== Первая задача === | === Первая задача === | ||
<u>Задание:</u> | |||
Задана та же предметная область (про пилотов), но ФЗ другие: | Задана та же предметная область (про пилотов), но ФЗ другие: | ||
Строка 111: | Строка 162: | ||
=== Вторая задача === | === Вторая задача === | ||
<u>Задание:</u> | |||
Предметная область: курсы иностранных языков. | Предметная область: курсы иностранных языков. |
Версия от 15:15, 5 ноября 2012
Синтез хорошей схемы БД
Из семинара 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НФ.
ДЗ 1
Задание:
Проверить, находятся ли получившиеся $$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 - D)^+ = D^+ = D\neq R$$
- $$i$$ возросло.
- 2)
- $$i = 1$$, $$X_1 = B$$
- $$(X_1 - B)^+ = \varnothing^+ = \varnothing$$
- $$i$$ не возросло, значит $$B$$ - ключ.
- 1)
- $$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$$ возросло.
- 1)
- 2)
- $$i = 1$$, $$X_1 = BC$$
- $$(X_1 - B)^+ = C^+ = C\neq R$$
- $$(X_1 - C)^+ = B^+ = B\neq R$$
- $$i$$ не возросло,значит $$BC$$ - ключ.
- 2)
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$$ тоже находится в НФБК.
ДЗ 2
Сделать к послеследующему (шестому) семинару.
Первая задача
Задание:
Задана та же предметная область (про пилотов), но ФЗ другие:
$$F = (B\rightarrow D, D\rightarrow B, AB\rightarrow D, AD\rightarrow B, BC\rightarrow A, BC\rightarrow D, CD\rightarrow A, CD\rightarrow B, ABC\rightarrow D, ACD\rightarrow B, BCD\rightarrow A)$$
Синтезировать БД с помощью алгоритма.
Вторая задача
Задание:
Предметная область: курсы иностранных языков.
$$U =$$ (код курса, код филиала, условия обучения, номер группы (состоит из номера филиала и номера группы, номер уровня обучения, ФИО слушателя, число оплаченных слушателем занятий (оплачиваются все занятия курса сразу, стоимость обучения для студентов и школьников, стоимость обучения для взрослых, адрес филиала, заведующий филиалом, телефон филиала, часы работы преподавателя с группой слушателей (количество часов), зарплата преподавателя, ФИО преподавателя))) = $$(A, B, C, D, E, K, L, N, O, P, R, S, T, V, X)$$
ФЗ:
$$F = (A\rightarrow CNO, B\rightarrow PRS, ADE\rightarrow X, K\rightarrow DEL, L\rightarrow T, X\rightarrow VT, ET\rightarrow V, D\rightarrow XBE)$$
Синтезировать схему БД по алгоритму. Со следующими свойствами:
- соединение без потерь;
- каждая схема в 3НФ;
- каждую проверить ещё и на НФБК;
- наименьшее число схем отношений;
- сохранение ФЗ (если не обладает, то новых схемы отношений добавлять не надо).