Bazsalanszky/adatb
1
0
Fork 0
Code Issues Pull requests Releases Wiki Activity
adatb/db.org
Balazs Toldi 9c8173c166
Some small changes
2021-01-08 07:47:44 +01:00

73 KiB
Raw Permalink Blame History

Adatbázisok tételek

Adat, információ, tudás. Metaadatok. Strukturált, szemi-strukturált és nem strukturált adatok

Adat

A körülöttünk lévő világ egy része,ami értelmezhető ugyan,de nem értelmezzük.

Információ

Az adathoz rendelünk egy értelmet,egy jelentést.

Tudás

Kontextusba helyezett információ.

Metaadat

Adat, az adatról. Segéd adatok.

Szerkezeti(Strukturális) metaadat

pl. Hol található egy fájl fizikailag

Szemantikus(Üzleti információs) metaadat

Hogyan kell értelmezni egy adatot.

Üzemeltetési metaadat

Mi történt az adatokkal. pl. mikor lett módosítva.

Strukturált adat

Olyan adat,amire strukturális $\text{metaadat} << \text{adat}$ .

Semi-struktúrált adat

Olyan adat,amire struktúrális $\text{metaadat} \approx \text{adat}$ .

Nem struktúrált adat

Olyan adat,amihez egyáltalán nem értelmezünk.

\clearpage

Adatbázis-kezelő fogalma, feladatai, felépítése, használói

Adatbázis kezelő fogalma

Az adatbáziskezelő, olyan hardware- softwarerendszer, amelyet 3 fő tulajdonság jellemez:

  • nagy adatmennyiség
  • gazdag struktúra
  • hosszú életciklus

Feladatai

Adatok sémájának meghatározása

A felhasználónak meg kell tudnia határoznia az adatbázis sémáját,azaz az adatok logikai rendjét. Ezt tipikusan egy adatdeviníciós nyelven teheti meg(data definition language,DDL). Ezeket az ún. technikai metaadatokat egy speciális védett helyen kerülnek eltárolásra

Adatok tárolása

A séma meghatározása után felvehetünk adatadokat az adatbázisba.

Hozzáférés az adatokhoz

A felhasználónak lehetősége lehet az egyes adatok megkeresésére, módosítására, valamint törléásére. Ezt tipikusan egy adatlekérdező és -manipulációs nyelven teheti meg(data manipulation language,DML).

Adatbázis-menedzser

A DBMS központi része az adatbázis-menedzser (database manager), amely a lefordított séma alapján kezeli a felhasználói lekérdezéseket

Adatvédelem(privacy)

Nem minden felhasználó férhet hozzá minden adathoz. A kölönböző felhasználókhoz külön jogokat rendelünk. Lehet olyan felhasználó,aki csak a olvasni tudja a tárolt adatokat, lehet olyan felhasználó, aki olvasni és módosítani is tudja az adatokat,de lehet olyan is,aki egyáltalán nem fér hozzá az adatokhoz.

Adatbiztonság(security)

Bizonyos adatok, igen nyagy értéket képviselhetnek, és ezért semmi képpen nem toleráljuk elvesztésüket,vagy részleges elvesztésüket. Ezért különböző eszközöket alkalmazunk az adatok biztonsága érdekében. Pl. naplózás,rednszeres mentés,kettőzött állományok elosztott működés, stb.

Integritás

Fontos,hogy az adabázisban tárolt adatok helyesek legyenek, ne legyenek ellentmondások. Ezért ezeket ellenőrizni kell.

Formai ellenőrzés

Ez viszonyla egyszerú elvégezni. Csak meg kell nézni hogy az adat megfelel-e egy elvárt formának. Pl. egy keresztnév nem tartalmaz számokat vagy testmagasság nem lehet három és fél méter (domain sértés).

Referenciális integritás

Számos esetben kell annak a feltételnek teljesülnie, hogy az adatbázisból az egyik helyről kiolvasott adatelemnek meg kell egyeznie valamely más helyről kiolvasott másik adatelemmel

Strukturális integritás

Ellenőriznünk kell, hogy nem sérült-e meg valamely feltételezés, amelyre az adatbázis szerkezetének megtervezésekor építettünk. Gyakori hiba, az egyértelműség megszűnése(pl több feleség). Ide tartoznak az adatbáziskényszerek ellenőrzése is.

Szinkronitás

Fontos,hogy a különböző felhasználók által, egyidőben végzett műveleteknek ne legyenek nemkívánatos mellékhatásai. Ezt tanzakciókezeléssel módszereivel oldjuk meg. pl. zárak.

Felépítése

A felépítésének leírásához egy rétegmodellt alkalmazunk. A legegyszerűbb adatbázis kezelő modelle 3 rétegből áll:

Fizikai adatbázis

Itt valósul meg az adatok,valamint az adat struktúrák fizikai tárolása.

Fogalmi(logikai) adatbázis

Ez a való világ egy részének leképezése,egy sajátos modell,ahogyan az adabázis tükrözi a valóság egy részét.

Nézetek

Ez az amit a felhasználók látnak. Az adatbázisban szereplő adatok és metaadatok egyes megjelenítései.A nézetekhez tartozó sémákat gyakran külső sémának (external schema) is nevezik.

Felhasználói

Képzetlen felhasználó (naive user)

A felhasználók legszélesebb rétege, akik csak bizonyos betanult ismeretekkel rendelkeznek a rendszerről.

Alkalmazás programozó

Az a szakember, aki a (képzetlen) felhasználó által használt programot készíti és karbantartja. Ez olyan feladat, amely programozót igényel, de megoldásához nem feltétlenül szükséges, hogy az illető belelásson az adatbázis belső szerkezetébe is.

Adatbázis adminisztrátor

Hagyományosan így nevezzük azt a személyt, aki az adatbázis felett gyakorlatilag korlátlan jogokkal bír. Kizárólag ő végezhet egyes feladatokat,mint pl:

Generélás

Adatbázisok létrehozása, szerkezetének kialalítása.

Jogosultságok karbantartása

A hozzáférések jogának naprakészen tartása, módosítása.

Szerkezetmódosítás

Az adatbázis eredeti szerkezetének

Mentés-visszaállítás.

Célszerű lehet adatbiztonsági okokból időnként vagy bizonyos időközönként másolatot készíteni az adatbázisról. Ha az adatbázis megsérül, ez a másolat teszi lehetővé a visszaállítást a mentés időpontjának állapotába.

DBMS tervező/programozó (DBMS designer/programmer)

Tudja, hogyan kell DBMS-t készíteni, ami különösen specializált tudást igényel. \clearpage

Heap szervezés

Általános jellemzői

Jelentése halmaz, kupac. Ez a legegyszerűbb tárolási megoldás. Legalább annyi blokkot használ fel,amennyit a rekordok száma és mérete megkövetel,de nem rendelünk hozzás semmilyen segédstruktúrát.

Műveletek heap szervezésben

Keresés

Mivel nem rendelkezik semmilyen segéd struktúrával ezért lineáris keresést alkalmazunk. Ez általánosan $\frac{\text{blokkok száma}+1}{2}$ blokkműveletet igényel. (Mivel egy keresés nem végezhető el 0 blokkműveletből,ezért kell a $+1$ )

Törlés

Először meg kell keresni a törlendő rekodot,majd a felécben jelezni,hogy a rekord felszabadult. Ezek után a megváltoztatott blokkot vissza kell írni.

Következményei: Az előbb felvázolt metódus egy gyakori következménye a szétszódódott lemezterület. Erre megoldást jelenthet a lemezterületek összegyűjtése és egyesítése.

Beszúrás

Először mindenképpen ellenőrizni kell a rekod egyedidégét,majd szabad tárolóhelyet kell találni. Ha nincs, állománybővítés szükséges(adminisztrátor feladata).

Módosítás

Először meg kell keresnünk a blokkot,amiben a keresett rekord található. Majd a rekord módosítása után a blokkot vissza kell írni a háttértárra. \clearpage

Hash-állományok

A hash-címzés során a kesesés kulcsának bitmintájából csonkolás segítségével is kinyerhető egy cím, amely alapján a keresett rekord megtalálható.

A legegyserűbb változatában egy ún. hash függvényt használunk,ami egy egyértelmű címet ad.Ezzel ugyan sokkal gyorsabb a keresés,mint hagyományos módszerekkel,de a háttértárakat ebben a formában igen rosszul használja ki.

Egy gyakori megoldás erre a vödrös hash-elés,ahol az egyes blokkok vödrökbe vannak elhelyezve. Keresés során a hash függvénnyel megkaphatjuk,hogy a keresett rekord melyik vödörben található.

Műveletek vödrös hash szervezésben

Keresés

Először lefutattjuk a kulcson a hash függvényt. Ez alapján tudjuk,hogy melyik vödörben található a keresett rekord. Ezek után a vödörben lényegében lineáris keresést alkalmazunk.

Beszúrás

Előszür a hash függvény alapján megkeressük,hogy melyik vödörbe tartozik a rekord,majd megkeressük a rekord kulcsát a vödörben. Ha megtalátuk akkor, hibaüzenetet küldünk. Ha nem találtuk meg,akkor az első szabad vagy törölt helyre beírjuk. Végül a módosított blokkot visszaírjuk a háttértárra.

Törlés

Megkeresés utá a felécben jelezni,hogy a rekord felszabadult. Ezek után a megváltoztatott blokkot vissza kell írni.

Módosítás

Ha nem a kulcs mezőt módosítjuk,akkor az a módosítás a szokott módon történik. Ha kulcs mező is módosul akkor a törlés és a beszurás műveletet kell alkalmazni egymás után. \clearpage

Indexelt állományok

Az indexelt szervezés alapgondolata: a keresés kulcsát egy ún. indexállományban (kb. katalógus) megismételjük, és a kulcshoz egy mutatót rendelünk, amely a tárolt adatrekord helyére mutat.

Az indexállományt mindig rendezve tartjuk. Ha a kulcs numerikus, akkor a rendezés triviális. Ha szöveges, akkor lexikografikus rendezést alkalmazhatunk. Összetett kulcs (composite key) esetén, vagyis amikor a kulcs több mezőből áll, definiálnunk kell a rendezés módját. Általában nincs akadálya, hogy több indexállományt is létrehozzunk ugyanazon adatállományhoz,különböző (vagy különbözően rendezett) kulcsmezőkkel.Ezért ebben a kontextusban a (keresési) kulcs lesz minden, ami szerint egy indexet felépítünk, illetve a keresést végezzük.

Két alapvetően különböző megvalósítás lehetséges:

  1. indexrekordot rendelünk minden egyes adatrekordhoz (sűrű index)
  2. indexrekordot rendelünk adatrekordok egy csoportjához, tipikusan az egy

blokkban levőkhöz. (ritka index) \clearpage

