Informatika | Adatbázisok » Adatbázis-kezelés, kidolgozott szigorlati tételek

Adatbázis-kezelés Kidolgozott szigorlati tételek 7.) Az adatbázis-kezelő rendszerek fogalmai Alapfogalmak „definíció nélkül”: o Adatbázis: egymással kapcsolatban álló információk összessége. o Adatbázis-kezelő rendszer (DBMS): egy olyan szoftverrendszer amelyik lehetővé teszi adatbázisok kialakítását és kezelését. o Információs rendszer: az adatbázis-kezelő általában valamely szervezet (például egy cég) információit kezeli. Az adatbázis ilyen esetben a szervezet információs rendszerének a része. Az információs rendszer egy szervezetnek egy olyan részrendszere, amelyiknek a feladata az információ-feldolgozás. Az információs rendszer általában hardver és szoftverkomponensekből és a szervezet információkezelési folyamataiból áll. Az adatbázis-kezelő rendszer feladata: sok tárolt információ hatékony, biztonságos kezelése, megosztása több alkalmazás között. Az adatok kezelése o frissítés (beszúrás,

törlés, módosítás) o visszakeresés o összetett lekérdezések Látható hogy különbséget tettünk az adatok visszakeresése és az összetett lekérdezések között. Valóban itt különböző felhasználási módokról van szó A visszakeresésre egy példa az, amikor szeretnénk a telefonkönyvből kikeresni egy ismerősünk telefonszámát. Összetett lekérdezésnél általában összesítéseket, statisztikákat akarunk készíteni. Például szeretnénk tudni, hogy az egyes kerületekben hányan laknak és a lakók mekkora részének van telefonja. Az első esetben (a visszakeresésnél) operatív adatbázisról beszélünk. Az operatív adatbázisokat tranzakció-feldolgozásra (OLTP) használják. Ez azt jelenti, hogy az adatbázis tartalma dinamikusan változik, mindig az aktuális információkat tartalmazza. Például operatív adatbázisról beszélünk, ha egy könyvtárban egy adatbázisban tartják nyilván azt hogy ki melyik könyvet vette ki. A második

esetben analitikus adatbázisról beszélünk Az analitikus adatbázis egy olyan adatbázis, amelyiknek a tartalma ritkán változik. Az ilyen adatbázisokat általában statisztikai kimutatások készítésére, más szóval analitikus feldolgozásra használják. OLAP adatbázisokat a felsővezetői információs rendszerekben és döntés-előkészítésben használnak. A továbbiakban operatív adatbázisokkal fogunk foglalkozni Az adatbázis-kezelő környezetét az ábra mutatja: Információs rendszer felhasználó Alkalmazás DBMS Az adatbázis-kezelő közvetlenül is kapcsolatban állhat a felhasználókkal, de gyakran a felhasználó egy alkalmazói programot használ, amelyik az adatbázis szolgáltatásait használja. A felhasználóval való kapcsolat parancssoros vagy grafikus interfészen valósulhat meg. Az alkalmazások és az adatbázis-kezelő közötti kapcsolatot általában egy API felületen valósítják meg. Az adatbázis-kezelőtől elvárjuk az is,

hogy több alkalmazást, több felhasználót tudjon kezelni. A több felhasználó miatt szükség van a jogosultságok és a párhuzamos elérés kezelésére. Az adatbázis definíciójához és az alkalmazások együttműködéséhez szükség van egy adatmodell támogatására. Mivel az adatbázis-kezelőben sok adatot tárolnak, fontos hogy az adatbázis-kezelő hatékony legyen. A hatékonyság elsősorban a műveletek futásidejére jelent megszorítást Az adatbázisban levő adatokat sok alkalmazás használja, ezért az adatvesztést mindenképpen el kell kerülni. Az adatbázis-kezelőnek lehetőséget kell adnia integritási feltételek megfogalmazására és lehetővé kell tennie az adatbázis helyreállítását akár rendszerösszeomlás esetén is. Adatbázis-kezelők szolgáltatásai Felsoroljuk, hogy egy adatbázis-kezelőnek milyen tulajdonságokkal kell rendelkeznie 1. Adatmodell támogatása Az adatmodell használatával tudjuk specifikálni az adatbázisban

levő adatok formátumát és integritási feltételeit. Az alkalmazások közötti együttműködéshez és az adatbázis integritásának biztosításához az adatbázist pontosan specifikálni kell, ehhez ad eszközöket az adatmodell. 2. Konkurens hozzáférési lehetőség, tranzakció-kezelés Ha egyszerre többen férnek az adatbázishoz, akkor kezelni kell a zárolásokat, stb. A tranzakció-kezelés az adatbázison végzett műveleteket olyan egységekre bontja, amelyek vagy teljesen lefutnak, vagy változatlan állapotban hagyják az adatbázist. 3. Több felhasználó, jogosultságok kezelése 4. Biztonsági másolatok készítése, helyreállíthatóság 5. Interfész az alkalmazások felé Adatdefiníciós, adatmanipulációs, lekérdező és vezérlő nyelvek. Adatmodellek Az adatok formátumának és jelentésének leírására használható fogalomrendszert nevezzük adatmodellnek. Általában elvárjuk, hogy egy adatmodellhez legyenek o jóldefiniált alapfogalmak,

pontosan meghatározott szemantika, o kidolgozott elmélet, o tervezési módszerek, o szabványos jelölésrendszer. Az adatmodellt három absztrakciós szintre lehet osztani o A fizikai szint az adatfájlok tárolási módját és fizikai megvalósítási módját adja meg. o A fogalmi szint leírja az adatbázis logikai felépítését. A fogalmi szinten van megadva, hogy az adatbázisban milyen adatok szerepelnek, és hogy az adatok között milyen kapcsolatok vannak. o Az alkalmazói szint megmondja, hogy kívülről hogyan lehet elérni az adatbázist. Az adatbázishoz kapcsolódó programok az alkalmazói szintet látják. Mindegyik szinten vannak sémák és előfordulások. A séma az adatok formáját, típusát A sémában vannak megadva a táblák nevei és az, hogy egy táblában milyen oszlopok szerepelnek. Az adatbázisra vonatkozó megszorítások is a séma részét képezik Az adatbázis előfordulás az adatbázisban levő konkrét értékekből áll. Az

adatbázis szintjei Alkalmazói szint Séma Nézetek definíciói pl.: A 1 , sum(A 2 ) Fogalmi szint Táblák definíciói pl.: R(A 1 ,A 2 ,A 3 ), elsődleges kulcs A 1 . Fizikai szint A fizikai fájlszervezésre vonatkozó információk pl. sorfolytonos ábrázolás, sűrű index Előfordulás Nézetek konkrét értékei pl.: A 1 , sum(A 2 ) a 11111 b 43232 Az adattáblák konkrét értékei pl.: A1, A2, A3 0 1 2 3 4 5 Az adatfájlok konkrét értékei pl. (A 1 ,A 2 ,A 3 ,0,1,2,3,4,5), elsődleges index A 1 Logikai és fizikai adatfüggetlenség o Fizikai adatfüggetlenség: az adatbázis fizikai tárolási módja független a fogalmi szint szerkezetétől. Ilyenkor a fájlok fizikai formátumát, az indexek felépítését megváltoztathatjuk, úgy hogy az adattáblák nem változnak. o Logikai adatfüggetlenség: az alkalmazói programok függetlenek az adatbázis fogalmi szintjének szerkezetétől. Ilyenkor a fogalmi séma bővíthető vagy kisebb mértékben

változtatható, attól még az alkalmazásokat nem kell átírni. A logikai adatfüggetlenség megvalósítható nézettáblák használatával. Figyelem! Az adatbázis-tervezési módszerek tárgyalásakor egyesek az alkalmazói szint tervezését nevezik konceptuális modellezésnek és a fogalmi szint sémáinak a megtervezését fizikai vagy részletes tervezésnek. Fontosabb adatmodellek: o Történeti jelentőségű adatmodellek: hálós, hierarchikus. Ezeket manapság már szinte sehol nem használják. Közös jellemzők: adatok elérése API felületen keresztül, egyszerre egy rekordhoz tudunk hozzáférni. o Hierarchikus adatmodell: az adatbázis fába szervezett rekordokból áll. Bizonyos esetekben egy információt többször is el kell tárolni, vannak olyan kapcsolatok, amiket csak ronda trükkökkel lehet megvalósítani. Az összetettebb keresések és lekérdezések sokszor fabejárás implementálását igénylik az alkalmazói programban. o Hálós adatmodell: az

egyes rekordok között 1:n kapcsolatokat lehet megadni. A kapcsolatok expliciten el vannak tárolva, ezért bizonyos integritási szabályok könnyen megvalósíthatók, de a kapcsolatok módosítása nehézkes. A hálós adatbázist kezelő programokban sok mutatóüldözési feladatot kell megoldani. o Manapság használatos adatmodellek o A relációs modellben az adatbázis adattáblákból áll. A rekordok közötti kapcsolatokat nem tároljuk el közvetlenül, hanem a kapcsolatokat a táblákban szereplő azonos értékekkel reprezentáljuk. A legtöbb relációs adatbáziskezelőnek van saját API felülete, amelyiken keresztül a táblákat úgy tudjuk kezelni, mintha rekordokból álló fájlok lennének. Összetett lekérdezéseket és frissítéseket SQL-ben tudunk leírni. A relációs modell előnyei: egyszerű, pontosan definiált alapfogalmak és kidolgozott elmélet; vannak tervezési módszerek, amelyekkel az adatbázis integritása biztosítható. A relációs

modell hátránya: bizonyos adatokat nem lehet benne tárolni: CAD és egyéb tervek, verziókövetés, multimédia klipek és metaadatok, térinformatikai adatok. o Adatbányászati rendszerekben többdimenziós adatmodellt szoktak használni. Az adatokat egy többdimenziós kockában tároljuk, lehetőség van gyakorlatilag bármilyen összesítés-kombináció lekérdezésére. A többdimenziós adatmodell lehetővé teszi nagy adatbázisok statisztikai elemzését. Adatbányászati rendszereket az üzleti döntéselőkészítési folyamatban használnak. o Az objektumrelációs adatmodellről: ez lényegében a relációs modell bővítése összetett adattípusokkal. Az új adattípusok lehetnek sor vagy mező-típusok A sortípus esetén egy tábla azonos típusú objektumokból áll. Összetett mezőtípus lehet például a BLOB (binary large object) típusú mező Tranzakciókezelés Konkurens hozzáférésről beszélünk, ha egy adatbázist egyszerre több alkalmazás

használhat. A konkurens hozzáférés problémái: o elveszett update (ha egyszerre ketten ugyanazt akarják felülírni) o inkonzisztens állapot kiolvasása (egymás utáni lekérdezésekkel, ha közben valaki más módosította az adatbázist) o versenyhelyzet (pl. színházban helyfoglalás: kiolvasás + ellenőrzés + hely lefoglalása; előfordulhat, hogy ketten ugyanazt a helyet egyszerre lefoglalják) Megoldás: a tranzakció. Az adatbázison elvégzett műveletek egy logikai egységét nevezzük tranzakciónak. Ha a tranzakció végére értünk, akkor a tranzakciót jóvá kell hagyni (commit), vagy ha hiba történt a tranzakció végrehajtása során, akkor vissza kell vonni (rollback). Ha a tranzakciót visszavonjuk, akkor az adatbázis visszaáll az eredeti állapotba. Tranzakciók követelményei (ACID) o Atomic egy tranzakció vagy sikeres, vagy nem csinál semmi változtatást o Consistent az adatbázis konzisztens marad o Isolated a felhasználónak úgy látszik,

mintha csak ő használná a rendszert o Durable egy tranzakció hatásai megmaradnak rendszerösszeomlás után is A tranzakciókról megkövetelik, hogy sorbarendezhetők legyenek. Ez azt jelenti, hogy ha az adatbázison a T 1 , ., T n tranzakciók párhuzamosan lefutnak, akkor végén olyan állapotba kell jutnunk, mintha a tranzakciók egymás után lettek volna végrehajtva. Izolációs szintek (egy tranzakció szemszögéből) o Serializable minden egyes folyamat úgy látja, mintha csak ő használná az adatbázist, valódi sorbarendezhetőség o Repeatable read a tranzakció által írt és olvasott adatokat más nem módosíthatja, ezért amihez egyszer már hozzáfértünk azt a tranzakció futása alatt más nem tudja megváltoztatni, azonban lehet, hogy egy táblában fantomsorokat látunk, ha valaki törölt belőle de még nem hagyta jóvá a törlést o Read comitted o Read uncomitted csak jóváhagyott (comitted) adatokat tudunk kiolvasni, de ha egy táblából

egymás után többször kiolvassuk ugyanazt az értéket, akkor lehet, hogy mást kapunk bármit lehet látni, akár még más tranzakciók félkész módosításait is Adatbáziskezelők felülete Egy adatbázis-kezelőnek egységes, lehetőleg szabványos felületet kell nyújtania az alkalmazások és a felhasználók felé. Ezeket általában az adatbázis elérésére használatos nyelvekkel valósítják meg. 1. DDL Data Definition Language Sémák definiálása A DDL feladata az adatbázisban levő sémák létrehozása, karbantartása, információinak lekérdezése. 2. DML Data Manipulation Language Adatbázis feltöltése, frissítése A DML feladata az adatbázis sémáinak adatokkal való feltöltése és az adatokon frissítési műveletek végzése (beszúrás, törlés, módosítás). 3. QL Query Language Lekérdezések 4. (D)CL (Data) Control Language Vezérlőnyelv Jogosultságok, tranzakciók és rendszerparaméterek beállítása. Adatbáziskezelők felépítése

Egy adatbáziskezelő általában az alábbi komponensekből áll: o Lekérdezés-feldolgozó o Tárkezelő (file- és pufferkezelés) o Tranzakciókezelő o Adatok, metaadatok fizikai tárolója Az egyes komponensek kapcsolódásait az ábrán láthatjuk felhasználó alkalmazások Lekérdezésfeldolgozó tárkezelő adattároló Tranzakciókezelő A tárkezelő feladata az adatok fizikai tárolásának megvalósítása. A tárkezelő általában fájlkezelést és pufferezést végez. A lekérdezés-feldolgozó komponens értelmezi a lekérdezéseket és egyszerű fájlműveletek sorozatára bontja. A lekérdezés-feldolgozó feladata az lekérdezések optimalizálása is. Ehhez egy végrehajtási tervet kell készíteni, amelyik a lekérdezés kiértékeléséhez szükséges műveleteket valamilyen belső reprezentációban adja meg. A tranzakciókezelő komponens feladata a zárolások kezelése és a tranzakciók ACID tulajdonságának biztosítása a megfelelő

izolációs szint megvalósításával. Az adatbázis és a felhasználók közötti kapcsolat általában valamilyen parancssoros vagy grafikus felületen keresztül valósul meg. A külső alkalmazások általában API felületen keresztül érik el az adatbázist. Gyakran az API hívások paramétereként egy lekérdezést lehet megadni. Ezenkívül még általában az API lehetőséget ad az adatbázis rekordszintű elérésére Ilyenkor egy eljáráshívással egyszerre egy rekordot tudunk olvasni, módosítani, stb. Katalógusok, sémák Az adatbázis általában valamilyen adatmodellre épül. Az adatmodellekről láttuk, hogy megkülönböztetik az adatbázis sémáját és előfordulását az egyes absztrakciós szinteken. Az adatbázis-kezelőben az adatok (vagyis az adatbázis-előfordulás) mellett el kell tárolni a sémaelemeket. A sémát leíró adatokat metaadatoknak nevezzük, mert ők az adatok formáját leíró adatok. A metaadatok az alábbi információkat

tartalmazzák: o Tábla-definíciók o felhasználók, jogosultságok o fizikai megvalósításra vonatkozó információk: indexek, karakterkészletek o megszorítások, aktív adatbázis-elemek (triggerek, tárolt eljárások) A metaadatokat több szinten lehet csoportosítani: sémák, katalógusok, klaszterek. Séma: a fenti listában felsorolt elemek gyűjteménye. A sémák listáját a katalógus tartalmazza Az egy felhasználó (vagy egy SQL-utasítás) által elérhető adatbáziselemeket tartalmazza a klaszter. Minden felhasználóhoz hozzá van rendelve egy klaszter, amelyikben fel van sorolva, hogy ő mely katalógusokat érheti el. Tranzakciók megvalósítása Amikor egy tranzakció egy adatbázis-objektumot akar elérni, akkor zárolnia kell azt. A zárolás lehet megosztott vagy kizárólagos. Ha egy erőforrást olvasni akarunk, akkor megosztott zárat rakunk rá, ha írni akarjuk, akkor kizárólagosat. (ld írók és olvasók problémája). A tranzakciók

sorbarendezhetőségi követelménye úgy valósítható meg, ha minden tranzakcióra bevezetjük a kétfázisú zárolás (two-phase locking) protokollt. Ez a protokoll azt jelenti, hogy egy tranzakcióban egy zár elengedése után már nem lehet újabb zárakat igényelni. Látható, hogy ilyenkor egy tranzakciónak, a zárolás szempontjából két fázisa van. Az első a növekvő fázis Ilyenkor a tranzakció egyre több zárat igényel A második fázis a csökkenő fázis. Ebben a fázisban elengedjük a zárakat Gyakran a tranzakció futása során végig csak igényeljük a zárakat, és a végen egyszerre engedjük el mindet (ilyenkor szigorú kétfázisú protokollról beszélünk). A tranzakciók atomicitása megvalósítható árnyéklapok vagy naplózás használatával. Az árnyéklapok használatakor az adatbázisba beírt változások nem kerülnek be rögtön az adattáblákba, hanem külön blokkokba kerülnek. A tranzakció jóváhagyásakor ezeket a blokkokat be

