ТОРА (9) - Семинар №2 - Функциональные зависимости

Материал из Кафедра ИУ5 МГТУ им. Н.Э.Баумана, студенческое сообщество
Версия от 16:20, 20 января 2013; ILobster (обсуждение | вклад) (→‎Построение УНП: ошибка наоборот)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Задача №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)$$