Ritka index, B*-fák

Ritka index

Ebben az esetben indexrekordot redot az adatrekordok egy csoportjához rendeljül. Ez hasonlít a szótárban található első és utolsó szó megjelölése az egyes oldalak tetején.

Keresés

Keresés során először az index állományon bináris keresést alkalmazunk a keresett kulcsra. Ha megtaláljuk, akkor megkapjuk,hogy a keresett rekord melyik blokkban található. Ezek után a blokkon belül lineáris keresést alkalmazunk (vagy ha rendezett akkor bináris keresést).

Beszúrás

Először meg kell keressük azt a blokkot, amelyben a rekodnak lennie kellene, ha az állományban lenne. Ha ebben a blokkban van elég hely, akkor a rekordot beírjuk a blokkba. Ha nincs , akkor helyet kell csinálnuk neki. Erre egy lehetőség lehet az, ha létrehozunk egy új blokkot és a korbábban megtalát blokk rekorjait megfelezzük az új blokkal. Ez után frissítenünk kell az index struktúrát is az blokkokban található kulcsoknak megfelelően.

Törlés

Először megkeressük azt a blokkot,amelyik a rekordot tartalmazza. Ha ebben a blokkban nem a legkisebb kulcsot akarjuk törölni,akkor ezt egyszerűen elvégezhetjük, a keletkező lyukat pedig mozgatással megszüntethetjük. Ha a legkisebb kulcsot töröltük a blokkban akkor az indexállományt is firssíteni kell.

Módosítás

A módosítás egyszerű, ha nem érint kulcsot. Ekkor meg kell keresni a szóban forgó rekordot, elvégezni a módosítást, majd az érintett adatblokkot visszaírni a háttértárra. Ha a módosítás kulcsmezőt is érint, akkor egy törlést követő beszúrás valósíthatja meg egy rekord módosítását.

B*-fák

Az alapgondolat az, hogy az indexállományban való keresést meggyorsíthatjuk, ha az indexállományhoz is (ritka) indexet készítünk hasonló szabályok szerint.Az eljárás mindaddig folytatható, ameddig az utolsó index egyetlen blokkba be nem fér.A legalsó szint mutatói az adatállomány egy-egy blokkjára mutatnak, a fölötte levő szintek mutatói pedig az indexállomány egy-egy részfáját azonosítják.

Keresés

Hasonló az egyszintű ritka indexek esetéhez,azomban ebben az esetben több lépésben kell elvégeznünk a keresést:

A fa (azaz az indexállomány) gyökeréből indulunk. Ebben a blokkban megkeressük azt a rekordot.amely kulcsa a legnagyobb azok közül,amelyek kisebbek még a keresett kulcsnál(vagy egyenlő). Ez a rekord a mutatója a fa egy alsóbb szintjére vezet. Ha az előző lépéseket addig ismételjük, amíg meg nem találjuk a keresett rekordot.

Beszúrás

Az eljárás nagy mértékben megyegyezik a ritka indexbe beszúrással, viszont ügyelni kell arra is, hogy a fa kiegyenlítettsége ne károsodjon. Ez azt is igényelhetni, hogy az index állomány minden szintjén néhány blokk megváltozzon.

Törlés

Megkeressük a kívánt adatot és töröljük. Az adatblokkokat lehetőség szerint összevonjuk. Összevonáskor, vagy ha egy adatblokk utolsó rekordját is töröltük, a megszűnt blokkhoz tartozó kulcsot is ki kell venni az indexállomány érintett részfájából. Ehhez adott esetben a fa minden szintjén szükség lehet néhány blokk módosítására.

Módósítás

Megegyezik a ritka index beli módosítás elvével. \clearpage

Sűrű indexek, előnyök és hátrányok

Minden adatrekordhoz tartozik egy index rekord. Ez általában még mindig a rekodot tartalamzó blokkra mutat,de elképzelhető az is, hogy közvetlenül az adatrekordra mutat. Emiatt az adatokat nem kell rendezni. Ez nagy előny a ritka indexel szemben, hiszen ez nagyban megnehezítette a beillesztést.

Fontos megjegyezni azomban, hogy a sűrű indexelés önmagában nem állományszervezési módszer. Hash vagy ritka indexre építhet.

A sűrű indexnek hátrányai is vannak. Ezek közé tartozik a nagyobb hely igény (a plusz indexelés miatt), az egyel több indirekció a rekord eléréséhez és több adminisztrációval is jár.

Viszont támogatja a több kulcs szerinti keresést és az adatállomány rekordjai szabadokká tehetők, ha minden további rekordhivatkozást a sűrű indexen keresztül történik.

Műveletek sűrűindexel

Keresés

Az indexállományban megkeressük a kulcsot, pl. bináris kereséssel. A hozzá tartozó mutatóval elérhetjük a tárolt rekordot.

Törkés

Először megkeressük a törlendő rekordot. A hozzátartozó törölt bitet szabadra állítjuk,majd a kulcsot kivesszük az indexállományból, és az indexállományt időnként tömörítjük.

Beszúrás

Keresünk egy szabad helyet a tárolandó rekordnak. Ha nem találunk akkor az állomány végére vesszük föl. A kulcsot és a tárolásm helyére hivetkozó mutatót a kulcs szerint berendezzük az indexállományba.

Módosítás

Sűrű indexelés esetén a módosítás viszonylag egyszerű: megkeressük a módosítandó rekordot tartalmazó adatblokkot, majd a módosított tartalommal visszaírjuk a háttértárra. Ha a módosítás kulcsmezőt is érintett, akkor az indexállományt újrarendezzük. \clearpage

Változó hosszúságú rekordok kezelése

Változó hosszú ságú rekordok oka

  • Egy mező hossza változó
  • Ismétlődő mező(csoport) van a rekordban

Megoldások

Általános megoldás

Egy rekord változó hosszúságú részeit a rekord mezőlistájának a végén helyezzük el. Így a rekord eleje fix hosszúságú marad.

Megoldás változó hosszúságú mezőre

Gyakrori megoldás az,hogy a mező helyére egy fix hosszúságú mutatót rakunk,ahol a mező tényleges tartalma van. Így egy állomány csak egy féle rekordot tartalmaz.

Megoldás ismétlődő mezőkre

Erre több megoldás is létezik:

  • A maximális számú ismétlődésnek elegendő helyet foglalunk le minden rekordnak
  • Mutatók használata

\clearpage

Részleges információ alapján történő keresés

Gyakran megesik, hogy egy rekord több mezéjét is ismerjük és meg akarjuk keresni azokat a rekordokat, amelyek ugyanezen értékeket tárolják. A továbbiakban úgy vesszük, hogy egyik ismert mező sem kulcs.

Index felépítése

Egy lehetőség lehet több (esetleg minden) mezőre egy index felépítése. Ezek után minden megadott értékre alapján előállíthatunk rekord halmazokat, majd ezek metszetét képezve megkapjuk a kívánt eredményt. Ez nem túl praktikus.

Particionált(feldarabolt) hash-függvény

Veszünk egy hash függvényt, amely

\begin{align} h(m_1,m_2,\ldots,m_k)=h_1(m_1)*h_2(m_2)*\ldots*h_k(m_k) \end{align}

alakú, ahol az $m_i\text{-k}$ a rekord összes $k$ darab, releváns mezőjének az értékeit jelentik, $h_i$ az $i\text{-edik}$ mezőre alkalamazott hash függvény komponens, a $*$ pedig a konkatonáció (összefűzés) jele.

Az ismert mezők értékei alapján meghatározhatjuk az $N$ hosszúságú bitmintának az ismert darabjait. Mindenazon vödröket kell megnézni amelyeknek a sorszáma illeszkedik a kapott bitmintára. \clearpage

Több kulcs szerinti keresés támogatása

Fontos, hogy egy adatbáziskezelő ne csak elsődleges kulcs szerint tudjon keresni, hanem egyéb mezők alapján is. Ezeket a mezőket keresési kulcsoknak nevezzük.

Indexelt megoldás

Invertált állomány fogalma

Azt az indexállományt, amely nem kulcsmezőrea tartalmaz indexeket, invertált állománynak nevezzük.

Invertált állomány mutatói

Az invertált állomány mutatói lehetnek:

  1. <<elso>>Fizikai mutatók, amelyek pl. mutathatnak

    1. <<elso.a>>közvetlenül az adatállomány megfelelő blokkja (esetleg rekordja)
    2. <<elso.b>>az adatállomány elsődleges kulcsa szerinti (sűrű) indexállomány megfelelő rekordjára
  2. <<masodik>> Logikai mutatók, amelyek az adatállomány valamely kulcsának értékét tartalmazzák

Az /Bazsalanszky/adatb/src/branch/master/elso.a esetben az adatállomány rekordjai kötöttek és ráadásul csak egyetlen invertált állomány esetén használható.

Az /Bazsalanszky/adatb/src/branch/master/elso.b esetben egyel több indirekción keresztül elrejtjük a keresett rekordot, de az adatrekord megváltoztatásakor csak az érintett mezőhöz (vagy mezőkhöz) tartozó invertált állományt kell frissíteni.

A /Bazsalanszky/adatb/src/branch/master/masodik. lehetőségben az adatállomány rekordjai szabadok lehetnek, viszont nem ismerjük a keresett rekord címét. \clearpage

Adatmodellek, modellezés

Amikor egy adatbázist létrehozunk a cél az, hogy egy kiválasztott valós dologról úgy tároljunk adatokat, hogy utána később ugyanarról a dologról információt tudjunk kinyerni. A legtöbb esetben nem tudunk minden adatot eltárolni egy adott témakörrel kapcsolatban, ezért csak az adatok egy részét tároljuk. Az eltárolni kívánt adatokat klasszikus modellezési eszközökkel választjuk ki: a fontos információkat megtartjuk, a kevésbé fontosakat elhanyagoljuk.

Adatmodell két része

  1. formalizált jelölésrendszer adatok, adatkapcsolatok leírására
  2. műveletek az adatokon

Adatmodellek osztályozása

A felhasználó számára az adatbázis egyik legfontosabb jellemzője az a forma, amelyben a tárolt adatok közötti összefüggések ábrázolva vannak. Mivel egy adatbázis struktúráját jelentős részben a rekordtípusok közötti kapcsolatok határozzák meg, ezért az adatmodelleket aszerint osztályozzuk, hogy a felhasználó szempontjából miként valósul meg az adatok közötti kapcsolatok ábrázolása.

Adatmodellek

  • Hálós adatmodell
  • Relációs adatmodell
  • Objektumorientált adatmodell

\clearpage

Az E-R modell és elemei

Az egyed kapcsolat (entity-relationship; ER) modell nem tekinthető adatmodellnek, hiszen nem definiál műveleteket az adatokon.