lehet rakni az adatbázisba. Ha a tranzakciót visszavonják, az árnyéklapokat egyszerűen el lehet dobni. A naplózás technikája a változtatásokat beírja egy naplófájlba, ez alapján lehet visszavonni a tranzakciók műveleteit. A naplófájlt rendszerösszeomlás után is fel lehet használni egy konzisztens állapot helyreállítására. Kliens-szerver adatbázisrendszerek Gyakori probléma, hogy egy adatbázist több felhasználó, több gépről szeretne elérni. Régen ezt úgy oldották meg, hogy az adatfájlokat felrakták egy fájlszerverre, és minden egyes kliensgépen az adatbázis-kezelő úgy volt beállítva, hogy a közös adatfájlokat használja. Az ilyen régi adatbáziskezelők (DBase, ForPro) nem támogatták a külső alkalmazásokat, hanem saját script-nyelvük volt, az alkalmazásokat azon lehetett elkészíteni. Ezzel a módszerrel sok probléma van. Egyrészt, mivel az adatbázis-műveletek a kliensen futnak és a szerveren levő adatfájlokat

kezelik, nagyon nagy lesz a hálózat terhelése. Az adatbázis konzisztenciája szinte egyáltalán nem garantálható, mivel a kliensek számára minden fájlművelet megengedett. A párhuzamos hozzáférés kezelése a hálózati szoftvertől függ. Általában a rekordszintű zárolást lehet megvalósítani Azonban ha az egyik kliensprogram egy módosítás közben abortál (például hálózati hiba miatt), a táblaszerkezetek fizikailag is megsérülhetnek. Kliens Kliens Kliens Fájl-szerver Ha az adatbázis-kezelő és az alkalmazói programok nem ugyanazon a gépen futnak, akkor kliens-szerver architektúráról beszélünk. Ilyenkor az adatbázist egy nagyteljesítményű adatbázis-szerveren tárolják. Amikor egy alkalmazás hozzá akar férni az adatbázishoz, az igényeit egy üzenetben kell elküldenie az adatbázis-szervernek. Az adatbázis-szerveren futó adatbáziskezelő feldolgozza a kérelmet és visszaküldi az eredményt a kliensnek. Így egy adatbázist

több programmal, több helyről is el lehet érni. A kliens-programok csak az adatbázis elérésére vonatkozó kérelmekkel fordulnak a szerverhez, de közben az alkalmazás folyamatai a kliensgépen futnak. Ezzel a szerver terhelése kisebb, mintha minden feladat a szerveren futna. Mivel a lekérdezések kiértékelése a szerveren történik, a hálózati kapcsolaton csak az eredményt kell átvinni, így a hálózat leterhelése nem olyan nagy mintha fájl-szervert használnánk. Az adatbázis-szerverek elérésének szabványos interfésze az ODBC felület. Az ODBC az adatbázisokhoz driverekkel csatlakozik, így egy kliens akár többféle adatbázishoz is tud kapcsolódni. A legtöbb adatbázis-kezelőhöz adnak ODBC-drivert is, ezért az ODBC-t használó alkalmazások nem nagyon függnek a konkrét adatbázis-kezelő programtól. Kliens Kliens Kliens Adatbázis-szerver DBMS Látható hogy a kliens-szerver architektúrában két réteg van: alul van az

adatbázis-kezelő, és a felső rétegben az alkalmazások. Az adatbázis-kezelő tárolja az adatokat, az alkalmazások felelősek a feldolgozási folyamatok végrehajtásáért és az adatok megjelenítéséért. Ezért a kliens-szerver architektúrát kétszintű architektúrának (two-tier architecture) is szokás nevezni. A kétszintű architektúrával azonban nehezebb megőrizni az adatbázis integritását, mivel a kliensek közvetlenül hozzáférhetnek az adatokhoz. Például, ha egy kliens egy tábla frissítése közben „lefagy” akkor lehet, hogy inkonzisztens állapotot hagy maga után. Ráadásul a feldolgozási folyamatokat bele kell építeni a kliensprogramba. Egy rugalmasabb megoldás a háromszintű architektúra, ahol az adatbázist, a feldolgozási folyamatokat és a megjelenítést külön komponensekben valósítjuk meg. Ilyenkor a kliensprogramok csak a megjelenítést végzik, az adatfeldolgozási folyamatok egy alkalmazás-szerveren futnak. Az

alkalmazásszerveren futó folyamatok kezelik az adatbázist és magasszintű szolgáltatásokat nyújtanak a kliensprogramoknak. A kliensprogramok feladata csak az adatok megjelenítése és a felhasználói felület kezelése. Az adatbázis-szerver és az alkalmazás-szerver fizikailag futhat ugyanazon a gépen, de lehet valóban két külön szerver is. Az alkalmazás-szerveren találhatók a feladatot magas absztrakciós szinten leképező objektumok. Ezeket az objektumokat a kliensprogram gyakran komponensalapú felületen keresztül éri el (pl. DCOM, CORBA, Enterprise JavaBeans). Mivel a kliensek csak jól meghatározott műveleteket végezhetnek el, az adatbázis integritása így könnyebben biztosítható. Látható, hogy a kétszintű architektúra esetén az adattárolás kivételével mindent a kliensnek kell csinálnia. Az ilyen klienst vastag kliensnek nevezzük A háromszintű architektúra esetén a kliens feladata csak az adatok megjelenítése és a felhasználóval

való interakció. Ekkor vékony kliensről beszélünk. A háromszintű architektúra kevesebb terhet és kevesebb felelősséget ró a kliensekre, de megvan az a hátránya, hogy bonyolultabb és nagyobb a hardverigénye. Fizikai fájlszervezés Az adatbázisban levő adatokat a memóriában és a háttértárolón tároljuk. A memória és a háttértároló között adatátvitelért a pufferkezelő modul felelős. A háttértároló és a memória között átvihető legkisebb egységet blokknak nevezzük. A blokk mérete 512 bájttól néhány kilobájtig terjed. A blokkok írása vagy olvasásakor az olvasás időigénye három tényezőből tevődik össze: 1. Seek time: az az idő, amíg az író-olvasó fej a kért blokkot tartalmazó sávra áll 2. Rotational delay: ha ráálltunk a kért sávra, meg kell várni, amíg a diszk beforog úgy, hogy a kért blokk a fej alá essen 3. Transfer time: a blokk beolvasásának ideje 4. Verification: írás esetén kérhetünk

ellenőrzést Ilyenkor újra körbefordul a diszk, és a vezérlő leolvassa a frissen kiírt blokkot, hogy tényleg jól lett-e rögzítve. Random hozzáférésnél az előzőkből a Seek time a meghatározó, ezért IO-ütemezésre van szükség. Megfelelő fájlszervezéssel elérhető, hogy a diszk-hozzáférések szekvenciálisak legyenek, ilyenkor az (1)-es és (2)-es tényezők elhanyagolhatóvá válnak, az IO időigényében a blokkok száma lesz a meghatározó. Látható, hogy a diszkekkel rögzített méretű blokkokban tudunk „beszélgetni”. Ezért az adatbázisban levő rekordokat blokkokba kell szervezni. Egy blokk eszerint tartalmaz o Blokk-fejlécet o Rekordokat o Esetleg szabad helyet A blokk-fejlécben általában a blokk sorszámát, a rekordok méretét és számát vagy a szabad hely kezdetét szokták tárolni. Egy rekord mezőkből áll össze A relációs adatmodellben például egy adattábla egy sorának megfelel egy rekord, és minden egyes

attribútumnak megfelel egy mező. A blokkokhoz hasonlóan a rekordnak is lehet fejléce, ebben például lehet a rekord sorszáma, egy töröltséget jelző flag, vagy a rekord mérete, stb. Az adatbázis-kezelő műveleteiben az IO-költség a meghatározó. Ezért az egyes fájlszervezési műveletekre az IO-költséget fogjuk vizsgálni. A műveletigény mellett meg fogjuk még nézni a fájlok blokkokban számolt tárigényét is. A lekérdezések vizsgálatához az elemi összehasonlítások műveletigényét fogjuk megnézni. Továbbá, megvizsgáljuk az alábbi frissítést műveletek műveletigényét is: o Egy rekord beszúrása o Egy rekord törlése o Módosítás Jelölések: B R b r bf blokkméret rekordméret blokkok száma rekordok száma blokkolási faktor, fb = B/R Adatfájlok felépítése A legegyszerűbb adatfájl a rendezetlen fájl, más néven kupac (heap). Ilyenkor a rekordokat egyszerűen egymás után beírjuk a blokkokba. o Tárigény b = r/bf

o Keresés átlagosan b/2, legrosszabb esetben b o Beszúrás (a fájl végére) 1 olvasás + 1 írás o Törlés keresés + 1 írás (törölt flag beállítása) o Módosítás keresés + 1 írás Ha egy mező szerint rendezett fájlt használunk, akkor az arra a mezőre vonatkozó keresés meggyorsítható, de cserébe a frissítések bonyolultabbak lesznek. o Tárigény b = r/bf o Keresés (A=a alakú) log 2 b, logaritmikus keresés o Beszúrás léptetni kell, átlagosan b/2 darab írás o Törlés keresés + 1 írás (törölt flag beállítása) o Módosítás keresés + 1 írás Látható, ez nem egy jó megoldás. A beszúráson javíthatunk úgy, hogy az új rekordokat a fájl végére, egy rendezetlen területre írjuk be. Ekkor a beszúrás műveletigénye csökken Azonban a fájl végén levő rendezetlen blokkokat időnként (üresjárati időben, kötegelt feldolgozásban) bele kell illeszteni a rendezett fájlba. o Keresés (A=a alakú) log 2 b + k, ahol k a

rendezetlen blokkok száma o Beszúrás 1 olvasás + 1 írás o Törlés keresés + 1 írás (törölt flag beállítása) o Módosítás keresés + 1 írás o Karbantartás b log 2 b (adatbázis újrarendezése) Másik lehetőség a beszúrás javítására, ha üres helyeket hagyunk a blokkokban. Például, lehet kezdetben minden blokk csak félig telítve. Ilyenkor is szükség van az adatbázis karbantartására, a túl telített blokkokat szétvágjuk, nehogy teljesen beteljenek. o Tárigény 2b o Keresés (A=a alakú) log 2 b + 1, logaritmikus keresés o Beszúrás keresés + 1 írás o Törlés keresés + 1 írás (törölt flag beállítása) o Módosítás keresés + 1 írás o Karbantartás költséges Hasító függvények A hash-függvényekkel az A=a alakú kereséseket tudjuk felgyorsítani. A hash-függvény egy h:DOM(A)  {0.M-1} alakú függvény, ahol M egy előre rögzített szám Ilyenkor azt mondjuk, hogy M darab kosárba rakjuk szét az elemeket.

Részletesebben ld: algoritmusok Indexelés Ha tudjuk, hogy egy mező szerint sokat fogunk keresni, akkor az adatbázist a szerint a mező szerint indexeljük. Ha az adatfájl rendezett, elsődleges indexről beszélünk Ha az adatfájl nem rendezett, vagy egy másik mezőre készítünk indexet, akkor azt másodlagos indexnek nevezzük. Egy index lehet ritka vagy sűrű index A ritka indexben csak az egyes blokkok elején levő kulcsot tüntetjük fel, a sűrű indexben a kulcs minden értékét. Ritka indexet csak rendezett adatfájlra lehet használni! Elsődleges indexek Az elsődleges index olyan mezőre vonatkozik, amelyik szerint az adatfájl rendezett. Ezért elsődleges indexnek használhatunk ritka indexet. A ritka indexben csak az adatfájl blokkjainak elején levő kulcs-értékeket tüntetjük fel. Az indexben csak kulcs-blokkszám párokat kell tárolni, ezért az index rekordmérete kicsi. Az index rekordjainak száma megegyezik az adatfájl blokkjainak számával. o

Tárigény b I = b/bf I  << b o Keresés (A=a alakú) log 2 b I, logaritmikus keresés o Frissítések bonyolult, ld. rendezett adatfájl Másodlagos indexek A másodlagos index olyan mezőre vonatkozik, amelyik szerint nincs rendezve az adatfájl. Lehet rendezetlen az adatfájl, vagy lehet, hogy másik mező szerint rendeztük. A másodlagos index egy sűrű index, az adatfájl minden egyes rekordjához egy index-rekord tartozik. Az index egy rekordjában kulcs-rek.pointer párok vannak o Tárigény b I = r/bf I  o Keresés (A=a alakú) log 2 b I, logaritmikus keresés o Frissítések bonyolult, ld. rendezett adatfájl Az indexek frissítésekor ugyanazok a problémák merülnek fel, mint a rendezett adatfájloknál. A beszúrás gyorsítására itt is használhatunk részben kitöltött blokkokat, stb. Kereső fák, B-fák Az előbb megállapítottuk hogy az index olyan, mint egy rendezett adatfájl. Ha az indexet is indexeljük, többszintű indexelésről

beszélünk. Mivel az index már rendezett, őt ritka indexszel lehet indexelni. Ráadásul az index rekordmérete is kisebb, mint az adattábláé, ezért nagyobb a blokkolási faktora! Ilyenkor az indexek tárigénye növekszik, de a keresés gyorsabb lesz: o Tárigény b 1 + b 2 + . + b t o Keresés (A=a alakú) t + log 2 b t , ahol t a szintek száma és a legfelső szinten b t blokk van Ha az indexelés szintjeinek száma kellően nagy, akkor egy B-fát kapunk. Ilyenkor a keresés műveletigénye tovább csökken, bár most is logaritmikus, de a logaritmus alapszáma a bf I ritka indexekre vonatkozó blokkolási faktor (ami akár néhány száz is lehet!). A módosíthatóság javítására a blokkokban hagyjunk üres helyeket! Ha ezt minden szinten megcsináljuk, akkor a beszúrás, törlés műveletigénye is logaritmikus lesz. Ha a blokkoknak legalább félig kell kitöltve lennie, akkor az adatszerkezetet B+ fának nevezzük, ha a blokkoknak 2/3 részt kell kitöltve lenniük

akkor B* fának. o Szintek száma t = log bfI b o Tárigény nagyságrendben lineáris o Keresés (A=a alakú) log bfI b o Frissítési műveletek log bfI b 8.) Adatmodellezés Adatmodellezésnek nevezzük azt az absztrakciós folyamatot, amikor a rendszerről megfogalmazott követelmények alapján meghatározzuk a problémára jellemző adatokat. Az absztrakció ebben az esetben azt jelenti, hogy az adatok konkrét értékeitől eltekintünk, csak az adatok szerkezetét és logikai kapcsolatait vizsgáljuk. Az adatok szerkezetének leírásakor valamilyen adatmodellt használunk, ami megadja, hogy az adatokat és a közöttük levő kapcsolatokat milyen formában írhatjuk le. Továbbá, egy adatmodell általában megadja az adatszerkezetek szemantikáját is: ez azt jelenti, hogy az adatbázis tartalmát úgy tekinthetjük, mint állítások halmazát (ekkor szemantikus adatmodellről beszélünk). Az adatmodell a lehetséges állítások formai tulajdonságait írja le. Egy jó

adatmodellnek rendelkeznie kell az alábbi tulajdonságokkal: o Egyértelműen meghatározott alapfogalmak o Kidolgozott elméleti háttér o Tervezési módszer o Lehetőleg szabványos jelölésrendszer Az adatbázis-tervezés folyamata: konceptuális terv készítése, fizikai/részletes tervezés. o Konceptuális tervezés: az alkalmazási terület fogalmi adatmodelljének elkészítése. Ebben a fázisban egy már meglevő követelményleírásból indulunk ki. A követelményleírás elemzése során előállítunk egy formálisabb adatmodellt. Konceptuális tervezéshez általában szemantikus adatmodellezési technikákat szoktunk használni. Most részletesen az Egyed-Kapcsolat modellel fogunk foglalkozni o Részletes tervezés: az adatbázis fogalmi szintű sémájának leírása. Ebben a fázisban a konceptuális terv alapján egy teljesen formalizált adatmodellt készítünk el. Mi a relációs adatmodellel és a függőségek elméletével fogunk részletesen foglalkozni.

Az adatbázis-tervezés célja egy olyan adatbázis kialakítása, amelyikben az adatokat hatékonyan tudjuk tárolni és kezelni, és lehetőleg biztosítani tudjuk az adatbázis konzisztenciáját és integritását. Egy adatbázis konzisztens, ha nincsenek benne ellentmondó állítások. Az integritás azt jelenti, hogy az adatbázis konzisztens és nincsenek benne értelmetlen vagy félreérthető állítások. Nyilván ez utóbbit sokkal nehezebb biztosítani A hatékonyság azt jelenti, hogy az adatok visszakeresését és frissítését szeretnénk, ha gyorsan el tudnánk végezni, de közben az adatok lehetőleg ne foglaljanak sok helyet. Az adatbázis-tervezés problémái: redundancia, anomáliák. Redundanciáról beszélünk, ha egy adatbázisban ugyanazt az információt többször is eltároljuk. A redundancia következményeként az adatbázis frissítésekor anomáliák, vagyis rendellenességek léphetnek fel: o Beszúrási anomália: egy új sor beszúrásához több

más információra is szükségünk van, hogy a redundáns mezőket jól tudjuk kitölteni. o Módosítási anomália: ha egy érték több helyen szerepel, előfordulhat hogy csak egy helyen módosítjuk és akkor az adatbázis inkonzisztens lesz. o Törlési anomália: ha törlünk egy sort az adatbázisból, azzal lehet hogy információt veszítünk. Példa Tekintsük az alábbi adattáblát Film Csodálatos Júlia Sörgyári Cappriccio Szigorúan ellenőrzött vonatok Rendező Szabó István Jiři Menzel Jiři Menzel Rendező telefonszáma 123-1234 112233-445566 112233-445566 Az adatbázisban redundáns információk vannak, mivel az a tény hogy Menzel telefonszáma 112233-445566, kétszer is el van tárolva. A redundancia miatt a következő anomáliák léphetnek fel: o Beszúrási anomália: tegyük fel, hogy be akarjuk szúrni még a Mephisto című filmet is. Tudjuk, hogy ezt a filmet Szabó István rendezte, de ha fejből nem tudjuk a telefonszámát, akkor bajban

