adatb/db.org

#+TITLE: Adatbázisok tételek
#+AUTHOR: Toldi Balázs Ádám
#+OPTIONS: H:5
#+LANGUAGE: hu-HU
#+LATEX_HEADER: \usepackage[magyar]{babel}
#+LATEX_HEADER: \usepackage{authblk}
#+LATEX_HEADER: \usepackage{blindtext}
#+LaTeX_HEADER: \setcounter{secnumdepth}{5}
#+LaTeX_HEADER: \usepackage{tikz}

* 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 [[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 [[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 [[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, Unió][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}
 2. $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}
 3. $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}
 4. $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.