ER modell elemei

  • egyedtípusok
  • attribútumtípusok
  • kapcsolattípusok

Entitások(egyedek)

A valós világban létező, logikai vagy fizikai szempontból saját léttel rendelkező dolog, amelyről adatokat tárolunk.

Tulajdonságok(property)

Az entitásokat jellemzi; ezeken keresztül különböztethetőek meg az entitások.

Egyedhalmaz

Azonos attribútumokkal rendelkező egyedek összessége.

Kapcsolatok

Entitások névvel ellátott viszonya.

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 lehet kapcsolatban.

Több-egy kapcsolat

Egy K : E1, E2 kapcsolat több-egy, ha E1 példányaihoz legfeljebb egy E2-beli példány tartozhat, viszont E2 példányai tetszőleges számú E1-beli példányhoz tartoznak.

Több-több kapcsolat

Egy K : E1, E2 kapcsolat több-több, ha E1 példányaihoz is tetszőleges számú E2-beli példány tartozhat, és E2 példányaihoz is tetszőleges számú E1-beli példány tartozhat.

Kulcs

Az ER-modellezésben az attribútumok azt a halmazát, amely egyértelműen azonosít egy entitás példányait, kulcsnak nevezzük. \clearpage

Az E-R diagram, ISA kapcsolatok, gyenge egyedhalmazok

ER-diagram

Az ER modell egy grafikus megjelenítése az ER diagram.

ER-diagram elemei

ER modell elem Alakzat
Egyedhalmaz Téglalap
Attribútum Ellipszis
Kapcsolat Rombusz

Az aláhúzott attribútumok az adott egyedhalmaz kulcsait jelenti.

ISA kapcsolat

Gyakori az a modellezési szituáció, amikor egy entitáshalmaz minden eleme rendelkezik egy másik (általánosabb) entitáshalmaz attribútumaival, de azokon kívül még továbbiakkal is (specializáció). Ez a viszony a kapcsolatok egy sajátos típusával, az ún. „isa” kapcsolattal írható le. Az objektumorientált modelleknél kitüntetett szerepe van.

Gyenge egyedhalmaz

Gyakran előfordul, hogy egy entitáshalmaznak nem tudunk kulcsot kijelölni, ehelyett az egyedek azonosításához valamely kapcsolódó egyed(ek)re is szükség van. Ebben az esetben gyenge egyedhalmazokról beszélünk. Az identitását egy tulajdonos egyedhalmaz (owner entity set) biztosítja,amely a gyenge egyedhalmazzal több-egy kapcsolatban áll. Az ilyen kapcsolat neve: determináló kapcsolat. \clearpage

A relációs adatmodell: adatok strukturálása és műveletek

Struktúrája

A relációs adatmodell alapját, ahogyan a neve is árulkodik róla, relációk alkotják.

Reláció

Halmazok Descartes szorzatának részhalmaza.

A halmazokban található értékek egy-egy ún. tartományból (domain) kerülnek ki.

Fontos megjegyezni, hogy alapvetően a relációban tárolt elemek sorrendjének nincs jelentősége. Sőt az attribútumok nevének sincs jelentősége a modellre nézve, de egy adatbázis akkor jó, ha információt tudunk kinyerni belőle. Ehhez viszont szükséges az, hogy az egyes relációk, attribútumok valamilyen, a modell szempontjából értelmezhető információval rendelkezzen.

Relációs séma

A relációban tárolható attribútumok halmaza.

Ha egy adatbázis több relációs sémát is tartalmaz, akkor a relációs sémák összességének neve adatbázis séma.

A relációk további jellemzői

A relációk foka

A relációban lévő oszlopok (attribútumok) száma.

A relációk számossága

A relációban található sorok száma

Műveletek

A relációs adatmodell a relációkon megengedett műveletek meghatározásával válik teljessé. Ezen műveletekből épül fel az ún. relációs algebra (relational algebra). \clearpage

Relációalgebra

Egyesítés, Unió

Az attribútumok száma mindkét relációban ugyanannyinak kell lennie, de az egyes attribútumok nevének és értelmezésének nem feltétlenül kell megegyeznie.

Különbség

Ugyanazok a feltételek szükségesek,mint az egyesítés műveleténél.

Metszetképzés

Nem szükséges külön műveletként felvennünk, hiszen képezhető két különbség művelet segítségével:

\begin{align} A\cap B &= A\setminus(A\setminus B) \end{align}

Descartes szorzat

Két halmaz Descartes szorzatának attribútumainak száma a két reláció attribútumainak összege, a benne található adatok pedig a relációk összes sorának összes kombinációja.

Jelölése: $r_1\times r_2$

Vetítés, projekció

Vetítés során a reláció egyes kiválasztott attribútumait megtartjuk, a többit pedig töröljük.

Jelölése: $\pi_{A,B}(r_1)$

Kiválasztás, szelekció

A kiválasztás művelete alatt, azt értjük, amikor egy részhalmazt képezünk egy $r$ relációból, egy meghatározott logikai formula alapján. A formulát a reláció összes során kiértékeljük, és csak azokat tesszük bele a részhalmazba, amelyre a formula igaz értéket kap.

Jelölés: $\sigma_{F}(r)$, ahol az $F$ a kiértékelendő logikai formulát jelöli, vagy más néven a szelekciós feltételt.

A formula elemei

  • Konstansok
  • Reláció attribútumainak azonosítója
  • Aritmetikai összehasonlítók (pl. $<,>,=,\neq,\ldots$)
  • logikai operátorok ($\wedge$ $\vee$ $\neg$)

Természetes illesztés (natural join)

Vegyük két olyan relációt, amelyeknek van legalább egy azonos nevű attribútumok. Ekkor természetes illesztés alatt azt a műveletet érjük, amikor a két reláció összes elemét összefűzzük (Descartes szorzat), majd azokat a sorokat választjuk ki, amelyekben a megegyező nevű attribútumok megegyező értéket tartalmaznak.

Jelölés:

\begin{align} r\Join s &= \pi_{R\cup S}\sigma_{(r.X_1=s.X_1)\wedge\ldots\wedge(r.X_n=s.X_n)}(r\times s) \end{align}

$\Theta\text{-illesztés}$

Legyen $r$ és $s$ két reláció, $\Theta$ pedig egy kvantormentes feltétel, melyet az $r$ és $s$ relációk egy-egy attribútuma között definiálunk. A táblák Descartes-szorzatából a rekordpáron értelmezett $\Theta$ feltétel szerint választunk ki sorokat: $t = \sigma_\Theta(r\times s)$.

Jelölése: $r \underset{\Theta}{\Join} s$

Hányados

Jelölje $r \div s$ azt a relációt, amelyre igaz az, hogy az $s\text{-sel}$ alkotott Descartes-szorzata a lehető legbővebb részhalmaza $r\text{-nek}$ : $(r \div s) \setminus s \subseteq r$ \clearpage

Sorkalkulus, oszlopkalkulus

Sorkalkulus

Fogalma

A relációs sorkalkulus egy elsőrendű nyelv, amely kvantorokat is tartalmazhat és a kvantorok sorvektor változókat kvantifikálhatnak.

Felépítése

A nyelv szimbólumból atomokat épít fel, amelyek formulákká rakhatók össze, a formulák pedig egy kifejezéssé építhetők, amelyek segítségével relációk írhatók le.

Szimbólumai

  • Zárójelek: (,)
  • Aritmetikai relációk $<,>,=,\neq,m,\leq,\geq$
  • logikai műveletek $\vee,\wedge,\neg$
  • Sorváltozók: $s^{(n)}$, $n$ változós
  • sorváltozók komponensei: $s^{(n)}[i]$,ahol $1\leq i \leq n$
  • (konstans) relációk: $R^{(m)}$, $m$ változós
  • konstansok
  • kantorok: $\exists,\nexists,\forall$

Atomok felépítése

  • $R^{(m)}(s^{(m)})$
  • $s^{(n)}[i]\Theta u^{(k)}[j]$, ahol $1\leq i \leq n$, $1\leq j \leq k$ és $\Theta$ aritmetikai relációs jel
  • $s^{(n)}[i]\Theta c$
  • $R^{(m)}(c_1,c_2,\ldots,c_n)$

Formulák felépítése

  • minden atom formula
  • Ha $\Psi_1$ és $\Psi_2$ formulák, akkor $\Psi_1\vee\Psi_2$, $\Psi_1\wedge\Psi_2$ és $\neg\Psi_1$ is formulák
  • Ha $\Psi$ formula és $s^{(n)}$ egy szabad sorváltozója, akkor $(\exists s^{(n)})\Psi$ és $(\forall s^{(n)})\Psi$ is formulák, amelyben $s^{(n)})$ már kötött sorváltozó

Kifejezések felépítése