vagyunk. o Ha rossz telefonszámot írunk be, akkor az adatbázis inkonzisztenssé válik. o Ha a telefonszám mezőt üresen hagyjuk (NULL érték), akkor az adatbázis integritása megsérülhet: a most beszúrt sorban a telefonszám üres értéke félreérthető: vajon azt jelenti, hogy Szabó Istvánnak nincs telefonja? Vagy azt hogy nem tudjuk a telefonszámát? Vagy azt hogy még nem írtuk be? o Megtehetjük, hogy kikeressük hogy már benne van-e a táblázatban Szabó István telefonszáma, de akkor meg a beszúrás művelet nem lesz hatékony. o Módosítási anomália. Tegyük fel, hogy megváltozott Jiri Menzel telefonszáma Ekkor az összes filmjénél be kell írni az új telefonszámot, mert különben az adatbázisunk inkonzisztens lesz. o Törlési anomália. Ha töröljük a Csodálatos Júlia című filmet, akkor elveszítjük azt az információt, hogy Szabó István telefonszáma 123-1234. Vegyük észre azt is, hogy a táblában többször is szerepel Menzel

neve, ez mégsem redundancia. Valóban, a két sorban Menzel nevének feltüntetése két különböző állítást jelent, mivel különböző filmekre vonatkozik. De a telefonszám kétszeri megadása ezzel szemben tényleg redundancia, ugyanis mindkét sorban azt az állítást fejezi ki, hogy „Jiri Menzel telefonszáma 112233-445566”. Relációs adatmodell A relációs adatmodellben egy adatbázis adattáblák összessége, ahol minden adattábla egy reláció vagyis sorok halmaza. Ezért azt is szokták mondani, hogy a relációs adatmodell egy rekord-orientált adatmodell. Def.: reláció séma R(A 1 ,,A n ) az R a séma neve, az A i -k az attribútumok nevei. Használni fogjuk az A ∈ R jelölést, ami azt jelenti hogy az A attribútumnév szerepel az R séma attribútumai között. Az X, Y, V, betűkkel általában attribútumhalmazokat jelölünk. Általában az attribútumokhoz típusokat (értéktartományokat) is szoktunk rendelni, ez is a séma része. reláció

előfordulás r:R(A 1 ,,A n ), r ⊆ × DOM ( Ai ) , véges halmaz. Ai ∈R sor (tuple) Jelölések: t.A i , t[X], $i t ∈ r , t=(a 1 ,,a n ) adatbázis-séma D(R 1 ,R m ) R-et. adatbázis-előfordulás d=(r 1 ,,r m ), r i :R i reláció előfordulások dekompozíció d=(R 1 ,.,R m ), ahol az R i -k uniója kiadja pont az Példa: o Reláció sémák: Alkalmazottak(név, cím, telefonszám, beosztás) Telephelyek(cím, alapterület) Dolgozik(alkalmazottNév, telephelyCím) o Ezeket a relációsémákat bepakolhatjuk egy adatbázis-sémába: Vállalat(Alkalmazottak, Telephelyek, Dolgozik) o A reláció előfordulásokat táblázat formájában szoktuk megadni. Adatbázis-előfordulás megadásakor egyenként felírjuk a táblák értékeit. Alkalmazottak: Név Kovács Béla Nagy Júlia Kis Éva Szabó János Cím Retek u.1 Hagyma u. 2 Alma utca 3. Körte u. 4 Telefonszám 2383848372 4738932679 3695983744 3839375999 Beosztás Ügyvezető igazgató Titkárnő

Takarítónő Raktáros Gyakran megengedjük hogy egy attribútum értéke a ⊥ „null-érték” legyen. Ez egy olyan extremális érték vagy más néven nemdefiniált érték, ami nincsen benne semmilyen értéktartományban. A null-értékre semmilyen művelet vagy összehasonlítás nincs értelmezve Ez azt jelenti, hogy ha egy művelet egyik operandusa a ⊥, akkor az eredmény is ⊥ lesz. Ha egy össsehasonlítás egyik operandusa ⊥, akkor az összehasonlítás igazságértéke nemdefiniált. Másképp fogalmazva a ⊥ értéket bevezethetjük egy „harmadik igazságértéknek”. Ekkor egy háromértékű logikát kapunk. Ezzel a logikával és a logikai műveletek háromértékű értelmezésével részletesen az SQL tárgyalásakor foglalkozunk. Olyankor szoktak null-értéket beírni egy mezőbe, ha azt akarják jelezni, hogy az ottani érték „hiányzik” vagy nem értelmezhető. Például, elképzelhető hogy az alkalmazottak táblában van egy leánykori név

mező. A férfi alkalmazottak esetén ebbe a mezőbe null értéket kéne írnunk A következőkben egy formális modellt mutatunk be, amely a redundanciát matematikai fogalmakkal írja le. Az anomáliák kiküszöbölésére feltételeket fogunk megfogalmazni (normálformák), amelyek alapján megfelelő dekompozíciókkal csökkenteni tudjuk a redundanciát. Funkcionális függőségek A funkcionális függőség informális definíciója: egyes attribútumok értékéből néhány más attribútum egyértelműen meghatározható. Vagyis ha egy táblában van két olyan sor, amelyek az X attribútumhalmazon megegyeznek, akkor ők megegyeznek valami Y attribútumhalmazon is. A továbbiakban egy rögzített R sémával fogunk dolgozni. Def.: Funkcionális függőség (FD): XY alakú kifejezés, ahol X , Y ⊆ R , Az r előfordulás megfelel az XY funkcionális függőségnek, ha ∀t1 , t 2 ∈ r : (t1 [X ] = t 2 [X ]) ⇒ (t1 [Y ] = t 2 [Y ]) Jelölés: r |= XY.

Ilyenkor azt is mondhatjuk: r kielégíti az XY függőséget. Def.: Az XY FD-nek megfelelő előfordulások halmaza: SAT ( X Y ) = {r | r |= X Y } N.B: r megfelel az XY FD-nek, acsa, ha r ∈ SAT ( X Y ) . Látható, hogy a funkcionális függőség definíciója bizonyos értékek egyenlőségét követeli meg. A továbbiakban legyen F funkcionális függőségek halmaza. (a függőséghalmazokat néha (trehányságból) formulahalmazoknak is nevezzük). Def.: Az F-et kielégítő reláció előfordulások halmaza: SAT ( F ) =  SAT ( X Y ) X Y ∈F N.B: A SAT definíciójából következik, hogy SAT(F ∪ G) = SAT(F) ∩ SAT(G). Fontos megemlíteni hogy a funkcionális függőségek a séma részei. Vagyis a funkcionális függőségek nem annyira egy reláció tulajdonságai, hanem az adatbázissal kapcsolatos követelmények vagy megszorítások. Egyes könyvekben ilyenkor a sémafogalmat ki is bővítik, úgy hogy ezentúl a séma egy R=(A 1 .A n , F) rendezett

pár: az első komponensben megadjuk az attribútumok neveit (ahogy eddig is volt), a második komponens egy funkcionális függőségeket tartalmazó halmaz. Az ilyen sémák esetén az r előfordulás az R sémába tartozik, ha az r fejlécében az A 1 .A n attribútumok vannak és r-re teljesülnek az F-beli függőségek A funkcionális függőségek a redundancia egyik fajtáját jelenítik meg: ha egy táblában fennáll az XY függőség, akkor X-en egyező sorokat véve, egyetlen sor Y-beli értékeiből már következtetni tudunk hogy a többi sorban is ugyanaz az Y értéke. Példa: Tekintsük az előző filmes példát. Attribútumok: Film, Rendező, Rendező telefonszáma. Függőségek: o Film  Rendező o Rendező  Rendező telefonszáma Látható, hogy más függőségek is fennállnak a megadott példatáblában (pl. Film  Rendező telefonszáma), de most csak ezt a két függőséget követeljük meg. A funkcionális függőségekre vonatkozó implikációs

probléma A kérdés az, hogy egy adott F függőséghalmaz és egy X’Y’ funkcionális függőség esetén vajon az F-ből következik-e az X’Y’? Ehhez a „következik”-et kell először definiálnunk. Azt mondjuk, hogy F-ből következik az X’Y’ függőség, ha minden olyan r előfordulás, amelyik kielégíti az F-et, kielégíti az X’Y’ függőséget is. Def.: F-ből következik X’Y’, ha Jelölés: F |= XY SAT ( F ) ⊆ SAT ( X Y ) Def.: Adott F formulahalmaz és XY függőség esetén az F |= XY eldöntését szemantikai implikációs problémának nevezzük. Lemma: (a szemantikai következmény „tranzitivitása”) Tegyük fel, hogy teljesül az alábbi három feltétel: 1. F |= X’Y’, 2. G |= X’’Y’’, 3. {X’Y’, X’’Y’’} |= XY Ekkor F ∪ G |= XY. Biz.: trivi o (1) miatt SAT(F) ⊆ SAT(X’Y’), o (2) miatt SAT(G) ⊆ SAT(X’’Y’’) o A kettőt elmetszve azt kapjuk hogy

SAT(F ∪ G) ⊆ SAT(X’Y’, X’’Y’’) o (3) miatt SAT(X’Y’, X’’Y’’) ⊆ SAT(XY)-nak o Tehát SAT(F ∪ G) ⊆ SAT(XY)-nak. QED N.B: ez általánosítható több feltételhalmazra is Mivel a szemantikai implikációs problémát a definíció alapján nehéz eldönteni, megadunk egy levezetési rendszert a funkcionális függőségekre. Az Armstrong-axiómák Ezeket az axiómákat „törtek” formájában adjuk meg. Egy ilyen tört azt jelenti, hogy ha igazoltuk a tetején levő állításokat, akkor abból az alul levőre következtethetünk. (A1) X ⊆Y YX (reflexivitás) (A2) X Y XW YW (bővítés) (A3) X Y ,Y Z X Z (tranzitivitás) N.B: Az (A1) átírható olyan alakba is, hogy a „semmiből” következtethetünk az YXX funkcionális függőségre: (A1’) XY X Így az Armstrong-axiómáknak rendre nulla, egy és kettő előfeltételük (bemenetük) van. Ha egészen pontosan akarunk fogalmazni, ezek az (A1’)

kivételével nem is igazi axiómák, hanem levezetési szabályok. Á.: Az Armstrong-axiómák helyesek, vagyis: 1. minden r esetén r ∈ SAT ( XY Y ) , 2. SAT(XY) ⊆ SAT(XWYW), 3. SAT(XY) ∩ SAT(YZ) ⊆ SAT(XZ) Biz. nélk Def.: Az F függőséghalmaz feletti levezetésnek nevezzük az X 1 Y 1 , , X n Y n funkcionális függőségekből álló véges sorozatot, ha minden i=1,,n esetén az X i Y i függőségre teljesül az alábbi feltételek valamelyike: 1. ( X i Yi ) ∈ F , vagy 2. (A1) Y i ⊆ X i , vagy 3. (A2) van olyan j<i, hogy a levezetés j-edik X j Y j tagjából az (A2) bővítési szabállyal kapjuk az X i Y i -t, vagyis valamely W attribútumhalmazra X i =X j W és Y i =Y j W. 4. (A3) van olyan k,l<i, hogy a levezetés k-adik és l-edik tagjából az (A3) tranzitivitási szabállyal kapjuk az X i Y i -t, vagyis X i =X k , Y k =X l és Y i =Y l . Az F függőséghalmazból levezethető az XY függőség, ha van olyan F

feletti levezetés, melynek az utolsó tagja pont az XY. Jelölés: F |– XY Def.: Adott F formulahalmaz és XY függőség esetén az F |– XY eldöntését szintaktikai implikációs problémának nevezzük. A következő állítás a levezetések összefűzésére épül. Lemma: (a levezethetőség „tranzitivitása”) Legyenek F, G függőség-halmazok. Tegyük fel, hogy teljesül az alábbi három levezethetőségi tulajdonság: 1. F |– X’Y’, 2. G |– X’’ Y’’, 3. {X’Y’, X’’Y’’} |– XY Ekkor F ∪ G |– XY. Biz.: Összefűzzük az (1), (2), (3) levezetéseit. Az így kapott sorozat valóban levezetése XY-nak, és csak F∪G-beli feltételeket használ fel. N.B: Az előző tétel miatt a levezetéseket a továbbiakban nem sorozatként hanem levezetési faként adjuk meg. Ezek olyan „emeletes törtek” amelyek egy fordított fát alkotnak, ahol a fa levelei a feltételhalmaz elemei, a fa gyökerében pedig a

levezetett következmény található. Vegyük észre, hogy ebben az a jó hogy a levezetési fákat össze tudjuk „ragasztani” és az összeragasztással is jó levezetéseket kapunk. Tétel: Az Armstrong-axiómákból következik az alábbi három állítás. 1. F |– XY, W ⊆ Y esetén F |– XW, (dekompozíció) 2. F |– XY, F |– XZ esetén F |– XYZ, (kompozíció) 3. F |– XY, F |– WYZ esetén F |– WXZ (pszeudo-tranzitivitás) Biz.: Elegendő megadni az állítások levezetési fáit. Az előző lemma miatt ekkor a bizonyítandó állítások valóban fennállnak. 1. A fa levelei az XY, W ⊆ Y lesznek W ⊆Y ( A1) X Y, Y W ( A3) X W Az előző lemma miatt G=∅ választással az XW függőség valóban következik Fből. 2. Most az XY és az XZ lesznek a fa leveleiben X Y X Z ( A2), ( A2) X XY XY YZ ( A3) X YZ Az előző lemma miatt F=G választással XYZ valóban következik F-ből. 3. Hasonlóan, az XY és WYZ

függőségeket vesszük fel a fa leveleibe X Y ( A2), WY Z WX WY ( A3) WX Z Az előző lemma miatt F=G választással XYZ valóban következik F-ből. Def.: Az F függőséghalmaz szemantikai következményeinek halmaza: F * = {X Y | F |= X Y } Az F függőséghalmaz szintaktikai következményeinek halmaza: F + = {X Y | F | − X Y } Egy ( )′ halmazfüggvényt lezárásnak nevezünk, ha ′ 1. H ⊆ (H ) , (extenzív) ′ ′ 2. F ⊆ G ⇒ (F ) ⊆ (G ) (monoton) ′ ′ ′ 3.  (F )  = (F ) (idempotens)   Á.: ( )* és ( )+ lezárások. Biz.: trivi (1,2 a definíciókból adódnak, a 3 bizonyítható a következményfogalmak tranzitivitására vonatkozó lemmákból) Á.: Az Armstrong-axiómák egy adekvát levezetési rendszert határoznak meg, abban az értelemben hogy F+=F* Biz.: (vázlat) 1. Helyesség: F + ⊆ F * . Levezetés hossza szerinti indukció Az i-edik lépésben esetszétválasztást csinálunk. Ha a sorozat i-edik tagja eleme

F-nek, akkor nyilván eleme F*-nak is (a lezárás miatt). Ha valamelyik axiómával került oda, akkor felhasználjuk az Armstrong-axiómák helyességére vonatkozó tételeket és a szemantikai következmény „tranzitivitásáról” szóló lemmát. 2. Teljesség: F * ⊆ F + . Indirekt bizonyítás Tegyük fel, hogy van egy XY függőség, melyre: XY nem vezethető le az F-ből. Konstruálunk egy kétsoros adattáblát, stb Attribútumhalmaz lezárása Mivel egy formulahalmaz következményeinek halmazát nehéz lenne kiszámolni, bevezetjük az attribútumhalmaz lezárását. Def.: Az X attribútumhalmaznak az F függőségekre vonatkozó szemantikai, szintaktikai lezárásai: X*(F)={A | F |= XA} X+(F)={A | F |– XA} Á.: 1. Ezek valóban lezárások 2. Minden X és F esetén X*(F)= X+(F). 3. F |– XY acsa, ha Y részhalmaza X+(F)-nek Biz. nélk Attribútumhalmaz lezárásának kiszámolása Megadunk egy iterációt: X 0 := X , X i +1 := X i ∪ {A | ∃(V W

) ∈ F : V ⊆ X i , A ∈W } Á.: Az iteráció egy idő után stabilizálódik, és X k =X k+1 esetén X k =X+(F). Biz. nélk Az iterációs algoritmus megvalósítása: o Naiv algoritmus Lezár(X,F) 1. Y := X 2. while (Y változik) do 3. foreach (VW) in F do 4. if (V része Y-nak) then 5. Y := Y+W 6. next 7. done 8. return Y o A naiv algoritmuson egy kicsit tudunk javítani, ha az 5. sorban még az épp felhasznált VW függőséget kivesszük az F-ből. Így a naiv algoritmus futásideje n2 nagyságrendű. o Javított (lineáris futásidejű) algoritmus: ld. Informatikai algoritmusok, 508 oldal Formulahalmazok ekvivalenciája Def.: F ekvivalens G-vel (F fedése G-nek) , ha F+=G+ Á.: A formulahalmazok ekvivalenciája valóban ekvivalenciareláció, és F fedése G-nek, acsa, ha F része G+-nak és G része F+-nak. Def.: F minimális fedése G-nek, ha 1. F fedése G-nek, 2. minden F-beli függőség jobb oldalán csak egy attribútum van, 3. ha F-ből elhagyjuk

valamelyik elemét, akkor az már nem fedése G-nek, 4. ha F valamelyik elemének a bal oldalát csökkentjük, akkor az már nem fedése G-nek. Á.: Minden formulahalmaznak létezik minimális fedése, és a minimális fedést mohó algoritmussal, a definícióban szereplő sorrend szerint elő tudjuk állítani az alábbi módon: MinFedés(F) 1. F := G 2. foreach (XY) in F, (Y nem egyetlen attribútum) do 3. F := F – (XY) 4. foreach A in Y, A not in X do 5. F := F + (XA) 6. next 7. next 8. foreach (XA) in F do 9. if (A in Lezár(X, F – (XA))) then 10. F := F – (XA) 11. end if 12. next 13. foreach (XA) in F do 14. foreach B in X do 15. if (A in Lezár(X, F – (XA) + ((X-B)A))) then 16. F := F – (XA) + ((X-B)A) 17. end if 18. next 19. next Az algoritmus elemzése: a minimális fedés kialakításakor az eredeti függőséghalmazból indulunk ki. A 2-7 sorokban végigmegyünk a függőségeken és mindegyiket szétvágjuk annyi kis

