Information Technology | Databases » Adatbázisok tételek és definíciók

Adatbázisok tételek és definíciók 2002. január 8 1. Az E-R modell 1.1 Definíció (Egyed (entitás)) A valós világban létező, logikai vagy fizikai szempontból saját léttel rendelkező dolog, amelyről adatokat tárolunk. 1.2 Definíció (Tulajdonság) Az, ami az entitásokat jellemzi, amelyen vagy amelyeken keresztül az entitások megkülönböztethetők 1.3 Definíció (Egyedek halmaza) Az azonos attribútum-típusokkal jellemzett egyedek összessége 1.4 Definíció (Kapcsolat) Entitások névvel ellátott viszonya 1.5 Definíció (Egy-egy kapcsolat) Olyan (bináris) kapcsolat, amelyben a résztvevő entitáshalmazok példányaival egy másik entitáshalmaznak legfeljebb egy példánya van kapcsolatban 1.6 Definíció (Több-egy kapcsolat) Egy K : E1, E2 kapcsolat több-egy, ha E1 példányaihoz legfeljebb egy E2beli példány tartozik 1.7 Definíció (Több-több kapcsolat) Egy kapcsolat több-több funkcionalitású, ha nem több-egy egyik irányban sem. 1.8

Definíció (Kulcs) Az E-R modellezésnél az attribútumoknak azt a halmazát, amely az entitás példányait egyértelműen azonosítja, kulcsnak nevezzük. 2. A relációs adatmodell 2.1 Definíció (Reláció) Halmazok Descartes-szorzatának részhalmazát relációnak nevezzük 2.2 Definíció (Reláció foka) A relációban lévő oszlopok (attribútumok, tulajdonságok) számát a reláció fokának nevezzük. 2.3 Definíció (Reláció számossága) A relációban lévő sorok számát a reláció számosságának nevezzük (nk ) 2.4 Tétel Minden, az Rk ⊆ Ank , (k = 1, 2, . r) relációkból felépített E relációalgebrai kifejezéshez van olyan (n ) Ψ sorkalkulus formula, hogy Ψ csak az Rk k -k közül tartalmaz relációkat és az E kifejezés megegyezik {s(m) |Ψ(s(m) )}vel. 2.5 Definíció (DOM(Ψ)) {Ψ-beli alaprelációk valamennyi attribútumának értékei}∪{Ψ-ben előforduló konstansok} 1 2.6 Definíció (Biztonságos kifejezés) {t|Ψ(t)}

biztonságos, ha 1. minden Ψ(t)-t kielégítő t minden komponense DOM(Ψ)-beli 2. Ψ-nek minden ∃u ω(u) alakú részformulájára teljesül, hogy ha u kielégíti ω-t az ω-beli szabad változók valamely értéke mellett, akkor u minden komponense DOM(ω)-beli (a részformula biztonságos). 2.7 Tétel A relációs algebra és a biztonságos sorkalkulus ekvivalensek (n ) 2.8 Tétel Rögzített A interpretációs halmaz és Rk k ⊆ Ank relációk esetén a sorkalkulus bármely kifejezéséhez létezik az oszlopkalkulusnak olyan kifejezése, amely az előzővel azonos relációt határoz meg. 3. A hálós adatmodell 3.1 Definíció (Rekord-típus) Egy R rekord-típus egy olyan A1 , A2 , , An n-es, ahol Ai -k az attribútumnevek és minden Ai -hez egy Di halmaz, az attribútum domainje is hozzátartozik, amely halmazból az Ai attribútum értéket vehet fel. 3.2 Definíció (Set-típus) Legyen R1 és R2 két rekord-típus és legyenek ℑ(R1 ) és ℑ(R2 ) a konkrét

