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

2012-09-26T10:01:34Z

83.149.9.19: /* Выявление всех ФЗ */

== Задача №1 - Определение ФЗ ==

Отношение "поставка":

* {{Формула|f=SP}} - поставка.
** N - номер поставщика;
** PN - номер детали;
** kol - количество поставляемых деталей.

{| class="wikitable"
! SN || PN || kol
|- align="center"
| S1 || P1 || 100
|- align="center"
| S1 || P2 || 150
|- align="center"
| S2 || P1 || 50
|- align="center"
| S2 || P2 || 100
|- align="center"
| S3 || P2 || 200
|}

Определить, выполняется ли:
* {{Формула|f=SN\rightarrow kol}} - нет
* {{Формула|f=PN\rightarrow kol}} - нет
* {{Формула|f=(SN,PN)\rightarrow kol}} - да (оно первичный ключ)
* {{Формула|f=kol\rightarrow (SN,PN)}} - нет

== Задача №2 - Как выявлять ФЗ ==

Первый способ: на основании знания предметной области.

Второй способ: построением абстрактного экземпляра отношения, позволяющего понять семантику предметной области.

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

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

Предпосылки:
* рейс может выполняться в разные дни, но в одно и то же время;
* два пилота не могут выполнять один и тот же рейс одновременно (самолёт однопилотный);
* у аэродрома всего одна взлётно-посадочная полоса.

Строим экземпляр отношения:

{| class="wikitable"
! A !! B !! C !! D
|- align="center"
| P1 || r1 || d1 || v1
|- align="center"
| P1 || r2 || d1 || v2
|- align="center"
| P1 || r1 || d2 || v1
|- align="center"
| P1 || r2 || d2 || v2
|- align="center"
| P2 || r1 || d3 || v1
|- align="center"
| P2 || r2 || d3 || v2
|- align="center"
| P2 || r3 || d1 || v3
|}

В принципе, если семантика более сложная, то можно ещё много добавить, но нам хватит этого.

=== Выявление всех ФЗ ===

Теперь по этому экземпляру надо выявить все ФЗ.

1) выписать все возможные ФЗ с одним атрибутом в левой части (в правой части всегда будет один атрибут):

{{Формула|f=A\rightarrow B}} - нет

{{Формула|f=A\rightarrow C}} - нет

{{Формула|f=A\rightarrow D}} - нет

{{Формула|f=B\rightarrow A}} - нет

{{Формула|f=B\rightarrow C}} - нет

{{Формула|f=B\rightarrow D}} - да

{{Формула|f=C\rightarrow A}} - нет

{{Формула|f=C\rightarrow B}} - нет

{{Формула|f=C\rightarrow D}} - нет

{{Формула|f=D\rightarrow A}} - нет

{{Формула|f=D\rightarrow B}} - да

{{Формула|f=D\rightarrow C}} - нет

2) выписать все возможные ФЗ с двумя атрибутами в левой части (в правой так же один):

{{Формула|f=AB\rightarrow C}} - нет

{{Формула|f=AB\rightarrow D}} - да

{{Формула|f=AC\rightarrow B}} - нет

{{Формула|f=AC\rightarrow D}} - нет

{{Формула|f=AD\rightarrow B}} - да

{{Формула|f=AD\rightarrow C}} - нет

{{Формула|f=BC\rightarrow A}} - да

{{Формула|f=BC\rightarrow D}} - да

{{Формула|f=BD\rightarrow A}} - нет

{{Формула|f=BD\rightarrow C}} - нет

{{Формула|f=CD\rightarrow A}} - да

{{Формула|f=CD\rightarrow B}} - да

3) выписать все возможные ФЗ с тремя атрибутами в левой части (в правой всё так же один):

{{Формула|f=ABC\rightarrow D}} - да

{{Формула|f=ABD\rightarrow C}} - нет

{{Формула|f=ACD\rightarrow B}} - да

{{Формула|f=BCD\rightarrow A}} - да

Теперь выписываем все ФЗ: {{Формула|f=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)}}

=== Выявление лишних ФЗ ===

Теперь надо выявить лишние ФЗ (которые выводятся из остальных):

* имеет ли место {{Формула|f=B\rightarrow DE\in(F - B\rightarrow D)^+}}?