függőségecskére, ahány attribútum az ő jobb oldalán áll. A kompozíciós és dekompozíciós szabályok miatt a 7. sor után kapott eredmény valóban fedése G-nek A 8-12 sorokban sorban végignézzük az egyes függőségeket, hogy van-e köztük fölösleges, vagyis olyan amelyik következik a többiből. Mivel csak olyan függőséget dobunk ki, amelyik következik a többiből, a fedés tulajdonság nem romlik el. Fontos megjegyezni, hogy itt nem mindegy hogy milyen sorrendben megyünk végig az F halmaz elemein. Valóban, hiszen a függőségek „fölöslegességének” ellenőrzésekor valójában azt ellenőrizzük hogy következik-e a többiből, nem számítva az eddig kidobott függőségeket. A 13-19 sorban a függőségek bal oldalait csökkentjük amíg lehet, vagyis amíg a csökkentéssel kapott függőséghalmazból következik a csökkentés előtti függőség. Függőségek és dekompozíciók Def.: A d=(R 1 ,.,R m ) dekompozíció veszteségmentes

az F függőséghalmazra vonatkozóan, ha minden r ∈ SAT (F ) esetén md (r ) = mi=1 π Ri (r ) = r . ( ) Eljárás a veszteségmentesség ellenőrzésére (chase-algoritmus): készítünk egy próbatáblát, és utána erre alkalmazgatjuk egymás után az F függőségeit. Az eljárás egy olyan táblát állít elő, hogy a d dekompozíció veszteségmentes, pontosan akkor, ha a próbatáblára veszteségmentes. Chase(F) 1.Init(r) 1.1 r := {}:R(A 1 ,,A n ) 1.2 foreach R i in d 1.3 t := (b i ,.,b i ) 1.4 t[R i ] := (a,.,a) 1.5 r := r + t 1.6 next 2.foreach XY in F, A in Y do 3. while exists t 1 , t 2 in r, t 1 [X] = t 2 [X], t 1 [A] ≠ t 2 [A] do 4. if t 1 [A]=a then t 2 [A] := a 5. else 6. if t 1 [A]=a then t 1 [A] := a; 7. else 8. foreach t in r, t[A]=t 2 [A] do 9. t[A]:=t 1 [A] 10. next 11. end if 12. done 13.next 14.return r Á.: a Chase-algoritmus leáll, és a végén d veszteségmentes acsa, ha r tartalmaz csupa aból álló sort. Biz. nélk Következmény: A

d=(R 1 ,R 2 ) kétkomponensű felbontás veszteségmentes, (wrt F), acsa, ha F |– R 1 ∩ R 2  R 1 -R 2 vagy F |– R 1 ∩ R 2  R 2 -R 1 . Á.: t.fh d=(R 1 ,,R m ) vm wrt F, és d’=(S 1 ,,S k ) vm R 1 -re, wrt π R1 (F ) Ekkor d’’=(S 1 ,.,S k ,R 2 ,,R m ) is vm dekomp R wrt F Biz.: kijön a nyakkendő asszociativitásából (azt is mondhatjuk, hogy ld később, a relációs algebránál) Def.: Az F függőséghalmaznak az R i -re vett vetülete: π Ri (F ) = {X Y | X , Y ⊆ Ri , F | − X Y } A d dekompozíció függőségmegőrző az F függőséghalmazra vonatkozóan, ha ( m i =1 ) + π R (F ) = F + i N.B: a függőségmegőrzéshez elegendő ellenőrizni az alábbi tartalmazást: F ⊆ G + , ahol a G a fenti ronda halmaz (sok kis vetület uniója). Ahhoz, hogy ezt a tartalmazást ellenőrizzük, elegendő, ha az F egy XY eleméről el tudjuk dönteni, hogy benne van-e a G lezárásában. Ez viszont azzal ekvivalens hogy az Y részhalmaza az

X+(G)-nek. Most arra adunk egy eljárást, hogy ezt az attribútumhalmaz-lezárást hogyan lehet kiszámolni a G kiszámolása nélkül. VetületLezár(d, F) 1. Z := X 2. while (Z változik) do 3. foreach R i in d do 4. W := Lezár(Z metszet R i , F) 5. Z := Z + (W metszet R i ) 6. next 7. done 8. return Z Á.: a VetületLezár program terminál és az eredménye pont az X+(G) Biz. nélk N.B: a veszteségmentesség és a függőségmegőrzés nem következnek egymásból, semelyik irányba: lehet példát adni olyan dekompozícióra amelyik veszteségmentes, de nem függőségőrző, és olyanra is amelyik függőségőrző, de nem veszteségmentes. 1. Tekintsük az F={AB, CD} függőséghalmazt A d=(AB, CD) dekompozícióról látható hogy függőségőrző, de nem veszteségmentes. 2. Tekintsük a G={ABC, CA} függőséghalmazt A d=(AC, BC) dekompozíció veszteségmentes, de nem függőségőrző, ugyanis ABC elvész. Normálformák, normalizálási eljárások Az

előbbi fogalmakat és tételeket azért vezettük be, hogy a redundancia fogalmát formálisan is le tudjuk írni. A következőkben a normálformákkal feltételeket adunk meg arra, hogy egy adatbázisban ne legyen „túl sok” redundancia. Azt a stratégiát fogjuk követni, hogy az adatbázist szétvágjuk kisebb adattáblákra. A szétvágással csökkentjük a redundanciát, de vigyázni kell arra, hogy ne vágjuk szét túlzottan az adatbázist. Csak annyira vághatjuk szét az adatbázist, hogy a sok kicsi adattáblából vissza lehessen állítani az adatbázis tartalmát. Ez azt jelenti, hogy a normálformákat veszteségmentes dekompozíciókkal akarjuk elérni. Először bevezetjük a kulcsok és szuperkulcsok fogalmait. Def.: Az X attribútumhalmaz szuperkulcs az F függőséghalmaz szerint, ha F |– XR. Az X attribútumhalmaz kulcs, ha szuperkulcs, és bármely valódi részhalmaza már nem szuperkulcs. Ha egy kulcs egyetlen attribútumból áll, akkor az

egyszerű kulcs, ha többől, akkor összetett kulcs. Def.: Az R reláció séma Boyce-Codd normálformában van az F függőséghalmazra vonatkozóan, ha minden F+-beli XA nemtriviális függőség esetén X szuperkulcs. Az R reláció séma harmadik normálformában van az F függőséghalmazra vonatkozóan, ha minden F+-beli XA nemtriviális függőség esetén X szuperkulcs, vagy A elsődleges attribútum. Egy XY függőség nemtriviális, ha Y nem része X-nek. Az A attribútum elsődleges attribútum, ha része egy kulcsnak. Használni fogjuk az R BCNF, R 3NF, (wrt. F) rövidített jelöléseket is Láthatóan a 3NF gyengítése a BCNF-nek. N.B: Ha egy XA függőség bal oldala szuperkulcs, azt is mondhatjuk, hogy ez egy elkerülhetetlen függőség. Valóban, hiszen a szuperkulcsnak pont ez a definíciója Ezek alapján a BCNF definícióját úgy is megfogalmazhatjuk, hogy R BCNF (wrt F), ha minden F+beli nemtriviális függőség elkerülhetetlen. Á.: Legyen F

olyan függőséghalmaz, hogy minden elemének a jobb oldala egyetlen attribútum. Ekkor a normálformák ellenőrzéséhez elegendő az F-beli XA függőségeket nézni. Biz.: külön BCNF-re és 3NF-re, de mind a kettő strukturális indukció 1. BCNF: tegyük fel, hogy F |– XA Ha XA benne van az F-ben, akkor a feltevésünk miatt X szuperkulcs, készen vagyunk. Ha XA nincs benne az F-ben, akkor nézzük meg: vajon hogyan kerülhetett bele az F+-ba? Nyilván valamelyik axióma felhasználásával. De a felhasznált axióma nem lehetett az (A1), mivel A nem eleme X-nek. Nem lehet (A2) sem, mert A egyetlen attribútum Tehát az XA levezetésének az utolsó lépése a tranzitív szabály alkalmazása valamilyen XY, YA függőségekre. De akkor az YA függőségre ugyanezt el lehet játszani: vagy benne van F-ben, akkor jó, vagy ha nincs benne, akkor ő egy lépéssel rövidebb levezetéssel került az F+-ba, ezért feltehetjük hogy őrá már érvényes az

állításunk. Ezzel azt kapjuk, hogy Y szuperkulcs. De XY benne van F+-ban, ezért a tranzitivitási axióma felhasználásával az jön ki hogy akkor X is szuperkulcs. 2. 3NF: hasonlóan, eljutunk oda hogy XA benne van az F+-ban, de nincs F-ben Csak a tranzitív axiómával lehetett oda berakni, XY, YA. Indukciós feltevés miatt ekkor két lehetőségünk van: Y szuperkulcs vagy A elsődleges attr. Ha A elsődleges attribútum, akkor készen vagyunk, különben alkalmazzuk a tranzitivitást az XY, YR függőségekre, kijön hogy X szuperkulcs. Á.: Biz.: Minden kétattribútumos séma BCNF-ben van (tetszőleges függőséghalmazra). trivi. Következmény: minden kétattribútumos séma 3NF-ben van. Def.: A d=(R 1 ,.,R n ) dekompozíció (BCNF/3NF) normálformában van az F függőséghalmazra vonatkozóan, ha miden R i (BCNF/3NF) normálformában van az F vetületére vonatkozóan. N.B: azt szoktuk mondani, hogy a normálformák megszüntetik a

redundanciát, stb De közben mi szüntetjük meg a redundanciát, amikor egy adatbázis tervezésekor dekompozíciókat hozunk létre. Veszteségmentes BCNF felbontási algoritmus A naiv BCNF-felbontási algoritmus: vegyünk egy XA függőséget, amelyik megsérti a BCNF-et. A relációs sémát felbontjuk XA és R-A részekre, kiszámoljuk a függőséghalmaz vetületeit és az eljárást ismételjük XA és R-A –ra. NaívBCNF(R,F) 1. let XA in F, X nem szuperkulcs 2. d 1 := NaivBCNF(XA, vetület(XA, F)) 3. d 2 := NaivBCNF(R-A, vetület(R-A,F)) 4. Return d 1 +d 2 Látható, hogy a rekurzív hívások miatt ez az algoritmus exponenciális futásidejű. De a következő tétel alapján tudunk rajta javítani. Tétel: ha R nem BCNF akkor van olyan A és B, hogy F |– (R-AB)A. Biz.: tfh az XA függőség megsérti a BCNF feltételt: F |– XA, de X nem szuperkulcs De akkor az R-XA nemüres. Valóban, ha XA=R fennállna, akkor X szuperkulcs lenne, akkor viszont az XA

mégsem sértené meg a BNCF feltételt. Legyen B egy attribútum R-XA-ból Ekkor R-ABA fennáll. Valóban, az (A1) axióma miatt R-ABX teljesül, innen tranzitivitással kapjuk a bizonyítandó állítást. N.B: ez a tétel nem fordítható meg, vagyis van olyan relációséma, amelyik BCNF, de mégis vannak olyan A,B attribútumok, amilyenekről a tétel beszél. Példa: Film, Főszereplő, Szinkronhang Függőségek: o Film  Főszereplő o Film Főszereplő  Szinkronhang o Most feltesszük, hogy csak a főszereplő nem határozza meg a szinkronhangot, vagyis egy színészt különböző filmekben mások szinkronizálhatnak. Valóban, A=Főszereplő, B=Szinkronhang választással: Film  Főszereplő fennáll, de ez a relációséma BCNF-ben van, u.i a Film attribútum kulcs A javított BCNF felbontási algoritmus. DekompBCNF(R,F) 1. Z := R; 2. d := (); 3. repeat 4. if exists A,B in Z: A in Lezár(Z-AB, F) then 5. Y := Z-B; 6. while exists A,B in Z: A in Lezár(Y-AB, F)

do 7. Y := Y-B 8. done 9. d := d + (Y); 10. Z := Z-A; 11. else 12. Z BCNF 13. end if 14. until (Z BCNF) 15. d := d+(Z); 16. return d Az algoritmus elemzése: a Z változóban tartjuk a táblából még meglevő, nem biztosan BCNF részt. A főciklusban olyan attribútumokat keresünk, amelyek megfelelnek a javításhoz használt tételnek. Ha ilyen nincsen, akkor a Z-ben levő maradék-séma már BCNF, ezért készen vagyunk a dekompozícióval. Ha a Z még nem BCNF, akkor az lesz a célunk, hogy kivágjunk belőle egy olyan részt, amelyik már BCNF-ben van. Ehhez az Y=Z-B-ből indulunk ki, és a javító tétel felhasználásával egyenként harapdálunk ki belőle attribútumokat. Ha már nem tudunk kiharapni többet, az azt jelenti, hogy az Y BCNF, ezért beírhatjuk a készülő dekompozíciónkba. Függőségőrző veszteségmentes felbontás 3NF-re Legyen G := MinFedés(F), S := R – attr(F). T.fh G = { X 1 A1,,X n A n } d = (S, X 1 A 1 ,.,X n A n ) Ez nyilván

függőségőrző, mivel a komponenseket direkt a G függőségeiből gyártottuk le. Ha ez még nem veszteségmentes akkor hozzáveszünk egy kulcsot. d = (S, K, X 1 A 1 ,.,X n A n ) Összevonások: (!!!fontos, ha valóban használható adatbázist akarunk készíteni!!!) d = (S, (K, ), XABC., YPQRS, ) Dekomp3NF(R, F) 1. G := MinFedés(F) 2. S := R – attr(F) 3. d := (S) 4. while exists XA in G do 5. Y := A; 6. G := G – {XA} 7. while exists XB in G do 8. Y := Y+B 9. G := G – {XB} 10. done 11. d := d+(XY); 12. done 13. (d := d + K kulcs hozzávétele, ha kell) Példa olyan relációsémára amelyik 3NF-ben van de nincs BCNF-ben. Cím(város, utca, irányítószám). Függőségek: város utca  irányítószám irányítószám  város Valóban, u.i ennek a sémának két kulcsa van: 1. város utca 2. irányítószám utca Ha például a város utca kulcsot választjuk akkor az irányítószám  város egy kulcstörő függőség. BCNF-re hozott változat:

Cím1(irányítószám, utca) Cím2(irányítószám, város) Többértékű függőségek, negyedik normálforma A többértékű függőség informális definíciója: ha többértékű attribútumokat tartalmazó adatmodellt relációs sémával akarunk megvalósítani, előállhat olyan eset, hogy bizonyos attribútumokat rögzítve, a többi attribútum független komponensekre bomlik. Egy táblára teljesül az XY többértékű függőség, ha az X-en megegyező sorokat tekintve, az Y és az R-XY oszlopokban levő attribútumok függetlenek. Ezt azt jelenti, hogy ha van két sorunk, amelyek az X-ben megegyeznek, akkor az Y és R-XY értékek oda-vissza cserélgetésével is olyan sorokat kapunk, amelyek benne vannak az adattáblában. X Y R-XY t1 t’ t2 Def.: Többértékű függőség (MVD) XY. Az r reláció előfordulás megfelel az XY többértékű függőségnek, ha ∀t1 , t 2 ∈ r : (t1 [X ] = t 2 [X ]) ⇒ ∃t ∈ r : t [XY ] = t1 [XY ] ∧ t

[R − XY ] = t 2 [R − XY ] Vegyük észre hogy ez majdnem ugyanaz mint a bővített identitás bevprogból. Jelölés: r |= XY N.B: A definícióból következik olyan t’’ ∈ r létezése is, amelyre: t’’[XY]=t 2 [XY] és t’’[R-XY]=t 1 [R-XY]. Vagyis a t’’ pont fordítottja a t’-nek, a t’’-ben az Y mező vízszintesen lesz csíkos, az R-XY mező meg cakkos lesz. És természetesen az X mező most is sraffozott Látható, hogy a többértékű függőség definíciója bizonyos sorok létezését követeli meg. A funkcionális függőségekhez hasonlóan definiáljuk a SAT(XY) halmazt. A továbbiakban legyen F funkcionális és többértékű függőségek halmaza (függőséghalmaznak, formulahalmaznak is nevezzük az ilyen halmazokat). A SAT(F) halmazt az előzőekhez hasonlóan a benne levő függőségek SAT-jainak a metszeteként definiáljuk, és hasonlóan felírhatjuk az F |= XY, illetve F |= XY szemantikai eldöntésproblémákat.

Világos hogy a metszetes definíció miatt ebben az esetben is fennáll a szemantikai következmény „tranzitivitására” vonatkozó lemma. A szemantikai eldöntésprobléma megoldására az Armstromg-axiómákat bővítjük a többértékű függőségekre vonatkozó axiómákkal. A bővített Armstrong-axiómák (A4) X Y X R − Y (komplementálás) (A5) X Y , V ⊆ W WX VY (bővítés) (A6) X Y , Y Z X Z − Y (tranzitivitás) (A7) X Y X Y (gyengítés) (A8) X Y , Z ⊆ Y , W Z , W ∩ Y = ∅ X Z (szigorítás) Ezek alapján definiálhatjuk a levezetéseket, most nyolc axiómával. A levezethetőség jelölése most is F |– XY illetve F |– XY. Mivel a levezetéseket most is össze lehet fűzni, a többértékű függőségek esetén is fennáll a levezethetőség „tranzitivitását” kimondó lemma. Tétel: 1. 2. 3. 4. A bővített Armstrong axiómákból következik az alábbi négy állítás. F |– XY, F |– XZ