eseteik halmazai Ekkor az S set-típust az S := R1 × R2 művelettel definiálhatjuk, ami egy ℑ(R1 ) ℑ(R2 ) függvényszerű kapcsolatot ír le. R1 az owner-típus, R2 pedig a member-típus 4. Relációs adatbázisok logikai tervezése 4.1 Definíció (Redundancia) Származtatott adatok, vagy alapadatok többször való tárolását az adatbázisban redundanciának nevezzük. 4.2 Definíció (Funkcionális függőség) Legyen adott az R(A1 , A2 , , An ) relációs séma, ahol Ai -k (i = 1, 2, , n) (alap)attribútumok. Legyen X és Y a reláció attribútumainak két részhalmaza: X ⊆ R és Y ⊆ R Ha a reláció bármely két t,t 0 ∈ r(R) sorára bármely időpillanatban fennáll az, hogy ha t[X] = t 0 [X] akkor t[Y ] = t 0 [Y ] (ahol t[Z] jelentése ΠZ (t)), akkor azt mondjuk, hogy az Y attribútumok funkcionálisan függenek az X attribútumoktól. Azt is mondhatjuk, hogy az X értékei meghatározzák az Y értékeit. Mindezt így jelöljük: X Y 4.3

Definíció (Determináns) Ha X,Y ⊂ R és X Y , de Y nem függ funkcionálisan X egyetlen valódi részhalmazától sem, akkor X-et Y determinánsának nevezzük Azt is mondjuk, hogy Y teljesen függ (funkcionálisan) X-től Ha van olyan X 0 ⊂ X, hogy X 0 Y , akkor Y részlegesen függ X-től. 4.4 Definíció (Kulcs) X-et pontosan akkor nevezzük kulcsnak az R reláción, ha 1. X R, és 2. X-nek nincs olyan X 0 valódi részhalmaza, hogy X 0 R 4.5 Definíció (Szuperkulcs) X-et szuperkulcsnak nevezzük, ha igaz, hogy X R Más szavakkal: akkor, ha tartalmaz kulcsot. 4.6 Tétel Minden relációnak van kulcsa 4.7 Definíció (Idegen kulcs) Legyen adott egy R és egy R0 relációs séma Tegyük fel, hogy R0 6= R Ha ∃D ⊆ (R ∩ R0 ), hogy D R0 és minimális – azaz R0 kulcsa –, akkor D neve az R sémával kapcsolatban idegen kulcs. 2 4.8 Definíció (Igaz) Egy adott R sémán az attribútumain értelmezett FR függéshalmaz mellett egy X Y függőség pontosan

