Összes következmény FF megtalálása

Motiváció

"Normalizálás", mely során egy relációsémát több sémára bonthatjuk szét

Példa

\(ABCD\) FF-k: \(AB\to C,\;C\to D,\;D\to A\)

• Felbontba \(ABC\)-re:
  • \(AB\to C\)
  • \(C\to A\) is...

Alapötlet

• Induljunk ki a megadott FF-ekből, és keressül meg az össze nem triviális FF-t
  • Nem triviális = A jobboldalt nem tartalmazza a bal
  • \(A\to B\implies B\not\subseteq A\)
• Csak akozzal az FF-kel foglalkozzunk, amelyekbena projektált séma attribútumai szerepelnek
  • Így fogjuk tudni felbontani, külső függések azt jelentik, hogy azon keresztül már fel lett bontva

Exponenciális algoritmus

Legrosszabb esetben ennek kiszámolása exponenciális lehet

1. Minden \(X\)-re állítsuk elő \(X^+\)-t
2. Adjuk hozzá függőségeinkhez \(X\to A\)-t minden \(A\) ra \(X^+-X\)-ből
3. Dobjuk el \(XY\to A\)-t , ha \(X\to A\) is teljesül (triviális)
4. Tartsuk meg azokat, amikben csak a projektált attribútumok vannak

Trükkök

• Üreshalmaznak, illetve annak attribútum-halmazának nem kell kiszámolni a lezártat
• Ha \(X^+\) az összes attribútumot tartalmazza, akkor semelyik \(X\)-et tartalmazó halmazt ki lehet hagyni

FF-k projeklciója - Példa

• \(ABC, A\to B,\;B\to C\). Projektálunk \(AC\)-re
  • \(A^+=ABC\), ebből \(A\to B,\;A\to C\)
    • Az \(AB^+\) és \(AC^+\) lezártakat nem kell kiszámolnunk
  • \(B^+=BC\), ebből \(B\to C\)
  • \(C^+=C\), semmit nem ad
  • \(BC^+=BC\), semmit nem ad

FF-k Geometriai reprezentációja

• Vegyük a reláció összes előfordulásainak halmazát
  • Ahol a megkötések helyesek
• Minden ilyen halmazt pontként reprezentálunk a térben

Geometria - Példa

\(R(A,B)\)

• Minden \(X\to A\) FF megadható azon előfordulások részhalmazaként, mely teljesítik azt
• Egy FF így a tér egy régiója
  • Benne azon előfordulások jelennek meg, amikre igaz a függőség
  • Több FF metszete is megadható ily módon
• Minden triviális FF kiképezi az egész teret, azokat kihagyjuk
  • \(A\to A\) minden esetben telejsül

Példa metszetre

Ebből következik, hogy ha nem teljesül valahol mind a kettő FF, akkor a mezszeten kívűl kell esnie