esetén F |– XYZ (kompozíció) F |– XY, F |– WYZ esetén F |– XZ-XW (pszeudo-tranzitivitás) F |– XY, F |– XYZ esetén F |– XZ-Y (vegyes pszeudo-tranzitivitás) F |– XY, F |– XZ esetén (vágás) a. F |– XY metszet Z b. F |– XY-Z c. F |– XZ-Y Formulahalmaz szemantikus és szintaktikus lezárásai: mint az FD-knél. Á.: az (A1-A8) bővített axiómarendszer adekvát: F+=F*. Biz.: (vázlat) 1. Helyesség: csak az egyes axiómák helyességét kell belátni Akit érdekel, a bizonyításokat összedobálhatja, nem nehezek. Ebből a következményfogalmakra kimondott lemmák alapján adódik a bővített Armstrong-axiómarendszer helyessége. 2. Teljesség: nehéz, itt nem tárgyaljuk Def.: Az R relációséma negyedik normálformában van az F függőséghalmazra vonatkozóan, ha minden F+-beli XY nemtriviális függőség esetén X szuperkulcs. A nemtriviális függőség alatt most azt értjük,

hogy Y nem része X-nek és XY ≠ R. Nyilván 4NF-ből következik BCNF. Minden kétattribútumos séma 4NF N.B: Figyelem! A szuperkulcs továbbra is az XR funkcionális függőségre vonatkozik! Most is érvényes az a megjegyzés, amit a BCNF-nél tettünk: ha X szuperkulcs, akkor az XY függőség elkerülhetetlen. Valóban, hiszen az XR FD-ből következik az XR MVD, az (A7) axióma miatt. Ezért azt is mondhatjuk: egy R séma 4NF (wrt F), ha minden F+-beli nemtriviális (funkcionális vagy többértékű) függőség elkerülhetetlen. Veszteségmentes 4NF felbontási algoritmus A 4NF-re hozás a naiv-normalizálás algoritmussal: ha találtunk egy XY többértékű függőséget, amelyik megsérti a negyedik normálformát, akkor a táblát szétvágjuk XY, X(RY) részekre (ld. Informatikai algoritmusok) A 4NF megszünteti az attribútumfüggetlenségből eredő redundanciát. Példa: Tárgy Tanár Jegyzet

Adatbázisok Kiss Ullman: Adatbázisrendszerek Adatbázisok Kiss Informatikai algoritmusok Analízis Fridli Leindler-Schipp Analízis Fridli Pál-Schipp-Simon Algoritmusok Fekete Cormen: Új algoritmusok Algoritmusok Fekete Rónyai: Algoritmusok Algoritmusok Fekete Knuth: The art of computer programming Látható, ebben a táblában sok felesleges ismétlődés (redundancia!) található, mivel ha egy tárgyhoz több jegyzet tartozik akkor a tárgyat előadó tanár nevét is annyiszor be kell írni. Ilyen eset akkor állhat elő, ha a táblát egy olyan egyed-kapcsolat modellből állítottuk elő, ahol a Jegyzet egy többértékű mező. (ld később) A következő többértékű függőséget állapíthatjuk meg: Tárgy  Jegyzet. Most: X=Tárgy, Y=Jegyzet. A sémát felbontjuk az XY = Tárgy Jegyzet és az X(R-Y) = Tárgy Tanár táblákra. Tárgy Tanár Adatbázisok Kiss Analízis Fridli Algoritmusok Fekete Tárgy Jegyzet

Adatbázisok Ullman: Adatbázisrendszerek Adatbázisok Informatikai algoritmusok Analízis Leinder-Schipp Analízis Pál-Schipp-Simon Algoritmusok Cormen: Új algoritmusok Algoritmusok Rónyai: Algoritmusok Algoritmusok Knuth: The art of computer programming Létezik még a függőség fogalmának egy további általánosítása, az összekapcsolási függőség. Összekapcsolási függőségnek (JD) nevezünk egy  [R1 ,  , Rn ] alakú kifejezést, és azt a követelményt jelenti hogy az adattáblákra az R 1 ,.,R n dekompozíció legyen veszteségmentes Felírhatjuk az eldöntésproblémát az összekapcsolási függőségekre is, de ebben az esetben nem lehet adekvát axiómarendszert konstruálni. Az összekapcsolási függőség fogalmából aztán levezethetjük az ötödik normálforma fogalmát: egy R séma 5NF, ha minden nemtriviális összekapcsolási függősége elkerülhetetlen. Hogy mit értünk egy összekapcsolási függőség nem-triviális vagy

elkerülhetetlenségi tulajdonságán azt nem tárgyaljuk részletesen. Elég annyit megjegyezni hogy a nyakkendőfüggőség egy általánosítása a többértékű függőségnek (egy többértékű függőség felírható kételemű összekapcsolási függőségként). Ebből következik az is, hogy minden 5NF séma 4NF is. Még megjegyezzük azt is, hogy ha egy adattábla 5NF-ben van, akkor nagyon ritka esetektől eltekintve 4NF-ben is van. Normálformák összefoglalása A redundancia fajtáira formális modellt adtunk: FD, MVD, (JD). Megadtunk olyan eljárásokat, amelyekkel megszüntethetjük egy adatbázisban a redundanciát. A normálformák definíciójakor korlátoztuk azt, hogy milyen függőségek fordulhatnak elő egy függőséghalmaz következményei között. Úgy is mondhatjuk, hogy a normálformák megtiltják a közvetett függőségeket. Nevezetes nemkívánatos (közvetett) funkcionális függőségek: 1. Kulcstól való részleges függés Példa: Cégnév, Év,

Bevétel, Igazgató. Függőségek: o Cégnév Év  Bevétel o Cégnév  Igazgató Itt az a probléma, hogy az igazgató neve csak a cégnévtől függ, de a mostani példánkban az évszámtól nem. (persze ez a valóságban nem biztos, hogy így van) 2. Kulcstól való tranzitív függés Példa: Film, Rendező, Rendező telefonszáma. Függőségek: o Film  Rendező o Rendező  Rendező telefonszáma 3. Kulcstörő függés Példa: Város, Utca, Irányítószám Függőségek: o Város Utca  Irányítószám o Irányítószám  Város Ez olyan esetet jelent, amikor egy függőség jobb oldalán összetett kulcs egy része áll. Normálformák o 1NF – azt követeli meg, hogy csak egyértékű, egyszerű attribútumok legyenek. A relációs modellben ez mindig teljesül. o 2NF – megköveteli, hogy a kulcstól való függés mindig teljes legyen, ezért megszünteti az összetett kulcstól való részleges függésből adódó redundanciát. Ha egy tábla 1NF és

egyszerű kulcsa van, akkor biztosan 2NF is. o 3NF – megszünteti a részleges függésből és a tranzitív függésből adódó redundanciát. Ha egy tábla 2NF és a nemkulcs attribútumok között nincs függőség, akkor 3NF is. o BCNF – megszüntet minden közvetett FD-ből adódó redundanciát. Úgy is szokás mondani, hogy megszünteti a nemkulcs típusú redundanciát. Gyakorlatban a 3NF táblák nagy része BCNF-ben is van. Egy 3NF tábla csak akkor tudja megsérteni a BCNF feltételeit, ha több összetett kulcsa van. Ilyenkor előfordulhatnak kulcstörő függőségek is, amit a 3NF nem szüntetne meg. o 4NF – megszüntet minden FD-ből és MVD-ből adódó redundanciát, ezért megszünteti az attribútumfüggetlenségből adódó redundanciát is. o 5NF – inkább csak elméleti jelentősége van. Általában ha egy tábla 4NF akkor 5NF is, kivéve ha van benne olyan összekapcsolási függőség, amelyiket két részre való felbontással nem lehetne

megszüntetni. A 2NF-4NF mindegyikére használható a naiv normalizálási eljárás: XY vagy XY rossz függőség esetén a sémát felbontjuk XY és X(R-Y)-ra. Normálformák használatának kérdései Általában egy adatbázis tervezésekor törekedjünk legalább a harmadik normálforma elérésére. Ha egyszerű kulcsot használunk és az adatbázis 3NF-ben van akkor, általában már nem nagyon tér el a magasabb normálformáktól. A magasabb normálformák nem minden esetben jobbak, mert ha egy adatbázist több adattáblára tördelünk szét, akkor összetett lekérdezések készítéséhez több összekapcsolásra van szükség, ami növeli a lekérdezés műveletigényét. Ha egy adatbázis több kicsi táblából áll, akkor a frissítések is bonyolultabbak lesznek. Másik érv a túlnormalizálás ellen az, hogy a magasabb normálformákban nem minden esetben tudunk függőségőrző dekompozíciót létrehozni. A függőségőrző dekompozíció azért

fontos, mert így táblaszinten definiált megszorításokkal kikényszeríthető az adatbázis konzisztenciája. Példa: Ügyfél(Ügyfél neve, Város, Utca, Irányítószám) Az ir.szám meghatározza a várost, de nem érdemes különválasztani: a lekérdezések bonyolultabbakká válnának. Ha ez a tábla egy vállalat ügyfeleit tárolja, akkor nem is igazán fontos szempont az irányítószámok ilyen fajta konzisztenciája. Példa nem-függőségőrző BCNF-re: Könyvek(Szerző, Cím, Kiadó). Tegyük fel hogy egy szerzőnek a művei csak egy kiadónál jelennek meg. Továbbá, egy kiadónál nem jelenik meg két azonos című könyv. Ezt a következő funkcionális függőségekkel tudjuk leírni: o Szerző  Kiadó o Kiadó Cím  Szerző. A séma kulcsai a Kiadó, Cím és Szerző, Cím összetett kulcsok. Látható, hogy a Szerző  Kiadó egy kulcstörő függőség, ezért a sémát szét kell bontani két részre: o KönyvetÍr(Szerző, Cím) o

KönyvetKiad(Kiadó, Cím) Azonban most a Kiadó Cím  Szerző funkcionális függőség elveszett. Valóban, a következő táblákra teljesül az eredeti függőséghalmaz vetítése, de a második funkcionális függőség nem: Szerző Kiadó Rónyai Typotex Knuth Typotex Szerző Rónyai Knuth Cím Algoritmusok Algoritmusok Ebben az esetben a Typotex kiadónál két algoritmusok könyv is megjelent (különböző szerzővel), de ezt csak úgy derül ki, ha a két táblát összekapcsoljuk. Egyed kapcsolat (E/K) modell Az egyed-kapcsolat modell (entity-relationship model, E-R model) más néven egy szemantikus objektummodell. Ez azt jelenti, hogy az E/K modell központi fogalma az egyed, ami olyan, mint egy objektum. (ezért az E/K modellre szokás azt is mondani, hogy ez egy objektum-orientált adatmodell). Az E/K modellben az egyedeknek jellemzői vannak, amiket attribútumoknak nevezünk. Az egyedek egymással kapcsolatban állhatnak Az E/K modell alapfogalmai

„definíció nélkül”: o Egyed, attribútum: egyednek nevezünk egy önállóan létező dolgot. Az egyed attribútumai olyan jellemző tulajdonságok, amelyek alapján az egyedeket azonosítani tudjuk. Két egyed azonos, ha minden tulajdonságuk megegyezik Formális definíció: az egyed egy e=(A 1 :a 1 ,.,A n :a n ) n-es, ahol az A i -k az attribútumok nevei, az a i -k az attribútumok értékei. o Egy attribútum lehet egyszerű, ha csak egy értéke van és az nem bontható részekre. Ha ezek valamelyike nem teljesül akkor összetett attribútumról beszélünk. Az összetett attribútum lehet többértékű vagy többrészes attribútum. Példa: o Egyszerű attribútum egy ember életkora. o Többértékű attribútum lehet a telefonszám: egy embernek lehet több telefonszáma is. o Többrészes attribútum lehet a lakcím: egy cím felbontható irányítószám, település, utca és házszám részekre. o Egyedosztály: egy egyedosztály séma az egyedosztály nevét és

az osztályba tartozó egyedek attribútumainak a neveit tartalmazó séma. Az egyedosztály előfordulás a sémának megfelelő egyedek halmaza. Formálisan: az egyedosztály-séma egy E(A 1 ,.,A n ) alakú szignatúra, E az egyedosztály neve, az A i -k az attribútumok nevei. Az egyedosztály előfordulás (e(A 1 ),.e(A n )) alakú n-esek halmaza o Kapcsolat: egy kapcsolat séma a kapcsolat nevét és a benne résztvevő egyedosztályok neveit tartalmazza. A kapcsolat előfordulás egy olyan halmaz, amelyikben a megfelelő egyedosztályokba tartozó egyedekből álló rendezett n-esek vannak. Egy kapcsolatnak is lehetnek attribútumai, ekkor a sémában megadjuk az attribútumok neveit, illetve a kapcsolat előfordulása olyan n-esekből áll, amelyek egyedeket és kapcsolat-attribútumokat tartalmaznak. Formálisan: a kapcsolat-séma egy K(E 1 ,.,E n ,A 1 ,,A k ) alakú szignatúra, K a kapcsolat neve, az E i -k a résztvevő egyedosztályok nevei, az A i -k a kapcsolathoz

tartozó attribútumok nevei. Gyakran k=0, ekkor a kapcsolatnak nincsenek saját attribútumai. o Bizonyos esetekben előfordulhat hogy olyan „objektumokat” is bele kell venni az E/K modellbe, amelyek nem önállóan léteznek (pl. vállalatok részlegei) Ilyenkor gyenge egyedosztályról beszélünk. A gyenge egyedosztályba tartozó gyenge egyedek nem képesek önállóan létezni, hanem csak egy „normál” (nem gyenge) egyedhez való kapcsolaton keresztül. Ezek mindig 1:N kapcsolatok, amelyiknek a „sok” oldalán szerepel a gyenge egyedosztály. Kapcsolattípusok o Egy kapcsolat bináris, ha két egyedosztály vesz benne része (a sémája K(E 1 ,E 2 ) alakú) o A K bináris kapcsolat N:1 típusú (sok-egy), ha minden e1 ∈ E1 -hez legfeljebb egy darab e2 ∈ E 2 -t rendel. o Hasonlóan 1:M (egy-sok), M:N (sok-sok), 1:1. o Lehetőség van egy kapcsolat végződéseihez szerepneveket rendelni. Ezek segítenek a rekurzív és a párhuzamos kapcsolatok értelmezésében

o Egy kapcsolatot rekurzív kapcsolatnak nevezünk, ha mindkét végén ugyanaz az egyedosztály van. Például egy többszintű vállalati hierarchiában az alkalmazottak között egy rekurzív kapcsolat lehet a főnök-beosztott viszony. o Párhuzamos kapcsolatokról beszélünk, ha több kapcsolat állhat fenn ugyanazon egyedosztályok között. Például a Személy és Cég egyedosztályok között lehetséges kapcsolat az Alkalmaz és a Birtokol. Egyik a cég és alkalmazottai között áll fenn, másik a cég és a cégtulajdonosok között. Egy részvénytársaság esetén (sok részvényes, stb.) e két kapcsolat között nagyon kicsi lehet az átfedés! o Az isa (az-egy) kapcsolat egy speciális 1:1 kapcsolat: minden e1 ∈ E1 -hez pontosan egy darab e2 ∈ E 2 -t rendel. Integritási feltételek megfogalmazása az E/K modellben o Értéktartomány megszorítások (mezőszintű integritás) Az egyedek attribútumaihoz megadhatjuk az attribútum által felvehető értékek

halmazát. Gyakran nem a felvehető értékek halmazát adjuk meg, hanem az attribútum típusát, ami a felvehető értékeken kívül az attribútum-értékeken értelmezett műveleteket és lehetséges összehasonlításokat is meghatározza. o Egyedintegritás, kulcsok: az egyedintegritás fogalma azt jelenti, hogy két különböző egyednek nem lehetnek egyenlők az attribútumai. o Szuperkulcs: olyan attribútumhalmaz, amelyik az egyedet egyértelműen meghatározza. Kulcsjelölt: minimális szuperkulcs o Ha egy egyedosztályban több kulcsjelölt van, akkor a tervezés során ki kell választani közülük azt, amelyiket az egyedek azonosítására fogjuk használni. Ezt a kiválasztott kulcsjelöltet nevezzük elsődleges kulcsnak. A többi kulcsjelöltet alternatív kulcsnak nevezzük. o Az egyedintegritás ekvivalens átfogalmazása hogy minden egyedosztálynak legyen kulcsa. o Hivatkozási integritás, idegen kulcsok. o Legyen X egy attribútumhalmaz. Az X E 1 -beli idegen

kulcs az E 2 egyedosztályhoz, ha X elsődleges kulcsa E 2 -nek és az X E 1 -beli értékei mind szerepelnek az E 2 -ben. o Az idegen kulcsok segítségével megfogalmazhatunk hivatkozási integritás jellegű követelményeket, amennyiben megköveteljük, hogy a hivatkozott egyed valóban létezzen. Az E/K diagram Az egyedosztályokat az E/K diagramon téglalappal jelöljük, amihez hozzákötjük az attribútumait jelölő köröket (v. tojásokat, ha az attribútum neve hosszú) Az elsődleges kulcs attribútumait aláhúzzuk. Példák Film(Cím, Rendező, Év) Feltesszük hogy nincs két egyforma című film, ezért a Cím mező az elsődleges kulcs. Film Cím Rendező Év Példa összetett kulcsra Oscar-díj(Év, Kategória, Díjazott) Feltehetjük, hogy egy évben egy kategóriában csak egy ember kap díjat, ezért most az Év Kategória összetett kulcsot használjuk. Oscar-díj Év Kategória Díjazott A többértékű attribútumot dupla karikázással

jelöljük, a többrészes attribútumhoz ugyanúgy kötjük hozzá a komponenseit, mintha ő egy egyedosztály lenne. Figyelem! Általában, ha lehet, kerüljük az összetett attribútumokat! A következő példa csak elrettentésnek van itt. Színészek Cím Város Utca Név Telefonszám Házszám Kapcsolatok jelölése rombusszal, kapcsolatok attribútumait ugyanúgy jelöljük, mint az egyedosztályoknál. Filmek Szerepel Színészek Hallgató Tanul Tantárgy Jegy Az 1:N kapcsolatot úgy jelöljük, hogy az „1” oldalra nyilat teszünk. Filmek Rendezi Rendezők Az 1:1 kapcsolatnál mindkét oldalra nyilat teszünk. Többágú kapcsolatnál, ha egy résztvevő egyedosztálynál nyíl van, az azt jelenti, hogy az összes többi egyedosztály értéke együtt meghatározza azt, ahol a nyíl van. Filmek Szerepel Színészek Szerződés Ebben a példában azt láttuk, hogy egy színész-film párhoz csak egy szerződés tartozhat, vagyis egy színész egy

