Többértékű függőségek, egyed kapcsolat modell

• Többértékű függőségek, egyed kapcsolat modell
  • Többértékű függőségek
    • Többértékű függőség szabályok
    • Negyedik normálforma
      • Triviális TÉFek
      • 4NF definíció
      • BCNF vs 4NF
      • Dekompozíció és 4NF
    • TÉF és FFek együttes következtetése
      • Következtetés
        • FF használata
        • TÉF használata
        • Célok
        • Végjáték
    • TÉFek vetítése
  • Egyed kapcsolat modell
    • Egyedhalmazok
    • Diagrammok
  • Források

Többértékű függőségek

A többértékű függőség: az $R$ reláció fölött $X\to \to Y$ teljesül, ha bármely két sorra, amelyek megegyeznek az $x$ minden attribútumán, az $Y$ attribútumaihoz tartozó értékek felcserélhetők, azaz a keletkező két új sor $R$-beli lesz.

Más szavakkal: $X$ minden értéke esetén az $Y$-hoz tartozó értékek függetlenek az $R-X-Y$ értékeitől.

Többértékű függőség szabályok

• Minden funkcionális függőség egyben többértékű függőség is.

  • Ha $X\to Y$ és két sor megegyezik $X$-en, $Y$-on is megegyezik, emiatt ha ezeket felcseréljük, az eredeti sorokat kapjuk vissza, azaz: $X\to \to Y$

• Komplementálás: Ha $X\to \to Y$ és $Z$ jelöli az összes többi attrubútum halmazát, akkor $X\to \to Z$

• Ugyanúgy, mint az FF-ek esetében, a baloldalakat nem "bánthatjuk" általában.

• Az FF-ek esetében a jobboldalakat felbonthattuk, míg ebben az esetben ez sem tehető meg.

Negyedik normálforma

• A TÉF-ek okozta redundanciát a BCNF nem szünteti meg.
• Megoldás: a negyedik normálforma
• A negyedik normálformánál amikor dekomponálunk, a TÉF-eket úgy kezeljük, mint az FF-eket, a kulcsok megtalálásánál azonban nem számítanak.

Triviális TÉFek

Legyen $R$ egy reláció, $X$ és $Y$ részhalmazai $R$ attribútumainak, jelölés: $X,Y\subseteq R$

• $X\to \to Y$ TÉF automatikusan fennáll, ha $Y\subseteq X$
• $X\to \to Y$ TÉF automatikusan fennáll, ha $X\cup Y=R$

4NF definíció

Egy $R$ reláció 4NF-ben van, ha minden $X\to \to Y$ nemtriviális TÉF esetén $X$ szuperkulcs

• Nemtriviális TÉF:
  1. $Y$ nem részhalmaza $X$-nek
  2. $X$ és $Y$ együtt nem adják ki az összes attribútumot.
• A szuperkulcs definíciója ugyanaz marad, azaz csak az FF-ektől függ.

BCNF vs 4NF

• Kiderült, hogy minden $X\to Y$ FF $X\to \to Y$ TÉF is.
• Így ha $R$ 4NF-ben van, akkor BCNF-ben is.
• De $R$ lehet úgy BCNF-ben, hogy közben nincs 4NF-ben.

Dekompozíció és 4NF

Ha $X\to \to Y$ megsérti a 4NF-t, akkor $R$-t hasonlóan dekomponáljuk, mint a BCNF esetén.

1. $XY$ az egyik dekomponált reláció
2. Az $Y-X$-be nem tartozó attribútumok a másik.

TÉF és FFek együttes következtetése

• Probléma: $R$ relációsémához adott a TÉF-ek és FF-ek egy halmaza, kérdés: egy adott FF vagy TÉF következik-e ezekből $R$ fölött?
• Megoldás: használjunk egy táblázatot (tablót), hogy a függőségek hatásait feltárjuk. (A chase mögötti ötletet terjesztjük ki.)

Miért foglalkozunk ilyesmivel?

1. 4NF azon múlik, hogy van-e olyan TÉF, ami sérti a feltételt.

• Előfordulhat, hogy a megadott FF-ek és TÉF-ek nem sértik a feltételt, de egy belőlük következő függőség igen.

2. Amikor dekomponálunk az FF-eket és TÉF-eket is vetítenünk kell.

Következtetés

FF használata

FF $X\to Y$ alkalmazásánál keressük meg azon sorpárokat, amelyek megegyeznek $X$ attribútumain. Az $Y$ attribútumain is tegyük őket egyenlővé.

• Egy változót egy másikra cseréljünk.
• Ha a lecserélt változó a célsorban is megjelenik, ott is cseréljünk.

TÉF használata

Egy $X\to \to Y$ TÉF használatánál keressünk két sort, amelyek megegyeznek X attribútumain.

• Adjuk hozzá a tablóhoz azokat a sorokat, amelyeket az $Y$ attribútumaihoz tartozó értékek felcserélésével kapunk.

Célok

• Az $U\to V$ ellenőrzésekor akkor nyertünk, ha a megfelelő változók $V$-hez tartozó minden oszlopban egyenlőek.

• $U\to \to V$ akkor győztünk, ha sikerül egy olyan sort kigenerálni, ami az eredeti két sorból keletkezik $V$ értékeinek felcserélésével.

Végjáték

• Használjuk az összes FF-et és TÉF-et, amíg bármiféle változtatás történhet.
• Ha nyertünk, nyertünk.
• Ha nem, egy ellenpéldát kaptunk.
  • A kapott előfordulás az összes előre megadott függőséget teljesíti.
  • Az eredeti két sor megsérti a kikövetkeztetendő függőséget.

TÉFek vetítése

• Le kell tudnunk vetíteni megadott függőségeket 2 reláció sémára
• Legrosszabb eset: ki kell próbálnunk minden lehetséges FF-et és TÉF-et a felbontott relációkra
• Chase teszt alkalmazása; Cél egy TÉF ellenőrzésénél: olyan sor előállítása a tablóban, amely indexeletlen betűket tartalmaz a felbontott reláció oszlopaira

Egyed kapcsolat modell

• Egyed kapcsolat modellekkel adatbázissémát vázolhatunk fel.
• A főbb részek felvázolásával hatékonyabb lehet egy működő adatbázist.

Egyedhalmazok

• Egyed (entity)
• Egyedhalmaz
  • Az objektum-orientált nyelvek osztály fogalmához hasonló
• Attribútum
  • Atomi értékűek, nem rekordok, tömbök

Diagrammok

• Az egyed kapcsolat diagramban:
  • egyedhalmaz: téglalap
    • alosztályok: háromszög (nincs töbszörös öröklés)
  • attribútum: ovális
    • kulcs(ok): aláhúzás
  • sok-sok, sok-egy, egy-egy kapcsolat (rombusz)
  • kapcsolathalmaz
  • ezek össze vannak kötve

Források

• Diasor I
• Diasor II
• Diasor III
• Diasor IV