akkor igaz, ha minden olyan r(R) reláción fennáll, amelyeken FR valamennyi függősége is fennáll Jelölése: FR |= X Y . 4.9 Definíció (Levezethető) Egy W Z funkcionális függőség pontosan akkor vezethető le adott FR függőségekből, ha az axiómák ismételt alkalmazásával FR -ből kiindulva megkaphatjuk W Z-t Jelölése: FR ` W Z 4.10 Definíció (Armstrong axiómái a funkcionáis függőségekről) Adottak az R sémán az X, Y , Z attribútumhalmazok 1. Ha X ⊆ Y , akkor Y X (reflexivitás vagy triviális függőség) 2. Ha X Y és Y Z, akkor X Z (tranzitivitás) 3. Ha X Y , akkor XZ Y Z (bővíthetőség) 4.11 Tétel (Igazság tétel) Az Armstrong axiómák igazak, alkalmazásukkal csak igaz függőségek állíthatók elő 4.12 Definíció (Attribútumhalmaz lezárása) Az X attribútumhalmaz lezárása adott F függéshalmaz mellett az a legbővebb A ⊆ R halmaz, amelyre az X A függőség adott függéshalmaz mellett fennáll.

Jelölése: X + (F) 4.13 Tétel (Teljesség tétel) Az Armstrong axiómák teljesek, azaz belőlük minden függőség levezethető 4.14 Definíció (Függéshalmaz lezárása) Az F függéshalmaz lezárása mindazon függőségek halmaza, amelyek az F függéshalmaz elemeiből az Armstrong axiómák alapján következnek. 4.15 Definíció (Függéshalmazok ekvivalenciája) Két függéshalmaz pontosan akkor ekvivalens, ha lezártjaik megegyeznek. 4.16 Definíció (Minimális függéshalmaz) F minimális függéshalmaz akkor, ha: 1. a függőségek jobb oldalán csak egyetlen attribútum van, 2. nincs olyan függőség, amely elhagyható, 3. a függőségek bal oldaláról nem hagyható el attribútum 4.17 Tétel Adott függéshalmazzal ekvivalens minimális függéshalmaz mindig előállítható 4.1 Relációk normál formái 4.18 Definíció (0NF) Egy reláció 0NF alakú, ha legalább egy attribútuma nem atomi 4.19 Definíció (1NF) Egy reláció 1NF alakú, ha csak atomi

attribútum-értékek szerepelnek benne 4.20 Definíció (Elsődleges attribútum) Egy R reláció A ∈ R attribútuma elsődleges, ha A eleme a reláció valamely K kulcsának Egyébként A másodlagos attribútum 4.21 Definíció (2NF) Egy 1NF relációs séma 2NF alakú, ha benne minden másodlagos attribútum a reláció bármely kulcsától teljesen függ. Más szavakkal: másodlagos attribútum nem függ egyetlen kulcs egyetlen valódi részhalmazától sem. 4.22 Tétel Minden 1NF reláció felbontható 2NF relációkba úgy, hogy azokból az eredeti reláció torzulás nélkül helyreállítható. 3 4.23 Definíció (Triviális függőség) Ha az X, Y attribútumhalmazokra igaz, hogy Y ⊆ X, akkor az X Y függőséget triviális függőségnek nevezzük, egyébként a függőség nemtriviális 4.24 Definíció (Tranzitív függés) Adott egy R séma, a sémán értelmezett funkcionális függőségek F halmaza, X ⊆ R, A ∈ R. A tranzitíven függ X-től, ha

∃Y ⊂ R, hogy X Y, Y 9 X, Y A és A ∈ / Y. 4.25 Definíció (3NF) Egy 1NF R séma 3NF, ha ∀A ∈ R másodlagos attribútum és ∀X ⊆ R kulcs esetén @Y , hogy X Y, Y 9 X, Y A és A ∈ / Y . Más szavakkal: ha egyetlen másodlagos attribútum sem függ tranzitívan egyetlen kulcstól sem. 4.26 Definíció (3NF) Egy 1NF R séma 3NF, ha ∀X A, X ⊆ R, A ∈ R nemtriviális függőség esetén vagy X szuperkulcs, vagy A elsődleges attribútum. 4.27 Tétel A 3NF két definíciója egyenértékű 4.28 Tétel Minden legalább 1NF relációs séma felbontható 3NF sémákba úgy, hogy azokból az eredeti reláció információveszteség nélkül helyreállítható. 4.29 Tétel Ha egy séma 3NF alakú, akkor 2NF is egyben 4.30 Definíció (BCNF) Egy 1NF R séma BCNF, ha ∀A ∈ R attribútum és ∀X ⊆ R kulcs esetén @Y , hogy X Y, Y 9 X, Y A és A ∈ / Y . Más szavakkal: egyáltalán nincs tranzitív függőség kulcstól 4.31 Definíció (BCNF) Egy 1NF R séma

BCNF, ha ∀X A, X ⊆ R, A ∈ R nemtriviális függőség esetén X szuperkulcs. 4.32 Tétel A BCNF két definíciója egyenértékű 4.33 Tétel Ha egy séma BCNF alakú, akkor 3NF is 4.34 Tétel A BCNF sémákra illeszkedő relációk nem tartalmaznak redundanciát (legalábbis funkcionális függőségek következtében) 4.35 Definíció (Adatbázis normál formája) Egy adatbázis BCNF (3NF, 2NF, 1NF) alakú, ha a benne található valamennyi relációs séma rendre legalább BCNF (3NF, 2NF, 1NF). 4.36 Definíció (Felbontás) Egy R relációs sémának ρ = {R1 , R2 , , Rk } egy felbontása, ha R1 ∪ R2 ∪ ∪ Rk = R. 4.37 Definíció (Veszteségmentes felbontás) Az R relációs séma egy ρ(R1 , R2 , , Rn ) felbontását veszteségmentesnek mondjuk, ha ∀r(R) relációra ∏R1 (r) / ∏R2 (r) / / ∏Rn (r) = r 4.38 Tétel Adott egy R séma és egy ρ(R1 , R2 , , Rn ) felbontása ∀r(R) relációra r ⊆ mρ (r) 4.39 Tétel Adott egy R séma és R-nek

egy ρ(R1 , R2 , , Rn ) veszteségmentes felbontása Tetszőleges τ ⊇ ρ esetén τ is veszteségmentes. 4.40 Tétel Adott az R séma, a séma attribútumain értelmezett F függőséghalmaz és egy ρ = (R1 , R2 ) felbontás ρ veszteségmentes ⇔ (R1 ∩ R2 ) (R1 R2 ) ∈ F + vagy (R1 ∩ R2 ) (R2 R1 ) ∈ F + . 4.41 Tétel Adott R(XYZ) és funkcionális függőségek F halmaza esetén, ahol X, Y és Z attribútumhalmazok is lehetnek ρ = (XY, XZ) pontosan akkor veszteségmentes, ha X Y ∈ F + vagy X Z ∈ F + . 4.42 Tétel A ρ felbontás veszteségmentes ⇔ van csupa ’a’-ból álló sor a táblázatos módszer táblázatában 4 4.43 Definíció (Függőségek vetítése attribútumhalmazra) Adott az R séma attribútumain értelmezett függőségek F halmaza A függőségeknek egy Z ⊂ R attribútumhalmazra való vetítése az a ∏Z (F) függőséghalmaz, amelyre ∏Z (F) = {X Y |X Y ∈ F + és XY ⊆ Z}. 4.44 Definíció (Függőségőrző

felbontás) Adott egy R relációs séma és egy, a sémán értelmezett F függéshalmaz A séma ρ(R1 , R2 , . , Rn ) függőségőrző, ha {∏Ri (F)} ` F 4.45 Tétel Minden R relációs séma és a sémán értelmezett F függéshalmaz esetén ∃ρ sémafelbontás, amely veszteségmentes és függőségőrző, továbbá ∀Ri ∈ ρ-ra Ri 3NF tulajdonságú. 4.46 Tétel Minden, legalább 1NF R sémának létezik veszteségmentes felbontása BCNF sémákba 4.47 Definíció (Többértékű függőség) Adott egy R séma és attribútumainak egy X és Y halmaza Ha ∀t1 ,t2 ∈ r(R)-hez, amelyre t1 [X] = t2 [X] (de más attribútumokon ez nem áll fenn!) ∃t3 ,t4 ∈ r(R), hogy • t3 [X] = t4 [X] = t1 [X], • t3 [Y ] = t1 [Y ] és t3 [Ω − XY ] = t2 [Ω − XY ], • t4 [Y ] = t2 [Y ] és t4 [Ω − XY ] = t1 [Ω − XY ], akkor Y többértékűen függ X-től (X multideterminálja Y-t). Jelölése: X ³ Y 4.48 Tétel Ha X Y fennáll, akkor X ³ Y is igaz 4.49

