ТОРА (9) - Семинар №2 - Функциональные зависимости: различия между версиями
ILobster (обсуждение | вклад) (Новая страница: «== Задача №1 - Определение ФЗ == Отношение "поставка": * {{Формула|f=SP}} - поставка. ** N - номер п...») |
ILobster (обсуждение | вклад) |
||
Строка 234: | Строка 234: | ||
Так что больше никак сократить нельзя, и итоговая будет {{Формула|f=F = (B\rightarrow D, D\rightarrow B, BC\rightarrow A}} | Так что больше никак сократить нельзя, и итоговая будет {{Формула|f=F = (B\rightarrow D, D\rightarrow B, BC\rightarrow A)}} | ||
=== Построение УНП === | === Построение УНП === |
Версия от 21:02, 25 сентября 2012
Задача №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 DE\in(F - B\rightarrow D)^+$$?
Строим замыкание левой части (все атрибуты, которые выводятся из $$B$$):
$$B^+ = B$$, так что $$D\notin B^+$$
Значит, $$B\rightarrow DE\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$$, то $$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 = B$$
- $$D^+ = DB$$, $$D^+ - D = B$$
- $$(BC)^+ = BCAD$$, $$(BC)^+ - BC = AD$$
3) УНП получилось $$G = (B\rightarrow D, D\rightarrow B, BC\rightarrow AD$$