\begin{align*} \big\{s^{(m)}\big|\Psi(s^{(m)}\big\} \end{align*}

ahol $\Psi$ olyan formula, amelynek $s^{(m)}$ az egyetlen szabad sorváltozója.

Tétel

Minden, az $R_k^{(f_k)}\subseteq A^{f_k}$, ($k=1,2,\ldots,r$) relációból felépített relációs algebrai kifejezéshez van olyan $\Psi(s^{(m)})$ sorkalkulus formula, hogy $\Psi$ csak az $R_k^{(f_k}\text{-k}$ közül tartalmaz relációkat és az $E$ kifejezés megegyezik az $\big\{s^{(m)}\big|\Psi(s^{(m)}\big\}$ kifejezéssel.

Oszlopkalkulus

Az oszlopkalkulus elsősorban abban különbözik a sorkalkulustól, hogy sorváltozók helyet egyszerű változók szerepelnek benne. Ennek köszönhetően egy kicsivel egyszerűbb kifejezni vele bizonyos lekérdezéseket.

Szimbólumai

  • \ldots
  • oszlopváltozók: $u_i$
  • \ldots

Atomok felépítése

  • $R^{(m)}(x_1,x_2,\ldots,x_m)$, ahol $x_1,x_2,\ldots,x_m$ konstansok vagy oszlopváltozók.
  • $x\Theta y$, ahol $x$ és $y$ konstansok vagy oszlopváltozók és $\Theta$ aritmetikai relációjel.
  • $\ldots$

Formulák felépítése

  • $\ldots$

Kifejezések felépítése

\begin{align*} \big\{x_1,x_2,\ldots,x_m\big|\Psi(x_1,x_2,\ldots,x_m)\big\} \end{align*}

ahol $\Psi$ olyan formula, amelyek szabad változói csak $x_1,x_2,\ldots,x_m$

Tétel

Rögzített $A$ interpretációs halmaz és $R_k^{(n_k)}\subseteq A^{n_k}$ 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. \clearpage

Biztonságos sorkalkulus

A biztonságos sorkalkulus célja az, hogy a sorkalkulus kifejezések kiértékelhetőek legyenek számítógépen kezelhető méretű relációk/véges idő mellett is.

Formula doménje

$\text{DOM}\Psi\equiv\{\Psi\text{-beli alaprelációk összes attribútumának értékeik}\}\cup\{\Psi\text{-ben előforduló konstansok}\}$

Biztonságos kifejezés

$\{t|\Psi(t)\}$ biztonságos, ha

  1. minden $\Psi(t)\text{-t}$ kielégítő $t$ minden komponense
  2. $\Psi\text{-nek}$ miden $(\exists u)\omega(u)$ alakú részformulájára teljesül, hogy ha $u$ kielégíti $\omega\text{-t}$ szabad változók valamely értéke mellett, akkor $u$ minden komponense $\text{DOM}(\omega)\text{-beli}$

Tétel

A relációs algebra és a biztonságos sorkalkulus kifejezőereje ekvivalens. \clearpage

Relációs lekérdezések heurisztikus optimalizálása

A heurisztikus optimalizálás során, relációs algebrai műveletekből egy fát építünk. Ezt felhasználva próbáljuk a műveletek sorrendjét és felépítését módosítani, hogy kiválasszuk a leggyorsabb, még a helyes eredményt kapjuk.

Első lépés

A lekérdezés kanonikus alakjából indulunk ki. Vegyük először a kiválasztott relációk Descartes szorzatát, majd hajtsuk végre a szekciót, végül alkalmazzuk a kívánt projekciót.

Második lépés

Itt a szelekciós feltételeket próbáljuk meg süllyeszteni Ehhez fel kell használni a relációs algebrai kifejezések ekvivalenciáját A célja az input relációkat, a további műveletekhez szükséges részét redukáljuk le amennyire csak lehet.

Harmadik lépés

Ebben a lépésben a fában szereplő leveleket (azaz relációkat) próbáljuk minél jobb helyre rendezni. Ez akkor hasznos, ha ezzel nagyságrendekkel kisebb Descartes szorzatok jönnek létre.

Negyedik lépés

Előfordulhat, hogy a join megegyezik a Descartes-szorzattal. Ha ezt egy szelekció követi, akkor vonjuk össze a kettőt egy $\Theta\text{-illesztés}$ műveletté, így kevesebb rekordot kell generálni.

Ötödik lépés

Most a vetítéseket fogjuk a fában süllyeszteni, amennyire csak tudjuk. Ehhez új vetítéseket is létrehozhatunk, ha szükséges. \clearpage

Relációalgebraikifejezések transzformációi, ekvivalens kifejezések

A lekérdezés optimalizáció egy fontos eleme a relációs kifejezések transzformációja. Ehhez különböző ekvivalencia szabályokat alkalmazunk.

Ekvivalencia szabályok

Szelekció kaszkádosítása

\begin{align} \sigma_{\theta_1\wedge\theta_2}(E)=\sigma_{\theta_1}(\sigma_{\theta_2}(E)) \end{align}

Szelekció kommutativitása

\begin{align} \sigma_{\theta_1}(\sigma_{\theta_2}(E))=\sigma_{\theta_2}(\sigma_{\theta_1}(E)) \end{align}

Szelekció kaszkádosítása

\begin{align} \pi_{L_1}(\pi_{L_2}(\ldots\pi_{L_n}(E)\ldots))=\pi_{L_1}(E) \end{align}

A $\Theta\text{-illesztés}$ és a Descartes-szorzat kapcsolata

\begin{align} \sigma_\theta(E_1\times E_2) &= E_1\underset{\theta}{\Join}E_2 \\ \sigma_{\theta_1}(E_1\underset{\theta_2}{\Join}E_2) &= E_1\underset{\theta_1\wedge\theta_2}{\Join}E_2 \end{align}

Természetes illesztés asszociativitása

\begin{align} (E_1\Join E_2)\Join E_3= E_1 \Join (E_2\Join E_3) \end{align}

Szelekció és projekció kapcsolata

\begin{align} \pi_{A_1,A_2,\ldots,A_n}(\sigma_c(r)) &= \sigma_c(\pi_{A_1,A_2,\ldots,A_n}(r)) \end{align}

Halmazműveletek kommutatívak

Valóban.

Demorgen azonosságok

Itt is alkalmazhatóak.

STB

Ennél jóval több van. Csak egy pár fontosabbat soroltam itt fel. \clearpage

Relációs lekérdezések költségbecslés alapú optimalizálása

Ez egy jóval kifinomultabb metódus. Egy költség függvényt definiálunk, és ezek után azt a végrehajtási tervet alkalmazzuk, amelyre ez a függvény a legkisebb értéket adta.

Katalógusadatok

A költségbecslést segítő metaadatokat katalógus adatoknak nevezzük. Ilyen adat például a rekordok/blokkok száma, a relációhoz tartozó indexek, egyes lekérdezések költsége

Költsége

Ezeket az adatokat folyamatosan frissíteni kell. Ez bizonyos esetekben igencsak költséges lehet, jól meg kell gondolni, hogy ezt mikor tesszük meg.

Költség meghatározása

A költségek meghatározása elsősorban a blokkműveletek számára szoktunk optimalizálni,hiszen ez független a rendszer terhelésétől, valamint ennek a műveletnek általában nagyságrendekkel nagyobb az idő igénye, mint a processzor és memória műveleteknek. Ez viszont egyáltalán nem mondható kizárólagosnak, több szempontot is érdemes figyelembe venni. Jelölése:

\begin{align} E_{\text{alg.}}=\text{Az algoritmus becsült költsége (estimate)} \end{align}

\clearpage

Katalógusban tárolt információk

A katalógus adatai fontos szerepet játszanak a lekérdezés optimalizációban. Ezek segítségével lehet megbecsülni az egyes lekérdezések költségét.

Általános információk

  • $n_r$ : az $r$ relációban levő rekordok (elemek) száma (number)
  • $b_r$ : az $r$ relációban levő rekordokat tartalmazó blokkok (blocks) száma
  • $s_r$ : az $r$ reláció egy rekordjának nagysága (size) bájtokban
  • $f_r$ : mennyi rekord fér az $r$ reláció egy blokkjába (blocking factor)

  • $V(A, r)$: hány különböző értéke (Values) fordul elő az $A$ attribútumnak az $r$ relációban.

    • $V(A, r) = |\pi_A (r)|$
    • $V(A, r) = n_r$ , ha az A kulcs

  • $SC(A, r)$: azon rekordok várható száma, amelyek kielégítenek egy egyenlőségi feltételt az $A$ attribútumra (Selection Cardinality), feltéve, hogy legalább egy rekord kielégíti ezt az egyenlőségi feltételt.

    • $SC(A, r) = 1$, ha $A$ egyedi (vagy kulcs)
    • Általános esetben $SC(A, r) =\frac{n_r}{V(A,r)}$
  • Ha a relációk rekordjai fizikailag együtt vannak tárolva, akkor
\begin{align} b_r&= \left\lceil\frac{n_r}{f_r}\right\rceil \end{align}

Katalógus információk az indexekről

  • $f_i$ : az átlagos pointer-szám a fa struktúrájú indexek csomópontjaiban, mint pl. a

B* fáknál, azaz a csomópontokból induló ágak átlagos száma.

  • $HT_i$ : az i index szintjeinek a száma, azaz az index magassága (Height of Tree).

    • Az r relációt tartalmazó heap-szervezésű állományra épített B* fa esetén $HT_i=\lceil\log_{f_i}{b_r}\rceil$
    • hash-állománynál HTi = 1.
  • $LB_i$ : az $i$ index legalsó szintű blokkjainak a száma, azaz a levélszintű indexblokkok száma (Lowest level index Block)

\clearpage

A lekérdezés költsége: szelekció, indexelt szelekció, join műveletek és algoritmusok, egyéb műveletek.

Szelekciós művelet költségbecslése

Algoritmusok alapján

  • (A1) Lineáris keresés:

    • költsége: $E_{A1}=b_r$

  • (A2 )Bináris keresés:

    • Feltétele:

      • A blokkok folyamatosan helyezkednek el a diszken
      • Az $A$ attribútum szerinte rendezett
      • Szelekció feltétele egyenlőség
    • Költsége: $E_{A2}=\lceil\log_2(b_r+1)\rceil+\left\lceil\frac{SC(A,r)}{f_r}\right\rceil-1$

Indexelt szelekciós algoritmusok

Elsődleges index: segítségével a háttértáron a rekordokat a tényleges fizikai sorrendjében tudjuk elérni.

  • (A3) Elsődleges index használatával, egyenlőségi feltételt a kulcson vizsgálva

    • Költsége $E_{A3}=HT_i+1$

  • (A4) Elsődleges index használatával, egyenlőségi feltétel nem kulcson

    • Költség: $E_{A4}=HT_i+\left\lceil\frac{SC(A,r)}{f_r}\right\rceil$

  • (A5) Másodlagos index használatával, egyenlőségi feltétel mellett

    • $E_{A5}=HT_i+1$, ha $A$ kulcs
    • $E_{A5}=HT_i+SC(A,r)$, ha $A$ nem kulcs

Összehasonlítási szelekció

Most vegyük a $\sigma_{A\leq v}$ alakú szelekciókat.

  • Ha nem is merjük $v$ értékét, akkor átlagosan $\frac{n_r}{2}$ rekordot elégít ki
  • Ha ismerjük és egyenletes eloszlást feltételezünk akkor átlagosan $n_r\cdot\left(\frac{v-\min{(A,r)}}{\max{(A,r)-\min{(A,r)}}}\right)$

  • (A6) Elsődleges index használatával

    • $E_{A6}=HT_i+\frac{b_r}{2}$, ha $v$ nem ismert
    • $E_{A}=HT_i+\left\lceil\frac{c}{f_r}\right\rceil$, ahol $c$ jelöli a rekordok számát és $v$ ismert

  • (A7) Másodlagos index

    • $E_{A7}=HT_i+\frac{LB_i}{2}+\frac{n_r}{2}$, ha $v$ nem ismert

Join műveletek

Típusai

Természetes illesztés
\begin{align} r_1\Join r_2&= \pi_{A\cup B}(\sigma_{R1.X=R2.X}(r_1\times r_2)) \end{align}
Külső illesztések
  • Bal oldali külső illesztés $r_1*(+)r_2$
  • Jobb oldali külső illesztés $r_1(+)*r_2$
  • Teljes külső illesztés $r_1(+)*(+)r_2$
Theta illesztés
\begin{align} r_1 \Join_\theta r_2 = \sigma_\theta(r_1\times r_2) \end{align}

Egymásba ágyazott ciklikus illesztés (Nested loops join)

Két egymásba ágyazott ciklus használatával hajtja végre a join műveletet:

  1. Végig megy az egyik reláció összes rekordján, az ehhez tartozókat fogjuk keresni
  2. Végig megy a másik reláció összes rekordján és megnézi,hogy az előző ciklus futó változójához megfelel-e

Legrosszabb esetben a költsége $b_r+n_r\cdot b_s$,de ha legalább az egyik befér a memóriába akkor a költség $b_r+b_s$ lesz.

Blokk alapú egymásba ágyazott ciklikus illesztés(block nested

loop join) Itt négy darab egymásba ágyazott ciklust alkalmazunk:

  1. Végig megy az egyik reláció blokkjain
  2. Másik reláció blokkjai
  3. Első reláció beolvasott blokkjának rekordjai
  4. Másik reláció beolvasott blokkjának rekordjai

Ez legrosszabb esetben $b_r+b_r\cdot b_s$ a költsége, de sok memóriával $b_r+b_s$ -re le lehet csökkenteni.

Indexalapú egymásba ágyazott ciklikus illesztés(Indexed nested-loop join)

Az egyik reláción ($s$) van indexünk. Az első algoritmust írjuk át úgy, hogy a belső ciklus indexelt keresést alkalmaz, így a keresés az index alapján kisebb költséggel is elvégezhető.

Költsége: $b_r+n_r\cdot c$, ahol $c$ a szelekció költsége.

További join implementációk

  • Sorted merge join

    • A relációk a join feltételben meghatározott attribútumok mentén rendezzük,majd összefűzzük.

  • Hash join

    • Az egyik relációt hash-táblán keresztül érjük el, miközben a másik reláció egy adott rekordjához illeszkedő rekordokat keressük.

  • Egyéb

    • pl. bitmap join

Egyéb operációk

  • Ismétlődés kiszűrése (rendezés, majd törlés)
  • Projekciók(projekció,majd ismétlődések szűrése)
  • Unió(mindkét relációt rendezzük, majd összefésüléssel kiszűrjük az ismétlődéseket)
  • Metszet (mindkét relációt rendezzük, fésülésnél csak a másodpéldányokat tartjuk meg)
  • Különbség(mindkét relációt rendezzük, fésülésnél csak az első relációbeli rekordokat hagyjuk)
  • Aggregáció

\clearpage

Materializáció és pipelining

Materializáció

Ebben a módszerben az összetett kifejezésnek egyszerre egy műveletét hajtjuk végre, valamilyen rögzített sorrendben. Ehhez most is egy relációs algebrai fába foglaljuk a műveleteket, majd a levelektől (azaz a relációktól) indulva mindig azt a műveletet értékeljük ki, amelyik műveletnek éppen van rendelkezésre álló bemenete.

Pipelining

Itt egyszerre több elemi műveletet szimultán kiértékelése folyik, egy operáció eredményét azonnal megkapja a sorban következő operáció operandusaként.

Ez persze nem minden esetben működik, pl rendezés esetében. \clearpage

Kiértékelési terv kiválasztása

Az egyes műveletekre többféle algoritmust, metódust is megvizsgáltunk és közel sem triviális ezek kiválasztása. Tudnunk kell, hogy:

  • Milyen műveleteket
  • Milyen sorrendben
  • Milyen algoritmus szerint
  • és milyen workflow-ban értékeljük ki.

Költség alapú optimalizáció

Nem jó ötlet az összes ekvivalens kifejezést felsorolni, kiértékelni, majd a legjobbat kiválasztani. Ennek az az oka,hogy ezzel túl sok lehetőséget kell megvizsgálni. Ezért egy jobb megoldást biztosíthat a heurisztikus költségalapú optimalizálás. \clearpage

Relációs adatbázis sémák tervezése E-R diagramból

Egy ER-diagram megtervezése után fontos lehet, hogy a megtervezett modellt relációs adatmodellbe transzformáljuk, ezzel működőképessé téve. Ehhez transzformációt végzünk.

Transzformáció

  1. Az egyedhalmazokat olyan relációs sémában ábrázoljuk, amely tartalmazza az entitáshalmaz összes attribútumát. Ha van olyan egyedhalmaz, amely "isa" kapcsolatban van egy másik egyedhalmazzal, akkor a specializált egyedhalmazhoz rendelt relációs sémába az általánosabb egyedhalmaz attribútumait is fel kell venni.
  2. A kapcsolattípusokat olyan sémákká alakítjuk, amelyek attribútumai tartalmazzák a kapcsolatban szereplő összes reláció kulcsait is.

Ezen kívül számos más lehetőség van a kapcsolatok létrehozására, amelyek adott esetben jobbak is lehetnek. Ilyen pl. az idegen kulcsos megoldás. \clearpage

Anomáliák (módosítási, törlési, beszúrási)

A redundáns relációknak megfelelő adattárolással kapcsolatban egy sor kellemetlen jelenség fordulhat elő. Ezeket hagyományosan anomáliáknak nevezik.

Módosítási anomália

Ha egy adatot több helyen tárolunk és módosítani szeretnénk, akkor minden helyen meg kell azt változtatni. Ha ezt elmulasztjuk, akkor különböző helyekről különböző információt kapnánk. Az ilyen szituációk nem csak többletmunkát, hanem logikai ellentmondásokat is jelenthet.

Beszúrási anomália

Ennek alapja, hogy nem tudunk rekordot felvenni, ha van olyan adat, ami nem ismert és a tárolandó adattal meghatározott kapcsolatban áll.

Példa: egy új szállítót nem tudunk felvenni, ha még nem szállított semmit.

Törlési anomália

Ha csak egy attribútum értékét akarjuk törölni akkor előfordulhat,hogy ez csak az egész sor törlésével lehetséges (pl. ha az adott attribútum része valamely kulcsnak). Ezzel viszont olyan információt is törölnénk, amire még szükség lehet.

Erre egy megoldás lehet a relációk függőleges felbontása,de ez nem minden esetben alkalmazható. \clearpage

Adatbázis kényszerek, redundancia

Adatbázis kényszerek

Adatbázis kényszerek kényszerek alatt azokat a szabályokat értjük, amelyek segítségével korlátozni lehet az adatbázisunk tartalmát, olyan módon, hogy az valamilyen módon megfeleljen egy elvárásnak vagy elképzelésnek. Az alábbiak a leggyakrabban használt kényszerek:

  • értékfüggő kényszerek (pl. 0 < TESTMAGASSÁG < 300)

  • értékfüggetlen kényszerek.

    • Tartalmi függőség(pl. az idegen kulcsok értékeinek halmaza rész-

halmaza a neki megfeleltethető kulcsértékek halmazának)

  • Funkcionális függőség
  • Többértékű függőség

Redundáns reláció

Ha egy relációban valamely attribútum értéké a relációban található más attribútum(ok) értékéből ki tudjuk következtetni valamely ismert következtetési szabály segítségével, akkor a relációt redundánsnak nevezzük. \clearpage

Funkcionális függőségek

Definíció

Legyen adott az $R(A_1,A_2,\ldots,A_n)$ reláció séma, ahol $A_i\text{-k}$, $i=1,2,\ldots,n$ (alap)attribútumok. Legyen $X$ és $Y$ a reláció attribútumainak két részhalmaza: $X\subseteq R$ és $Y\subseteq R$. Ha bármely, az $R$ sémára illeszkedő $r$ reláció bármely két $t,t'\in r(R)$ sorára fennáll az, hogy ha $t[X]=t'[X]$, akkor $t[Y]=t'[Y]$ ($t[Z]:=\pi_Z(t)$), akkor azt mondjuk,hogy az $Y$ attribútumok funkcionálisan függenek $X$ attribútumoktól. Más megfogalmazásban azt is mondhatjuk, hogy az $X$ értékei meghatározzák az $Y$ értékeit. Mindezt így jelöljük: $X\rightarrow Y$ .

Determináns

Ha $X,Y\subseteq R$ és $X \rightarrow Y$, de $\nexists X'\subset X$, hogy $X'\rightarrow Y$, akkor $X\text{-et } Y$ determinánsának nevezzük.

Teljes függőség

Ha $X,Y\subseteq R$ és $X \rightarrow Y$, de $\nexists X'\subset X$, hogy $X'\rightarrow Y$, akkor azt mondjuk, hogy $Y$ teljesen függ $X\text{-től}$.

Részleges függés

Ha $X,Y\subseteq R$ és $X \rightarrow Y$ mellett $\exists X'\subset X$, hogy $X'\rightarrow Y$, akkor azt mondjuk, hogy $Y$ részlegesen függ $X\text{-től}$. \clearpage

Relációs sémák kulcsai

Kulcs

$X\text{-et}$ pontosan akkor nevezzük kulcsnak az $R$ relációs sémán, ha

  1. $X\rightarrow R$
  2. $\nexists X'\subset X$,hogy $X'\rightarrow R$.

Tehát, ha $R$ teljesen függ $X\text{-től}$

Szuper kulcs

$X\text{-et}$ szuper-kulcsnak nevezzük, ha igaz,hogy $X\rightarrow R$. Más szóval akkor, ha $X$ tartalmaz kulcsot.

Egyszerű kulcs

Ha egy kulcs csak egy attribútumból áll,akkor egyszerű kulcsról beszélünk. Ellenkező esetben összetett kulcsról van szó.

Tétel

Minden relációs sémának van kulcsa.

Elsődleges kulcs

Ha $X$ és $Z$ az $R$ relációs sémának egyaránt kulcsai, miközben $X\neq Z$, akkor az $R$ relációs sémának több kulcsa is van.

Ezek közül kiválasztunk egyet, amelyet elsődleges kulcsnak nevezünk. A többi kulcsot kulcsjelöltnek nevezzük.

Idegen (külső) kulcs

Adott egy $R$ és egy $R'$ relációs sémák. Tételezzük fel, hogy $R\neq R'$. Ha $\exists D \subseteq (R\cap R')$, hogy $D$ kulcsa $R'$ sémának, akkor $D$ neve az $R$ sémával kapcsolatban idegen kulcs.

Igaz funkcionális függés

Egy adott $R$ sémán az attribútumain értelmezett $F_R$ függéshalmaz mellett egy $X\rightarrow Y$ függés pontosan akkor igaz, ha minden olyan $r(R)$ reláción fennáll, amelyeken $F_R$ összes függése fennáll.

Jelölése: $F_R \models X\rightarrow Y$

Levezethető funkcionális függőség

Egy $W\rightarrow Z$ funkcionális függőség pontosan akkor vezethető le adott $F_R$ függőségből, ha az axiomák ismételt alkalmazásával $F_R\text{-ből}$ kiindulva megkaphatjuk $W\rightarrow Z\text{-t}$.

Jelölése: $F_R \vdash W\rightarrow Z$ \clearpage

Armstrong axiómái a funkcionális függőségekről

Adottak az $R$ sémán az $X$, $Y$, $Z$ attribútumhalmazok.

  1. Ha $X\subseteq Y$, akkor $Y\rightarrow X$ (reflexivitás vagy triviális függőség).
  2. Ha $X\rightarrow Y$ és $Y\rightarrow Z$,akkor $X \rightarrow Z$ (tranzitivitás).
  3. Ha $X\rightarrow Y$, akkor $XZ \rightarrow YZ$ (bővíthetőség)

Igazság tétel

Az armstrong axiómák igazak, alkalmazásukkal csak igaz függőségek állíthatók elő adott függéshalmazból.

Teljesség tétel

Az Armstrong axiómák teljesek, azaz belőlük minden igaz függőség levezethető. $F_R \models X \rightarrow Y \implies FR \vdash X \rightarrow Y$

Axiómák következményei

  1. $X \rightarrow Y$ és $X\rightarrow Z \models X \rightarrow YZ$(egyesítési szabály).
  2. $X \rightarrow Y$ és $WY \rightarrow Z \models XW \rightarrow Z$ (pszeudotranzitivitás).
  3. $X \rightarrow Y$ és $Z \subseteq Y \models X \rightarrow Z$ (dekompozíciós/felbontási szabály).

\clearpage

Az első normálforma (1NF)

Annak érdekében, hogy a fentebb említett anomáliák ne forduljanak elő, a relációs sémáinknak meg kell felelni egyes feltételeknek. Ezeket normálformáknak nevezik.

Nulladik normálforma

Ilyen alakúnak tekintünk minden olyan relációs sémát, amelyben legalább egy attribútum nem atomi abban az értelemben, hogy az attribútum értéke nem tekinthető egyetlen egységnek.

Első normálforma

Egy relációs séma 1NF alakú, ha csak atomi attribútum-értékek szerepelnek benne. \clearpage

A második normálforma (2NF)

Elsődleges és másodlagos attribútumok

Egy $R$ relációs séma $A\in R$ attribútuma elsődleges attribútum, ha $A$ eleme a séma valamely $K$ kulcsának. Egyébként $A$ másodlagos attribútum.

Második normálforma(2NF)

Egy 1NF relációs séma 2NF alakú, ha benne minden másodlagos attribútum a séma bármely kulcsától teljesen függ.

Más szavakkal: másodlagos attribútum nem függ egyetlen kulcs valódi részhalmazától sem.

Tétel

Minden 1NF séma felbontható 2NF sémákba úgy, hogy azok használatával az 1NF sémára illesztett, "eredeti" relációk helyreállíthatók. \clearpage

Harmadik normálforma (3NF)

Triviális függés

Ha az $X,Y$ attribútumhalmazokra igaz, hogy $Y\subseteq X$, akkor $X\rightarrow Y$ függőséget triviális függőségnek nevezzük, egyébként a függőség nemtriviális.

Tranzitív függés

Adott egy $R$ séma, a sémán értelmezett függőségek $F$ halmaza, $X\subseteq R,A\in R$. $A$ tranzitívan függ $X\text{-től}$, ha $\exists Y\subset R$, hogy $X\rightarrow Y$, $Y\not\to X$, $Y\to A$ és $A\notin Y$

Harmadik normálforma (3NF)

1. Definíció

Egy 1NF séma 3NF, ha $\forall A\in R$ másodlagos attribútum és $\forall X\subseteq R$ kulcs esetén $\nexists Y$, hogy $X\to Y$, $Y\not\to X$, $Y\to A$ és $A\not\in Y$

Más szavakkal: ha egyetlen másodlagos attribútuma sem függ tranzitívan egyetlen kulcstól sem.

2. Definíció

Egy 1NF $R$ séma 3NF, ha $\forall X\to A, X\subseteq R, A\in R$ nemtriviális függőség esetén

  • X szuperkulcs vagy
  • A elsődleges attribútum

Tétel

Az előző két definíció ekvivalens

Tétel

Ahhoz,hogy egy $(R,F)$ sémáról eldöntsük, hogy 3NF-e, elég az $F$ funkcionális függőségek vizsgálata.

Tétel

Minden legalább 1NF relációs séma felbontható 3NF sémába úgy, hogy azokból az eredeti reláció információveszteség nélkül helyreállítható.

Tétel

Ha egy séma 3NF alakú, akkor 2NF is egyben. \clearpage

A Boyce-Codd normálforma (BCNF)

A Boyce–Codd normálforma

1. Definíció

Egy 1NF séma 3NF, ha $\forall A\in R$ attribútum és $\forall X\subseteq R$ kulcs esetén $\nexists Y$, hogy $X\to Y$, $Y\not\to X$, $Y\to A$ és $A\not\in Y$

Más szavakkal: ha egyetlen attribútuma sem függ tranzitívan egyetlen kulcstól sem.

2. Definíció

Egy 1NF $R$ séma BCNF, ha $\forall X\to A,X\subseteq R,A\in R$ nemriviális függőség esetén $X$ szuperkulcs.

Tétel

Az előző két definíció ekvivalens.

Tétel

Ahhoz, hogy egy (R,F) sémáról eldöntsük, hogy BCNF-e, elég az $F\text{-beli}$ funkcionális függőségek vizsgálata.

Tétel

Ha egy séma BCNF alakú, akkor 3NF is.

Bizonyítás

Ez a definíció közvetlen következménye.

Tétel

A BCNF sémára illeszkedő relációk nem tartalmaznak redundanciát.(legalábbis funkcionális függőségek következtében)

Következmény

Emiatt egyetlen attribútum értékét sem lehet kikövetkeztetni más attribútumok értékeinek ismeretében, ismert funkcionális függőség alapján.

BCNF adatbázis

Egy adatbázis BCNF (3NF, 2NF, 1NF) alakú, ha a benne található összes relációs séma rendre legalább BCNF (3NF, 2NF, 1NF). \clearpage

ACID tulajdonságok adatbázis-kezelő rendszerekben

Tranzakció

Egy program egyszeri futása, amelyek vagy minden művelete hatásos, vagy belőle semmi sem.

ACID tulajdonságok

  • atomicitás (atomicitás, oszthatatlanság): vagy végigfut vagy nem
  • konzisztencia (consistency, ellentmondás mentes): csak sikeresen (teljes egészében) lefutott tranzakcióknak van hatása az adatbázis tartalmára, ekkor a tranzakciók az adatbázist egyik konzisztens állapotból egy másikba viszik át
  • izoláció (isolation): Az adatbázisokon úgy fussanak le a tranzakciók, mintha egyedül futna csak le
  • tartósság (durability): Ha egy tranzakció már sikeresen lefutott, akkor annak hatása ``nem veszhet el''.

\clearpage

lost update, non-repetable read, phantom read, dirty data

Lost update (elveszett frissítés)

Két tranzakció egyszerre ugyan azt az adategységet módosítani, úgy hogy az egyik felülírja a másik tranzakciót, így a az első módosítás elveszik.

Non-repeatable read (nem megismételhető olvasás)

Egy $T_1$ tranzakció különböző eredményeket kap egy adategység többszöri olvasásakor, mert egy másik, $T_2$ tranzakció időközben módosította azt.

Phanthom read (fantom olvasás)

Egy $T_1$ tranzakció többször is végrehajtja ugyanazt a lekérdezést, miközben egy másik, $T_2$ tranzakció olyan rekordokat szúr be vagy töröl, melyek kielégítik a $T_1$ lekérdezésének szelekciós feltételét. Így a korábbi lekérdezés más rekordhalmazt adhat vissza, mint az utána következő(k).

Dirty data(piszkos olvasás)

Egy $T_2$ tranzakció olyan – ún. piszkos - adatot olvas, melyet egy másik, $T_1$ tranzakció azelőtt írt az adatbázisba, hogy sikeresen befejeződött volna. Ha a $T_1$ tranzakció végül valóban sikertelennek bizonyul, akkor a piszkos adat az adatbázisból mihamarabb eltávolítandó. \clearpage

Problémák a zárakkal: pattok és éhezés

Zár (lock)

Hozzáférési privilégium egy adategységen, amely adható és visszaadható.

Legális ütemezés

Legális az ütemezés, amelyben

  • a lockolt adategységet fel is szabadítják
  • ha egy adategység már foglalt - mert egy másik tranzakció zárat tart fenn rajta -, akkor a tranzakció a zár feloldásáig várakozik

Problémák zárakkal

Patt

Ha egy $T_m$ tranzakció azért nem tud továbblépni, mert egy olyan $A$ adategységre vár, amin egy olyan $T_n\neq T_m$ tranzakció tart fenn zárat, ami azért nem tud továbblépni mert, ehhez olyan adategységhez kéne hozzáférnie, amin már $T_m$ tart fenn zárat, akkor pattról, holtpontról (deadlock) beszélünk.

Megoldási lehetőségek
  • A tranzakcióhoz szükséges összes adategységet már a kezdéskor lefoglalja. Ha valamely zárat nem kapja meg, akkor meg sem próbálkozhat egyetlen művelettel sem.
  • Ha egy tranzakció túl sokat várakozik, akkor valószínűleg patt-helyzetbe került, ezért abortálandó
  • Valamilyen egyértelmű sorrendet rendelünk az adategységekhez és zárat csak ennek sorrendjében lehet kérni.
  • Folyamatosan monitorozzuk a zárak elhelyezkedését, és ha valahol patthelyzetet érzékelünk akkor valamely tranzakciót, amely a pattot okozza, megszakítjuk.
Várakozási gráf

Olyan irányított gráf, ahol a csomópontjai a tranzakciók, egy élt pedig akkor rajzolunk a $T_i$ csomópontól a $T_j$ csomópont felé, ha $T_i$ tranzakció bármely okból várakoztatja $T_j$ tranzakciót úgy, hogy nem tud továbbmenni.

Tétel

Adott időpillanatban nincs patt $\Leftrightarrow$ a várakozási gráfban nincs kör, azaz a gráf DAG.

Éhezés (starving,livelock)

Ha egy tranzakció egy adategység lockolására vár, de közben más tranzakciók mindig lockolják előtte a kédéses adategységet, akkor éhezésről beszélünk.

Egy lehetőség az éhezés elkerülésére, ha feljegyezzük a sikertelen zárkéréseket, és ha egy adategység felszabadul, akkor zárat csak a zárkérések sorrendjében ítélünk oda (FIFO stratégia) \clearpage

Ütemezések fajtái

Ütemezés

Tranzakciók elemi műveleteinek összessége, melyben a műveletek időbeli sorrendje is egyértelműen meghatározott.

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, tehát időben nem lapolódnak át, akkor ez egy soros ütemezés.

Sorosíthatóság

Egy ütemezés pontosan akkor sorosítható, ha létezik olyan soros ütemezés, amelyek minden hatása a módosított adatokra azonos az adott ütemezéssel.

Izolációs elv

Feltételezzük, hogy egy tranzakció elvárt, korrekt eredménye az, amit akkor kapunk, ha a tranzakció futása közben más tranzakció nem fut.

Korrekt

Egy ütemezés pontosan akkor korrekt, ha sorosítható.

Ütemező

A DBMS azon része, amely az adatelérési igények megtérítése felett dönt (pl sorosíthatóság biztosítása). Ennek során

  • Engedélyezheti az egyes műveleteket

  • Ha ennek feltételei nem állnak fent, akkor

    • várakozásra kényszerítheti
    • abortálhatja

\clearpage

Tranzakció modellek

Egyszerű tranzakció modell

Egyszerű tranzakció modellről beszélünk ha:

  • csak egy fajta zár létezik
  • egy adatelemen egy időben csak egyetlen zár lehet.

sorosítási gráf, precedenciagráf

Olyan irányított gráf, amely csomópontjai tranzakciók és egy $T_i$ csomópontból egy $T_j$ csomópontba akkor húzunk élt, ha van olyan $A$ adategység, amely egy adott $S$ ütemezésben a $T_i$ tranzakció zárat helyezett el, majd a zár felszabadítása után először a $T_j$ tranzakció helyez el zárat.

Tétel

Egy $S$ ütemezés sorosítható $\Leftrightarrow$ a sorosítási gráf DAG. \clearpage

Kétfázisú zárolás (2PL)

Kétfázisú zárolás (2PL)

Egy tranzakció a kétfázisú zárolás protokollt követi, ha az első zárfelszabadítást megelőzni mindegyik zárkérés.

Tétel

Ha egy legális ütemezés minden tranzakciója a 2PL-t követi, akkor az ütemezés sorosítható.

Zárpont

Az az időpont, amikor egy kétfázisú protokoll szerinti tranzakció az utolsó zárját is megkapja.

RLOCK-WLOCK modell

A modell két fajta zárt definiál:

  • RLOCK: ha $T$: RLOCK A érvényes, akkor más tranzakció is olvashatja $A\text{-t}$, de írni egy sem írhatja
  • WLOCK: ha $T$: WLOCK A érvényes, akkor $T\text{-n}$ kívül más tranzakció nem fér hozzá $A\text{-hoz}$, sem írásra , sem olvasásra.

Tétel

Egy RLOCK-WLOCK modellbeli $S$ ütemezés sorosítható $\Leftrightarrow$ a fenti szabályok szerint rajzolt sorosítási gráf DAG.

Definíció

Egy RLOCK-WLOCK modell szerinti tranzakció kétfázisú, ha minden RLOCK és WLOCK megelőzi az első UNLOCK-ot.

Tétel

Ha egy ütemezésben csak kétfázisú, RLOCK-WLOCK modell szerinti tranzakciók vannak, akkor az ütemezés sorosítható. \clearpage

A 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.

Szabályai

  1. Egy tranzakció az első LOCK-ot akárhová teheti
  2. A további LOCK-ok csak akkor helyezhetők el, ha az adategység szülőjére az adott tranzakció már rakott zárat
  3. Egyazon tranzakció kétszer ugyanazt az adategységet nem zárolhatja

Tétel

A fa protokollnak eleget tevő legális ütemezések sorosíthatók. \clearpage

Figyelmeztető protokoll

Az egyszerű tranzakció modellt követjük, de egy csomópont zárolása a gyerek és az összes leszármazott csomópontok zárolását is jelenti(implicit zár).

Zárkonfliktus

Egy $T_2$ tranzakció, egy olyan adategységre tesz lockot, amely leszármazottját már egy $T_1$ tranzakció lezárt magának.

Figyelmeztető protokoll zárművei

  • LOCK A: zárolja $A\text{-t}$ és az összes leszármazott csomópontot is. Két különböző tranzakció nem tarthat fent zárat ugyanazon adategységen.
  • WARN A: $A\text{-ra}$ figyelmeztetést rak. Ekkor $A\text{-t}$ más tranzakció nem zárolhatja
  • UNLOCK A: eltávolítja a zárat vagy az UNLOCK-ot kiadó tranzakció által elhelyezett figyelmeztetést $A\text{-ról}$

További szabályok

  1. Egy tranzakció első művelete kötelezően LOCK gyökér vagy WARN gyökér
  2. LOCK A vagy WARN A akkor helyezhető el, ha $A$ szülőjén ugyanaz a tranzakció már helyezett el WARN-t.
  3. UNLOCK A akkor lehetséges, ha gyerekein már ugyanaz a tranzakció nem tart fenn sem LOCK-ot sem WARN-t
  4. Kétfázisú: az első UNLOCK után nem következhet LOCK vagy WARN

Tétel

A figyelmeztető protokollt követő legális ütemezés zárkonfliktusmentesek és sorosíthatóak. \clearpage

Tranzakcióhibák kezelése, commit pont

Mindeddig nem foglalkoztunk azokkal a problémákkal, amelyek akkor lépnek fel, ha egy tranzakció nem fut le teljesen, valamely ok miatt idő előtt befejeződik.

Tranzakció nem várt leállásának lehetséges okai

  1. tranzakció félbeszakad (felhasználó megszakítja, nullával osztás, nem fér bele valamely adategységbe)
  2. Az ütemező patt miatt kilövi
  3. Az ütemező kilövi, mert a sorosíthatóság így biztosítható
  4. valamely rendszerhiba lép fel, emiatt az adatbáziskezelő hibásan kezd működni
  5. a háttértár tartalma megsérült

Konzisztens állapot

Az adatbázisnak olyan állapota, amely csak teljesen lefutott tranzakciók hatását tükrözi.

Készpont (commit point)

Az az időpillanat, amikor egy tranzakció futása során minden befejeződött, ami a tranzakció 1-3. okok miatti abortját eredményezheti.

Piszkos adat

Olyan adat, amit az előtt írt valamely tranzakció az adatbázisba, mielőtt commitált volna.

Lavina

Azt a jelenséget, amikor egy tranzakciók piszkos adatot olvasnak be és ezzel végeznek el műveleteket, lavinának nevezzük, hiszen ezek az eredmények nem tekinthetők helyesnek. \clearpage

Szigorú kétfázisú protokoll

A tranzakcióhibák kezelésének igen gyakori módszere. Egy tranzakció ezt a protokollt követi, ha kétfázisú, továbbá

  1. nem ír az adatbázisba, amíg a készpontját el nem érte,
  2. a zárait csak az adatbázisba írás után engedi el.

Vegyük észre, hogy az 1. szabály ahhoz kell, hogy ne kelljen az adatbázist helyreállítani, ha egy tranzakció abortál (csak redo kell). A 2. szabály biztosítja valójában azt, hogy piszkos adatot ne lehessen olvasni – hiszen commit után nem lehet abort-, tehát a lavinákat elkerüljük.

Mindez természetesen csak akkor igaz, ha nem kell rendszerhibákkal is számolni, amelyek az írási folyamat megzavarásával eredményezhetik, hogy piszkos adat kerül az adatbázisba. Ez ellen azonban más módszerekkel kell védekezni

Tétel

A szigorú kétfázisú protokollt követő tranzakciókból álló legális ütemezések sorosíthatóak és lavinamentesek.

Bizonyítás

Az ütemezés sorosítható, mert kétfázisú; továbbá lavinamentes, mert nincs lehetőség piszkos adat olvasására. \clearpage

Agresszív és konzervatív protokollok

Tranzakciós protokoll kiválasztásánál fontos, hogy az adott protokoll mennyire ``hatékony''. A hatékonyságot nézhetjük úgy, hogy

  • egy adott tranzakció minél hamarabb fusson le
  • adott idő alatt minél több tranzakció fusson le sikeresen (tranzakció teljesítmény)

Ezek ellentmondásosak, és olykor az egyik sokkal fontosabb a másiknál, mégis, gyakran a tranzakció teljesítményét kívánjuk maximalizálni.

Agresszív protokoll, optimista konkurenciakezelés

Egy protokoll agresszív, ha megpróbál olyan gyorsan lefutni, amennyire csak lehetséges, nem törődve azzal, hogy ez esetleg aborthoz is vezethet.

Konzervatív protokoll, pesszimista konkurenciakezelés

Egy protokoll konzervatív, ha megkísérli elkerülni az olyan tranzakciók futtatását, amelyek nem biztos, hogy eredményesek lesznek. \clearpage

Védekezés rendszerhibák ellen

A rendszerhibák elleni védekezés általános módszere a (tranzakciós) naplózás. 6 A naplózásnak számos módja lehet, itt csak a leggyakoribbakra térünk ki.

Napló (journal, log)

A napló a mi értelmezésünk szerint az adatbázison végrehajtott változások története.

Ha tudható, hogy undo műveleteket nem kell a napló alapján végezni, akkor elég az adategység új értékének naplózása. Néha még ez is túl nagy méretű, ekkor esetleg az kerülhet a naplóba, hogy hogyan kell az adategység új értékét előállítani.

Alapszabály, hogy a naplót azelőtt írjuk, mielőtt a naplózott műveletre sor kerülne (kivétel: az abort művelet naplózása). \clearpage

Hatékonysági kérdések

Fontos, hogy a napló stabil tárban legyen eltárolva,hiszen ez használható helyreállításra. Ez viszont azzal jár, hogy az adatbázis blokkjai mellett a napló blokkjait is a merevlemezre kell írni. Erre gyakran valamilyen lapozási stratégiát alkalmaznak. Számos napló oldalt lehet egyidejűleg a memóriában és egy lapmenedzser gondoskodik a háttértárra.

Ha változtatunk az adatbázisunkon, a változás elveszhet egy rendszerösszeomlás esetén, ha a naplót vagy a megváltozott adatbázis oldalakat nem írjuk ki a stabil tárba.

Hatékonyabb, ha a naplót írjuk, mert a napló tömörebben tartalmazza a változásokat, mint maguk az adatbázis oldalak. Ekkor tehát kevesebb blokkműveletet végzünk. Ugyanakkor szabály, hogy egy tranzakció vége után a napló akkor is kiírandó a háttértárra, ha a lapozási stratégia ezt még nem követelné meg, hiszen ezáltal válik a tranzakció tartósan – akár megismételhetően – végrehajtottá (az ACID-ból a tartósság így teljesül). \clearpage

A redo protokoll

A protokoll onnan kapta a nevét, hogy rendszer- vagy tranzakcióhiba esetén nincs szükség undo műveletre, csak redo művelet kell.

Redo naplózás

A redo naplózás a szigorú 2PL finomítása.

Lépései

  1. $(T,\text{ begin})$ naplóba
  2. $(T,A, [A\text{ új értéke}])$ naplóba, ha $T$ megváltoztatja valamely $A$ adategység értékét
  3. $(T,\text{ 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ékének a tényleges írása az adatbázisba
  6. a piszkos $DB$ blokkok diszkre írása egyéb szempontok szerint
  7. zárak elengedése

Redo helyreállítás

Az adatbázist egy konzisztens állapotba viszi át a helyreállítás végére.

Lépései

  1. összes zár felszabadítása
  2. napló vizsgálata visszafelé: feljegyezzük azokat a tranzakciókat, amelyek eljutottak commitig.
  3. addig megyünk visszafelé a naplóban, amíg nem találunk egy konzisztens állapotot
  4. A 2. pontnak megfelelő tarnzakciókra vonatkozó bejegyzásel segítségével az adatbázisban található értékeket felülírjuk az újal.

A redo helyreállítás eredményeként a 2. pontnak megfelelő tranzakciók hatása megmarad, a többié elvész, és az adatbázis egy újabb konzisztens állapotba kerül.

Ha a redo helyreállítás elszáll, akkor egyszerűen megismételendő, hiszen a 4. pontban végzett műveletek hatása az adatbázisra idempotens (idempotent). \clearpage

Ellenőrzési pontok

A redo helyreállításnál előfordulhat, hogy túl régi időpontra kell visszamennie ahhoz, hogy a helyreállításhoz megfelelő időpontot találjunk. Ezen a problémán segítenek az ellenőrzési pontok, amikor kikény- szerítik az adatbázisnak egy konzisztens állapotát:

  1. ideiglenesen megtiltjuk az új tranzakciók indítását és megvárjuk, amíg minden tranzakció befejeződik vagy abortál
  2. Megkeressük azokat a memóriablokkokat, amelyek módosultak, de még nem kerültek a háttértárba
  3. Ezeket a blokkokat visszaírjuk
  4. naplózzuk az ellenőrzisi pontot
  5. A naplót is kiírjuk a háttértárra

Előnyök

  • redo helyreállításnál, csak a legutóbbi ellenőrzési pontig kell visszamenni a naplóban
  • a napló korábbi részei eldobhatóak (ha más miatt sem kell)
  • csökkenti a lavinák számát

Hátrányok

  • csökkenti a tranzakciós teljesítményt

Ütemezése

  • adott idő eltelte után
  • adott számú tranzakció után
  • az előző kettő kombinációja

\clearpage

Időbélyeges tranzakciókezelés R/W modellben

Időbélyeg

Olyan érték, amelyet minden tranzakcióhoz szigorú egyediséget biztosítva rendelünk hozzá, és amely arányos (legegyszerűbb esetben azonos) a tranzakció kezdőidejével. Jele: $t(\text{Tranzaakció})$

Ezzel a módszer egy soros ekvivalens ütemezést valósíthatunk meg. Ehhez az időbélyegek egyértelmű sorrendjét határozzuk meg, az egyes tranzakciókat pontszerűnek vesszük, azaz nem vesszük figyelembe az adott tranzakció időigényét.

Az időbélyeges ütemező működése:

  1. megvizsgálja minden írás-olvasás előtt a hivatkozott adategység időbélyegét,
  2. ha ez a sorosítási szabályokkal összhangban van (ld. később), akkor az adategység időbélyegét felülírja a műveletet végrehajtó tranzakció időbélyegével,ha nincs összhangban, akkor pedig abortálja a tranzakciót.

Időbélyegek kiosztása során az egyértelműség kritikus:

  • Egyprocesszoros rendszer: processzor időbélyege
  • Többprocesszoros rendszer: az processzor vagy csomópont azonosítója is hozzáveendő.

R/W modell

Két féle időbélyeget különböztet meg a modell:

  • $R(A)$: olvasási időbélyeg
  • $W(A)$: írási időbélyeg

Négy lehetséges eset

Legyen $T$ egy vizsgálandó tranzakció és $t(T)$ a $T$ tranzakció időbélyege, illetve $A$ adategység, $R(A)$ olvasási- és $W(A)$ írási-időbélyege

  1. $t(T) > R(A) \wedge t(T) > (W)$: Mindkét művelet elvégezhető
\begin{center} \begin{tikzpicture} % a straight line segment \draw (0.5,0) -- (10.5,0); % the ticks and their labels \foreach \x in {1,...,10} \draw[xshift=\x cm] (0pt,2pt) -- (0pt,-1pt) node[below,fill=white] {\the\numexpr\x +112\relax}; % the thicker segment %\draw[ultra thick] (2.06,0) -- (8.94,0); % the labels \node[fill=white,draw=black,circle,inner sep=2pt,label=above:{$W(A)$}] at (3.0,0) {}; \node[fill=white,draw=black,circle,inner sep=2pt,label=above:{$R(A)$}] at (5,0) {}; \node[fill=white,draw=black,circle,inner sep=2pt,label=above:{$t(T)$}] at (8.0,0) {}; \node at (5.5,-0.8) {Időbélyegek azonosítója}; \end{tikzpicture} \end{center}
  1. $t(T) < R(A) \wedge t(T) < W(A)$: Egyik művelet sem végezhető el, abortálni kell
\begin{center} \begin{tikzpicture} % a straight line segment \draw (0.5,0) -- (10.5,0); % the ticks and their labels \foreach \x in {1,...,10} \draw[xshift=\x cm] (0pt,2pt) -- (0pt,-1pt) node[below,fill=white] {\the\numexpr\x +112\relax}; % the thicker segment %\draw[ultra thick] (2.06,0) -- (8.94,0); % the labels \node[fill=white,draw=black,circle,inner sep=2pt,label=above:{$R(A)$}] at (3.0,0) {}; \node[fill=white,draw=black,circle,inner sep=2pt,label=above:{$t(T)$}] at (5.0,0) {}; \node[fill=white,draw=black,circle,inner sep=2pt,label=above:{$W(A)$}] at (8,0) {}; \node at (5.5,-0.8) {Időbélyegek azonosítója}; \end{tikzpicture} \end{center}
  1. $t(T) < R(A) \wedge t(T) > W(A)$: Ha $T$ olvasni akar, akkor azt megteheti, de ha írni akar, akkor abortálandó
\begin{center} \begin{tikzpicture} % a straight line segment \draw (0.5,0) -- (10.5,0); % the ticks and their labels \foreach \x in {1,...,10} \draw[xshift=\x cm] (0pt,2pt) -- (0pt,-1pt) node[below,fill=white] {\the\numexpr\x +112\relax}; % the thicker segment %\draw[ultra thick] (2.06,0) -- (8.94,0); % the labels \node[fill=white,draw=black,circle,inner sep=2pt,label=above:{$W(A)$}] at (3.0,0) {}; \node[fill=white,draw=black,circle,inner sep=2pt,label=above:{$t(T)$}] at (5.0,0) {}; \node[fill=white,draw=black,circle,inner sep=2pt,label=above:{$R(A)$}] at (8,0) {}; \node at (5.5,-0.8) {Időbélyegek azonosítója}; \end{tikzpicture} \end{center}
  1. $t(T) > R(A) \wedge t(T) < W(A)$: Mindkét esetben abortálandó a tranzakció
\begin{center} \begin{tikzpicture} % a straight line segment \draw (0.5,0) -- (10.5,0); % the ticks and their labels \foreach \x in {1,...,10} \draw[xshift=\x cm] (0pt,2pt) -- (0pt,-1pt) node[below,fill=white] {\the\numexpr\x +112\relax}; % the thicker segment %\draw[ultra thick] (2.06,0) -- (8.94,0); % the labels \node[fill=white,draw=black,circle,inner sep=2pt,label=above:{$t(T)$}] at (3.0,0) {}; \node[fill=white,draw=black,circle,inner sep=2pt,label=above:{$W(A)$}] at (5.0,0) {}; \node[fill=white,draw=black,circle,inner sep=2pt,label=above:{$R(A)$}] at (8,0) {}; \node at (5.5,-0.8) {Időbélyegek azonosítója}; \end{tikzpicture} \end{center}

\clearpage

Az időbélyeges R/W modell és a 2PL összehasonlítása

Elképzelhető, hogy egy ütemezés sorosítható – időbélyegesen, de kétfázisú zárakkal nem – időbélyegesen is és zárakkal is (pl. minden olyan ütemezés, amelyben a tranzakciók nem használnak közös adatokat), – kétfázisú zárakkal, de időbélyegesen nem, – időbélyegesen sem és zárakkal sem.

Tanulság: sem a zárakkal, sem az időbélyegekkel való sorosítás nem jobb egyér- telműen a másiknál. \clearpage

Tranzakcióhibák és az időbélyegek

Elképzelhető olyan helyzet, amelyben egy $T_1$ tranzakció előállít egy $A$ adategységben értékeket, majd egy $T_2$ tranzakció ezt beolvassa, de később $T_1$ valamilyen oknál fogva abortál. Ez a piszkos adat olvasásának esete, amikor tehát lavinaveszéllyel kell számolni.

Megoldások

  1. elfogadjuk a lavinát, hiszen időbélyeges tranzakciókezelést tipikusan olyan környezetbe használjuk, ahol eleve kevés az abort, tehát kisebb a lavina veszély
  2. Megakadályozzuk a piszkos adat olvasását. Pl addig nem írunk az adatbázisba adatot amíg a tranzakció el nem érte a kész pontját.
\begin{center} \begin{tikzpicture} % a straight line segment \draw (0.5,0) -- (10.5,0); % the ticks and their labels \foreach \x in {1,...,10} \draw[xshift=\x cm] (0pt,2pt) -- (0pt,-1pt); %node[below,fill=white] {\the\numexpr\x +112\relax}; % the thicker segment %\draw[ultra thick] (2.06,0) -- (8.94,0); % the labels \draw[black] (1.0,0.15) -- (1.0,-0.15) node[below] {\shortstack{írás,olvasás művelete\\ időbélyeg ellenőrzése}}; \draw[black] (5.0,0.15) -- (5.0,-0.15) node[below] {készpont}; \draw[black] (9.0,0.15) -- (9.0,-0.15) node[below] {írás az adatbázisba}; \end{tikzpicture} \end{center}

\clearpage

Verziókezelés időbélyegek mellett ($MVCC$)

Feltételezés: minden adatelem írásakor a régi értéket is megőrizzük.

Kézenfekvő megoldás, ha idősor jellegű adatokat kívánunk tárolni (betegek adatai, tőzsdei árfolyamváltozások, szoftver projektek verziói stb.).

Ez megoldja a ``jövőben olvasás'' problémáját (Tehát $T$ olvasni akarna $A\text{-ból}$,de $t(T)<W(A)$), hiszen mivel tároljuk $A$ korábbi változatait,így adott esetben ezt olvasná ki.

Ha $T$ írni akarja $A\text{-t}$ és $t(T)<R(A)$ akkor $T\text{-t}$ abortálni kell.