Tétel Legyen R egy séma, ρ = (R1 , R2 ) egy felbontása, D pedig az R sémán értelmezett funkcionális és többértékű függőségek halmaza. ρ akkor és csak akkor veszteségmentes, ha (R1 ∩ R2 ) ³ (R1 R2 ) ∈ F + vagy (R1 ∩ R2 ) ³ (R2 R1 ) ∈ F + következik a D függőségekből. 4.50 Definíció (4NF) Egy relációs séma 4NF alakú, ha X ³ Y esetén X szuperkulcs, de 1. Y nem üres halmaz 2. Y nem részhalmaza X-nek 3. XY-on kívül a sémának van más attribútuma is 5. Tranzakciók 5.1 Definíció (Tranzakció) Egy program egyszeri futása, amelynek vagy valamennyi hatása hatásos, vagy belőle semmi sem. 5.2 Definíció (Ütemezés) Tranzakciók elemi műveleteinek összessége, melyben a műveletek időbeli sorrendje is egyértelműen meghatározott. 5.3 Definíció (Zár) A zár egy hozzáférési privilégium egy adategységen, amely adható és visszavonható 5.4 Definíció (Legális ütemezés) Legális az az ütemezés, amelyben a lock-olt

adategységet fel is szabadítják (unlock-al), továbbá ha egy adategység már foglalt – mert egy másik tranzakció tart fenn nem megosztható zárat rajta –, akkor a tranzakció a zár felszabadulásáig várakozik. 5.5 Definíció (Várakozási gráf) Olyan irányított gráf, ahol a gráf csomópontjai a tranzakciók, egy élt pedig akkor rajzolunk a Ti csomópontból a T j csomópont felé, ha a Ti tranzakció bármely okból várakoztatja a T j tranzakciót úgy, hogy az nem tud továbbmenni. 5 5.6 Tétel Adott időpillanatban nincs patt ⇔ a várakozási gráfban nincs kör (azaz DAG) 5.7 Definíció (Soros ütemezés) Ha a tranzakciók egy rendszerben szigorúan egymás után futnak le úgy, hogy egyidejűleg mindig csak egyetlen tranzakció fut, akkor ez egy soros ütemezés. 5.8 Definíció (Sorosítható) Egy ütemezés sorosítható, ha valamennyi hatása ekvivalens valamely soros ütemezéssel Egy ütemezés nem sorosítható, ha ilyen ekvivalens soros