filmre csak egyszer köthet szerződést. Az Isa kapcsolatot háromszöggel jelöljük. Menedzser Prémium Azegy Alkalmazott Név Fizetés A gyenge egyedosztályokat és a hozzájuk tartozó kapcsolatokat dupla kerettel jelöljük. Példa: Egy vállalatnak lehet több osztálya, például értékesítési osztály, kutatás-fejlesztési osztály. Azonban a vállalatok osztályai nem létezhetnek önmagukban. Ráadásul egy vállalat osztályának nincs olyan jellemzője, amelyik egyértelműen azonosítaná. Valóban, több vállalatnak is lehet értékesítési osztálya. Ezért az osztály egy gyenge egyedosztály  Vállalatok Cégnév Adószám Osztály Név Főnök neve Egyed-kapcsolat modell átírása relációs sémákká !!! transzformációk !!! o Promote attribute to entity type (többértékű attrib.!) o Compound attribute felbontása o Entity type expansion (split entity type) o Weak to strong entity type o ?? history transformation ?? o generalization

hierarchy bevezetése (sok NULL helyett) o promote relation to entity type o biztos van még, majd megnézem az OOMDwUML könyvben. o Többes asszociáció transzformálása kapcsoló (gyenge) osztály bevezetésével o Kapcsolat attribútumainak megszüntetése új egyedosztály bevezetésével o Csillag-klaszterek bevezetése(?) Minden nem gyenge egyedosztálynak megfeleltetünk egy relációsémát, a relációséma attribútumai az egyedhalmaz attribútumai, a relációséma kulcsa az egyedhalmaz kulcsattribútumaiból fog állni. Minden kapcsolatnak megfeleltetünk egy relációsémát, amelyiknek az attribútumai a kapcsolatban résztvevő egyedosztályok elsődleges kulcsai és a kapcsolat attribútumai (ha vannak). Rekurzív kapcsolat esetén a kulcsokat át kell nevezni! Elsődleges kulcs, idegen kulcsok meghatározása. Speciális esetek: 1-1, 1-N Gyenge egyedhalmaz átírása. Az ISA kapcsolat átírása o Hagyományos megoldás o NULL-értékek használata o OOP típusú

megoldás Példák. Összevonások. Normalizálás. Adatbázis-tervezési módszerek összefoglalása Az adatbázis-tervezési folyamat általában a rendszerelemzés, tervezés és megvalósítás lépéseiből áll. A rendszerelemzés során meg kell vizsgálni az adatbázisban tárolandó adatokat és az adatbázis felhasználására vonatkozó igényeket. A rendszerelemzés eredménye a rendszer fogalmi modellje. A fogalmi modell lehet E/K modell, UML statikus modell, stb A fogalmi modellből kiindulva a tervezés során kialakítjuk az adatbázis logikai felépítését. A tervezés eredménye a rendszerterv. A rendszertervben részletesen le kell írni a táblák és mezők szerkezetét, a nézettáblákat, a kulcsokat és az integritási feltételeket és a fizikai szintre vonatkozó döntéseket (indexek, oszlopok típusa, stb.) A megvalósítás során létrehozzuk a rendszertervben megadott táblákat, indexeket, nézeteket, és betöltjük az adatbázisba a kezdeti

értékeket. Finomítás, stb az egyes fázisok lépései! Régen úgy tervezték az adatbázisokat, hogy elkészítették a mezők listáját és utána azt adattáblába és kapcsolatokba rendezték össze. Ezután jöhetett az iteratív normalizálás darálója: megnézték hogy az adatmodell aktuális változata valahol megsérti-e egy normálforma szabályait, és ha ilyet találtak, akkor dekompozíciót hoztak létre. A végén a normalizált adatmodellben lehetett megfogalmazni az integritási feltételeket. Ezzel a módszerrel van néhány probléma: 1. a függőségek meghatározása nehéz, sokszor nem is lehet teljesen felderíteni az összes függőséget, könnyen ki lehet hagyni néhányat 2. az iteratív normalizálás nem egy jól működő módszer, keresgélni kell a nemnormalizált táblákat, nem lehet igazán tudni, hogy az egész mikor áll le 3. a mezőlista-készítés technikája nem hatékony, nehezen integrálható egy fejlesztés többi folyamatával

(ugyanis a mezőlistán alapuló adatbázistervezés egy bottom-up tervezési módszer, míg a szoftvereket általában top-down, lépésenkénti finomítással szokták tervezni) Ezekre a problémákra Hernandez egy olyan tervezési módszert javasol, ahol a tervezési folyamat lépéseibe ellenőrzések vannak beépítve, így a végén (legalábbis az ő állítása szerint) egy normalizált táblaszerkezet jön ki. A mezőlista előtt egy előzetes táblalista elkészítését is javasolja, a meglevő adatkezelési szokások feltárásával. Az Object Oriented Modeling and Design című könyvben azt látjuk, hogy az adatbázisok táblaszerkezete akár UML használatával is megtervezhető. Az UML statikus modell osztályait objektum-azonosító mezők bevezetésével tudjuk relációs adattáblákba átírni. Az asszociációk megvalósítására ugrótáblák használatát javasolják. 9.) Lekérdező nyelvek Lekérdező nyelvnek nevezünk egy olyan formális nyelvet, amelyet

arra lehet használni, hogy egy adatbázisból információt nyerjünk ki. A lekérdezőnyelvben megfogalmazható kifejezéseket nevezzük lekérdezésnek. A lekérdezések jólformáltsági szabályait nevezzük a lekérdező nyelv szintaxisának. Ha van egy lekérdezésünk, akkor azt szeretnénk végrehajtani Pontosabban fogalmazva, a lekérdezést kiértékeljük egy adatbázis-előforduláson. A kiértékelés szabályait a lekérdező nyelv szemantikája határozza meg. Ha elvégeztük a lekérdezés kiértékelését a lekérdező nyelv szabályai alapján, akkor megkapjuk a lekérdezés eredményét. Vagyis fontos hogy lássuk a különbséget a lekérdezés mint kifejezés (karaktersorozat), a lekérdezés kiértékelése (szemantikai szabályok alkalmazása egy kifejezés alapján, egy konkrét adatbázison) és a lekérdezés eredménye között. Azt is mondhatjuk, hogy egy lekérdezés meghatároz egy leképezést, ami az adatbázis aktuális tartalmához rendeli hozzá a

lekérdezés eredményét. Egy lekérdező nyelvre azt mondjuk, hogy operatív, ha a szemantikai szabályai az eredmény kiszámítására egy eljárást határoznak meg. Egy lekérdező nyelv deklaratív, ha a szemantikája a lekérdezés eredményét logikai feltételekkel határozza meg. Bemutatunk egy operatív lekérdező nyelvet: a relációs algebrát; és egy relációs logikát, amelyik deklaratív lekérdező nyelvnek is tekinthető: a relációs kalkulust. A végén pedig jön az SQL.  Relációs algebra A relációs algebra értelmezéséhez meg kell adni, hogy mik az operandusok és mik a relációs algebrai műveletek. o Az operandusok a relációs adatmodell reláció-előfordulásai. Minden ilyen reláció előfordulásnak van sémája, pl r:R(A 1 ,.,A n ) A mezők értékei csak egyszerű értékek lehetnek (számok, stringek.) o A relációs algebrában az alábbi alapműveletek értelmezettek: 1. Unió Ha r és s két reláció-előfordulás és a sémáik

illeszkednek, abban az értelemben, hogy az oszlopok száma és nevei megegyeznek, vehetjük az r és s unióját. Ez megegyezik a halmazoknál szokásos unió művelettel: az eredmény olyan reláció lesz, amelyikbe az r és s sorai vannak összeöntve, de duplikátok nélkül. Formálisan: r , s : R( A1 , , An ), r ∪ s : R( A1 , , An ) r ∪ s = {t | t ∈ r ∨ t ∈ s} 2. Kivonás Hasonlóan, ha r és s sémái illeszkednek, képezhetjük a különbségüket, ugyanúgy, mint a halmazok különbségét. r − s = {t | t ∈ r ∧ t ∉ s} 3. Szorzás Ez a halmazok direktszorzásának felel meg Azonban csak akkor van értelmezve, ha a két összeszorzott reláció attribútumai mind különböző nevűek. r : R( A1 , , An ), s : S (B1 ,  , Bm ) (Ai ≠ B j ), r × s : P( A1 ,  , An , B1 ,  , Bm ) r × s = {t | t [A1  An ] ∈ r ∧ t [B1  Bm ] ∈ s} 4. Vetítés Ilyenkor egy relációnak bizonyos oszlopait elhagyjuk r : R( A1 ,  , An ), X ⊆ {A1 , 

, An }, π X (r ) : P( X ) π X (R ) = {t | ∃t ∈ r : t = t [X ]} 5. Kiválasztás Egy relációból kiválogatjuk azokat a sorokat, amelyek megfelelnek egy feltételnek. A feltételt egy (nullarendű) „minikalkulusban” fogalmazzuk meg, amelyben hivatkozhatunk a reláció attribútumaira a nevükkel vagy $i alakban a számukkal, használhatunk ezekből képzett összehasonlításokat (=, <, > stb.) és használhatjuk a nullarendű logikai műveleteket (OR, AND, NOT). Formálisan: r : R( A1 , , An ), σ F (r ) : R( A1 , , An ) σ F (r ) = {t | t ∈ r ∧ F (t ) = igaz} ahol az F egy olyan feltétel, ami elemi összehasonlítások és nullarendű logikai műveletek (és, vagy, nem) használatával írható fel. Elemi összehasonlításnak nevezünk egy op 1 θ op 2 alakú kifejezést, ahol θ az =, <, > stb. összehasonlító jelek valamelyike, op 1 és op 2 az R relációsémából való oszlop-nevek. A feltétel kiértékelésére vonatkozó

szabályokat nem adjuk meg, mindenki tudja, hogy miről van szó. 6. Átnevezés Erre a műveletre igazából csak azért van szükség, hogy az oszlopok neveit megfelelő alakra hozhassuk, pl. egy szorzás előtt Az átnevezést ρ-val jelöljük, például ρ A B az A attribútumot nevezi át B-re, de lehetőség van a séma átnevezésére is: ρ R S . Ezzel meghatároztuk a relációs algebrát, mint matematikai struktúrát. N.B: A továbbiakban a szorzásnál az ütköző neveket automatikusan átnevezzük RA, SA, stb-re, (az átnevező operátor feltüntetése nélkül) és esetleg nem-ütköző neveknél is használható az R.A, stb minősített attribútumnév A fent definiált műveletekből lekérdezéseket állíthatunk össze, amelyek nem mások, mint relációs algebrai kifejezések. Egy relációs algebrai kifejezés az alábbi módon állítható elő 1. Minden relációs konstans (konstans tábla) egyben relációs algebrai kifejezés is 2. Minden relációs változó

(ezeket kis nyomtatott betűkkel jelöljük, r, s, ) egyben relációs algebrai kifejezés is. 3. Relációs algebrai kifejezésre alkalmazott műveletekkel is relációs algebrai kifejezést kapunk. 4. Minden relációs algebrai kifejezés előáll az előző három szabály véges sokszori alkalmazásával. Egy relációs algebrai kifejezés kiértékeléséhez minden benne szereplő relációs változónak megfeleltetünk egy reláció előfordulást, majd a kifejezésben szereplő műveleteket az előbb megadott szabályok alapján, belülről kifelé haladva kiszámoljuk. Ezekkel a szabályokkal meghatároztuk a relációs algebrát, mint lekérdező nyelvet. Ez azt jelenti, hogy a továbbiakban relációs algebra alatt az összes relációs algebrai kifejezés halmazát fogjuk érteni. Példák Tegyük fel hogy adva van az sz: Szeret(Név, Gyümölcs) tábla. o Milyen gyümölcsöket szeret Micimackó? π Gyümölcs (σ Név = Micimackó (sz )) o Kik szeretik az epret? π Név

(σ Gyümölcs = eper (sz )) Most tekintsük a b: Beosztottak(Név, Munkakör), f: Főnökök(Név, Prémium) táblákat. o Soroljuk fel a cég összes alkalmazottját! (feltéve, hogy minden alkalmazott beosztott vagy főnök) π Név (b ) ∪ π Név ( f ) o Ki kapja a legtöbb prémiumot? π Név1 ( f1 ) − π Név1 (σ Pr émium1< Pr émium 2 ( f1 × f 2 )) ahol az f 1 , f 2 táblákat az f táblából kapjuk átnevezéssel, úgy hogy a Név helyett Név1, Név2-t írunk, stb. Származtatott műveletek Most bevezetünk néhány olyan műveletet, amely kifejezhető a relációs algebra alapműveleteivel. Ez azt jelenti, hogy a relációs algebra kifejezőerején nem változtatnak ezek a műveletek, de olyan konstrukciókat tudunk velük kifejezni, amit gyakran használunk a lekérdezésekben, ezért érdemes új műveleti jeleket bevezetni. Metszet. Ha r és s sémája illeszkedik, képezhetjük a metszetüket (ugyanúgy, mint a halmazoknál). A metszet kifejezhető a

kivonással: r ∩ s = r − (r − s ) Osztás. Ez valamilyen értelemben a direktszorzás ellentéte, vagyis olyasmit szeretnénk kihozni, hogy p x s = r esetén r ÷ s = p legyen. Ha most a második egyenletet behelyettesítjük az elsőbe, akkor azt kapjuk, hogy (r ÷ s) x s = r. Természetesen az osztást nem lehet mindig ilyen szépen elvégezni, maradhat „maradék”, ezért elégedjünk meg azzal, hogy az egyenlőség helyett csak tartalmazást követelünk meg: (r ÷ s ) × s ⊆ r , és az ilyenek közül keressük a legbővebbet. Formálisan: attr (S ) ⊆ attr (R ) esetén p = r ÷ s , ha p : attr (R ) − attr (S ), p × s ⊆ r , és bármely p’-re, ha ő is teljesíti ezeket a feltételeket, akkor p’ ⊆ p. Á.: ∃!r ÷ s = π (r ) − π (π (r ) × s − r ) Példa arra hogy mire jó az osztás. Legyen adva az Sz(név, gyümölcs) tábla, ami megadja, hogy ki milyen gyümölcsöt szeret. Írjunk olyan relációs algebrai lekérdezés, amelyik megmondja, hogy ki

szereti az összes gyümölcsöt! Az összes gyümölcsöt könnyen ki tudjuk keresni: Gy = π gyümölcs (sz ) . Most keressük azokat a neveket, akik mellett az Sz táblában fel van sorolva a Gy-ben szereplő gyümölcsök mindegyike. Ha ezt a táblát most eljelöljük R-rel, akkor megállapíthatjuk, hogy RxGy része lesz az Sz táblának. Valóban, hiszen ha valaki benne van az R-ben akkor az Sz táblában mindegyik gyümölcs fel van sorolva az ő neve mellett. Ráadásul az R az ilyenek közül a legbővebb tábla lesz. Ugyanis ha feltesszük, hogy pl Malacka nincs benne az R-ben, de az R ∪ {Malacka} táblára is teljesül az a feltétel, hogy a Gy-vel direktszorozva része az Sz-nek, akkor kijön hogy Malacka mégis szeret minden gyümölcsöt. Hát akkor R nem lehet más, mint az Sz ÷ Gy. Összekapcsolások. (más néven nyakkendők) r  s = σ AΘB (r × s ) o Thetanyakkendő: AΘB o Naturalnyakkendő attribútuma. o Félnyakkendő r  s = π A, R. B ,C (σ

R B = S B (r × s )) ahol B az r és s összes közös r  s = π R (r  s ) Példa a nyakkendőkre. Tekintsük megint az előbbi főnökös példát. A Beosztottak és Főnökök táblák mellet felvesszük az i: Irányít(BeosztottNév, FőnökNév) táblát is. o Készítsük el a beosztottak listáját, de úgy hogy mindenkinek fel van tüntetve a főnöke is! b  i o Van-e olyan főnök, akinek valójában nincs beosztottja? Készítsünk listát az ilyenekről! π Név f − π Név ( f  i ) o Ki kapja a legtöbb prémiumot? π Név1, Név 2  f1  f 2  ÷ π Név 2 ( f 2 )  Pr 1> Pr 2  Műveleti tulajdonságok Először a relációs algebra azonosságaival fogunk foglalkozni. Az alább megadott egyenleteket mindig úgy kell érteni, hogy a relációs változók tetszőleges kiértékelése mellett a két oldal egyenlő. 1. Az unió, szorzás, metszet és a nyakkendők kommutatívak és asszociatívak 2. Több egymás utáni