Строим замыкание левой части (все атрибуты, которые выводятся из {{Формула|f=B}}):

{{Формула|f=B^+ = B}}, так что {{Формула|f=D\notin B^+}}

Значит, {{Формула|f=B\rightarrow DE\notin(F - B\rightarrow D)^+}}

* имеет ли место {{Формула|f=D\rightarrow B\in(F - D\rightarrow B)^+}}?

{{Формула|f=D^+ = D}}, так что {{Формула|f=B\notin D^+}}

* имеет ли место {{Формула|f=AB\rightarrow D\in(F - AB\rightarrow D)^+}}?

{{Формула|f=(AB)^+ = ABD}} и значит {{Формула|f=D\in (AB)^+}}

вычеркиваем: {{Формула|f=F = (B\rightarrow D, D\rightarrow B}} {{Формула|f=AB\rightarrow D}}, {{Формула|f=AD\rightarrow B, BC\rightarrow A, BC\rightarrow D, CD\rightarrow A, CD\rightarrow B, ABC\rightarrow D, ACD\rightarrow B, BCD\rightarrow A)}}

* имеет ли место {{Формула|f=AD\rightarrow B\in(F - AD\rightarrow B)^+}}?

{{Формула|f=(AD)^+ = ADB}} и значит {{Формула|f=B\in (AD)^+}}

вычеркиваем: {{Формула|f=F = (B\rightarrow D, D\rightarrow B}} {{Формула|f=AB\rightarrow D}}, {{Формула|f=AD\rightarrow B}}, {{Формула|f=BC\rightarrow A, BC\rightarrow D, CD\rightarrow A, CD\rightarrow B, ABC\rightarrow D, ACD\rightarrow B, BCD\rightarrow A)}}

* имеет ли место {{Формула|f=BC\rightarrow A\in(F - BC\rightarrow A)^+}}?

{{Формула|f=(BC)^+ = BCDA}} и значит {{Формула|f=A\in (BC)^+}}

вычеркиваем: {{Формула|f=F = (B\rightarrow D, D\rightarrow B}} {{Формула|f=AB\rightarrow D}}, {{Формула|f=AD\rightarrow B}}, {{Формула|f=BC\rightarrow A}}, {{Формула|f=BC\rightarrow D, CD\rightarrow A, CD\rightarrow B, ABC\rightarrow D, ACD\rightarrow B, BCD\rightarrow A)}}

* имеет ли место {{Формула|f=BC\rightarrow D\in(F - BC\rightarrow D)^+}}?

{{Формула|f=(BC)^+ = BCDA}} и значит {{Формула|f=D\in (BC)^+}}

вычеркиваем: {{Формула|f=F = (B\rightarrow D, D\rightarrow B}} {{Формула|f=AB\rightarrow D}}, {{Формула|f=AD\rightarrow B}}, {{Формула|f=BC\rightarrow A}}, {{Формула|f=BC\rightarrow D}}, {{Формула|f=CD\rightarrow A, CD\rightarrow B, ABC\rightarrow D, ACD\rightarrow B, BCD\rightarrow A)}}

* имеет ли место {{Формула|f=CD\rightarrow A\in(F - CD\rightarrow A)^+}}?

{{Формула|f=(CD)^+ = CDBA}} и значит {{Формула|f=D\in (CD)^+}}

вычеркиваем: {{Формула|f=F = (B\rightarrow D, D\rightarrow B}} {{Формула|f=AB\rightarrow D}}, {{Формула|f=AD\rightarrow B}}, {{Формула|f=BC\rightarrow A}}, {{Формула|f=BC\rightarrow D}}, {{Формула|f=CD\rightarrow A}}, {{Формула|f=CD\rightarrow B, ABC\rightarrow D, ACD\rightarrow B, BCD\rightarrow A)}}

* имеет ли место {{Формула|f=CD\rightarrow B\in(F - CD\rightarrow B)^+}}?

{{Формула|f=(CD)^+ = CDBA}} и значит {{Формула|f=B\in (CD)^+}}