ütemezés nincs 5.9 Definíció (Korrekt) Egy ütemezés pontosan akkor korrekt, ha sorosítható • csak egyfajta zár létezik 5.10 Definíció (Egyszerű tranzakció modell) • egy adatelem zárolása (LOCK) után a tranzakció vége előtt a zár elengedése következik • egy adatelemen egyidőben csak egyetlen zár lehet 5.11 Definíció (Sorosítási (precedencia) gráf) Olyan irányított gráf, amelynek a csomópontjai a tranzakciók, egy élt pedig akkor rajzolunk a Ti csomópontból a T j csomópont felé, ha van olyan A adategység, amelyen egy adott S ütemezésben a Ti tranzakció zárat helyezett el, majd a zár felszabadítása után először a T j tranzakció helyez el zárt A-n. 5.12 Tétel Egy S ütemezés sorosítható ⇔ a sorosítási gráf DAG 5.13 Definíció (Kétfázisú zárolás) Egy tranzakció a kétfázisú zárolás protokollt (2PL) követi, ha az első zárfelszabadítást megelőzi valamennyi zárkérés 5.14 Tétel Ha egy legális

ütemezés valamennyi tranzakciója a 2PL protokollt követi, akkor az ütemezés sorosítható 5.15 Definíció (Zárpont) Zárpont az az időpont, amikor egy kétfázisú protokoll szerinti tranzakció az utolsó zárját is megkapja. 5.16 Definíció (RLOCK-WLOCK modell) (nem megosztható, kemény) • Kétfajta zár létezik: RLOCK (megosztható, puha) és WLOCK • Ha T:RLOCK A érvényes, akkor más tranzakció is olvashatja A-t, de senki nem írhatja. • Ha T:WLOCK A érvényes, akkor semmilyen más tranzakció nem fér hozzá A-hoz, sem írásra, sem olvasásra. • Egy adatelem zárolása (RLOCK vagy WLOCK) után a tranzakció vége előtt a zár elengedése (UNLOCK) következik. 5.17 Tétel Egy RLOCK-WLOCK modellbeli S ütemezés sorosítható ⇔ a következő szabályok szerint rajzolt precedenciagráf DAG • Ti : RLOCK A, Ti : UNLOCK A, T j : WLOCK A • Ti : WLOCK A, Ti : UNLOCK A, T j : WLOCK A • Ti : WLOCK A, Ti : UNLOCK A, T j : RLOCK A A fenti

esetekben a precedenciagráfban Ti T j él rajzolandó. 5.18 Definíció (2PL RLOCK-WLOCK) Egy RLOCK-WLOCK modell szerinti tranzakció kétfázisú, ha minden RLOCK és WLOCK megelőzi az első UNLOCK-ot. 6 5.19 Tétel Ha egy ütemezésben csak kétfázisú, RLOCK-WLOCK modell szerinti tranzakciók vannak, akkor az ütemezés sorosítható. 5.20 Definíció (Fa protokoll) Az egyszerű tranzakció modellt követjük, és egy csomópont zárolása nem jelenti a gyerekek zárolását is. • Egy tranzakció az első LOCK-ot akárhová teheti • további LOCK-ok csak akkor helyezhetők el, ha az adategység szülőjére ugyanaz a tranzakció már rakott zárat • Egyazon tranzakció kétszer ugyanazt az adategységet nem zárolhatja 5.21 Tétel A fa protokollnak eleget tevő legális ütemezések sorosíthatók 5.22 Definíció (Fa protokoll sorosíthatósági gráfjának rajzolása) Legyen E(T) az a csúcs, amit a T tranzakció elsőnek zárol. Ha E(Ti ) és E(T j ) közül