vetítés összevonható A ⊆ B ⇒ π A (π B (r )) = π A (r ) 3. Több egymás utáni kiválasztás összevonható σ F (σ G (r )) = σ F ∧G (r ) 4. Kiválasztás és vetítés felcserélése attr (F ) ⊆ A ⇒ π A (σ F (r )) = σ F (π A (r )) ált.: π A (σ F (r )) = π A (σ F (π A,attr ( F ) (r ))) 5. Kiválasztás és szorzás felcserélése attr (F ) ⊆ attr (E1 ) ⇒ σ F (E1 × E 2 ) = σ F (E1 ) × E 2 Ha van valami összetett feltételünk (sok kicsi feltételből össze és-elve), ú.h a kis feltételecskékre más alkalmazható ez a feltétel akkor előbb szétszedhetjük két kiválasztásra és akkor már be tudjuk vinni a szorzásba. 6. Kiválasztás és halmazműveletek: a kiválasztás mindig felcserélhető a halmazműveletekkel. 7. Vetítés és unió: a vetítés mindig felcserélhető az unióval 8. Kiválasztás és naturaljoin felcserélése ha attr(F) része egy naturaljoin mindkét tagjának akkor az alábbi módon lehet őt bevinni: σ F (r 

s ) = σ F (r )  σ F (s ) 9. Vetítés és szorzás felcserélése A = B ∪ C , B ⊆ attr (E1 ), C ⊆ attr (E 2 ) esetén: π A (E1 × E 2 ) = π B (E1 ) × π C (E 2 ) A másik fontos műveleti tulajdonság a monotonitás. Def.: Az f relációs algebrai kifejezés monoton, ha ∀i: r i ⊆ r i * esetén f(r 1 ,.,r n ) ⊆ f(r 1 *,.,r n *) Á.: 1. 2. 3. Biz.: 1. 2. Az unió, szorzás, vetítés, kiválasztás, átnevezés monotonak. Monoton kifejezések egymásba helyettesítésével monoton kifejezést kapunk. A metszet és a nyakkendők monotonak. Az unió, szorzás, vetítés, kiválasztás, átnevezés triviális. t.fh az f i -k monoton kifejezések (i=0,,n), továbbá legyenek ∀i,j: r ij ⊆ r ij * tudjuk: f i (r i1 ,,r ik ) ⊆ f i (r i1 *,,r ik ) (i=1,,n) és f 0 (r 1 ,,r n ) ⊆ f 0 (r 1 *,,r n ) legyen r i =f i (r i1 ,,r ik ), r i *=f i (r i1 ,,r ik ) ekkor r i ⊆ r i *, ezért f 0 (f 1 (r 11 ,.,r 1l ),,f n (r n1 ,,r nk )) = f 0 (r 1 ,,r n ) ⊆ f 0 (r 1

*,,r n ) = f 0 (f 1 (r 11 *,.,r 1k *),.,f n (r n1 *,.,r nk *)) 3. A nyakkendők monotonitása kijön az előző két pontból, a metszet monotonitása triviális. A relációs algebra alkalmazásai A relációs algebra kifejezőerejéről Á.: 1. 2. 3. Biz.: 1. 2. A relációs algebrában nem fejezhető ki a tranzitív lezárás Kifejezhető a minimum, maximum Nem fejezhető ki a számlálás, összegzés biz. nélk t.fh az r relációs változónak egyetlen egész értékű oszlopa van   Ekkor r − π 1  r  r  pont az r-ben szereplő értékek minimumát adja meg.  $1>$2  3. biz nélk Dekompozíciók Tegyük fel, hogy adva van egy R relációs séma, aminek sok attribútuma van, ráadásul arra számítunk, hogy az ő előfordulásaiban sok adatot fogunk tárolni. Ilyenkor célszerű lenne ezt az R sémát felbontani több kisebb adattáblára. Def.: Az R séma egy dekompozíciójának nevezzük az d = (R1 ,  , Rn ) n-est, ahol R1 ∪ ∪ Rk = R

Az eredeti tábla a dekompozícióból a nyakkendő operátorral állítható vissza, a közös oszlopok felhasználásával: n (ri ) i =1 ahol r i :R i sémájú reláció előfordulás, és őt úgy kapjuk az eredeti r adattáblából, hogy csak az R i -ben szereplő oszlopait tekintjük, a többi oszlopot egyszerűen „elfelejtjük”. Ez a relációs algebrában a vetítésnek felel meg: ri = π Ri (r ) Vajon a dekompozíciók értékeiből tényleg vissza tudjuk állítani az eredeti adattáblát? Ehhez az kell hogy az előző nyakkendős kifejezés pont az r-et adja vissza, ha az r i -ket az előbbi vetítéssel helyettesítjük be. Def.: n md (r ) =  (π R (r )) i =1 i Á.: (az m d egy lezárás-operátor) 1. az m d monoton 2. r ⊆ m d (r) 3. m d (m d (r)) = m d (r) Def.: Az R séma d dekompozíciója veszteségmentes egy SAT = { r:R | F(r)=true } osztályra vonatkozóan, ha ∀r ∈ SAT : md (r ) = r N.B: itt az F egy tetszőleges logikai feltételt,

függőséget, stb jelent Lekérdezések optimalizálása A „műveleti tulajdonságok” című részben felsorolt azonosságokat felhasználhatjuk a lekérdezések algebrai optimalizációjára, vagyis egyszerűbb alakra hozására. Ha adva van egy lekérdezés, akkor szeretnénk olyan ekvivalens alakba átírni, amelyik gyorsan kiértékelhető. Azonban nagyon nehéz azt megmondani, hogy egy adott lekérdezéssel ekvivalens kifejezések közül melyiket lehet legrövidebb idő alatt kiértékelni, ezért most megelégszünk azzal, hogyha a kifejezést olyan egyszerűbb alakra tudjuk hozni, hogy lehetőleg minél kevesebb művelet legyen benne. Az algebrai optimalizáció egy olyan kifejezés-újraírási eljárás, amellyel egy lekérdezést egy másik, vele ekvivalens lekérdezéssé alakítunk át, úgy hogy közben az a célunk, hogy minél kevesebb legyen az elvégzendő műveletek száma. Ennek az átírásnak az elvégzéséhez felrajzoljuk a lekérdezés kifejezésfáját.

Ezek után az alábbi lépéseket kell elvégezni: 1. szigmák szétvágása 2. szigmák lejjebb vitele ameddig lehet 3. nyakkendők kialakítása a szigmák és szorzások összevonásával 4. mivel a nyakkendő asszociatív, a nyakkendős részkifejezéseket átrendezhetjük úgy hogy a részeredmény-táblák mérete minél kisebb legyen (ha van valami információnk az egyes táblák méretéről) 5. vetítések lejjebb vitele ameddig lehet 6. szigma-sorozatok összevonása 7. vetítés-sorozatok összevonása 8. azonos részfák keresése (azokat ki lehet előbb értékelni és eltárolni az eredményüket) Ha ezeket elvégezzük akkor az eredmény általában egy „elég jól” egyszerűsített lekérdezés lesz, de általában nem optimális. Akinek jobb optimalizálási eljárásra van szüksége, használjon inkább költségalapú optimalizálást. Relációs kalkulusok A fejezet elején relációs kalkulust ígértünk, de igazából kettő van belőle: a

tartománykalkulus (DRC) és a sorkalkulus, (TRC). A relációs kalkulusok általános elve: a lekérdezés {x 1 x n | F[x 1 x n ]} alakja, értelmezés: keressük az F-et kielégítő (x 1 ,.,x n ) n-eseket (tuple-eket) Ezek elsőrendű logikai nyelvek, a szabad változók egy kiértékelése meghatároz egy sort, ha egy kiértékelés kielégíti a formulát, akkor a sor belekerül a lekérdezés eredményébe. A DRC tartománykalkulus A DRC jelkészlete: relációszimbólumok (nagybetűk), komponensváltozók (kisbetűk), konstansok, összehasonlító operátorok (=, >, <), elsőrendű logikai jelek. A DRC szintaktikája megadja hogy mik a (jól formált) formulák: o Ha R egy n-változós relációszimbólum, x 1 ,.,x n változók akkor R(x 1 ,,x n ) jól formált formula. o Ha x,y változók, c egy konstans és Θ az = ≠ < > ≤ ≥ jelek valamelyike, akkor xΘy és xΘc jól formált formulák. o Ha x egy változó és P, Q jól formált formulák, akkor ¬P,

P∧Q, P∨Q, ∀xP, ∃xP is jól formált formulák o Minden jól formált formula előáll az előbbi szabályok véges sokszori alkalmazásával. A továbbiakban a jól formált formulát egyszerűen formulának fogjuk nevezni. Szabad változók: a P formula szabad változóit FV(P)-vel fogjuk jelölni, és a szokásos módon lehet meghatározni: o FV( P(x 1 ,.,x n ) ) = {x 1 ,,x n } o FV( xΘy ) = {x, y} o FV( xΘc ) = {x} o FV( ¬P ) = FV( P ), o FV( P∧Q ) = FV( P∨Q ) = FV( P ) ∪ FV( Q ) o FV(∀xP ) = FV( ∃xP ) = FV( P ) {x} A DRC-ben lekérdezésnek nevezünk egy { x 1 ,.,x n | P(x 1 ,,x n ) } alakú kifejezést, ahol pontosan x 1 ,.,x n a P formula szabad változói A lekérdezés eredménye azon (u 1 ,,u n ) rendezett n-esek halmaza, amelyekben szereplő értékekre a P-t kiértékelve igazat kapunk. A kiértékelése a DRC szemantikája adja meg, amit mindenki el tud képzelni az elsőrendű logika alapján. A DRC kifejezőerejéről Á.: a rel algebra átírható

DRC-be Biz.: (vázlat) Meg fogjuk mutatni, hogy bármely relációs algebrai kifejezéshez lehet konstruálni egy olyan DRC lekérdezést, aminek az eredménye megegyezik a relációs algebrai kifejezés értékével. A bizonyításhoz strukturális indukciót használunk Ez azt jelenti, hogy először megadjuk a relációs változók és relációs konstansok átírási szabályokat, majd az összetett kifejezéseket tagonként fogjuk átírni. A továbbiakban tekintsük a K relációs algebrai kifejést 1. Ha K=R egy relációs változó, akkor őt át tudjuk írni az alábbi lekérdezéssé: R  {x 1 ,.,x n | R(x 1 ,,x n ) }, ahol az R-nek n darab oszlopa van 2. Ha K egy relációs konstans, amelyiknek m darab sora és n darab oszlopa van, akkor az alábbi lekérdezéssé tudjuk átírni: {x 1 ,.,x n | ((x 1 =c 11 ) ∧∧(x n =c 1n )) ∨∨((x 1 =c m1 ) ∧∧(x n =c mn ))} ahol c mn a relációs konstans m-edik sorában, n-edik oszlopában szereplő érték. 3. Ha K egy

összetett kifejezés, akkor megnézzük, hogy mi az a művelet, amelyiket legutoljára kell elvégezni. Például, tfh K=K 1 ∪K 2 egy unió, ahol a K i -k tetszőleges, akár összetett kifejezések is lehetnek. Tegyük fel, hogy K 1 -et már sikerült átírni P 1 -be, K 2 -t sikerült átírni P 2 -be. Ekkor a Kt is át tudjuk írni: K1  P1 K2  P2 K 1 ∪K 2  { x 1 ,.,x n | P 1 (x 1 ,,x n ) ∨ P 2 (x 1 ,,x n )} A többi művelet is hasonlóan elintézhető. 4. Mivel minden egyszerű relációs algebrai kifejezést és minden műveletet át tudunk írni ha ismerjük a részformuláit, most már tényleg minden relációs algebrai kifejést át tudunk írni DRC-be. Á.: (a DRC kifejezőerejéről) 1. a DRC-ben megfogalmazható a minimum, maximum 2. nem fejezhető ki a számlálás, összegzés 3. nem fejezhető ki a tranzitív lezárás (vagyis nem adható olyan F DRC lekérdezés, amelyik egy gráf éleit tartalmazó táblához hozzárendelné azt, hogy melyik csúcsból

melyikbe vezet út) Fontos megjegyzés A DRC-ben megadható olyan lekérdezés, amelyik véges táblák esetén is végtelen eredményt ad, ezért bizonyos értelemben „túl nagy” a kifejezőereje. Például: 1. ¬P(x) 2. P(x)∨Q(y) A TRC sorkalkulus A TRC jelkészlete: relációszimbólumok (nagy betűk), sorváltozók (kis betűk, felül indexezve a komponensek számával), konstansok, összehasonlító jelek, elsőrendű logikai műveleti jelek. A TRC szintaktikája: hasonlóan az eddigiekhez. o Ha t(n) egy n-komponensű változó és R egy n-oszlopú relációszimbólum akkor R(t(n)) jól-formált formula. o Az elemi összehasonlítások is jól formált formulák: ha x(n) és y(m) változók és c egy konstans, 1≤i≤n, 1≤j≤m és Θ egy összehasonlító jel, akkor x i Θyj , x i Θc jól formált formulák. Ezek az összehasonlítások az x változó i-edik és az y változó j-edik komponensére vonatkoznak. o Ha vannak formuláink akkor a logikai jelekkel és a

kvantorokkal a szokásos módon összetett formulákat képezhetünk. Szabad változók: a szokásosan. A TRC-ben lekérdezésnek nevezünk egy { t(n) | P(t(n)) } alakú kifejezést, ahol a P egy olyan formula, aminek a t az egyetlen, n-komponensű szabad változója. A lekérdezés eredménye azon soroknak a halmaza, amelyekre a P-t kiértékelve igazat kapunk. A kiértékelés a szokásos módon értelmezhető. Á.: (a TRC kifejezőerejéről) A DRC és a TRC kifejezőereje megegyezik, abban az értelemben, hogy bármely DRC lekérdezéshez konstruálható vele ekvivalens TRC lekérdezés, és ugyanez igaz visszafelé is. Biz.: (vázlat) Oda-vissza átírásokkal lehet bizonyítani. Az egyetlen dolog amire figyelni kell az hogy a változókat hogyan rakosgatjuk ide-oda. Amit a végtelen eredményhalmazú lekérdezésekről megjegyeztünk a DRC-nél, ugyanaz igaz a TRC-re is. Tartományfüggetlenség és biztonságosság Láttuk hogy a relációs kalkulusokban megfogalmazhatók

olyan lekérdezések is, amelyek véges táblák esetén is végtelen nagy eredményhalmazt adnak. Ezt nem szeretjük Ezért most megadunk egy módosított szemantikát a relációs kalkulusokhoz: az egyes változók által felvehető értékeket korlátozzuk. Def.: R(F, D) = { az F lekérdezés eredménye a D tartományon kiértékelve } = = { x 1 ,.,x n ∈ D | F(x 1 ,,x n ) } Azt szeretnénk elérni, hogy a lekérdezések eredménye ne nagyon függjön a D-től. Ezt pontosabban úgy lehetnek megfogalmazni, hogy ha a D-t bővítjük, akkor az R(F, D) egy idő után megálljon a növekedésben. Hogy a D mikor lesz „kellően bő”, az viszont függ a lekérdezés formájától. Def.: Az F lekérdezés tartománya az F-ben szereplő konstansok és az F-ben szereplő táblák összes értékének halmaza. Ezt felírhatjuk formálisan is, hogy pontosabbnak látszódjon:     DOM (F , D ) =   {ci }     π j Ri   ci < F   Ri

< F j  ahol a c i <F, R i <F azt jelenti, hogy az F-ben előfordul a c i konstans, illetve az R i relációszimbólum. N.B: DOM(F, D) egy relációs algebrai kifejezés, amiben egyoszlopos konstans táblák és az F-ben szereplő relációszimbólumoknak megfelelő relációs változók találhatók. Def.: Az F lekérdezés tartományfüggetlen, ha DOM(F)-nél bővebb tartomány felett kiértékelve nem ad bővebb eredményt, mind DOM(F)-en kiértékelve: ∀D ⊇ DOM (F ) : R(F , D ) = R(F , DOM (F )) N.B: 1. A tartományfüggetlenség definíciója azt jelenti, hogy az F lekérdezésbe az F-ben szereplő konstansokon és a táblákba betöltött adatokon kívül „nem jönnek be” extra értékek. (az F eredményében csak olyan adat van, amit mi beletettünk az F-be vagy az adatbázisba) 2. Az R(F, D), DOM, tartományfüggetlenség fogalmai hasonlóan értelmezhetőek a TRCre is Á.: tart.ftlen DRC ≡ (1) tartftlen TRC ≡ (2) rel alg Biz. nélkül Á.: A

tartományfüggetlenség nem eldönthető. (biz nélkül) N.B: Ez nem valami vidám dolog A tartományfüggetlenséget pont azért vezettük be, hogy ne legyenek végtelen lekérdezéseink, és most tessék, kijön hogy nem tudjuk eldönteni hogy egy lekérdezés szép-e. Ezért bevezetjük a biztonságos lekérdezés fogalmát Def.: Az F DRC formula biztonságos, ha 1. Nincs benne „∀” univerzális kvantor 2. Diszjunkció esetén a két össze vagy-olt részformulának a szabad változói megegyeznek: (F 1 ∨F 2 ) részf. F-nek  FV( F 1 ) = FV( F 2 ) 3. Minden maximális konjunkciós láncban van nem-negált nem-aritmetikai tag 4. Minden maximális konjunkciós lánc minden változója korlátozott Egy x változó korlátozott, ha az alábbiak közül legalább egyik teljesül: a. Benne van egy x=c alakú összehasonlításban b. Benne van egy nem-negált nem-aritmetikai tagban c. Benne van egy x=y alakú összehasonlításban, ahol y egy korlátozott változó. A

biztonságosság hasonlóan értelmezhető a TRC esetén is: egy F TRC formula biztonságos, ha 1. Nincs benne „∀” univerzális kvantor 2. Diszjunkció esetén a két össze vagy-olt részformulának egyetlen közös szabad változója van: (F 1 ∨F 2 ) részf. F-nek  FV( F 1 ) = FV( F 2 ) = { x } valamely x változószimbólumra 3. Minden maximális konjunkciós láncban van nem-negált nem-aritmetikai tag 4. Minden maximális konjunkciós lánc minden változójának minden komponense korlátozott. Egy x i komponens korlátozott, ha az alábbiak közül legalább egyik teljesül: a. Benne van egy x i =c alakú összehasonlításban b. Az x változó benne van egy nem-negált nem-aritmetikai tagban c. Benne van egy x i =y j alakú összehasonlításban, ahol y j korlátozott Á.: Minden biztonságos kifejezés tartományfüggetlen. Ennek örülünk. A biztonságos lekérdezések kifejezőereje Á.: Biz.: bizt. DRC ≡ bizt TRC ≡ rel algebra (vázlat) – átírási

