Теорема Фейджина: Пусть X, Y, Z - непересекающиеся множества атрибутов отношения R(X,Y,Z). Декомпозиция отношения R на проекции R1=R[X,Y] и R2=[X,Z] будет декомпозицией без потерь тогда и только тогда, когда имеется многозначная зависимость X->>Y|Z.
Напомню, что функциональная зависимость - это однозначное соответствие левой и правой части. Например:
- ребенок -> биологические родители
- идентификатор товара -> его название
Многозначная зависимость - это когда левой части (детерминанту) соответствует один из множества вариантов правой части. Например:
- родители -> ребенок (так как детей может быть несколько)
- студент -> зачет
Если многозначная зависимость имеет вид X->>Y|Z, при этом функциональные зависимости X->Y или X->Z не существуют, такая зависимость является нетривиальной многозначной зависимостью.
Вернемся к теореме Фейджина.
Допустим, вы с друзьями любите пиво. По пятницам вы посещаете пабы, где дегустируете все доступные сорта пива.
| man | pub | beer |
| Darth | Golden Gate Pub | Guinness |
| Darth | Golden Gate Pub | Murphy's Irish Stout |
| Darth | O'Connor's | Murphy's Irish Stout |
| Darth | O'Connor's | Newcastle |
| Yoda | Golden Gate Pub | Guinness |
| Yoda | Golden Gate Pub | Murphy's Irish Stout |
| Jabba the Hutt | O'Connor's | Murphy's Irish Stout |
| Jabba the Hutt | O'Connor's | Newcastle |
Ваше времяпровождение определяется многозначной зависимостью good_life(pub->>man|beer).
А это значит, что можно выполнить следующую декомпозицию:
| pub | beer |
| Golden Gate Pub | Guinness |
| Golden Gate Pub | Murphy's Irish Stout |
| O'Connor's | Murphy's Irish Stout |
| O'Connor's | Newcastle |
| pub | man |
| Golden Gate Pub | Darth |
| Golden Gate Pub | Yoda |
| O'Connor's | Darth |
| O'Connor's | Jabba the Hutt |
И из неё при желании можно восстановить исходное отношение:
pub_beer(pub->>beer) NATURAL JOIN pub_men(pub->>man) = good_life(pub->>man,beer)
Хотелось бы отдельно обратить внимание на то, что ни в оригинальном, ни в производных отношениях нет функциональных зависимостей, да и вообще все атрибуты являются ключевыми.
В 4 нормальной форме отношение находится тогда, когда оно соответствует НФБК и все нетривиальные многозначные зависимости фактически являются функциональными зависимостями от её потенциальных ключей.
А это значит, что отношение good_life(pub->>man,beer) не находится в 4 НФ.
И теперь небольшой трюк. Возьмем отношение paid_goof_life(pub,man,beer->payment):
| man | pub | beer | payment |
| Darth | Golden Gate Pub | Guinness | 10$ |
| Darth | Golden Gate Pub | Murphy's Irish Stout | 20$ |
| Darth | O'Connor's | Murphy's Irish Stout | 30$ |
| Darth | O'Connor's | Newcastle | 15$ |
| Yoda | Golden Gate Pub | Guinness | 10$ |
| Yoda | Golden Gate Pub | Murphy's Irish Stout | 20$ |
| Jabba the Hutt | O'Connor's | Murphy's Irish Stout | 30$ |
| Jabba the Hutt | O'Connor's | Newcastle | 15$ |
Трюк этот называется внедренной зависимостью. После добавления атрибута payment отношение стало соответствовать 4 НФ.
Комментариев нет:
Отправить комментарий