ТОРА (9) - Семинар №2 - Функциональные зависимости
Содержание
Задача №1 - Определение ФЗ
Отношение "поставка":
- $SP$ - поставка.
- N - номер поставщика;
- PN - номер детали;
- kol - количество поставляемых деталей.
| SN | PN | kol |
|---|---|---|
| S1 | P1 | 100 |
| S1 | P2 | 150 |
| S2 | P1 | 50 |
| S2 | P2 | 100 |
| S3 | P2 | 200 |
Определить, выполняется ли:
- $SN\rightarrow kol$ - нет
- $PN\rightarrow kol$ - нет
- $(SN,PN)\rightarrow kol$ - да (оно первичный ключ)
- $kol\rightarrow (SN,PN)$ - нет
Задача №2 - Как выявлять ФЗ
Первый способ: на основании знания предметной области.
Второй способ: построением абстрактного экземпляра отношения, позволяющего понять семантику предметной области.
Предметную область зададим следующую: "график полётов".
График = (пилот, рейс, дата, время), сокращённо: $\rho=(A,B,C,D)$
Предпосылки:
- рейс может выполняться в разные дни, но в одно и то же время;
- два пилота не могут выполнять один и тот же рейс одновременно (самолёт однопилотный);
- у аэродрома всего одна взлётно-посадочная полоса.
Строим экземпляр отношения:
| A | B | C | D |
|---|---|---|---|
| P1 | r1 | d1 | v1 |
| P1 | r2 | d1 | v2 |
| P1 | r1 | d2 | v1 |
| P1 | r2 | d2 | v2 |
| P2 | r1 | d3 | v1 |
| P2 | r2 | d3 | v2 |
| P2 | r3 | d1 | v3 |
В принципе, если семантика более сложная, то можно ещё много добавить, но нам хватит этого.
Выявление всех ФЗ
Теперь по этому экземпляру надо выявить все ФЗ.
1) выписать все возможные ФЗ с одним атрибутом в левой части (в правой части всегда будет один атрибут):
$A\rightarrow B$ - нет
$A\rightarrow C$ - нет
$A\rightarrow D$ - нет
$B\rightarrow A$ - нет
$B\rightarrow C$ - нет
$B\rightarrow D$ - да
$C\rightarrow A$ - нет
$C\rightarrow B$ - нет
$C\rightarrow D$ - нет
$D\rightarrow A$ - нет
$D\rightarrow B$ - да
$D\rightarrow C$ - нет
2) выписать все возможные ФЗ с двумя атрибутами в левой части (в правой так же один):
$AB\rightarrow C$ - нет
$AB\rightarrow D$ - да
$AC\rightarrow B$ - нет
$AC\rightarrow D$ - нет
$AD\rightarrow B$ - да
$AD\rightarrow C$ - нет
$BC\rightarrow A$ - да
$BC\rightarrow D$ - да
$BD\rightarrow A$ - нет
$BD\rightarrow C$ - нет
$CD\rightarrow A$ - да
$CD\rightarrow B$ - да
3) выписать все возможные ФЗ с тремя атрибутами в левой части (в правой всё так же один):
$ABC\rightarrow D$ - да
$ABD\rightarrow C$ - нет
$ACD\rightarrow B$ - да
$BCD\rightarrow A$ - да
Теперь выписываем все ФЗ: $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)$
Выявление лишних ФЗ
Теперь надо выявить лишние ФЗ (которые выводятся из остальных):
- имеет ли место $B\rightarrow D\in(F - B\rightarrow D)^+$?
Строим замыкание левой части (все атрибуты, которые выводятся из $B$):
$B^+ = B$, так что $D\notin B^+$
Значит, $B\rightarrow D\notin(F - B\rightarrow D)^+$
- имеет ли место $D\rightarrow B\in(F - D\rightarrow B)^+$?
$D^+ = D$, так что $B\notin D^+$
- имеет ли место $AB\rightarrow D\in(F - AB\rightarrow D)^+$?
$(AB)^+ = ABD$ и значит $D\in (AB)^+$
вычеркиваем: $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)$
- имеет ли место $AD\rightarrow B\in(F - AD\rightarrow B)^+$?
$(AD)^+ = ADB$ и значит $B\in (AD)^+$
вычеркиваем: $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)$
- имеет ли место $BC\rightarrow A\in(F - BC\rightarrow A)^+$?
$(BC)^+ = BCDA$ и значит $A\in (BC)^+$
вычеркиваем: $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)$
- имеет ли место $BC\rightarrow D\in(F - BC\rightarrow D)^+$?
$(BC)^+ = BCDA$ и значит $D\in (BC)^+$
вычеркиваем: $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)$
- имеет ли место $CD\rightarrow A\in(F - CD\rightarrow A)^+$?
$(CD)^+ = CDBA$ и значит $D\in (CD)^+$
вычеркиваем: $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)$
- имеет ли место $CD\rightarrow B\in(F - CD\rightarrow B)^+$?
$(CD)^+ = CDBA$ и значит $B\in (CD)^+$
вычеркиваем: $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)$
- имеет ли место $ABC\rightarrow D\in(F - ABC\rightarrow D)^+$?
$(ABC)^+ = ABCD$ и значит $D\in (ABC)^+$
вычеркиваем: $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)$
- имеет ли место $ACD\rightarrow B\in(F - ACD\rightarrow B)^+$?
$(ACD)^+ = ABCD$ и значит $D\in (ABC)^+$
вычеркиваем: $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)$
- имеет ли место $BCD\rightarrow A\in(F - BCD\rightarrow A)^+$?
$(BCD)^+ = BCD$, так что $A\notin (BCD)^+$
Итоговая $F = (B\rightarrow D, D\rightarrow B, BCD\rightarrow A)$
Сокращение числа атрибутов
А нельзя ли теперь сократить атрибуты в левой части третьей ФЗ, которая $BCD\rightarrow A$?
Ну например, если $X\rightarrow Y$, а $Z\subset X$, то $Z\rightarrow Y$
Ну и вот у нас:
1)
- $BC\rightarrow A\in F^+$?
- $(BC)^+=BCDA$
- $F = (B\rightarrow D, D\rightarrow B, BC\rightarrow A)$
2)
- $B\rightarrow A\in F^+$?
- $B^+=BD$, значит $A\notin B^+$
3)
- $C\rightarrow A\in F^+$?
- $C^+=C$, значит $A\notin C^+$
Так что больше никак сократить нельзя, и итоговая будет $F = (B\rightarrow D, D\rightarrow B, BC\rightarrow A)$
Построение УНП
А теперь надо построить УНП для него:
1)
- $G = (B\rightarrow D, D\rightarrow B, BC\rightarrow A)$
2)
- $B^+ = BD$, $B^+ - B = D$
- $D^+ = DB$, $D^+ - D = B$
- $(BC)^+ = BCAD$, $(BC)^+ - BC = AD$
3) УНП получилось $G = (B\rightarrow D, D\rightarrow B, BC\rightarrow AD)$
