Az egyik legfontosabb fogalom a relációs sématervezés elméletében a funkcionális függés fogalma. Ebben a fejezetben definiálni fogjuk a funkcionális függés fogalmát, a 8.3. alfejezetben pedig megmutatjuk, hogyan lehet felhasználni ezt a fogalmat relációs sémák normálformáinak a definiálására.
A funkcionális függés egy olyan megszorítás, amely az adatbázis két attribútumhalmaza között áll fenn. Tegyük fel, hogy a relációs adatbázissémánknak n attribútuma van: A 1, A 2, ..., An ; és gondoljunk az egész adatbázisunkra úgy, hogy azt egyetlen, univerzális R = { A 1, A 2, …, An } relációsémával írjuk le. Ez nem jelenti azt, hogy az adatbázisunkat egyetlen univerzális táblaként fogjuk tárolni; ezt a fogalmat csak az adatfüggőség formális elméletének a kialakításához használjuk.
Definíció. Az R két attribútumhalmaza, X és Y között értelmezett, X → Y alakú funkcionális függés egy megszorítást ír elő az R relációséma bármely r relációjának lehetséges rekordjaira. A megszorítás az, hogy bármely két r-beli t 1 és t 2 rekord esetén, amelyekre t 1[X] = t 2[X] teljesül, teljesülnie kell t 1[Y] = t 2[Y]-nak is.
Ez azt jelenti, hogy r-beli rekord Y komponensének az értékei függnek az X komponens értékektől; más szavakkal egy rekord X komponensének az értékei egyértelműen (vagy funkcionálisan) meghatározzák az Y komponens értékeit. Azt is mondhatjuk, hogy X funkcionálisan meghatározza Y-t, vagy Y funkcionálisan függ X-től. Az X attribútumhalmazt a funkcionális függés bal oldalának, az Y-t pedig a jobb oldalának nevezzük.
Ennélfogva X akkor és csak akkor határozza meg funkcionálisan Y-t egy R relációsémában, ha valahányszor r(R) két rekordja megegyezik az X-hez tartozó értékeikben, szükségszerűen megegyeznek az Y-hoz tartozó értékeikben is. Vegyük észre a következőket:
Abból, hogy egy R-re előírt megszorítás szerint bármely r(R) relációpéldányban nem szerepelhet több rekord egy adott X-hez tartozó értékkel — azaz X kulcsjelöltje R-nek —, következik X → Y az R attribútumainak bármely Y részhalmazára (mivel a kulcsmegszorításból következik, hogy egyetlen legális r(R) állapotban sem lehet két olyan rekord, amelyeknek azonosak lennének az X-hez tartozó értékeik).
Ha X → Y teljesül R-ben, még semmit sem tudunk mondani arról, hogy vajon Y → X is teljesül-e R-ben.
Egy funkcionális függés az attribútumok szemantikájának vagy jelentésének egy jellemzője. Az adatbázistervezők R attribútumai szemantikájának — azaz hogy milyen kapcsolat van közöttük — az általuk vett értelmezését használják fel ahhoz, hogy megadják azokat a funkcionális függéseket, amelyek R minden r relációállapotában fennállnak. Valahányszor R két attribútumhalmazának a jelentése azt sugallja, hogy egy funkcionális függés fennáll, akkor felvesszük ezt a függést a megszorítások közé. Azokat a r(R) relációállapotokat, amelyek megfelelnek a funkcionális függés megszorításoknak, R legális vagy jogszerű relációállapotainak nevezzük. A funkcionális függések fő felhasználása tehát az, hogy tovább jellemezzük az R relációsémát azzal, hogy az attribútumaira olyan megszorításokat adunk, amelyek mindig érvényesek. Bizonyos funkcionális függéseket anélkül is felírhatunk, hogy egy konkrét relációra utalnánk, ehelyett a szóban forgó attribútumok egy tulajdonságaként adjuk meg őket a hétköznapi értelmük alapján. Például az {Állam, Jogosítványszám} → Társadalombiztosítási_szám fennáll minden egyesült államokbeli felnőtt esetén. Az is elképzelhető, hogy egyes funkcionális függések a valós világban megszűnnek létezni, ha a kapcsolat módosul. Például az Irányítószám → Körzetszám valaha létező kapcsolat volt a postai kódok és a telefonszámkódok között az Egyesült Államokban, de a körzetszámok elburjánzása miatt ez ma már nem teljesül.
Tekintsük a 8.3. (b) ábrán szereplő DOLG_PROJ relációsémát; az attribútumok jelentése alapján tudjuk, hogy a következő funkcionális függéseknek kell fennállniuk:
Szsz → Dnév
Pszám → {Pnév, Phelyszín}
{Szsz, Pszám} → Órák
Ezek a funkcionális függések azt mutatják, hogy (a) egy dolgozó személyi száma (Szsz) egyértelműen meghatározza a dolgozó nevét (Dnév), (b) a projektszámnak egy értéke (Pszám) egyértelműen meghatározza a projekt nevét (Pnév) és helyszínét (Phelyszín), és (c) az Szsz és a PSzám értékeinek együttese egyértelműen meghatározza azt az időtartamot, ahány órát jelenleg a dolgozó a projekten hetente dolgozik (Órák). Másképpen úgy is mondhatjuk, hogy a Dnév funkcionálisan függ az Szsz-től (az Szsz funkcionálisan meghatározza a Dnév attribútumot), vagy az Szsz egy adott értéke esetén ismerjük a Dnév értékét, stb.
8.7. ábra - A TANÍT egy relációállapota a lehetséges Jegyzet → Kurzus funkcionális függéssel. Az Oktató → Kurzus azonban ki van zárva.
A funkcionális függés az R relációséma egy tulajdonsága, nem az R egy konkrét r legális relációállapotáé. A funkcionális függések ezért nem következnek automatikusan egy adott r relációállapotból, hanem explicit módon kell definiálnia valaki olyan személynek, aki ismeri R attribútumainak szemantikáját. Példaként tekintsük a 8.7. ábrán a TANÍT relációséma egy konkrét állapotát. Bár első pillantásra úgy tűnhet, hogy Jegyzet → Kurzus, ezt nem tudjuk megerősíteni, hacsak nem tudjuk, hogy a TANÍT minden lehetséges legális állapotára érvényes. Elegendő azonban egyetlen ellenpélda annak demonstrálására, hogy megcáfoljunk egy funkcionális függést. Például abból, hogy „Fazekas” mind „Adatszerkezeteket”, mind pedig „Adatkezelést” tanít, következtethetünk, hogy az Oktató nem határozza meg funkcionálisan a Kurzust.
A 8.3. ábra egy grafikus jelölést vezet be a funkcionális függések ábrázolására: Minden funkcionális függést egy vízszintes vonal jelöl. A funkcionális függés bal oldali attribútumait függőleges vonalak kapcsolják a függést jelképező vonalhoz, míg a jobb oldali attribútumokat az attribútumok felé mutató nyilak kötik össze vele, ahogy a 8.3. (a) és (b) ábrákon látható.
Jelöljük F-fel az R relációséma feletti funkcionális függések halmazát. A sématervező tipikusan csak a szemantikailag nyilvánvaló funkcionális függéseket adja meg; általában azonban számos további funkcionális függés is fennáll különböző attribútumhalmazok között minden legális relációpéldány esetében, amelyek következnek az F-beli függésekből. Ezek a további függések levezethetők vagy következnek az F-beli funkcionális függésekből.
A valós életben lehetetlen megadni az összes lehetséges funkcionális függést egy konkrét esetben. Ha például minden osztálynak egy vezetője van, tehát Oszám egyértelműen meghatározza Ovez_szsz-t (Oszám → Ovez_szsz), és az osztályvezetőnek egyetlen telefonszáma van, amelyet Ovez_telefonnak hívunk (Ovez_szsz → Ovez_telefon), akkor ebből a két függésből együtt következik, hogy Oszám → Ovez_telefon. Ez egy levezetett funkcionális függés, és nem kell explicit módon megadni a két említett funkcionális függés mellett. Formálisan tehát célszerű definiálni egy olyan fogalmat — amit lezártnak nevezünk —, amely az F halmazból levezethető összes lehetséges függést tartalmazza.
Definíció. Formálisan azt a függéshalmazt, amely tartalmazza az összes F-beli függést éppúgy, mint azokat a függéseket, amelyek levezethetők F-ből, F lezártjának nevezzük és F +-szal jelöljük.
Az X → Y funkcionális függés levezethető az R-re vonatkozó F függéshalmazból, ha X → Y teljesül R minden r relációjában; azaz ha valahányszor r kielégíti az F-ben lévő összes függést, mindannyiszor X → Y is teljesül r-ben. Az F függéshalmaz F + lezártja az összes, F-ből levezethető funkcionális függés halmaza. Ahhoz, hogy megadjuk a függések levezetésének egy szisztematikus módszerét, levezetési szabályok egy halmazát kell bevezetnünk, amelyek segítségével új függéseket vezethetünk le egy adott függéshalmazból. A következőkben ilyen levezetési szabályok közül tekintünk át néhányat. Az F ⊨ X → Y jelölést fogjuk használni annak jelölésére, hogy az F függéshalmazból az X → Y funkcionális függés levezethető.
A következőkben rövidített jelölést fogunk használni a funkcionális függések tárgyalásánál. A kényelem kedvéért az attribútumváltozókat konkatenáljuk, a vesszőket pedig elhagyjuk. Így az { X, Y } → Z funkcionális függést röviden XY → Z, míg az { X, Y, Z } → { U, V } funkcionális függést XYZ → UV alakban írjuk. A következő hat szabály a funkcionális függések jól ismert levezetési szabályai:
A reflexivitás szabálya kimondja, hogy attribútumok egy halmaza mindig meghatározza saját magát vagy önmaga egy részhalmazát, ami nyilvánvaló. Mivel ez a szabály olyan függéseket generál, amelyek mindig igazak, az ilyen szabályokat triviálisnak nevezzük. Formálisan: egy X → Y függés triviális, ha X ⊇ Y; egyébként nemtriviális. Az augmentivitás szabálya azt állítja, hogy egy függés mindkét oldalához ugyanazt az attribútumhalmazt hozzáadva újabb érvényes függést kapunk. A tranzitivitás szabálya szerint a funkcionális függések tranzitívak. A dekompozíció szabálya kimondja, hogy egy függés jobb oldaláról elhagyhatunk attribútumokat; ezt a szabályt egymás után többször alkalmazva az X → { A 1, A 2, …, A n } funkcionális függés felbontható az { X → A 1, X → A 2, …, X → A n } függéshalmazra. Az unióképzés szabálya ennek az ellenkezőjét teszi lehetővé; funkcionális függések egy { X → A 1, X → A 2, …, X → A n } halmazát összevonhatjuk egyetlen X → { A 1, A 2, …, A n } funkcionális függéssé.
Ezeket a szabályokat nagy körültekintéssel kell alkalmazni. Bár X → A-ból és X → B-ből következik X → AB a fent említett unióképzés szabálya alapján, azonban önmagában sem X → A-ból, sem Y → B-ből nem következik XY → AB. Hasonlóan XY → A-ból sem következik szükségszerűen X → A és Y → A.
A felsorolt levezetési szabályok mindegyike bebizonyítható a funkcionális függés definíciója alapján vagy közvetlenül, vagy indirekt módon. Az indirekt módon történő bizonyítás során feltételezzük, hogy a szabály nem teljesül, és megmutatjuk, hogy ez nem lehetséges. A következőkben bebizonyítjuk, hogy az első három szabály érvényes. A másodikat indirekt módon bizonyítjuk.
A reflexivitás bizonyítása. Tegyük fel, hogy X ⊇ Y és hogy léteznek t 1 és t 2 rekordok az R séma valamely r relációjában, melyekre t 1[X] = t 2[X]. Ekkor t 1[Y] = t 2[Y] is teljesül, mivel X ⊇ Y. Tehát X → Y biztosan teljesül r-en.
Az augmentivitás bizonyítása (indirekt módon). Tegyük fel, hogy X → Y teljesül R egy r relációpéldányában, de XZ → YZ nem teljesül benne. Ekkor kell léteznie két rekordnak, t 1-nek és t 2-nek r-ben úgy, hogy (1) t 1[X] = t 2[X], (2) t 1[Y] = t 2[Y], (3) t 1[XZ] = t 2[XZ] és (4) t 1[YZ] ≠ t 2[YZ]. Ez nem lehetséges, mert (1)-ből és (3)-ból levezethetjük, hogy (5) t 1[Z] = t 2[Z], míg (2)-ből és (5)-ből következik (6) t 1[YZ] = t 2[YZ], ami ellentmond (4)-nek.
A tranzitivitás bizonyítása. Tegyük fel, hogy mind (1) X → Y, mind pedig (2) Y → Z teljesül egy r relációban. Ekkor bármely két r-beli t 1 és t 2 rekordra, amelyre t 1[X] = t 2[X] teljesül, az (1)-es feltevés miatt kapjuk, hogy (3) t 1[Y] = t 2[Y]; majd a (3)-ból és a (2)-es feltevésből azt is kapjuk, hogy (4) t 1[Z] = t 2[Z]; így teljesülnie kell X → Z-nek r-ben.
Hasonló bizonyítási lépéseket felhasználva bebizonyíthatjuk a dekompozíció, az additivitás és a pszeudotranzitivitás szabályát, valamint tetszőleges további érvényes levezetési szabályokat is. Mindazonáltal sokkal egyszerűbb úgy bebizonyítani egy levezetési szabályról azt, hogy érvényes a funkcionális függésekre, ha azoknak a levezetési szabályoknak a felhasználásával tesszük meg ezt, amelyekről korábban már bebizonyítottuk, hogy érvényesek. A példa kedvéért a dekompozíció, az additivitás és a pszeudotranzitivitás szabályát a következőképpen bizonyíthatjuk be a reflexivitás, az augmentivitás és a tranzitivitás szabályainak a felhasználásával:
A dekompozíció bizonyítása (a reflexivitás, az augmentivitás és a tranzitivitás felhasználásával).
X → YZ (adott).
YZ → Y (tudjuk, hogy YZ ⊇ Y, amire alkalmazzuk a reflexivitás szabályát).
X → Y (1-re és 2-re alkalmazzuk a tranzitivitás szabályát).
Az additivitás vagy unióképzés bizonyítása (a reflexivitás, az augmentivitás és a tranzitivitás felhasználásával).
X → Y (adott).
X → Z (adott).
X → XY (1-re alkalmazzuk az augmentivitás szabályát X-szel; megjegyezve, hogy XX = X).
XY → YZ (2-re alkalmazzuk az augmentivitás szabályát Y-nal).
X → YZ (3-ra és 4-re alkalmazzuk a tranzitivitás szabályát).
A pszeudotranzitivitás bizonyítása (a reflexivitás, az augmentivitás és a tranzitivitás felhasználásával).
X → Y (adott).
WY → Z (adott).
WX → WY (1-re alkalmazzuk az augmentivitás szabályát W-vel).
WX → Z (3-ra és 2-re alkalmazzuk a tranzitivitás szabályát).
Armstrong 1974-ben megmutatta, hogy a reflexivitás, az augmentivitás és a tranzitivitás szabálya együtt helyes és teljes. Helyesség alatt azt értjük, hogy ha adott egy R relációsémán fennálló funkcionális függéseknek egy F halmaza, akkor bármilyen függés, amely levezethető F-ből a három szabály segítségével, teljesülni fog R minden olyan r relációjában, amely kielégíti az F-beli függéseket. Teljesség alatt azt értjük, hogy a három szabályt mindaddig ismételten alkalmazva, míg már nem kapunk újabb függéseket, előállítható az F-ből levezethető összes lehetséges függés teljes halmaza. Más szavakkal, a függések F + halmaza, amelyet F lezártjának nevezünk, meghatározható F-ből kiindulva, kizárólag a három szabály alkalmazásával. A reflexivitás, az augmentivitás és a tranzitivitás szabályát együtt Armstrong-axiómáknak is nevezzük.
Egy adatbázis-tervező először általában a funkcionális függések azon F halmazát adja meg, amely könnyen meghatározható R attribútumainak a szemantikájából; azután a reflexivitás, augmentivitás és tranzitivitás szabályát felhasználva további funkcionális függéseket vezet le, amelyek szintén teljesülni fognak R-en. Ezen funkcionális függések meghatározásának egy szisztematikus módja az, ha először meghatározzuk azon X attribútumhalmazok mindegyikét, amelyek megjelennek valamely F-beli funkcionális függés bal oldalán, majd meghatározzuk az összes olyan attribútum halmazát, amelyek függnek X-től.
Definíció. Minden ilyen X attribútumhalmaz esetén meghatározzuk az attribútumoknak azt az X + halmazát, amelyek funkcionálisan függnek X-től az F alapján; X +-t X F feletti lezártjának nevezzük. X + kiszámítására az 1. algoritmus használható.
1. algoritmus − X F feletti lezártjának, X +-nak a meghatározása.
X + := X;
repeat
oldX + := X +;
for each F-beli Y → Z funkcionális függésre do
if X + ⊇ Y then X + := X + ∪ Z;
until (X + = oldX +);
A 1. algoritmus azzal kezdődik, hogy X +-nak értékül adja az X-et. Az IR1 szabály alapján tudjuk, hogy ezen attribútumok mindegyike funkcionálisan függ X-től. Az IR3 és IR4 szabályok felhasználásával újabb attribútumokat adunk hozzá X +-hoz az F-beli funkcionális függések alapján. Végigmegyünk az összes F-beli függésen (a repeat ciklusban), amíg már nem tudunk újabb attribútumot hozzáadni X +-hoz az F-beli függéseket bejáró (for) ciklus teljes lefutása során. Vegyük például a 8.3. ábra DOLG_PROJ relációsémáját; az attribútumok szemantikájából a DOLG_PROJ sémán fennálló funkcionális függések következő F halmazát adhatjuk meg:
F = { Szsz, → Dnév, Pszám → { Pnév, Phelyszín }, { Szsz, Pszám } → Órák }
A 1. algoritmus segítségével az alábbi lezárt halmazokat állítjuk elő F-re vonatkozóan:
{ Szsz }+ = { Szsz, Dnév }
{ Pszám }+ = { Pszám, Pnév, Phelyszín }
{ Szsz, Pszám }+ = { Szsz, Pszám, Dnév, Pnév, Phelyszín, Órák }
A jobb oldalon álló attribútumok halmaza a fenti sorokban azokat az attribútumokat tartalmazza, amelyek a bal oldalon álló attribútumhalmaztól funkcionálisan függnek a megadott F halmaz alapján.
A fejezet további részeiben funkcionális függések két halmazának az ekvivalenciájával foglalkozunk. Ehhez először is néhány előzetes definíciót adunk.
Definíció. Azt mondjuk, hogy funkcionális függések egy F halmaza lefedi funkcionális függések egy másik, E halmazát, ha minden E-beli funkcionális függés F +-ban is fennáll; azaz ha minden E-beli függés levezethető F-ből.
Definíció. Funkcionális függések E és F halmazai ekvivalensek, ha E + = F +. Az ekvivalencia tehát azt jelenti, hogy minden E-beli funkcionális függés levezethető F-ből, és minden F-beli funkcionális függés levezethető E-ből; azaz E akkor ekvivalens F-fel, ha E lefedi F-et, és F is lefedi E-t.
Azt, hogy F lefedi-e E-t, úgy dönthetjük el, hogy kiszámítjuk X +-t F-re nézve minden E-beli X → Y funkcionális függésre, majd ellenőrizzük, hogy X + tartalmazza-e az Y-beli attribútumokat. Ha ez minden E-beli funkcionális függésre igaz, akkor F lefedi E-t. Azt, hogy E és F ekvivalensek-e, úgy döntjük el, hogy megvizsgáljuk, hogy E is lefedi-e F-et, és F is lefedi-e E-t.
Funkcionális függések egy E halmazának a minimális lefedése informálisan funkcionális függéseknek egy olyan F halmaza, amelyre teljesül, hogy minden E-beli függés az F-nek az F + lezártjában is megtalálható. Ráadásul ez a tulajdonság nem teljesül, ha F-ből bármelyik függést kivesszük; F-ben nem lehet redundancia, ugyanakkor az F-beli függések standard formájúak. Hogy eleget tegyünk ezeknek a tulajdonságoknak, formálisan akkor mondjuk funkcionális függések egy F halmazára, hogy minimális, hogyha eleget tesz a következő feltételeknek:
Az összes F-beli függés jobb oldalán egyetlen attribútum áll.
Egyetlen F-beli X → A függést sem cserélhetünk ki olyan Y → A függésre, ahol Y valódi részhalmaza X-nek, és az így kapott függéshalmaz ekvivalens F-fel.
Nem távolíthatunk el egyetlen függést sem F-ből úgy, hogy a kapott függéshalmaz ekvivalens marad F-fel.
A függések minimális halmazát úgy képzelhetjük el, mint standard vagy kanonikus alakú függések redundanciáktól mentes halmazát. Az első feltétel csak annyit mond ki, hogy minden függésnek kanonikus alakban kell lennie, azaz a jobb oldalon csak egyetlen attribútum állhat.[31] A második és harmadik feltételek biztosítják, hogy ne legyen redundancia a függések között, amely redundanciát vagy az okozhatja, hogy egy függés bal oldalán redundáns attribútumok állnak (2. feltétel), vagy az, hogy olyan függés van F-ben, amely a többi F-beli függésből levezethető (3. feltétel).
Definíció. Funkcionális függések egy E halmazának egy minimális lefedése (standard kanonikus alakú) függéseknek egy olyan minimális (redundanciamentes) halmaza, amely ekvivalens E-vel. A 10.2-es algoritmus segítségével bármilyen E függéshalmazhoz előállítható legalább egy minimális F lefedés.
Ha több olyan függéshalmaz is létezik, amely a fenti definíció szerint E minimális lefedése, akkor a minimalitáshoz további kritériumokat szoktunk megfogalmazni. Választhatjuk például az a minimális halmazt, amely a legkevesebb függést tartalmazza, vagy amely a legkisebb teljes hosszal rendelkezik (egy függéshalmaz teljes hosszát úgy számítjuk ki, hogy összefűzzük a függéseket, és egy hosszú karaktersorozatnak tekintjük).
2. algoritmus − Funkcionális függések egy E halmazához az F minimális lefedés meghatározása.
Legyen F := E.
Cseréljük ki az összes F-beli X → { A 1, A 2, …, An } az X → A 1, X → A 2, …, X → An n darab funkcionális függéssel.
Minden F-beli X → A funkcionális függésre
minden X-beli B attribútumra
ha ( F − { X → A } ) ∪ { ( X − { B } ) → A } ekvivalens F-fel,
akkor cseréljük ki F-ben X → A-t ( X − { B } ) → A-ra.
Az összes többi F-beli X → A funkcionális függésre
ha az F − { X → A } ekvivalens F-fel,
akkor töröljük F-ből X → A-t.
A fenti algoritmust az alábbi példával illusztráljuk:
Legyen adott funkcionális függések egy E = { B → A, D → A, AB → D } halmaza. Határozzuk meg E egy minimális lefedését!
A felsorolt függések mind kanonikus alakúak; így teljesítettük a 2. algoritmus 2. lépését, és mehetünk tovább a 3. lépésre. A 3. lépésben el kell döntenünk, hogy az AB → D bal oldalán van-e redundáns attribútum; azaz helyettesíthetjük-e A → D-vel vagy B → D-vel.
Ha a B → A-t mindkét oldalon bővítjük B-vel (IR2), akkor BB → AB-t, azaz röviden (i) B → AB-t kapjuk. Ezenkívül (ii) AB → D is adott.
Ekkor a tranzitivitás szabályát (IR3) alkalmazva (i)-re és (ii)-re, kapjuk B → D-t. Az AB → D tehát kicserélhető B → D-re.
Van tehát egy, az eredeti E-vel ekvivalens halmazunk, E' = { B → A, D → A, B → D }. A harmadik lépésben nem lehet további redukciót végrehajtani, mivel mindegyik függésnek egyetlen attribútum áll a bal oldalán.
A 4. lépésben redundáns funkcionális függéseket keresünk E'-ben. A tranzitivitás szabályát alkalmazva B → D-re és D → A-ra, B → A-t kapjuk. B → A tehát redundáns E'-ben, így törölhető.
E minimális lefedése tehát { B → D, D → A }.
A 9. fejezetben látni fogjuk, hogyan szintetizálhatunk relációkat függések egy E halmazából úgy, hogy először meghatározzuk E-nek a minimális lefedését.
[31] Ez egy standard alak, amivel egyszerűsíthetjük azokat a feltételeket és algoritmusokat, amelyek a redundanciák létezését vizsgálják F-ben. Az IR4 levezetési szabály segítségével az olyan függések, amelyeknek a jobb oldalán több attribútum szerepel, átkonvertálhatók olyan függések halmazává, amelyeknek a jobb oldalán csak egy attribútum szerepel.