вычеркиваем: {{Формула|f=F = (B\rightarrow D, D\rightarrow B}} {{Формула|f=AB\rightarrow D}}, {{Формула|f=AD\rightarrow B}}, {{Формула|f=BC\rightarrow A}}, {{Формула|f=BC\rightarrow D}}, {{Формула|f=CD\rightarrow A}}, {{Формула|f=CD\rightarrow B}}, {{Формула|f=ABC\rightarrow D, ACD\rightarrow B, BCD\rightarrow A)}}

* имеет ли место {{Формула|f=ABC\rightarrow D\in(F - ABC\rightarrow D)^+}}?

{{Формула|f=(ABC)^+ = ABCD}} и значит {{Формула|f=D\in (ABC)^+}}

вычеркиваем: {{Формула|f=F = (B\rightarrow D, D\rightarrow B}} {{Формула|f=AB\rightarrow D}}, {{Формула|f=AD\rightarrow B}}, {{Формула|f=BC\rightarrow A}}, {{Формула|f=BC\rightarrow D}}, {{Формула|f=CD\rightarrow A}}, {{Формула|f=CD\rightarrow B}}, {{Формула|f=ABC\rightarrow D}}, {{Формула|f=ACD\rightarrow B, BCD\rightarrow A)}}

* имеет ли место {{Формула|f=ACD\rightarrow B\in(F - ACD\rightarrow B)^+}}?

{{Формула|f=(ACD)^+ = ABCD}} и значит {{Формула|f=D\in (ABC)^+}}

вычеркиваем: {{Формула|f=F = (B\rightarrow D, D\rightarrow B}} {{Формула|f=AB\rightarrow D}}, {{Формула|f=AD\rightarrow B}}, {{Формула|f=BC\rightarrow A}}, {{Формула|f=BC\rightarrow D}}, {{Формула|f=CD\rightarrow A}}, {{Формула|f=CD\rightarrow B}}, {{Формула|f=ABC\rightarrow D}}, {{Формула|f=ACD\rightarrow B}}, {{Формула|f=BCD\rightarrow A)}}

* имеет ли место {{Формула|f=BCD\rightarrow A\in(F - BCD\rightarrow A)^+}}?

{{Формула|f=(BCD)^+ = BCD}}, так что {{Формула|f=A\notin (BCD)^+}}

Итоговая {{Формула|f=F = (B\rightarrow D, D\rightarrow B, BCD\rightarrow A)}}

=== Сокращение числа атрибутов ===

А нельзя ли теперь сократить атрибуты в левой части третьей ФЗ, которая {{Формула|f=BCD\rightarrow A}}?

Ну например, если {{Формула|f=X\rightarrow Y}}, а {{Формула|f=Z\subset X}} и {{Формула|f=Z\rightarrow Y}}, то {{Формула|f=Z\rightarrow Y}}

Ну и вот у нас:

1)

:{{Формула|f=BC\rightarrow A\in F^+}}?

:{{Формула|f=(BC)^+=BCDA}}

:{{Формула|f=F = (B\rightarrow D, D\rightarrow B, BC\rightarrow A}}

2)

:{{Формула|f=B\rightarrow A\in F^+}}?

:{{Формула|f=B^+=BD}}, значит {{Формула|f=A\notin B^+}}

3)

:{{Формула|f=C\rightarrow A\in F^+}}?

:{{Формула|f=C^+=C}}, значит {{Формула|f=A\notin C^+}}

Так что больше никак сократить нельзя, и итоговая будет {{Формула|f=F = (B\rightarrow D, D\rightarrow B, BC\rightarrow A)}}

=== Построение УНП ===

А теперь надо построить УНП для него:

1)

:{{Формула|f=G = (B\rightarrow D, D\rightarrow B, BC\rightarrow A)}}

2)

:{{Формула|f=B^+ = BD}}, {{Формула|f=B^+ - B = B}}

:{{Формула|f=D^+ = DB}}, {{Формула|f=D^+ - D = B}}

:{{Формула|f=(BC)^+ = BCAD}}, {{Формула|f=(BC)^+ - BC = AD}}

3) УНП получилось {{Формула|f=G = (B\rightarrow D, D\rightarrow B, BC\rightarrow AD)}}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)|С]]
[[Категория:Конспекты лекций и семинаров]]

Кафедра ИУ5 МГТУ им. Н.Э.Баумана, студенческое сообщество - Вклад [ru]

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