egyik sem őse a másiknak, akkor nem rajzolunk élet Ti és T j között, hiszen a protokoll garantálja, hogy ekkor Ti és T j sohasem fog közös csúcsot (adategységet) zárolni. Tegyük fel tehát, hogy E(Ti ) őse E(T j )-nek. • Ha Ti zárolja először E(T j )-t mielőtt T j zárolná, akkor egy Ti T j élet rajzolunk a gráfba • Ha T j zárolja először E(T j )-t, mielőtt Ti zárolná, akkor pedig egy T j Ti élet rajzolunk a gráfba. 5.23 Definíció (Figyelmeztető protokoll) Az egyszerű tranzakció modellt követjük, és egy csomópont zárolása a gyerek csomópontok zárolását is jelenti. • Egy tranzakció első művelete kötelezően LOCK gyökér vagy WARN gyökér • LOCK A vagy WARN A akkor helyezhető el, ha A szülőjén már van WARN • UNLOCK A akkor lehetséges, ha A gyerekein már nincs LOCK vagy WARN • Kétfázisú: az első UNLOCK után nem következhet LOCK vagy WARN 5.24 Definíció (Zárkonfliktus) Két tranzakció tart fenn

egyidejűleg zárat ugyanazon adategységen 5.25 Tétel A figyelmeztető protokollt követő legális ütemezések konfliktusmentesek és sorosíthatók 5.26 Definíció (Konzisztens állapot) Konzisztens állapot az adatbázisnak olyan állapota, amely csak teljesen lefutott tranzakciók hatását tükrözi. 5.27 Definíció (Kész (commit) pont) Az az időpillanat, amikor egy tranzakció futása során már minden befejeződött, ami rendszer- illetve médiahiba kivételével az abortját eredményezheti 5.28 Definíció („Piszkos” adat) Olyan adat, amit az előtt írt valamely tranzakció az adatbázisba, mielőtt committált volna 5.29 Definíció (Szigorú 2PL) Egy tranzakció a szigorú 2PL protokoll követi, ha kétfázisú, továbbá: • Nem ír az adatbázisba, amíg a kész pontját el nem érte • A zárait csak az adatbázisba írás után engedi el 5.30 Tétel A szigorú kétfázisú protokollt követő tranzakciókból álló ütemezések sorosíthatók és

lavinamentesek 7 5.31 Definíció (Agresszív) Ha megpróbál olyan gyorsan lefutni, amennyire csak lehetséges, nem törődve azzal, hogy ez esetleg abort-hoz is vezethet. 5.32 Definíció (Konzervatív) Ha megkísérli elkerülni az olyan tranzakciók futtatását, amelyek nem biztos, hogy eredményesek lesznek. 5.33 Definíció (Redo protokoll) Redo naplózás: 1. (T, begin) naplóba 2. (T, A, <A új értéke>) naplóba, ha T megváltoztatja valamely A adategység értékét 3. (T, commit) naplóba, ha T elérte a commit pontját 4. a napló mindazon oldalainak stabil tárba írása, amikkel ez még nem történt meg 5. az „A” értékeknek a tényleges írása az adatbázisba 6. zárak elengedése Véglegesített tranzakció az, amelyik eljutott a 4. pont végéig Redo helyreállítás: 1. valamennyi zár felszabadítása 2. napló vizsgálata visszafelé: feljegyezzük azon tranzakciókat, amelyekre találunk (T, commit) bejegyzést a naplóban 3. addig megyünk

visszafelé a naplóban, ameddig nem találunk egy konzisztens állapotot 4. a 2 pontnak megfelelő tranzakcióra vonatkozó bejegyzések segítségével az adatbázisban található értékeket felülírjuk az újakkal 5.34 Definíció (Időbélyeg) Olyan érték, amelyet minden tranzakcióhoz szigorú egyediséget biztosítva rendelünk hozzá és amely arányos a tranzakció kezdőidejével. Jele: t(Tranzakció) 5.35 Definíció (Elosztott adatbázis) Csomópontok összessége, amelyekben egy-egy számítógép üzemel saját CPUval és háttértárral A csomópontok egymással össze vannak kötve adatcserére alkalmas módon 5.36 Definíció (Globális adat) Globális adat az, amely egyetlen logikai egységnek számít az egész elosztott adatbázis szempontjából, valójában részekből állhat, tipikusan fizikailag különböző helyeken Ezek a részek a lokális (fizikai) adatok. 8