szabályokkal 1. rel algebra  DRC, TRC már volt, csak azt kell róluk megmutatni, hogy az eredmény biztonságos lesz. Ezt beláthatjuk strukturális indukcióval 2. DRC  rel algebra: strukturális indukció A relációszimbólumokat át tudjuk írni relációs változókra. A vagy-ból unió lesz, ezt megtehetjük, mert a szabad változók rendben vannak. Az „∃” egzisztenciális kvantort átírjuk vetítésre A maximális konjunkciós láncokból meg nyakkendőket csinálunk, úgy hogy az egyes nemnegált nem-aritmetikai részeket egy az egyben bevesszük a nyakkendőbe, a negált nem-aritmetikai részeket úgy vesszük be, hogy előbb kivonjuk őket a DOM(F)ből, az aritmetikai összehasonlításokat meg belerakjuk a nyakkendőzés feltételébe. 3. TRC  rel algebra: ugyanaz mind az előbb (konjunkcióslánc  nyakkendő, stb) Az SQL lekérdezőnyelv A relációs adatbázisok szabványos nyelve az SQL, ami a Structured Query Language rövidítése. Az SQL-ben

le tudunk írni lekérdezéseket, frissítéseket, séma-definíciókat és vezérlő utasításokat. Az SQL szabványnak van több változata is, legelterjedtebbek az SQL92 és az SQL99. Az SQL nyelven utasításokat lehet leírni. Egy utasítás egy vagy több sorból állhat, a sorvége jelek fehér szóköznek számítanak. Az utasítás végét pontosvessző jelzi A kifejezések típusa lehet egyszerű (numerikus, sztring, dátum), sor-érték vagy tábla-érték. Értékkifejezésnek fogunk nevezni egy olyan kifejezést, amelyiknek az értéke egyszerű típus. Az egyszerű típusokra általában értelmezve vannak az aritmetikai és összehasonító operátorok. A NULL szerepe és a háromértékű logika A NULL érték bármely egyszerű érték helyén állhat és hiányzó, vagy ismeretlen értéket jelöl. (ld. még: relációs algebra, ⊥) Ha egy aritmetikai művelet vagy egy függvény egyik operandusa NULL akkor az eredménye is NULL lesz. Ha a NULL egy

összehasonlításban szerepel akkor az összehasonlítás eredményen az „UNKNOWN” igazságérték lesz. Ez azt jelenti hogy az SQL-ben egy háromértékű logikát tudunk használni. Az alábbi táblázatokban megadjuk az egyes logikai műveletek igazságtáblázatát a háromértékű logikában. X TRUE FALSE UNKNOWN NOT X FALSE TRUE UNKNOWN X TRUE TRUE TRUE FALSE FALSE FALSE UNKNOWN UNKNOWN UNKNOWN Y TRUE FALSE UNKNOWN TRUE FALSE UNKNOWN TRUE FALSE UNKNOWN X OR Y TRUE TRUE TRUE TRUE FALSE UNKNOWN TRUE UNKNOWN UNKNOWN X AND Y TRUE FALSE UNKNOWN FALSE FALSE FALSE UNKNOWN FALSE UNKNOWN Elérési felületek SQL parancsok kiadására o Konzol/parancssoros interfész o API o programnyelvbe beágyazott SQL o aktív adatbázis-elemek (tárolt eljárások, triggerek) X IS Y TRUE FALSE FALSE FALSE TRUE FALSE FALSE FALSE UNKNOWN Lekérdezések (az SQL mint Query Language) Az SQL-ben a SELECT utasítással tudunk lekérdezéseket megfogalmazni. Egyszerű lekérdezések: SELECT {

* | mezőlista } FROM táblalista [WHERE feltétel]; Mezők listája o vesszővel elválasztva adjuk meg, hogy mely mezők értékeit akarjuk megkapni o ha ide *-ot írunk, akkor a felsorolt táblák összes mezőjét megkapjuk o ha több táblának van azonos nevű mezője, akkor a mezőnevet a tábla nevével kell minősíteni (tábla.mező alakban) o ha egy értékkifejezést írunk be, azzal számított mezőket tudunk létrehozni o egy mezőnek új nevet adhatunk az AS kulcsszóval: kifejezés AS oszlopnév ezt főleg számított mezőknél érdemes használni, mert különben a kiszámító kifejezés lenne a mező neve. Táblák listája o adattáblákat és nézettáblákat lehet itt megadni, vesszővel elválasztva o táblák átnevezése: tábla [AS] korrelációsnév o újabb adatbáziskezelők itt elfogadnak JOIN-kifejezéseket pl. tábla1 NATURAL INNER JOIN tábla2, stb Alkérdések A WHERE záradékban bonyolultabb feltételeket tudunk megfogalmazni az alkérdések

használatával. Ha olyan alkérdést írunk be egy feltételbe, amelyiknek egysoros az eredménye, akkor arra használhatjuk a szokásos összehasonlító operátorokat. Ha az alkérdés eredménye többsoros tábla, akkor az alábbi halmazműveleteket tudjuk használni: o IN: az (s IN r) feltétel igaz pontosan akkor, ha az s mint sor benne van az r táblában. o EXISTS: az (EXISTS r) feltétel pontosan akkor igaz, ha az r nem üres tábla. o ANY, ALL: aritmetikai összehasonlítást tudunk ezekkel táblákra kiterjeszteni: s > ALL r pontosan akkor igaz, ha s nagyobb az r mindegyik eleménél, s > ANY r pontosan akkor igaz, ha s nagyobb az r egyik eleménél. Az újabb SQL szabvány megengedi alkérdések használatát a FROM záradékban is, de ezt kevés adatbáziskezelő támogatja. N.B: Ha lehet, kerüljük az alkérdéseket Sok esetben alkérdés helyett összekapcsolás használatával is meg tudunk fogalmazni egy lekérdezést. Ilyenkor érdemesebb az összekapcsolást

választani, mert az általában jobb teljesítményt ad. (ld [3]) Halmazműveletek Lekérdezéseknek vehetjük az unióját, metszetét, különbségét az UNION, INTERSECT, EXCEPT utasításokkal: Lekérdezés1 halmazművelet lekérdezés2; ahol a halmazművelet = {UNION | INTERSECT | EXCEPT }. Ilyenkor mindig halmazként értelmezzük a lekérdezéseket, vagyis a duplikátok el lesznek dobva. Zsák vagy halmaz? A SELECT utasításnál mindig zsák az alapértelmezés, a halmazműveleteknél a halmaz. Ezen a DISTINCT, ALL kulcsszavakkal tudunk változtatni. Összesítések Ha összesítést akarunk használni, akkor a SELECT utasítás végén meg kell adni a csoportosító mezőket a GROUP BY záradékban. Ilyenkor a SELECT záradékban szereplő mezők mindegyikének összesített mezőnek kell lennie, vagy szerepelnie kell a csoportosító mezők között. Aggregáló függvények o COUNT(*) – az eredmény sorainak száma o COUNT(oszlop) – hány nem NULL van ebben az

oszlopban o MIN, MAX o SUM, AVG, STDDEV Az aggregáló függvényekre is használhatjuk a DISTINCT, ALL módosítókat. A HAVING záradék egy olyan feltételt ad meg, amelyiket az összesítés után vizsgáljuk meg. A lekérdezés a legvégén rendezni is lehet: ORDER BY oszlop [ ASC | DESC ]. Figyelem! Az ORDER BY záradékot csak az egész lekérdezés plusz halmazműveletek legvégén lehet megadni! A SELECT parancs általános alakja: SELECT [DISTINCT] { * | { összesítés | értékkifejezés } [AS oszlopnév] }. FROM { táblanév | alkérdés } [AS név] . [WHERE feltétel] [ GROUP BY oszlopnév. [HAVING feltétel]] [ ORDER BY oszlopnév [ASC|DESC]. ] A SELECT záradékainak kiértékelési sorrendje: o FROM o WHERE o GROUP BY o HAVING o SELECT o Halmazműveletek: UNION, EXCEPT, INTERSECT o ORDER BY Frissítések (az SQL mint Data Manipulation Language) Beszúrás INSERT INTO tábla [(oszlopnevek)] VALUES (értékek); Lekérdezés eredményének beillesztése: INSERT INTO

tábla [(oszlopnevek)] lekérdezés; Törlés DELETE FROM tábla WHERE feltétel; Módosítás UPDATE tábla SET oszlopnév=kifejezés . [WHERE feltétel]; Példa: UPDATE alkalmazottak SET beosztas=’tisztasági asszisztens’ WHERE beosztas=’takarító’; Adatbázisok létrehozása (az SQL mint Data Definition Language) Táblák létrehozása: CREATE TABLE tábla (oszlopdefiníciók, megszorítások.); Az oszlopdefiníciók az alábbi részekből állnak: o Oszlop neve o Oszlop típusa o (opcionális) oszlop-megszorítások NOT NULL – ebben az oszlopban a NULL érték nem megengedett UNIQUE – az oszlopba nem szerepelhet többször ugyanaz az érték PRIMARY KEY – v.ö UNIQUE + NOT NULL, de egy táblára csak egyszer adhatjuk meg. CHECK(feltétel) REFERENCES – idegen kulcs típusú megszorítás o (opcionális) alapértelmezett érték: DEFAULT kifejezés Táblaszintű megszorítások: o összetett kulcsok o összetett CHECK o idegen kulcsok FOREIGN KEY(oszlopok.)

REFERENCES tábla Módosítás, törlés: ALTER TABLE táblanév [ ADD COLUMN oszlopdefiníció | DROP COLUMN oszlopnév | ALTER COLUMN oszlopnév módosítás | ADD táblamegszorítás]; Tábla törlése: DROP TABLE táblanév; Nézettáblák használata CREATE VIEW név [(oszlopok listája)] AS lekérdezés; Ha egy nézettábla csak egy táblát tartalmaz akkor a frissítési műveleteket is lehet értelmezni rajta. Vezérlő utasítások (az SQL mint Control Language) Jogok kezelése GRANT jog ON tábla TO felhasználó [WITH GRANT OPTION]; REVOKE [GRANT OPTION FOR ] jog ON tábla FROM felhasználó; Jogosultság továbbadhatósága: GRANT OPTION. A jogosultság lehet: o ALL PRIVILEGES o SELECT o DELETE o INSERT [ (oszlop-lista) ] o UPDATE [ (oszlop-lista) ] Ha felhasználónak azt írjuk be hogy PUBLIC akkor az minden felhasználóra vonatkozik. Tranzakciókezelés COMMIT ROLLBACK SET TRANSACTION ISOLATION LEVEL [ READ UNCOMITTED | REPEATABLE READ | SERIALIZABLE ] SET

TRANSACTION READ ONLY SET TRANSACTION READ WRITE A COMMIT hatására a rendszer lezárja az aktuális tranzakciót és elmenti a változásokat. Ha a változásokat nem lehet elmenteni vagy egy megszorítás megsérülne, akkor a tranzakció visszavonásra kerül. A ROLLBACK megszakítja az aktuális tranzakciót és minden változtatást visszavon. A SET TRANSACTION utasítással a tranzakciók izolációs szintjét lehet beállítani, valamint azt hogy az aktuális tranzakció író-olvasó vagy csak olvasó módban fusson. Az izolációs szintekkel bővebben az első fejezetben foglalkoztunk. Megjegyzés: parancssoros SQL felület esetén gyakran van egy autocommit-flag. Ha ez be van állítva akkor minden egyes utasítás egy külön tranzakcióban hajt végre a rendszer. Ha kikapcsoljuk az autocommit flag-et akkor tudjuk használni a tranzakciókezelési utasításokat. Programnyelvbe ágyazott SQL (majd ezt letisztázom de ahhoz nem ártana kipróbálni amiket itt összehordtam.

majd valamikor biztos lesz rá időm) Motiváció: az SQL relációsan teljes, de nem Turing-teljes. Ezért csak SQL-ben nem lehet minden programozási feladatot megoldani. Az egyik lehetséges megoldás erre a beágyazott SQL használata. A beágyazás azt jelenti, hogy egy C nyelvű programban SQL utasításokat helyezünk el. Ezeket az utasításokat egy előfordító fogja feldolgozni Valójában az előfordító az SQL utasításokat API hívásokra fordítja, de ezeket a hívásokat nem kell ismernünk ahhoz, hogy a beágyazott SQL-t használhassuk. A beágyazott SQL használatával egy C-SQL kevert nyelvű program jön létre. Az ilyen programoknak általában .pc a kiterjesztése A pc forrásból a proc nevű előfordítóval tudunk igazi C programot előállítani. videotéka.pc  proc  videotéka.c Az így kapott C programot a szokásos módon tudjuk lefordítani, de arra figyeljünk hogy hozzá kell linkelni egy SQL library-t. (elvileg az kéne hogy gcc –c

videotéka.c ez a szokásos fordítás, és utána a linkeléskor hozzá kell venni az SQL könyvtárat: gcc –o videotéka videotéka.o –lsql de a Meduzán mintha nem lenne telepítve az SQL library.) Az SQL utasításokat az előfeldolgozó az EXEC SQL előtagról ismeri fel, és az utasítás a következő pontosvesszőig tart: EXEC SQL utasítás; Közös változók használata: EXEC SQL BEGIN DECLARE SECTION; /* Itt közötte a szokásos C szintaxisszal definiálhatjuk a változóinkat */ char SQLSTATE[6]; EXEC SQL END DECLARE SECTION; A közös változókra SQL-ből úgy tudunk hivatkozni, hogy a változó neve elé kettőspontot teszünk. Az SQL utasítások visszatérési értékét (sikeres volt-e a végrehajtás, vagy a hibakód) az SQLSTATE változóban lehet elérni. Mielőtt SQL utasításokat hajtanánk végre, csatlakozni kell az adatbázishoz. A program végén le kell zárni a kapcsolatot. CONNECT :felhasználónév IDENTIFIED BY :jelszó; DISCONNECT; Frissítési

parancsok kiadása beágyazott SQL-ben ugyanúgy megy mint máskor: DELETE FROM tábla WHERE feltétel; UPDATE tábla SET . WHERE feltétel; INSERT INTO tábla VALUES (változók); Egyértékű lekérdezések: SELECT mezők INTO változók FROM .; Rekord típusú változók használata.(?) Összetett lekérdezéseknél általában az eredmény sok sorból áll. Ilyenkor a sorokat úgy tudjuk kiolvasni, mintha egy szekvenciális input fájllal dolgoznánk. A lekérdezés eredményét egy CURSOR-ral tudjuk elérni, ez olyan, mint egy fájl-handle. A kurzort először deklarálni kell: DECLARE cur1 [INSENSITIVE] CURSOR FOR SELECT.; Ha a kurzor megnyitása után a tábla megváltozik, akkor a kurzor is a megváltozott adatokat adja vissza. Ha ezt el akarjuk kerülni, használjunk INSENSITIVE CURSOR-t OPEN cur1; CLOSE cur1; FETCH cur1 INTO változók; Iterálás kurzorral. (ciklusban nézegetjük az SQLSTATE változót) Frissítés kurzorral: UPDATE tábla SET . WHERE CURRENT OF kurzor;

DELETE FROM tábla WHERE CURRENT OF kurzor; Futásidőben összeállítható lekérdezések PREPARE név FROM :szövegesváltozó; EXECUTE név; EXECUTE IMMEDIATE :szövegesváltozó; Hibakezelés: mindig az SQLSTATE változóban kapjuk meg a legutóbbi utasítás visszatérési értéket. Ez egy ötjegyű, decimális számjegyeket tartalmazó változó A hibátlan végrehajtást a ’00000’ jelöli. Ha egy lekérdezésben arra számítunk, hogy valamelyik változóba null-érték kerülhet, akkor megadhatunk hozzá külön indikátorváltozót. Ilyenkor :változó:indikátor alakban kell írni a hivatkozást, ahol az indikátor egy short int típusú változó, és a nullérték esetén –1 íródik bele. Hasonlóan, ha null-értéket akarunk átadni egy SQL utasításnak, állítsuk az indikátor értékét –1-re. Felhasznált irodalom [1] [2] [3] [4] [5] [6] Ullman, Widom: Adatbázisrendszerek, alapvetés (Panem, 1998) Iványi Antal: Informatikai algoritmusok

http://elek.infeltehu/ Fred Rolland: Adatbázisrendszerek (Panem, 2002) Michael J. Hernandez: Adatbázis-tervezés (Kiskapu, 2004) Martin Gruber: SQL A-Z (Kiskapu, 2003) Blaha, Rumbaugh: Object Oriented Modeling and Design with UML (Prentice Hall, 2005) Tartalomjegyzék 7.) AZ ADATBÁZIS-KEZELŐ RENDSZEREK FOGALMAI 2 ADATBÁZISKEZELŐK SZOLGÁLTATÁSAI . 3 Adatmodellek . 3 Tranzakciókezelés . 5 Adatbáziskezelők felülete. 6 ADATBÁZISKEZELŐK FELÉPÍTÉSE . 6 Katalógusok, sémák . 7 Tranzakciók megvalósítása . 7 Kliens-szerver adatbázisrendszerek . 8 FIZIKAI FÁJLSZERVEZÉS . 9 Adatfájlok felépítése . 10 Hasító függvények . 11 Indexelés . 11 Kereső fák, B-fák . 12 8.) ADATMODELLEZÉS 13 RELÁCIÓS ADATMODELL . 14 Funkcionális függőségek . 15 Normálformák, normalizálási eljárások . 23 Többértékű függőségek, negyedik normálforma . 27 Normálformák összefoglalása . 30 EGYED KAPCSOLAT (E/K) MODELL . 32 Az E/K diagram . 33 Egyed-kapcsolat

modell átírása relációs sémákká . 36 Adatbázis-tervezési módszerek összefogalása . 37 9.) LEKÉRDEZŐ NYELVEK 38 RELÁCIÓS ALGEBRA . 38 Származtatott műveletek . 40 Műveleti tulajdonságok . 41 A relációs algebra alkalmazásai . 42 Lekérdezések optimalizálása . 43 RELÁCIÓS KALKULUSOK . 44 A DRC tartománykalkulus . 44 A TRC sorkalkulus . 45 Tartományfüggetlenség és biztonságosság . 46 AZ SQL LEKÉRDEZŐNYELV. 48 Lekérdezések. 49 Frissítések. 50 Adatbázisok létrehozása . 51 Vezérlő utasítások . 52 Programnyelvbe ágyazott SQL. 52 FELHASZNÁLT IRODALOM . 55