Informatika | Adatbázisok » Adatbázisok tételek

4. tétel Az egyed-kapcsolat modell 1. Az adatbázis fogalma, fontosabb összetevÿi, felhasználási módjai 1.1 Adatbáziskezelÿ rendszer (DBMS - DataBase Management System) A DBMS komplex SW-HW rendszer, mely adatok magas szintÿ kezelését szolgálja. A "magas szintÿ" jelz igényes felhasználói felületre utal. Jellemz i: ÿ nagy adatmennyiség: ez mega-, újabban pedig már terrabyte-os (1012 byte) adatmennyiséget jelent. A tárolás eszköze lehet diszk, dob vagy CD ÿ gazdag struktúra: ez adatmodell felállítását teszi lehetÿvé. Pl a ¶ Newton-közelítése 16 jegyre pontosan nem szolgáltat adatbázist, csupán strukturálatlan bitfolyamot. Adatbázisról akkor beszélhetünk, amikor a biteknek struktúrája és így jelentése van. ÿ hosszú életciklus: fontos az adatok permanens megÿrzése, mert az együtt lévÿ adatmennyiség értéket képvisel. 1.2 A DBMS felhasználásával szembeni követelmények 1.21 Új adatbázis (a továbbiakban DB)

létrehozása, ún séma kialakítása és kezelése ÿ Séma: adatok fogalmi struktúráját rögzíti. Ennek nyelvi eszköze a DDL (Data Definition Language), az adatdefiníciós nyelv. Erre a létrehozáskor ill a rendszer változásakor van szükség 1.22 Adatok beillesztése, törlése, módosítása, lekérdezése Ennek nyelvi eszköze a ÿ DML (Data Management Language), az adatmanipulációs nyelv, és a ÿ QL (Query Language), a lekérdezÿ nyelv. (Ilyen pl az SQL - Structured QL, ami felvállal DDL funkciókat is.) 1.23 Hatékony tárolás, kezelés, hozzáférés 1.24 Biztonság és védelem ÿ Biztonság a meghibásodásokkal (Security), és védelem az illetéktelen hozzáférésekkel szemben (Privacy). 1.25 Felügyelje több felhasználó egyidej konfliktusmentes munkáját ÿ A 90-es évektÿl kezdve a komolyabb rendszerek már ezt is figyelembe veszik. 1 4. tétel 1.3 Az egyed-kapcsolat modell A DBMS vázlatos modellje sémam veletek lekérdezések adatm

veletek "lekérdezés" processzor tranzakciókezelÿ tárkezelÿ DB adatok metaadatok A DBMS-hez az alábbi m veletekkel fordulhatunk: 1. Sémamÿveletek: ÿ a DB logikai vázának kialakítását, módosítását jelentik (a DDL igénybevételével). 2. Lekérdezések: ÿ kérdéseket fogalmazunk meg a DB tartalmával kapcsolatban. Ennek kétféle (bár nem teljesen független) változata: lekérdezÿ nyelven (QL) megfogalmazott kérdésekkel (pl. SQL), vagy alkalmazói programon keresztül feltett kérdésekkel nyerünk ki adatokat. Ez utóbbi esetben beszélhetünk gazdanyelvrÿl (host language), mely egy, a DBMS-hez hívásokat intézÿ általános célú programozási nyelv. 3. Adatmÿveletek: ÿ adatok beillesztését, törlését, módosítását célozzák - ezek a DML funkciói is egyben. Az adatm veletekben is érvényes a lekérdezéseknél megismert két ("a.)" és "b)") változat ("b.)"-re példa: banki rendszerekben kamatok

jóváírása) A DBMS architektúra komponensei: 1. Tárkezel : a diszkre ír és onnan olvas Részei: ÿ File-kezel : a fizikai szint I/O-ot végzi, ami az állomány nyilvántartására és elemeinek kezelésére szolgál. (DB-környezetben az adatvesztés veszélye miatt nem megengedett a "nem fizikai" írás/olvasás, így például a UNIX-ban használt lapozás, ami nem mindig jár konkrét I/O-tal. Vagyis a módosításokat azonnal rögzíteni kell!) ÿ Puffer-kezel : ez a file-kezelÿ belsÿ memóriás kiegészítése; elkülönülést tesz lehetÿvé az operációs rendszer tárkezelÿ mechanizmusaitól és kezeli az I/O számára rendelkezésre álló belsÿ memóriát. A puffer felépítése: blokk1 blokk2 2 4. tétel Az egyed-kapcsolat modell ÿ A blokk egy ütemben írható/olvasható terület, mérete leggyakrabban 212-214 byte (ez egy rendszerfüggÿ paraméter). ÿ A tárkezelÿ puffer-blokkjai elkülönülésének oka a fizikai adatfüggetlenség elve:

ha igényeinkben változások állnak be, akkor a továbbiakban is használható legyen az adatbázis, vagyis logikai vázát ne kelljen átszervezni. Célunk tehát az, hogy a fizikai kérdéseket a többitÿl nagyrészt függetlenül tudjuk kezelni. 2. "Lekérdezés" processzor (lekérdezés feldolgozó): magas szint (pl szelektor) kérdések átalakítását végzi egyszer utasítások sorozatára. A "MIT"-et bontja le kisebb elemekre, amelyek válaszolnak már a "HOGYAN"-ra is. Ebben a lebontásban fontos az optimalizálás, a lehetséges végrehajtások közül az "intelligens" feldolgozó választ: végrehajtási tervet készít. A standard formában megfogalmazott kérdéseket lehetÿséghez mérten átalakítja, majd a már végrehajtható utasításokkal a tárkezelÿ felé fordul. Példa: ÜGYFÉL tábla NÉV CÍM EGYENLEG NEMZETISÉG Azokra az nevekre vagyunk kíváncsiak az ÜGYFÉL táblából, akikhez negatív egyenleg tartozik

és nemzetiségük "dogon" (<- afrikai népcsoport). SELECT név FROM ügyfél WHERE egyenleg < 0 AND nemzetiség = DOGON A feltétel szÿrése hatékonyabb, ha elsÿként a nemzetiség szerint szelektálunk (mert példánkban egy ritka népcsoportot keresünk, s így a kisz rt hátralékos ügyfelek közül sokat kéne az eredménybÿl kizárni, mert nemzetiségük más), és csak ezután az egyenleg szerint. Látható tehát, hogy a jó szelektor-kérdések kialakítása nagyon fontos Lényeges a tábla elérési mechanizmusa is, ami lehet szekvenciális vagy indexelt, esetleg B-fával megoldott, stb. A rendszerek nem törekszenek valódi optimum megtalálására - hiszen a sz rési feltételek egymástól és az adatoktól való függése, hatékonysági sorrendje nagyon bonyolult lehet -, ezért inkább csak valamilyen módon közelítik az optimumot. 3. Tranzakció-kezel : célja az, hogy egyidej leg több folyamat párhuzamos hozzáférését biztosítsa az

adatbázishoz. Kulcsfogalma a tranzakció: ez utasítások egybetartozó sorozata, ami felfogható egy program-egységnek is (amit egyes nyelveken {}-ek között írunk le). Alapvetÿ követelmény a rendszerben a tranzakciók atomisága. A tranzakcióhoz tartozó utasítás-sorozat a "mindent vagy semmit" elven hajtódik végre, vagyis megszakíthatatlanul, oszthatatlanul. Vagy az összes, egy tranzakcióhoz tartozó utasítás lefut, vagy közülük egy sem. Ez a követelmény ahhoz, hogy teljesülhessen, a valós alkalmazásokban gyakran abortálást igényel (amikor a "semmit" ágon folytatódik a végrehajtás), mivel ütköztek az adatokhoz való hozzáférési igények. 3 4. tétel Az egyed-kapcsolat modell A tranzakció határait képezÿ elvi {}-ek a belül lévÿ utasítás-sorozat védelmét szolgálják. Ezek elhelyezése a tervezés lényeges kérdése. A tranzakció-kezel feladatai: atomiság biztosítása következetesség (konzisztencia)

biztosítása: adatok "közbülsÿ", tranziens állapota nem megengedett tranzakciók elkülönítése: a véletlenszer en, keveredve érkezÿ tranzakciók hatását el kell szeparálni tranzakció-tartósság: egy sikerrel befejezÿdött tranzakció hatása legyen permanens, állandó; lehessen késÿbb is erre a hatásra, eredményeire építeni. Komoly rendszerhibák ellen is legyen biztosítva a védettség, a DB ne sérüljön. A tranzakció-kezel alapeszközei: zárak: egy tranzakció "lelakatol" egy adatot, adatelemet, és biztosítja, hogy más tranzakció ne dolgozhasson a használt adattal. A tranzakció végeztével a zár feloldódik. A zárral ellátható adatelemek mérete rendszerenként változik, a méret meghatározása külön tervezési szempontokkal rendelkezik. naplózás: a naplóból végigkövethetÿk és "elszállás" esetén rekonstruálhatók a végzett tranzakciók, azaz a DB konzisztens állapotba hozható. érvényesítés: a

tranzakciók eredményének érvényességét igazolja. Például a "piszkos adatok" káros hatásait kisz rÿ protokollok tartoznak ide. Vázlatos modellünket bizonyos árnyaló tényezÿk teszik a valódi rendszerekhez hasonlóvá. Ezek közül egy hatékony munkamegosztási eszköz a kliens-szerver architektúra: kér Kliens Szerver teljesít A kliens elÿfeldolgozott SQL kérdést ad a szervernek és táblát kap vissza. Célszer tehát, ha a kliens oldal minél több munkát elvégez, hogy a szervertÿl gyors válaszidÿkkel kaphassa meg az eredményt. A szerverhez való fordulás e módja trendként is felfogható 1.4 A DBMS-sel kapcsolatos tevékenységek szintjei 1.41 Naiv felhasználó Egyszer lekérdezéseket intéz a rendszerhez vagy alkalmazói programokat indít. 1.42 DB-programozó Összetett kérdéseket állít össze, alkalmazói programokat ír. Lehetÿsége van arra, hogy árnyaltabban, összetettebben használja ki a rendszer lehetÿségeit. 1.43

DB-tervezÿ Tevékenységi körébe tartozik a DB séma kialakítása, az adatok szerkezetének meghatározása, az adatok kapcsolatainak és a fizikai felépítésnek a tervezése. 4 4. tétel Az egyed-kapcsolat modell (Itt húzhatunk egy képzeletbeli vonalat, mert nagy az ugrás a szakmai felkészültségben:) 1.44 DBMS-megvalósító Tudja, hogyan kell DBMS-t készíteni, ami már komoly, specializált tudást igényel. 1.5 Amivel mi foglalkozunk 1.51 Tervezés: ez az adatmodellezés feladatköre. Ezen belül is szó lesz a következÿkrÿl: ODL: objektumos adatmodellezés Egyed/Kapcsolat megközelítés, modellezés hálós és hierarchikus adatmodellezés relációs adatmodellezés (fontos eleme a modell normalizálása) 1.52 Programozás: ORACLE/SQL és alkalmazása (a Szg.labor 6 keretében) 1.53 Megvalósítás: szisztematikusan nem, de az alapötletek szintjén vizsgálni fogjuk a kérdést. Szó lesz: a fizikai szervezésrÿl, a lekérdezés

feldolgozásáról, és a tranzakciókról. 2. Az ODL-modellez nyelv 2.1 Az adatmodellezésr l általában Az adatmodellezés a DB logikai vázának megalkotását jelenti. Ez fogalmi szint m velet, mely az alábbi ábrával írható le: a valóság egy darabja a. adatmodell leírás adatmodellezÿ eszköz pl. ODL, E/K b. DB séma DDL A folyamat tehát felfogható úgy, hogy egy "a valóság egy darabjáról" - pl. egy cég nyilvántartásáról szeretnénk adatmodellt és arról késÿbb egy DB sémát, azaz konkrét adatbázist készíteni. A DB séma már egy tényleges. értelmezhetÿ kód A fázisok közötti átmenetek a következÿk: a. adatmodellezÿ eszközöket használva (pl ODL, E/K) készítjük el az adatmodell leírását 5 4. tétel Az egyed-kapcsolat modell b. DDL segítségével alakítható ki a DB séma A folyamat legfontosabb része az a.-ban zajló tevékenység; b ebbÿl már nagyrészt automatikusan adódik. Az adatmodellezÿ eszköz

többé-kevésbé formális jelölésrendszert biztosít adatok, kapcsolataik és a rajtuk végzett mÿveletek kifejezésére. Az adatmodellezés egyes eszközeinek kapcsolata és eredménye: ODL obj. DB a valóság egy darabja relációk relációs DB E/K 2.2 Az ODL (Object Definition Language) módszertan 2.21 Az ODL elemei: ÿ Lehetÿvé teszi az objektumos DB-tervezést (a módszer közel áll a szabványossághoz); ÿ és része a CORBA-nak, az osztott objektumos számítások tervezett szabványának. 2.22 Az ODL tulajdonságai ÿ a világot elsÿsorban objektumokkal írja le. Pl: Emberek, Termékek, stb ÿ az objektumok tartalmuktól független azonosítóval, OID-vel rendelkeznek. (Az objektumos világban két azonos példány két különbözÿ elem lehet.) ÿ az objektumokat osztályokba csoportosítja: egy adott osztály objektumai hasonlók ábrázolt tulajdonságaik (típusaik, jellegzetességeik) azonosak képet róluk a rekordsablon alapján kaphatunk. 2.23

Az ODL osztály-megvalósításának fÿ tényezÿi: 1. Attribútumok Az osztály-objektumok egyszer bb tulajdonságai egyszer bb típusokkal vannak ábrázolva (egész, valós, mutató, struct, enum, char, string, stb.) Osztály nem számít egyszer típusnak! 2. Kapcsolatok osztályok között Két alapvetÿ formája van: lehet hivatkozás egy (másik) osztály egy objektumára (egyértékÿ kapcsolat), vagy ÿ hivatkozás egy (másik) osztály több objektumára (többértékÿ kapcsolat). 3. Metódusok ÿ Az osztály objektumaira alkalmazott függvények. (A metódusok DB szempontból kevésbé relevánsak, de a modern SW-technológiának központi kérdése a metódusok tervezése és implementálása.) 2.24 Az osztálydeklaráció formája az ODL-ben: 6 4. tétel Az egyed-kapcsolat modell interface < Osztálynév > { < jellemzÿk listája > }; Az "interface" kulcsszó az ún. osztálykonstruktor Példák 1. filmes példa interface Film { attribute

string cím; attribute integer év; attribute integer hossz; attribute enum Szalag {színes, feketeFehér} szalagFajta; } Tapasztalatok: az attribútumnak van típusa és neve; enum: felsorolás típusú típusneve: Szalag neve: szalagFajta egy objektum képe ennek megfelelÿen: OID + {"Az erÿszak vége", 1998, 122, színes} 2. színészes példa interface Színész { attribute string név; attribute struct Cím { string város string utca} lakcím} típus rekordkonstruktor attribútumnév mezÿ típusa mezÿ neve 2.25 Kapcsolatok leírása A kapcsolatok (relationship) osztályszinten más objektumhoz való viszonyokat írnak le. Két alapvetÿ leírási formájuk van: 1. < osztálynév > < kapcsolatnév >, és 2. < kollekció típus > << osztálynév >> < kapcsolatnév > A kollekció típusa lehet Set, Bag, List, vagy Array. Az 1. leírás azt fejezi ki, hogy az objektum az adott típusú (nev ) kapcsolatban van a megadott osztállyal,

a 2. pedig azt, hogy az objektum kapcsolatban van osztályok egy kollekciójával A kapcsolat megfordítható, annak az objektumnak a szempontjából is megfogalmazható, amivel a kitüntetett objektumunk kapcsolatban áll. Ezt a fordított kapcsolatot (reverse) jelölni is kell, tehát maga a kapcsolat mindkét (ill. valamennyi) érintett objektumnál fel kell tüntetni Lényeges, hogy a kapcsolat (relationship) - inverz kapcsolat (reverse) pár egybetartozó szerkezet, ne válasszuk ÿket külön! Az inverz feltüntetése fontos konzisztencia-tényezÿ. Példák 1. filmes példa (kapcsolat a Film oldaláról) (2.)relationship Set < Színész > szereplÿk; reverse Színész: szerepel benne; 7 4. tétel Az egyed-kapcsolat modell A filmben szereplÿ színészek egy halmazba vannak foglalva. A Filmnek annyi kapcsolata lesz a Színésszel, ahány színész benne játszik. Ez a kapcsolatok leírásának 2 formája (1.)relationship Színész szereplÿje; reverse Színész:

szerepel benne; A kapcsolat leírható az 1. módon is, bár ez nem szerencsés 2. színészes példa (kapcsolat a Színész oldaláról) relationship Set < Film > szerepel benne; reverse Film: szereplÿk; 3. konkrét adatokkal a kapcsolatok így néznek ki: Film Színész Berlin fölött az ég Bruno Ganz Távol s mégis közel Bruno Ganz Távol s mégis közel Peter Falk Columbo Peter Falk Tanulság: egy színész több filmhez is tartozhat, ill. egy filmhez több színész tartozik 2.26 Kapcsolatok osztályozása Két osztály - pl. C és D - közötti kapcsolat lehet: ÿ egy-több (sok-sok, N:N) típusú: egy C osztálybeli objektumhoz az adott kapcsolatra nézve a Dbÿl több tartozhat, és fordítva. Pl.: C = Film, D= Színész – köztük a "szereplÿk", "szerepel benne" kapcsolatok N:N típusúak Ez a kapcsolat-típus a leggyakoribb (strukturálatlan) eset. Az N:N kapcsolat árulkodó jele az ODL-leírásban a két kollekció-operátor. (Színészek

halmaza, Filmek halmaza - mindkét oldalon több objektum van megengedve.) ÿ több-egy (sok-egy, N:1) típusú: egy C osztálybeli objektumhoz az adott kapcsolatra nézve legfeljebb egy D-beli tartozhat, de fordított irányban nincs megkötés (egy D-beli több C-belihez is tartozhat). Pl.: C = Film, D = Stúdió – köztük a "gyártó" kapcsolat N:1 típusú Jó példa a gyermek-anya kapcsolat is (egy gyereknek legfeljebb egy anyja lehet, de egy anyának lehet több gyereke). Az N:1 kapcsolat árulkodó jele az ODL-leírásban: egyértékÿ kapcsolat C-nél és kollekció Dnél. ÿ egy-több (egy-sok, 1:N) típusú: ez az N:1 kapcsolat fordítottja. ÿ egy-egy (1:1) típusú: egy C osztálybeli objektumhoz az adott kapcsolatra nézve legfeljebb egy Dbeli tartozhat, és fordítva. Pl.: C = Stúdió, D = Személy –az "elnök" kapcsolat 1:1 típusú, feltéve, hogy egy stúdiónak legfeljebb egy elnöke lehet, és egy személy nem lehet több stúdió elnöke.

Figyelem! A "legfeljebb egy" és "pontosan egy" nem ugyanazt jelenti. Az 1:1 kapcsolatban szerencsésebb a "legfeljebb egy"-et kikötni. A kapcsolatok osztályozásánál tehát azt vizsgáljuk, hogy a kapcsolat két oldaláról mennyire függvényszerÿ a kapcsolat (mikor egyértelmÿ a hozzárendelés). Alapvet tehát, hogy "mennyi dolog köt dik mennyihez". A kapcsolatok jó megválasztása rendkívül fontos szemantikai és hatékonysági szempontból is. Megj.: az ODL gyenge értelemben képes többágú kapcsolatot leírni Pl.: (a felírás megengedi két azonos egyed felvételét) interface Szerzÿdés { attribute integer Gázsi; realtionship Stúdió gyártóS; 8 4. tétel Az egyed-kapcsolat modell relationship Színész színész; relationship Film film;} 2.27 Típusok az ODL-ben Az ODL az alaptípusokra és bizonyos építkezési szabályokra (melyeket a bonyolultabb adatszerkezetek kialakításához használ fel)

támaszkodik. Ezen készlettel (adattípusok + szabályok) rendkívül sokféle feladat megoldható. 2.271 Alaptípusok: 1. Atomi típusok: a szokásos számítástechnikai adattípusok tartoznak ide, vagyis az egészek (integer), lebegÿpontos számok (float), karakterek (character), karakterláncok (string), logikai értékek (boolean), felsorolt adatok (enum). 2. Interface típusok: ezeket az interface kulcsszó vezeti be (ilyen pl a Film) 2.272 Típuskonstruktorok ÿ ezek adják az ODL építkezési szabályait. Tegyük fel, hogy T egy típus 1. Set < T > típus értéke T típusú elemek véges halmaza Pl.: Szereplÿk halmaza a Filmnél 2. Bag < T > típus értéke T típusú elemek véges multihalmaza, vagyis a halmazban lévÿ elemek multiplicitással rendelkezhetnek (az ismétlÿdés megengedett). Akkor használják, amikor a Set nem alkalmazható. 3. List <T > típus értéke T típusú elemek véges - esetleg üres - listája A Set-tÿl annyiban

különbözik, hogy benne fontos az elemek helye, sorszáma. Pl.: string = List < char > 4. Array < T, i > típus értéke T típusú elemek i-hosszú tömbje 5. Rekordkonstruktor Adott a T1, ., Tn (attribútum) típus-sorozat és az f1, ., fn mezÿnév-sorozat Ekkor a Struct N {T1 f1, T2 f2, . , Tn fn} egy N nev , n komponens rekordstruktúra Az i. komponens (mezÿ) típusa T1, neve fi Pl. A Színésznél a Cím egy kétkomponens struktúra (rekord) Az 1.-4 típuskonstruktorok az ún kollekció-operátorok Ezek valamilyen homogén összességet definiálnak, amelyekben eltérÿ lehet az, hogy megengednek-e ismétlÿdést vagy hogy fontos-e a pozíció, stb. Az attribútumok típusa lehet: ÿ atomi típus, ÿ atomi típusokból álló struktúra, ÿ vagy egy, az elÿzÿekre alkalmazható konstruktor 1.-5 közül Példa: Array < Struct T . {string név, integer tömeg}, 3 > A kapcsolat típusa lehet: ÿ interface típus ÿ egy, interface típusra alkalmazott

konstruktor 1.-4 közül 9 4. tétel 2.28 Az egyed-kapcsolat modell Alosztályok és öröklÿdés Az alosztály egy osztály speciális tulajdonságú objektumaiból jön létre (differenciális specifikációval). Ehhez a tevékenységhez tartozik a szÿkítés és a részképzés Alosztály jelölése: feltüntetjük a felettes osztály(oka)t. Pl.: filmes példa interface Rajzfilm: Film {relationship Set (Színész) hangok;}; interface Krimifilm: Film {attribute Set < string > bizonyítékok ;}: interface Krimirajzfilm: Rajzfilm, Krimifilm {}; Az alosztály örökli az összes felettes osztály (ún. "szuperosztály") tulajdonságait Ezek az attribútumok, metódusok és kapcsolatok. Pl.: a Krimirajzfilm örökli a Filmtÿl a címet Az alosztály-szerkezet hierarchiát definiál (egy felfelé irányított gráfot). Ez nem feltétlenül fastruktúra, bár ez a legjellemzÿbb. Pl.: a filmes példa öröklÿdési gráfja: Film Rajzfilm Krimifilm Krimirajzfilm

Az öröklÿdés révén konfliktus merülhet fel, ha egy alosztály többfelÿl örökölhet tulajdonságokat. Pl.: rajzfilm: vég = boldog / szomorú krimi: vég = ítélet / felmentés. Megoldás: átnevezést hajtunk végre a felsÿbb szinteken, vagy újradefiniáljuk a tulajdonságot az alsóbb szinten. (Például, ha a Sokszög - Négyszög - Négyzet alosztály öröklÿdési struktúrát nézzük, akkor célszer a területet alsóbb szinten definiálni.) 2.29 Megszorítások modellezése az ODL-ben Általunk az adatok közt további összefüggések is definiálhatók. Ezek ugyanúgy megszorítást jelentenek, mint a séma részei - például az N:1 kapcsolat, mert a kapcsolat másik oldalán egyetlen objektum állhat csak. A megszorítások fÿ típusai: 1. Kulcsok ÿ Olyan attribútum-halmazok, melyek egyértelm en azonosítják az objektumot. (Ha ismerjük a kulcsok értékét, akkor az azonosítás elvégezhetÿ.) ÿ 0 vagy több attribútum lehet kulcs; ugyanekkor több

kulcs is megadható. 10 4. tétel Az egyed-kapcsolat modell ÿ A kulcs általános alakja: interface < osztálynév > (key(s) K1, K2, . , Kn ) {-}; A Ki kulcsleírás alakja: < attribútumnév >; vagy (attr1, . , attrn) Példák filmes példa interface Film (key (cím, év)) {-}; dolgozói nyilvántartás interface Dolgozó (keys dolgAzon, tbSzám) {-} 2. Egyérték ségi megszorítások Azt rögzítik, hogy egy érték (-kombináció) az adott helyzetben egyedi. Pl a termék meghatározza az árat. Attribútumoknál a kollekció-operátorok mellÿzése szolgál az egyérték ség kifejezésére. Kétfajta értelmezés kapcsolódik az egyérték séghez: ÿ "legfeljebb egy": ez felel meg az N:1 felfogásnak ÿ "pontosan egy": ez már egy "hivatkozási épség" (lásd késÿbb) típusú követelmény. A "legfeljebb egy" értelmezés hatására vezették be a NULL értékeket. Ezen érték azt mutatja, hogy adott esetben

megengedett "üresen" hagyni egy attribútum-mezÿt. Pl.: {színes, feketeFehér, NULL} - ebbÿl a halmazból kerül ki a filmszalag típusa Ha a NULL érték van megadva, az azt jelenti, hogy a szalag típusa nem ismert. 3. Hivatkozási épség (referential integrity) Az a követelmény, hogy a hivatkozott dolognak léteznie kell (vagyis nem fordulhatnak elÿ "lógó" mutatók, hivatkozások). Lényeges, hogy az ODL a hivatkozási épség kérdését nem kezeli, csupán a megvalósítás szintjén ajánl különbözÿ módszereket: ÿ létrehozáskor kötelezÿ a "pontosan egy" kapcsolat kitöltése; ÿ hivatkozott objektum nem törölhetÿ - ez az ún. gyenge törlési elv (az elÿbbi pont inverze); ÿ a hivatkozott objektum csak a hivatkozóval együtt törölhetÿ. 4. Értelmezési tartomány korlátozása Ezen korlátozások a típusok értelmezési tartományára vonatkoznak! 5. Általános megszorítások Általános követelmények, pl. a kapcsolat

fokának korlátozása tartozik ide Megadhatjuk például, hogy legfeljebb hány színész szerepelhet egy filmben. Ha ez történetesen 10, akkor ez így írható le: relationship Array < Színész, 10 > Szereplÿk; 2.3 Adatmodellezési alapelvek 2.31 Valósághÿ modellezés ÿ a fontos adatelemek és ÿ a fontos kapcsolatok is legyenek benne a modellben! 2.32 A redundancia elkerülése ÿ Ugyanazt a dolgot két vagy több helyen ne jelenítsük meg az ábrázolt modellben. Ez azért fontos a következ k miatt: 11 4. tétel Az egyed-kapcsolat modell ÿ helygazdálkodás: nem ez a legfontosabb szempont, de mérlegelni kell; ÿ konzisztencia: a két vagy több helyen lév azonos adatnak minden el fordulási helyén mindig ugyanolyan tartalmúnak kell lennie. Ha ez nem teljesül, akkor anomáliák lépnek fel; ÿ egyszerÿség: a redundancia bonyolítja a modellt. 2.33 Megfelelÿ típusú elemek kiválasztása Alapkérdések: ÿ mit reprezentálunk attribútumként? ÿ

mit reprezentálunk kapcsolatként? ÿ A megfelelÿ típusú elemek kiválasztásának szempontjai: ÿ az attribútum: egyszer bb, mint a kapcsolat (hiszen ez direkt köthetÿ alaptulajdonság) ÿ az egyedhalmaz, osztály (azaz a kapcsolat): bonyolultabb, de kifejezÿbb. 3. Az egyed-kapcsolat modell 3.1 Az adatmodellezésr l általában Az adatmodellezés a DB logikai vázának megalkotását jelenti. Ez fogalmi szint m velet, mely az alábbi ábrával írható le: a valóság egy darabja a.) adatmodell leírás b.) DB séma adatmodellezÿ DDL eszköz pl ODL E/K A folyamat tehát felfogható úgy, hogy egy "a valóság egy darabjáról" - pl. egy cég nyilvántartásáról szeretnénk adatmodellt és arról késÿnn egy DB sémát, azaz konkrét adatbázist készíteni. A DB séma már egy tényleges. értelmezhetÿ kód A fázisok közötti átmenetek a következÿk: a. adatmodellezÿ eszközöket használva (pl. ODL, E/K) készítkjük el az adatmodell leírását

b. DDL segítségével alakítható ki a DB séma. A folyamat legfontosabb része az a.)-ban zajló tevékenység; b) ebbÿl már nagyrészt automatikusan adódik. Az adatmodellezÿ eszköz többé-kevésbé formális jelölésrendszert biztosít adatok, kapcsolataik és a rajtuk végzett mÿveletek kifejezésére. Az adatmodellezés egyes eszközeinek kapcsolata és eredménye: ODL obj. DB a valóság egy darabja relációk E/K 12 relációs DB 4. tétel 3.2 Az egyed-kapcsolat modell Az Egyed/Kapcsolat (E/K) modell Nevezik még Tárgy/Kapcsolat, vagy Entitás-relációs modellnek is. Az E/K modell nem teljeskör , mert nem tartalmaz m veleteket. Elÿnye viszont az, hogy látható formába önti a DB modelljét, vagyis jobban átlátható, mint az ODL formális leírásmódja. Elsÿdleges leírást ad, ami könnyen - jórészt gépiesen - finomítható igazi DB sémáig. Az E/K modell alapfogalmai 1. Egyedhalmazok (tárgy-, entitáshalmazok) Közelítÿleg az egyedek az

objektumoknak, az egyedhalmazok pedig az osztályoknak felelnek meg. (A különbség, mint tudjuk, az, hogy az objektumoknak mindig van azonosítójuk) Egyedhalmaz lehet bármi, aminek egyedei azonosíthatók. Az E egyedhalmaz jelölése: Például: E Film 2. Attribútumok Ezek az egyedek jellemzésére szolgáló egyszer - azaz egyszer típusú - tulajdonságok. (Egyes nézetek szerint attribútum nem lehet rekordtípus - aminek az ODL-ben nem volt akadálya.) Ha az E egyedhalmaz attribútumai rendre az A1,,Ak attribútumok, akkor a formális jelöléssel: E(A1, . , Ak) Rajzban: E Ak . . A1 . A2 Példa: az ODL-nél megismert Film az E/K modellben cím év Film hossz 3. Kapcsolatok 13 4. tétel Az egyed-kapcsolat modell Az egyedhalmazok közötti viszonyok kifejezésére szolgálnak. Jelentös eltérés az ODL-hez képest az, hogy az E/K modell megenged sokágú kapcsolatokat - nem úgy, mint az ODL, ami csak kétszereplÿs kapcsolatokat ábrázol. Az E1,.,Em

egyedhalmazok közti R nev kapcsolat jelölése: R(E1,,Em) (Az egyedhalmazok sorrendjének nincs lényegi szerepe.) Rajzban a kapcsolat nevét rombuszba foglaljuk: E1 R Em E2 . . . E3 Példák 1. Film-Színész kapcsolat: cím év Film hossz név Szereplÿk Színész szalagFajt Megj.: az ODL-ben a lakcím rekordként volt definiálva Itt ez nem megy! 2. Nemzetközi munkamegosztás Cég Ország Termel Termék Egy cég termékeit több országban is termelheti / értékesítheti. Ez egy m=3 komponens kapcsolat 14 4. tétel Az egyed-kapcsolat modell 3. a filmes példa továbbfejlesztése gázsi Film Színész Szerzÿdés Stúdió A filmet egy adott stúdió forgatja; erre a produkcióra szerzÿdik a színész. Ha a "gázsi" attribútumot szerepeltetni akarjuk az ábrán, akkor az csak a Szerzÿdés nev kapcsolathoz köthetÿ, mert: ÿ egy filmhez több színész és így gázsi tartozik; ÿ egy stúdió több filmet forgat; ÿ egy színész több

filmben játszik. Tapasztalat: kapcsolatnak is lehet attribútuma. (Bár ez új egyedhalmaz felvételével kiváltható) Kapcsolatok típusa az E-K modellben A kapcsolatok típusa megegyezik az ODL-ben ismertetett típusokkal, csak a jelöléstechnika más - a függvény-jellegre nyíl utal. 1:1 kapcsolat E1 R E2 N:1 kapcsolat E1 R E2 N:N kapcsolat Pl.: Személy Stúdióvezetó kapcsolat ("elnök") mindkét végén nyíl Pl.: Gyermek -Anya kapcsolat ("anyja") csak egy nyíl E1 R E2 nincs nyíl Az N:1 (több-egy) kapcsolat értelmes lehet kettÿnél több komponens kapcsolatnál is. (Lásd: filmes példa - nyíl a Stúdió felé.) Általánosan: az R(E1,.,Ek) több-egy kapcsolatban a nyíl Ej felé mutat, ha tetszÿlegesen választott e∈E (i≠j) egyedkollekcióhoz legfeljebb egy olyan ej van, amivel (e1,.,ej,,en) ∈ R Azaz a maradék - nyíl által nem mutatott - komponenseket (egyedeket) egyféleképp egészíthetjük ki úgy, hogy egy relációt

kapjunk. 15 4. tétel Az egyed-kapcsolat modell Sokágú kapcsolat átalakítása kétágú (több-egy) kapcsolattá Menete: R E1 E2 E1 => . E1-k R E2 E2-k Ek-k . E2 R - melyet kapcsoló halmaznak szokás nevezni - elképzelhetÿ úgy, mint egy k mutatót tartalmazó egyedhalmazt. R-nek gyakran nincs attribútuma (ekkor gyenge egyedhalmazról beszélünk) Példa: a Szerzÿdés kapcsolat átalakítása N:1 típusúvá (számunkra ez jobb) Színész Sz Film Szerz dés S Stúdió 16 F gázsi 4. tétel Az egyed-kapcsolat modell Örökl dés, alosztályok az E/K modellben Tfh. az E1 egyedhalmaz sz kítése az E2-nek Ezt jelölhetjük ezekkel: is-a vagy az egy is-a vagy az egy magyar Az alárendelt egyedhalmaz örökli felmenÿi attribútumait. Egy "objektum" nem feltétlen egy "osztályyhoz" tartozik. Példa: Film, Rajzilm, Krimifilm cím év hossz Színész Film Hangok is-a is-a Rajzfilm Krimifilm bizonyíték Itt

nincs szükség külön Krimirajzfilm egyedhalmazra. Pl ha a "Macskafogó" a krimirajzfilm, akkor lesz egy neki megfelelÿ Rajzfilm és egy Krimifilm egyed is, melyek ugyanoda, ugyanarra a filmre fognak mutatni, azaz közös apjuk lesz. Megszorítások az E/K modellben 1. Kulcsok • a rajzból indulunk ki, ezért fontos, hogy az egyszer legyen - ami a séma egyszer ségét is mutatja. • a rajzon csak egyetlen kulcsot jelölünk: ez az ún. elsÿdleges kulcs (primary key) • a nem elsÿdleges (azaz másodlagos) kulcsokat a modell külön leírásban tünteti fel. 17 4. tétel Az egyed-kapcsolat modell Pl. a Filmet a címe és a gyártási éve azonosítja, tehát itt a (cím,év) pár az elsÿdleges kulcs (amit aláhúzással jelölünk). Film cím év hossz 2. Egyérték ség • ajánlás: használjunk egyérték attribútumokat! • a NULL érték alapértelmezésben megengedett, kulcsokban azonban nem (aminek nem is lenne sok értelme, ha jól

belegondolunk) • a NULL érték tiltását külön leírás tartalmazza • az N:1 jelleget nyilak fejezik ki. 3. Hivatkozási épség A "pontosan egy" kapcsolatot lekerekített nyílhegy jelöli. Példák: 1. Egy filmnek kötelezÿen van egy (pontosan egy) gyártó stúdiója Film Stúdió Gyártó 2. Minden stúdiónak pontosan egy elnöke van, azaz nem létezhet stúdió elnök nélkül Egy elnök legfeljebb egy stúdióhoz tartozhat. Stúdió Vezeti Elnök Része Flotta 3. A kapcsolat fokának korlátozása Pl.: <= 3 Hajóraj (mindkét nyílfajta értelmes) Azt szabályozza, hogy egy egyedhez legfeljebb hány másik kapcsolódhat. A példában: egy flottához legfeljebb 3 hajóraj tartozhat. Gyenge egyedhalmazok Gyenge egyedhalmazról beszélünk, ha egy egyedhalmaz egyedei önmagukban nem, csak kapcsolataikon keresztül azonosíthatók. 18 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban Egy több komponens kapcsolat

átalakításakor a kapcsoló rekordot így jelöljük: Ennek az azonosításban résztvevÿ kapcsolatait pedig így: Követelmények: • ha az F egyedhalmaz hozzájárul az E gyenge egyedhalmaz kulcsához, akkor azt az megfelelÿ R (N:1) kapcsolattal együtt így kell ábrázolni (F is lehet gyenge egyedhalmaz): E F R • az E azonosítására szolgáló F-beli attribútumok elemei F kulcsának is. Példa: szervezeti egységek részegységekbÿl - csoportokból - épülnek fel. A csoportokat számukkal írjuk le (ez egyetlen attribútumuk): szám Csoport név Része cím Stúdió A Csoport gyenge egyedhalmazt jelöl: ennyi attribútummal (szám) önmagában nem azonosítható, csak a "Része" kapcsolatot követve a Stúdió alapján. Ha a Csoportba bekerülne a stúdiónév (azonosító!) is, akkor további redundanciaprobléma is felmerülhetne (inkonzisztens nevek: a névváltozást nem minden elÿfordulásában követjük). 3. Adatmodellezési alapelvek 1.

Valóságh modellezés • a fontos adatelemek és • a fontos kapcsolatok is legyenek benne a modellben! 2. A redundancia elkerülése 19 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban Ugyanazt a dolgot két vagy több helyen ne jelenítsük meg az ábrázolt modellben. Ez azért fontos a következÿk miatt: • helygazdálkodás: nem ez a legfontosabb szempont, de mérlegelni kell; • konzisztencia: a két vagy több helyen lévÿ azonos adatnak minden elÿfordulási helyén mindig ugyanolyan tartalmúnak kell lennie. Ha ez nem teljesül, akkor anomáliák lépnek fel; • egyszerÿség: a redundancia bonyolítja a modellt. 3. Megfelelÿ típusú elemek kiválasztása Alapkérdések: • mit reprezentálunk attribútumként? • mit reprezentálunk kapcsolatként? A megfelelÿ típusú elemek kiválasztásának szempontjai: • az attribútum: egyszer bb, mint a kapcsolat (hiszen ez direkt köthetÿ alaptulajdonság) • az egyedhalmaz, osztály

(azaz a kapcsolat): bonyolultabb, de kifejezÿbb. 4. Egyed-kapcsolat sémák átalakítása relációs, hálós és hierarchikus sémákká1 1. E/K - relációs séma átalakítás Az átalakításra van egy teljesen gépies út, ami azonban nem adja mindig a legjobb megoldást. Egyed: E(A1,.,Ak) R(A1,,Ak) Reláció Az egyed egy az egyben átalakítható relációvá (k-oszlopos táblává). E A1 . R(A1,.,Ak) Ak Bonyolultabb átalakítás: E1 Em E2 R . E1 kulcsa kulcsa E2 kulcsa . . 1 R(A1,.,As, B1,,Bl,, S1,,St) . . ez egy innen-onnan összeszedett tétel, a témával kapcsolatban ezt találtam! 20 Em 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban Hogyan kaphatunk jó átalakított relációs sémát? • ábrázoljunk minden információ-elemet! • a fontos igényeket kifejezÿ m veletek legyenek hatékonyak! Például: ne kelljen túl sok helyrÿl összeszedni egy fontos lekérdezés adatait. 2. E/K - hálós séma

átalakítás Tétel: minden E/K diagram átalakítható hálós diagrammá, azaz felrajzolható kizárólag kétkomponens N:1 kapcsolatok (kapcsoló rekordok) felhasználásával. Ez a megállapítás már az E/K modellben is szerepelt, amikor a több-több kapcsolatok számunkra kedvezÿbb, több-egy kapcsolatokká való átalakításáról beszéltünk. Mintapélda: E/K - hálós átalakításra Modellünkben egy kereskedelmi adatbázist ábrázolunk, melyben a Szállító és Megrendelÿ közötti kapcsolat az attribútumként felvett terméken ill. az Ár és Rendelés reláción keresztül valósul meg. Hálós E/K sznév szcím Szállító SZ Á Szállító Ár TERÁR Ár egys á Termék TERREN Rendelés termék SZEMREN Rendelés szám Személy menny Megrendel név cím egyenleg 21 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban 3. Hierarchikus séma átalakítása Állítás: minden hálós séma átírható hierarchiákká

(amely m veletben általában VRT-kre is szükség van). Az állítás bizonyítását egy példán keresztül mutatjuk be: 1. Hálós séma -> hierarchia A A D B C B E vD vB C D E vE vA Az átíráskor minden rekordtípust és nyilat ábrázolunk. Kijelöljük az elsÿ gyökeret - ez általában egy nagy be-fokszámú rekordtípus. (Itt: A) Az átalakítással gyakran nem kapunk "szép" fát, sokszor nem is lehet a feladatot egyetlen fával megoldani. Ezért célszer vagy szükséges is lehet több gyökeret választani 2. Hierarchia -> hálós séma C B A B A C vA D D vA vC Az eredmény több fa lett. A módszer elvileg jó, de nem ad túl értelmes megoldást. (Hármas lépcsÿben nemigen kérdezünk.) 22 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban 5. Az alapvet fizikai tárolási szerkezetek összehasonlítása 1. Alapfogalmak A fizikai szervezés célja, hogy egy rekordokból álló állomány

kezelése megoldható legyen a következÿ m veletekkel: beszúrás, törlés, keresésé, módosítás. Ez a külsÿ táras (diszkek, dobok) adatkezelés kérdésköre. A fizikai szervezés elemei: ÿ blokk (lap): fix méretÿ adatterület, tipikusan k . 512 byte (ált k=1,,10) méretÿ (ez egy rendszerenként változó paraméter). A blokk számunkra egyetlen I/O mÿvelettel elérhet tárterületet jelent. Egy blokk több rekordot tartalmazhat A blokkok elérése történhet abszolút vagy relatív cím alapján. A küls táras módszerek hatékonyságát a blokk(lap-)elérések számában mérjük. Tipikus blokkfelépítés: menedzsment információk maradék fej rek1 . rekn ÿ mutató (pointer): bejegyzés, ami egy blokk / rekord címét tartalmazza • blokk / rekord ÿ kötött rekord / blokk: mutat(hat) rá mutató. (Ellentéte: szabad rekord / blokk) Pl a 2-3 fáknál a csúcsvágás mÿvelete nem végezhet korlátok nélkül, mert "lógó", semmibe mutató

pointerek keletkezhetnek. ÿ rekord: kétféle lehet 23 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban ÿ rögzített formátumú (ez a tipikus eset): a mez k száma és hossza fix. Ekkor a rekord felépítése: fej menedzsment információk mezÿ1 fix mezÿ2 . ÿ változó hosszúságú: kétféle alkalmazási módjuk: fix mezÿszerkezet változó hosszúságú mezÿkkel: például regények text adatbázisában egy egész könyv szövege szerepelhet egy mezÿben. szerzÿ cím fix A rekordban szerepelhetnek azért fix hosszúságú mezÿk is, ha ezek hosszára található valamilyen ésszer szöveg fix változó Ez a struktúra kizárólag fix hosszúságú mezÿkkel így írható le: szerzÿ cím fix fix • szöveg mutató fix . szöveg . Itt a szöveg-mutató mezÿ egy kevéssé struktúrált másodlagos szövegállomány meghatározott mezÿjére tartalmaz egy mutatót. ÿ ismétlÿdÿ mezÿ csoportok (többérték

mezÿk): a rekordok mezÿszerkezete nem egységes. Például: filmek adatait tároljuk változó hosszúságú rekordokban. A változó hossz alkalmazását az indokolja, hogy nem lehet elÿre tudni, hogy az egyes filmeknek hány szereplÿje van. Cím Év Film . Szereplÿk További mezÿkre bomlik Azt, hogy egy mezÿt többször (ebben benne van a 0 is!) ismételi kell, a * jelöléssel ábrázoljuk. Itt: Film(Cím, Év, Szereplÿ*) a változó hosszúságú rekord leírása. Ezen felül a többérték mezÿk tárolási módszerei a következÿk lehetnek: 1. Foglalt hely technika: minden ismétlÿdésnek elÿre helyet kell foglalni Például az egy filmben szereplÿ színészek számát 30-ban maximáljuk. Ekkor a Szereplÿk mezÿ 30 mezÿre bomlik szét: Film Cím Év . Szereplÿ1 . 2. Mutató módszer: egyetlen mutató mezÿt kell lefoglalni, amely egy, az ismétlÿdÿ elemeket tartalmazó listára fog mutatni. A mutató tehát kimutat az eredeti állományból Például:

Cím Film Év . . 24 Szereplÿ-lista 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban 3. Kombinált módszer: valamennyi ismétlÿdésnek elÿre helyet foglalunk úgy, hogy az esetek döntÿ többségében a lefoglalt hely elégnek bizonyuljon (de ne legyen feleslegesen nagy), és ne kelljen mutatók mentén keresgélnünk. A bÿvítés lehetÿségét az utolsó lefoglalt mezÿ biztosítja, amiben egy listára mutató pointer foglal helyet. Például: C db színész számára méretezzük a rekordot: Film Cím Év . Szereplÿ1 . SzereplÿC Szereplÿ-lista állomány: blokkokon elhelyezkedÿ információtárolási szerkezet. Az állomány blokkjai elérésfolytonosan helyezkednek el a diszken - így van értelme a következÿ blokk (lap) fogalmának A rendszer a következÿ lapot különbözÿ mechanizmusokkal határozhatja meg. Az állomány felépítése: lap1 . lap2 lapn ÿ kulcs: a fizikai szervezés is ismeri a kulcsok fogalmát, de

az eddig megismerthez képest más jelentéssel ruházza azt fel. A kulcs bizonyos kitüntetett mezÿk összessége, ami a keresés alapjául szolgál és gyakran - de nem mindig - meghatározza a rekordot. ÿ elérési módok: elsÿdleges elérés: a rekordok keresése, elérése elsÿdleges kulcs szerint történik. másodlagos elérés: ide tartozik a rekordok elérésének minden más módja. Az elérési módok tárgyalásánál szokás az állományok "invertálásáról" beszélni. Ha egy állomány nem csak az elsÿdleges kulcs (pl. név) adta logikával áll rendelkezésünkre, hanem valamilyen másodlagos kulcs szerint is, akkor azt mondjuk, hogy az állomány az adott másodlagos kulcs (pl. telefonszám) szerinti inverzével dolgozhatunk. 2. Alapvetÿ fizikai szervezési elvek Ezek a következÿk: 1. Kupac (heap) (az alábbi kettÿrÿl a következÿ tételben lesz szó:) 2. Hash 3. Indexelt szervezés 1. Kupac (heap) Általában kis állományok fizikai

szervezésére szolgál. Az állomány lapjai így helyezkednek el: új rekord Új rekord beillesztése az utolsó rekord utáni elsÿ szabad helyre történik. A módszer a törlést "törölt" bit használatával oldja meg. A keresés elérés-folytonos, az alkalmazott operációs rendszertÿl függetlenül van megoldva a DBMS által. A rendszer a rekordot az állomány elejétÿl keresi mindaddig, míg meg nem találja (legrosszabb esetben az sikertelenül az állomány végére ér). 25 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban ÿ A sikeres keresés általánosan a blokkok felét érinti; ÿ a sikertelen keresés általánosan az összes blokkot megnézi. A kupac-szerkezet fenntartásához szükséges munka nem túl nagy, de a szerkezet bonyolódásával növekszik. Az adatbázis-állományok "pályafutásukat" kezdhetik kupacos szervezésben, növekedve pedig új formát, szerkezetet kaphatnak. 6. Hashelés és ritka

indexes szervezési módszerek 1. Adatbázisok alapvetÿ fizikai szervezési elvei Ezek a következÿk: 1. Kupac (heap) (errÿl az elÿzÿ rételben már volt szó) 2. Hash 3. Indexelt szervezés 2. Hash-szervezés Elsÿsorban a vödrös (bucket) hash-elés és változatai használatosak. Az alapmódszerben adott: B db vödör (egy vödör egy kis - kevés lapból álló - lap-láncot jelent); egy vödörkatalógus (0-tól (B-1)-ig indexelt tömb) és a h: {kulcsok} -> [0,B-1] hash-függvény, mely legyen gyorsan számítható és ne okozzon túl sok ütközést (ütközés: két kulcshoz h ugyanazt a tömb-cellát rendeli) Ábrázolva: 0 . vödör . . . i. . . . vödörkatalógus A hash-függvény a K kulcsú rekordhoz az i. vödröt sorsolja: h(K) = i A keresés a sorsoláshoz egész hasonlóan zajlik: a K rekordot keresve ki kell számítani a h(K) értékét és a megfelelÿ vödörhöz kell fordulni. Ez a módszer átlagos értelemben igen jó (a vödrök nem lesznek túl

kicsik / túl nagyok); átlagban konstans lapelérés elég. Tipikusan B-t prímnek választják, és a hash-függvényt így határozzák meg: h(K) := K (mod p). Az alapmódszer hibája, hogy statikus: rögzítve a vödörkatalógus méretét elÿfordulhat, hogy túl hosszú lap-láncok alakulnak ki a vödrökben, vagyis a szervezés nem követi dinamikusan az állomány méretváltozásait. Javaslatok a statikusság kiküszöbölésére: 1. Dinamikus hash-elés 26 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban Ötlete: a szófa és a vödrös hash-elés ötvözete segít. h(k)-t fogjuk fel úgy, mint egy bitsorozatot A szerkezet így épül fel: 0 0 1 vödör1 00. azon rekordokat tárolja, melyekre h(K) = 00. mindegy 1 vödör2 01. vödör3 1. A vödrök itt is lap-láncok, de méretük fix (bár rendszerenként más és más lehet). Keresés: h(K) bitjeit olvasva lehet megtalálni a kívánt vödröt és benne a megfelelÿ lapot.

Kezdÿállapot: 0 vödör1 0. A rendszer fenntart egy-egy vödröt a 0-val és 1-gyel kezdÿdÿ hash-függvény lapoknak. 1 vödör2 1. Ha egy vödör megtelik, akkor szét kell vágni. Például a 01 kezdet , 2-es számú vödör telt meg Ebbÿl csinálunk két vödröt a 010. és 011 -gyel kezdÿdÿ lapok számára 0 0 1 1 Ha ez az elválasztás nem lehetséges a következÿ (jelen esetben a harmadik) bitnél, akkor egy bittel tovább kell nézni a h(K) értékeket. A legrosszabb esetben ez a megkülönböztetés sosem ejthetÿ meg (de ennek nagyon kicsi a valószín sége). vödör1 00. vödör21 0 010. 1 vödör3 1. vödör22 011. Van értelme a testvér-vödrök összevonásának is. Ha törlünk egy vödörbÿl, akkor megnézzük a testvérét: ha együtt jobban ki vannak töltve, akkor érdemes összevonni ÿket. Természetesen a dinamikus hash-elés az alapmódszernél nehézkesebb és költségesebb. Ez részint attól is függ, hogy mi kerülhet be a belsÿ

memóriába (esetleg az egész szerkezet vagy csak a gyökérhez közeli csúcsok, stb.) A költséget ezért nehéz pontosan megbecsülni 2. Növelhetÿ (extendable) szervezés A módszer paramétere: d pozitív egész szám, ez a katalógus globális mélysége. A katalógusnak ekkor 2d számú bejegyzése lesz. h(K) továbbra is egy bitsorozatnak tekinthetÿ A szerkezet így épül fel d=3 esetén: 000. 001. 010. 011. . . . 27 d 3 vödör d 2 vödör 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban d a lokális mélység. Pl d=3=d => a katalógus elemeit címzÿ háromjegy cím mindhárom bitjére szükség van a vödörben; benne minden rekord 000-val kezdÿdik. Ha d=2, akkor az azt jelenti, hogy itt elég 2 bit a rekord eléréséhez, elhelyezéséhez. A szervezés során mindvégig igaz, hogy d<= d. Tehát a globális mélység a használható, a lokális mélység pedig a használt bitek számát jelenti. Túlcsordulás esetén a

vödör lapjait két vödörben próbáljuk elhelyezni. d nÿ (azaz új, nagyobb táblát készítünk), ha a d lokális mélységÿ vödör túlcsordult; ÿ d csökken (azaz új, kisebb táblát készítünk), ha minden d < d. 3. Indexelt szervezés A módszer kihasználja a kulcsok rendezettségét és alapvet mÿveletek megvalósítására szolgál. Index állomány Adott a tényleges, tárolni kívánt "fÿ" állomány ("nagy" rekordokkal). Felette helyezkedik el az index állomány, mely (kis) index rekordokból áll. A kett közötti összefüggések segítik a lapok elérését. F állomány Rekordok rendezettségi sorrendje (a sorrendben lehetnek, s t, jó indexeknél vannak is hézagok) Az index rekordokból - kis méretük miatt sok férhet el egy lapon. Az index rekord felépítése: Kulcs igazi rekordkulcs általában egy lapra mutat (ez lehet az index [bonyolultabb] vagy a f állomány [egyszerÿbb] egy lapja) Az indexelés fajtái: a.

Egyszintes ritka indexelés (ISAM) ÿ az index rekordok kulcs szerint rendezve vannak az index állományban elhelyezve; ÿ mutatójuk a f állományba mutat. Kapcsolat a mutató és a mutatott rekord között: K index rekord m K rek1 K rek2 a f . . K az els (legkisebb) kulcsérték a mutatott lapon. 28 állomány egy 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban Keresés: a K kulcsú rekordot keresve az index állományban megkeressük a legnagyobb K kulcsú index rekordot, amelyre K <= K teljesül. Ekkor biztosak lehetünk abban, hogy K mutatóját, met követve megkapjuk az "esélyes lapot", ahol K rekordja talán megtalálható - feltéve, hogy egyáltalán része a szerkezetnek. A ritka indexrekordok között - kihasználva a rendezettséget - kereshetünk (feltéve, hogy N db index lap van): ÿ lineáris kereséssel: az index állományt az elejét l kezdve szekvenciálisan járjuk be. A keresés id igénye az index lapok

számával arányos, ~ N lapelérés (N<<f állomány lapjainak száma). ÿ bináris kereséssel: felezéses módszerrel járjuk be az index állományt. Az id igény ~ logN lapelérés. ÿ interpolációs kereséssel: (pl. a telefonkönyvben így keresünk) szükség van valamilyen tárolt tudásra, statisztikára az index állomány bejárásában. A keresés jósága ennek a tudásnak a min ségéhez mérhet , ~ loglogN lapelérés. A további mÿveletekben lényeges, hogy mennyire mozgathatók a f állomány rekordjai: szabadok avagy kötöttek. Tegyük fel hogy a f állomány rekordjai szabadok, vagyis lógó mutatóktól nem kell tartani (a f állomány rekordjaira csak az index rekordok mutatói mutatnak). ÿ beszúrás: a rekordok helyét kereséssel határozzuk meg. Túlcsordulás esetén laplapvágást kell végezni (ez a B-fáknál vágás megismert módszert jelenti) és ennek megfelel en új index rekordot létrehozni ami esetleg az index állományban is új

lapvágást okozhat. ÿ törlés: a lapvágás inverzét, a lapösszevonást kell alkalmazni szükség esetén. ÿ tólig: a szervezés támogatja ezt a mÿveletet, ami adott kulcs-értékek közötti rekordok kilistáztatására szolgál. A stratégia következménye, hogy a lapok legalább félig telítve lesznek a f állományban. Ha a f állomány tömör, akkor a fenti mÿveletek nehézségekbe ütköznek. Ezért találták ki a módszer statikus változatát (kötött rekordokra). b. Egyszintes ritka indexelés - statikus változat Itt az index állomány el re elkészül; az index rekord pedig nem a f állomány egy lapjára, hanem egy "lap-oszlopára", listájára mutat. index állomány A Itt nincs szükség vágásra és összevonásra; a f állomány rekordja nem mozdul és az index sem változik. B . . A ritka index szabad és kötött változata között a költség szempontjából drámai különbség van. 29 9. tétel Tárolási struktúrák és

sémakezelés hálós adatbázisokban További módszerek: (a köv. tétel anyaga) c. Többszintes indexelés d. Sÿrÿ indexelés 7. B-fák és sÿrÿ indexek 1. Adatbázisok alapvet fizikai szervezési elvei Ezek a következÿk: 1. Kupac (heap) 2. Hash 3. Indexelt szervezés (ennek további módjairól lesz most szó) 2. Indexelt szervezés A módszer kihasználja a kulcsok rendezettségét és alapvetÿ m veletek megvalósítására szolgál. Index állomány Adott a tényleges, tárolni kívánt "fÿ" állomány ("nagy" rekordokkal). Felette helyezkedik el az index állomány, mely (kis) index rekordokból áll. A kettÿ közötti összefüggések segítik a lapok elérését. Fÿ állomány Rekordok rendezettségi sorrendje (a sorrendben lehetnek, sÿt, jó indexeknél vannak is hézagok) Az index rekordokból - kis méretük miatt sok férhet el egy lapon. Az index rekord felépítése: Kulcs igazi rekordkulcs általában egy lapra mutat (ez lehet az

index [bonyolultabb] vagy a fÿállomány [egyszer bb] egy lapja) Az indexelés fajtái: a. Egyszintes ritka indexelés (ISAM) b. Egyszintes ritka indexelés - statikus változat (ezekrÿl már az elÿzÿ tételben esett szó) c. Többszintes indexelés Ötlet: az index állomány fölé tegyünk egy (vagy több) újabb index állományt! 30 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban A felsÿ index állomány ritka indexe az alatta lévÿnek. Index állomány Index állomány Ha az index állomány túl nagy lett (vagyis a fÿ állomány hatalmas), akkor a szerkezet fölé teendÿ egy újabb index állomány. Fÿ állomány A dinamikus többszint indexek B-fákkal valósíthatók meg Az index állomány szintek ún. index fát alkotnak: gyökér szint Index fa Fÿ állomány i. index szint utolsó index szint Tulajdonságok: ÿ minden lap legalább félig telítve van (ez alól csak az egész kicsi szerkezetek jelentenek kivételt); ÿ a

gyökér-levél utak egyforma hosszúak (ez egy kiegyensúlyozottsági tényezÿ); ÿ a keresés logaritmikus; a logaritmus alapszáma attól függ, hogy hány index rekord fér egy lapra (tehát nem az elágazások száma befolyásolja); ÿ a módszer teljesen dinamikus - elkerüljük ezáltal, hogy egy nagy állomány közepébe ugorjunk. Ezt a szervezési módot az egyes SW-cégek többnyire szabványosítják - ilyen például az IBM VSAM szabványa, amelyben B-fákat használnak. d. S r indexelés A fÿ állomány minden rekordjához tartozik index bejegyzés. index állomány Fontos, hogy itt nem tételezünk fel semmiféle rendezettséget a fÿ állomány rekordjaival kapcsolatban! rek1 rek2 rekn . fÿ állomány A sÿrÿ indexelés célja, hogy a kötött fÿ állományt felszabadítsuk: ritka index A s r indexre építünk valamilyen elérési utat, például egy ritka indexet. s r index szabad rekordok Fÿ állomány kötött rekordok 31 9. tétel Tárolási

struktúrák és sémakezelés hálós adatbázisokban A s r indexelés tehát önmagában nem egy új elérési technika, hanem csak egy segédeszköz a fÿ állomány felszabadítására. Ez "szabadság" a módszer fÿ elÿnye, hiszen a s r index állomány rekordjait úgy mozgathatjuk, ahogy csak akarjuk. Ha fontos számunkra a fÿ állomány rekordjainak különbözÿ kulcsok szerinti gyors elérése, akkor a fenti s r indexes szervezés egyenesen el sem kerülhetÿ, nem csak praktikus szempontok miatt van rá szükség. Például: többféle elérési logikát használunk a fÿ állomány elérésére (név és telefonszám szerint is akarunk keresni) B-fa név szerint hash tel.szám szerint s r index 1. s r index 2. fÿ állomány [név, telefonszám, .] A s r indexek használatának hátránya, hogy a fÿ állomány fölé egy plusz szintet iktat, ami azt jelenti, hogy extra lapelérésekre van szükség. A helyzet azért nem olyan rossz, mert ez a veszteség nem

mindig számottevÿ. Ez abból ered, hogy az index rekordok gyakran sokkal kisebbek, mint a fÿ állomány rekordjai - hiszen csak rekord kulcsokat és mutatókat tartalmaznak -, és így több fér belÿlük egy lapra. Ha például B-fával szervezzük az indexet, akkor a fa alapja keskeny lesz és a kiegyensúlyozottsági tulajdonságból fakadóan a magassága sem lehet túl nagy. Mindebbÿl az következik, hogy az extra lapelérések száma sem lesz jelentÿsen nagy, vagyis a keresési sebesség döntÿen nem csökken. 3. Keresés részleges információ (Partial Match) alapján Az elsÿdleges elérések - és a legtöbb másodlagos is - valamilyen rekord kulcs (pl. személyi szám) alapján keresnek az állományokban. Részleges információra alapuló keresésnél azonban az elérés nem kulcs-szer információ alapján történik. Ennek megfelelÿen az elérés már nem lesz olyan gyors, mint a kulcs-alapú kereséseknél. Módszerei: 1. Többszörös (másodlagos) indexek

alkalmazása Többféle szempont szerint férünk hozzá az állományhoz, és ennek megfelelÿen többszörös indexeket használunk. (Például egy személy adatainak lekérdezése történhet név, cím, vagy telefonszám alapján is.) Ez egy célravezetÿ, de nagyon sok extra munkát igénylÿ módszer (gondoljunk csak a többszörös indexek követésére és a beillesztések elvégzésére). 2. Particionált hash-függvények alkalmazása A hash-függvényt úgy kell kialakítani, hogy ellenÿrizhetÿ módón a h függvény valamennyi rekord-mezÿbÿl számítható legyen. Vagyis nyomon követhetÿvé kell tenni h(K) kiszámításában az egyes mezÿk hozzájárulását. (K-val most a rekordot jelöljük, h(k)-t pedig egy N-hosszú bitsorozatként foghatjuk fel.) K = m1 h1 b1 m2 h2 b2 . . . hn bn "kis" hash-függvények bitek h(K) = h1(m1)+h2(m2)+.+hn(mn) "nagy" hash-függvény; eredménye Σbi bit hosszú 32 9. tétel Tárolási struktúrák és

sémakezelés hálós adatbázisokban Ha pl. egy kérdésben m4 és m9 ismert (ezek lehetnek: szemszín és hobby), akkor h4(m4) és h9(m9) jelentÿsen lesz kíti a keresést, a szóbajövÿ rekordok körét. A szervezési mód tehát a keresés idejét nagy mértékben lecsökkentheti, de a kulcs-alapú kereséssel szemben (vagy mintha minden kombinált kérdéshez saját index állományt készítenénk) gyorsaságban még így is messze alulmarad. 8. Tárolási struktúrák és sémakezelés hálós adatbázisokban 1. Bevezetés A hálós adatmodell a CODASYL DBTG (Comittee On Data Systems Languages - Data Base Task Group) bizottság munkájának eredménye. A CODASYL bizottság a 70-es években dolgozta ki a hálós adatkezelés alapelveit és foglalta össze a DBTG-ajánlásban. Az ANSI az ajánlást a 80-as években standarddé tette. A DBTG-ajánlás részei: ÿ hálós DDL ÿ DML és extra kiegészítések (például egy, a jó hatékonyságú DB-k létrehozásában fontos

szerepet játszó hasznos adatszerkezet.) Egy - elvi és gyakorlati szempontból is nagy jelentÿség - klasszikus hálós adatbázis-kezelÿ rendszer az IDMS nevet viseli. 2. A hálós adatmodell elemei a. Adattípusok ÿ (logikai) rekord típus, mely mezÿkkel rendelkezik (ez megfeleltethetÿ az ODL attribútumokkal rendelkezÿ objektum fogalmának illetve az E/K modell egyedhalmazainak) ÿ kapcsolat: a modellben kizárólag bináris - azaz kétkomponens - több-egy kapcsolatok engedélyezettek. Ezeket a bináris N:1 kapcsolatokat külön el is nevezték: ezek a (DBTG) SET-ek. Ábrázolás: E rekordtípus kapcs név E rekordtípus Lényeges, hogy a rekordtípusok közötti kapcsolatokat névvel el kell látni! Az attribútumokat - az ajánlás szerint rajzban általában nem jelöljük. A hálós ábra egy irányított gráf. Tétel: minden E/K diagram átalakítható hálós diagrammá, azaz felrajzolható kizárólag kétkomponens N:1 kapcsolatok (kapcsoló rekordok)

felhasználásával. Ez a megállapítás már az E/K 33 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban modellben is szerepelt, amikor a több-több kapcsolatok számunkra kedvezÿbb, több-egy kapcsolatokká való átalakításáról beszéltünk. b Hálós DDL i. A (logikai) rekordok leírása: ÿ rekordnév ÿ mezÿk leírása: (szintszám, név, típus, hossz) alakban. Ez a leírás a COBOL programozási nyelv stílusát követi. A szintszám a mezÿk csoportosításának eszköze; a nagyobb sorszámú mezÿk a közvetlenül elÿttük álló kisebb szintszámú mezö(k) részének tekinthetÿk. Pl: a Dátum egyben hivatkozik mindhárom komponensére 01 Dátum 03 Év . 03 Hó . 03 Nap . 01 . ÿ elhelyezési információk: a fizikai séma szervezéséhez tartozó elemek. Ezek a LOCATION MODE . kezdet sorok Az elhelyezési információk fajtái: CALC: egy eljárást adunk meg a . CALC < fnév > USING < mezÿlista > Az eljárás lehet

például hash-elés, ahol a USING kulcsszó után azt kell megadni, hogy mik alkotják a hash-elés kulcsait (pl. egy SZCÍM, SZNÉV összetett kulcs) Tényleges kulcs esetén ki kell kötni, hogy a kulcs-ismétlÿdés nem megengedett: DUPLICATES NOT ALLOWED. VIA SET: az rekordokat kapcsolataikra tekintettel léve kell elhelyezni. ÿ virtuális mezÿk: ez a modellben a redundancia-kezelés eszköze. Pl. az Ár kapcsolat N:1 típusúvá tételéhez mezÿ(ke)t kell kölcsönvennünk a szülÿtÿl, azaz a TERÁR kapcsolat révén a Termék TNÉV mezÿjét az Árba is betesszük. Ezt a mezÿt viszont felesleges lenne külön, redundánsan tárolni, ezért virtuálisnak vesszük fel. Tehát az általános eljárás szerint a virtuális mezÿknél egy N:1 kapcsolat mentén a szülÿtÿl vesszük át a szükséges mezÿt. A mezÿ pontos forrását fel kell tüntetni A DBTG terminológiában a szülÿt OWNER-nek, a gyermeket MEMBER-nek nevezik: OWNER MEMBER (gyermek) ii. Kapcsolatok (SET-ek)

leírása: ÿ név ÿ OWNER (a szülÿ neve, azaz az "1" oldal) ÿ MEMBER (a gyermek neve, azaz az "N" oldal) ÿ rendezési információ: a gyermekek elhelyezésére adunk utasítást az ORDER IS. kezdet sorokban. Ez az elhelyezés pedig az ún gy r be való illesztést jelenti ÿ A DBTG használja a gyÿrÿ fogalmát, ami egy szülÿ típusú rekord és a hozzá tartozó összes gyermek együttesét jelenti. Tehát a gy r a több-egy kapcsolat egy példánya A 34 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban gy r ben mindig van egy kurrens pozíció; ezért, és a szerkezet sorrendiségébÿl fakadóan értelmes m velet a gy r következÿ elemét venni. A gy r t multilistaként implementálják. Példák: 1. Logikai képe: Szállító Rezeda Termék rend1 ár-rekord: Ár . érdemi rész A gy r séma szinten tervezhetÿ. 2. Dolgozó-Projekt modell (lásd: 2 melléklet) Dolgozó rend2 Dolgozik rendn sz mut átlalában

annyi mezÿ van itt, ahány kapcsolatban gyermek az illetÿ Projekt átalakítva Dolgozó DP Projekt A DP rekordban két mutató mezÿ van. Az ORDER IS. sor folytatása lehet: ÿ SORTED: a gyermekeken rendezési reláció adott, erre nézve rendezetten kell a gy r elemeit tárolni. (Pl egy szállítóhoz a termék-rekordok ár szerint növekvÿ sorrendben tárolódnak) ÿ FIRST: a gyermek a gy r ben az elsÿ helyre kerül. ÿ NEXT: a gyermek a kurrens pozíció utáni helyre kerül. ÿ LAST: a gyermek a gy r ben az utolsó helyre kerül. SET SELECTION: új gyermek-rekord érkezésekor ennek értéke mutatja meg, hogy a gyermek gy r be illesztése hogyan történjen meg. Két lehetÿség: ÿ MANUAL: ahogy tetszik, azaz a felhasználó dönt. Pl: SZ Á ÿ AUTOMATIC: az új gyermek típusú rekord automatikusan bekerül egy gy r be. Alesetek: THRU OWNER USING <kulcs>: tulajdonoson (apán) keresztül történik a beillesztés, valamilyen kulcsérték alapján. (Abba a gy r be,

melynek apját a kulcs azonosítja) THRU CURRENT (<set-név>): a születÿ rekord a kapcsolat "kurrens", aktuális gy r jébe kerül. Megtartási kényszer (RETENTION) Azt mutatja meg, hogy egy gyermek mennyire vehetÿ ki a kapcsolatból. Lehetÿségek: ÿ FIXED: a gyermek nem vehetÿ ki a kapcsolatból, azaz a gy r bÿl. A gyermek e gy r t csak törléssel hagyhatja el. Pl: esetleg TERÁR ÿ OPTIONAL: nincs korlátozás, pl. ilyen a SZEMREND ÿ MANDATORY: egyfajta átvihetÿséget jelent, amikor a gyermek típusú rekord átvihetÿ másik gy r be, de egyúttal nem létezhet gy r nélkül. 35 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban Mintapélda: az E/K - hálós átalakításnál látott modell DDL-szer mellÿzve): sémája (több részletet RECORD SZÁLLÍTÓ. LOCATION MODE IS CALC HASH1 USING SZCÍM, SZNÉV DUPLICATES NOT ALLOWED. 01 SZNÉV CHAR(20). 01 SZCÍM CHAR(20). RECORD ÁR. LOCATION MODE IS VIA TERÁR SET. 01 ÁR

REAL. 01 TNÉV VIRTUAL SOURCE IS TERMÉK.TNÉV OF OWNER OF TERÁR 01 SZNÉV VIRTUAL SOURCE IS SZÁLLÍTÓ.SZNÉV OF OWNER OF SZ Á RECORD TERMÉK. LOCATION MODE IS CALC IND1 USING TNÉV. 01 TNÉV CHAR(20). RECORD RENDELÉS. LOCATION MODE IS VIA SZEMREND SET. 01 SZÁM INTEGER. 01 MENNYISÉG REAL. RECORD SZEMÉLY. LOCATION MODE IS CALC IND2 USING NÉV. 01 NÉV CHAR(20). 01 CÍM CHAR(30). 01 EGYENLEG REAL. . (DBTG) SET TERÁR. (DBTG) SET SZ Á. ORDER IS NEXT. ORDER IS SORTED. OWNER IS TERMÉK. OWNER IS SZÁLLÍTÓ. MEMBER IS ÁR. MEMBER IS ÁR. SET SELECTION IS AUTOMATIC SET SELECTION IS MANUAL. THRU OWNER USING TNÉV. ASCENDING KEY IS TNÉV. RETENTION IS MANDATORY. RETENTION IS MANDATORY. (DBTG) SET SZEMREND. ORDER IS LAST. OWNER IS SZEMÉLY. MEMBER IS RENDELÉS. SET SELECTION IS MANUAL. RETENTION IS OPTIONAL. (DBTG) SET TERREND. ORDER IS FIRST. OWNER IS TERMÉK. MEMBER IS RENDELÉS. SET SELECTION IS AUTOMATIC THRU CURRENT OF TERREND. RETENTION IS OPTIONAL. III. Hálós DML: köv

tétel 36 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban 9. Lekérdezés és adatkezelés hálós adatbázisokban 1. Bevezetés A hálós adatmodell a CODASYL DBTG (Comittee On Data Systems Languages - Data Base Task Group) bizottság munkájának eredménye. A CODASYL bizottság a 70-es években dolgozta ki a hálós adatkezelés alapelveit és foglalta össze a DBTG-ajánlásban. Az ANSI az ajánlást a 80-as években standarddá tette. A DBTG-ajánlás részei: • hálós DDL • DML és extra kiegészítések (például egy, a jó hatékonyságú DB-k létrehozásában fontos szerepet játszó hasznos adatszerkezet.) Most ezekrÿl lesz szó Egy - elvi és gyakorlati szempontból is nagy jelentÿség - klasszikus hálós adatbázis-kezelÿ rendszer az IDMS nevet viseli. 2. A hálós DML A futtatási környezet egy nagyon szigorú interface által van meghatározva. Ez az UWA (Users Work Area), ami három részbÿl áll: kurrencia mutatók rekord

sablonok program változók fÿleg COBOL változók, mivel a COBOL az ajánlás fÿ Az UWA részei: • Kurrencia (aktualitás) mutatók: mutatók (DBKEY) egy rekordra. Lényegében az utoljára elért rekord DB-kulcsát jelentik. Fajtái: Programkurrens (CRU, Current of Run Unit): az utoljára elért rekord DB-kulcsa Rekord kurrense: minden T rekordtípushoz mutatót jelent egy T típusú rekordra. Azaz az utoljára elért rekord DB-kulcsa a T-beliek közül. Kapcsolat kurrense: minden S set-hez mutatót jelent egy S-ben érintett rekordra (szülÿ vagy gyermek). Azaz az utoljára elért rekord DB-kulcsa az S-beliek közül Az ORDER IS után álló NEXT kulcsszó a kurrensre vonatkozik, a következÿ elem a kurrencia mutató alapján jelölÿdik ki. A gy r -szerkezet alapján kialakítható gy r kbÿl álló gy r is, aminek szintén van kurrens eleme (ami most egy gy r lesz). 37 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban • Rekord sablonok: minden T

rekord típushoz helyet jelent egy rekord leírására. Pl.: SZEMÉLY(NÉV, FIZETÉS, CÍM) Személy-keret: NÉV FIZETÉS külvilág Tehát a rekord sablon a rekord kitöltésére szolgáló közbülsÿ hely; a rekord ezen közbülsÿ helyen keresztül kapcsolódik a DB-hez és a külvilághoz. Hivatkozás mezÿre: Pl. SZEMÉLYFIZ vagy FIZ IN SZEMÉLY (egy más dialektus szerint). DML utasítások: a gy r kben való mászkálás bennük erÿsen támogatott. • GET • GET <rekordnév> • GET <rekordnév> <mezÿk> • GET <mezÿk> Ezek lényegében ugyanazt jelentik, ennek megfelelÿen a rekord, amire vonatkoznak, minden ugyanaz, csak az eredmény megjelenítése lesz más. A programkurrens alapján egyértelm , hogy melyik rekordról van szó. A GET parancs-változatok jelentése: a CRU által mutatott rekord a saját sablonjába másolódik. A paraméterek csak hibaellenÿrzésre szolgálhatnak • Az érdemi utasítások a kurrencia mutatókat kezelik.

Erre szolgálnak a FIND utasítások: 1. FIND <rekordtípus> BY DBKEY X - itt X egy változó Pl.: X = CURRENT OF TERMÉK FIND TERMÉK BY DBKEY X. FIND A hatása: X mindennek kurrense lesz, amire csak nézve értelmes lehet, valamint az általa elért rekord mindennek kurrense lesz, szintén, aminél ez értelmes (CRU, saját típusának és minden kapcsolatának kurrense). 2. FIND <rekordtípus> BY CALC KEY A kulcsmezÿk a típus sablonjából származnak. Írás a sablonba: SZEMÉLY.SZNÉV = Klopédia FIND SZEMÉLY BY CALC KEY GET Ez egy rekordtípuson belül a szokásos m veleteket jelenti, plusz mutatók mentén végzett mozgást is. Jellegzetes hálós m veletnek számít a nyilak mentén végzett navigáció 3. FIND OWNER OF CURRENT <kapcsolatnév>: a kapcsolatkurrens gy r jének a szülÿjére mutat. 4. FIND {FIRST/NEXT}<rektípus> IN CURRENT <kapcsnév> USING <mezÿlista>: A kitöltött mezÿk alapján (sablonból) sz r. Ha egy rekordtípus

nincs a kapcsolatok között, de ennél is szeretnénk alkalmazni a NEXT és FIRST m veletét, akkor a megoldást a szinguláris halmaz (OWNER SYSTEM) felvétele jelenti. Itt a MEMBER (gyermek) rekordjai egyetlen gy r t alkotnak Pl.: az összes személy egy gy r ben fog szerepelni a következÿ utasítás hatására: SET MINDENKI OWNER SYSTEM MEMBER SZEMÉLY 38 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban • Beillesztés: STORE <rekordtípus>. A T típusú sablon tartalma a DB-be kerül, és mindenek kurrense lesz, aminek csak lehet. Pl. r létezÿ, T típusú rekord, CRU INSERT T INTO <kapcsolatnév1> . <kapcsolatnévn> Ezzel r bekerül a kapcsolatok kurrens gy r jébe. • Törlés: REMOVE T FROM <kapcsolatnév1> . <kapcsolatnévn> Ezzel r kikerül a kapcsolatokból. • Rekord törlése: DELETE <rekordtípus>. Itt a program-, és nem az apa kurrenciák sz nnek meg. (Ellenkezÿ esetben a gyermekek árván

maradhatnának) • Erÿs törlés: DELETE <rekordtípus> ALL. Ez rekurzíve töröl, ami azt jelenti, hogy az apa fiaira is rekurzíve meghívódik. Azon gy r ket törli, melyeknek az apa a tulajdonosa A hálós DML jellegzetességei • kurrenciák által vezérelt • "egyszerre egy rekord"-típusú nyelv, ebben az SQL-hez képest sokkal kényelmetlenebb, mert az képes táblát utasítás eredményeként visszaadni. 10. Sémakezelés és tárolási struktúrák hierarchikus adatbázisokban 1. Bevezetés Szemben a hálós modellel ez az adatmodell úgymond "szervesen" alakult ki, nem egy bizottság munkájának eredménye. Például a hierarchikus adatmodellt használja az IMS (IBM), illetve a SYSTEM 2000 (egyetemi fejlesztés). Alapötlete az, hogy próbáljuk meg a világ - esetleg vélt - hierarchiái mentén megszervezni a DB-t. Ilyen hierarchiát követnek az emberi szervezetek, közösségek, vagy a hierarchikus világmodellek (pl.: állatok) A

hierarchia többé-kevésbé olyan hálós modellnek tekinthetÿ, melynek komponensei (felfelé) irányított gyökeres fák (azaz nem tartalmaz köröket). Az, hogy csak "többé-kevésbé" az, abból ered, hogy a kapcsolatok több-egy jellege rekord, és nem típus-szinten igaz. Például: a film-színész kapcsolatban (több-több jelleg ) annyi Marlon Brando-rekordot kell felvenni, ahány film van. Óhatatlan tehát a redundancia, amit úgy kell megoldani, hogy a valóságban csak egy igazi rekordot tartunk nyilván, a többi rekord pedig virtuális lesz. 2. A hierarchikus modell elemei A rekordtípusokat téglalappal jelöljük, a kapcsolatot pedig egy vonal reprezentálja - nyíl és név nélkül (azaz automatikusan "felfele mutat"). Példa több-egy kapcsolatra: 39 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban ORSZÁG rekordtípus kapcsolat MEGYE TELEPÜLÉS Példa több-több kapcsolatra és hierarchikus megoldására:

Film Színész Szerepel És ugyanez hierarchikusan: a színész redundanciát hordoz A navigáció mindig fentrÿl lefelé történik. Film Érdemes a gyökeret VRT-nek (virtuális rekordtípusnak) választani. Színész VRT (virtuális VRT (virtuális Színész Film Általánosan: E1 e1,e2,. E2 f1,f2,. e2 e1 f1 f2 f2 A rekordok szintjén megjelennek a rekordtípusok Def.: Adatbázis rekord 40 f4 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban Egy gyökér típusú rekord és leszármazottai együttesen egy adatbázis rekordot alkotnak. Pl. a film és a benne szereplÿ színészek egy adatbázis rekordba tartoznak, vagy ugyanígy: a színész és a filmek, amelyben szerepel. A tárolás alapegysége a hierarchikus modellben a DB-rekord. Állítás: minden hálós séma átírható hierarchiákká (amely m veletben általában VRT-kre is szükség van). Az állítás bizonyítását egy példán keresztül mutatjuk be: 1. Hálós séma

-> hierarchia A A D B C B E vD vB C D E vE vA Az átíráskor minden rekordtípust és nyilat ábrázolunk. Kijelöljük az elsÿ gyökeret - ez általában egy nagy be-fokszámú rekordtípus. (Itt: A) Az átalakítással gyakran nem kapunk "szép" fát, sokszor nem is lehet a feladatot egyetlen fával megoldani. Ezért célszer vagy szükséges is lehet több gyökeret választani 2. Hierarchia -> hálós séma B A B A C vA C D D vA vC Az eredmény több fa lett. A módszer elvileg jó, de nem ad túl értelmes megoldást. (Hármas lépcsÿben nemigen kérdezünk.) 3. A hierarchikus DDL A hierarchikus DDL-ben irányított fákat írunk le: TREE <fanév> <rekordtípusok leírása> <rekordtípusok leírása> ::= <rekordnév> <információ> 41 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban <információ> ::= 1. Mezÿk: név, szint, típus, hossz 2. Hely a fában: • ROOT

(gyökér) • PARENT <rekordnév> (szülÿ) 3. Virtualitás • virtuális: igen / nem • hol az eredetije VIRTUAL <rekordnév> IN <fanév> Példa: (3. melléklet) Fiók Ügynök Ügyfél a gyökér TREE BIZTOSÍTÓ RECORD FIÓK ROOT. 01 FNÉV. 01 FCÍM. RECORD ÜGYNÖK PARENT=FIÓK. 01 NÉV. 01 KÖTÉS. (* az ügynök által eladott biztosítások éves díjtételeinek összege *) RECORD ÜGYFÉL PARENT ÜGYNÖK 4. Hierarchikus DML (DL/I) köv tétel 11. Lekérdezés és adatkezelés hierarchikus adatbázisokban 1. Bevezetés Szemben a hálós modellel ez az adatmodell úgymond "szervesen" alakult ki, nem egy bizottság munkájának eredménye. Például a hierarchikus adatmodellt használja az IMS (IBM), illetve a SYSTEM 2000 (egyetemi fejlesztés). Alapötlete az, hogy próbáljuk meg a világ - esetleg vélt - hierarchiái mentén megszervezni a DB-t. Ilyen hierarchiát követnek az emberi szervezetek, közösségek, vagy a hierarchikus

világmodellek (pl.: állatok) A hierarchia többé-kevésbé olyan hálós modellnek tekinthetÿ, melynek komponensei (felfelé) irányított gyökeres fák (azaz nem tartalmaz köröket). Az, hogy csak "többé-kevésbé" az, abból ered, hogy a kapcsolatok több-egy jellege rekord, és nem típus-szinten igaz. Például: a film-színész kapcsolatban (több-több jelleg ) annyi Marlon Brando-rekordot kell felvenni, ahány film van. Óhatatlan tehát a redundancia, amit úgy kell megoldani, hogy a valóságban csak egy igazi rekordot tartunk nyilván, a többi rekord pedig virtuális lesz. 42 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban 2. Példa Az alább bemutatandó DML-hez (3. melléklet): Fiók a gyökér Ügynök Ügyfél TREE BIZTOSÍTÓ RECORD FIÓK ROOT. 01 FNÉV. 01 FCÍM. RECORD ÜGYNÖK PARENT=FIÓK. 01 NÉV. 01 KÖTÉS. (* az ügynök által eladott biztosítások éves díjtételeinek összege *) RECORD ÜGYFÉL PARENT

ÜGYNÖK 3. Hierarchikus DML (DL/I) Elég hatékonyan m ködik, viszont bizonyos dolgokat elég nehéz benne kifejezni. Lekérdezések: • GET LEFTMOST <T rekordtípus> WHERE <feltétel> Egy konkrét adatbázis felfogható úgy, mint egy rekordokból álló irányított erdÿt. Ebben az erdÿben értelmes a "balról-jobbra" kérdés, de a feltétel nem lehet akármilyen. Típusfa: • Csak T-re és felmenÿire (melyek ezen az úton vannak) tartalmazhat feltételt. T • A gyökértÿl T-hez vezetÿ út van. <feltétel> ::= <rekordnév>.<mezÿnév> Θ érték Θ ∈ {<,≤, >,≥,≠} elemi összehasonlító m veletek A feltételek kombinálhatók: AND, OR, NOT. Példa: (az elÿbb definiált sémában) Keressünk egy (a legelsÿ) olyan ügynököt, akinek kötései 100000 felett vannak és a csornai fiókban dolgozik. GET LEFTMOST ÜGYNÖK WHERE FCÍM="Csorna" AND KÖTÉS > "100000" vagy: read C, K. GET LEFTMOST

ÜGYNÖK WHERE FCÍM=C AND KÖTÉS > K • GET NEXT Egy lépést jobbra lép a fában, ha tud. 43 13. tétel Relációs algebra, relációs teljesség Vigyázni kell azonban, mert a jobbra lépés során elhagyhatja a szülÿt vagy akár magát a rekordtípust is. • GET NEXT <rekordtípus> Itt a jobbra lépés a típus megtartásával történik. WHERE <feltétel> itt is megadható Pl.: NEXT hatása: a szülÿ is NEXT hatása: a szülÿ Példa: (az elÿbbi feladat folytatása) Kilistázzuk a Nehagyd Döme nev ügynök összes kliensét. Feltételezzük, hogy sikertelen keresés esetén a FAIL nev Boole változó értéke T, különben F. GET LEFTMOST ÜGYFÉL WHERE NÉV = "Nehagyd Döme" while NOT FAIL do print ÜGYFÉL.ÜNÉV (* a rekordsablonra hivatkozunk ) GET NEXT ÜGYFÉL WHERE NÉV = "Nehagyd Döme" end while A while ciklusban az elsÿ kiírással Döme "legbaloldalibb" ügyfelét kapjuk meg. Ezután GET NEXT-tel

gyalogolunk végig a többi ügyfélen. Az utolsó WHERE sor szükséges, mert elhagyása esetén esetleg más ügynök ügyfeleit is kilistáznánk. Egyszerre egy rekordot kapunk meg, ezért ezt a DML-t nevezik "egyszerre egy" típusú nyelvnek is. Ahogyan a hálós modellben láttuk, itt is van rekordsablon, kurrencia, mezÿkre való hivatkozás. A szülÿ átlépésének elkerülése pedig WHERE-rel lehetséges Létezik a kurrens szülÿ fogalma is: a GET-tel vagy GET NEXT-tel legutoljára elért felmenÿ típusú rekord. • GET NEXT WITHIN PARENT Jobbra lép, megtartva a kurrens szülÿt. Példa: Nehagyd Döme további kalandjai Az elÿzÿ példa során megeshet, hogy több Nehagyd Döme nev ügynök is van. Ekkor az összes ilyen ügynök klienseit kiírja a program. A következÿ módon megtarthatjuk az apa típusú rekordot a keresés során: GET LEFTMOST ÜGYNÖK WHERE NÉV = "Nehagyd Döme" while NOT FAIL do GET NEXT WITHIN PARENT ÜGYFÉL print

ÜGYFÉL.ÜNÉV (* a rekordsablonra hivatkozunk ) end while A példában a fa preorder sorrendjének megfelelÿ legelsÿ adott nev ügynök klienseit listázzuk. 44 13. tétel Relációs algebra, relációs teljesség Rekord beillesztése: • A rekordot a sablonjában összerakjuk, • majd kiadjuk a következÿ utasítást: STORE / INSERT <rekordtípus> WHERE <feltétel> Az utasítás beilleszti a rekordot a legbaloldalibb alkalmas helyre. Példa: Új ügyfelet adunk a csornai Nehagyd Dömének. ÜGYFÉL.ÜNÉV = "Zsebenci Klopédia" ÜGYFÉL.ÜCÍM = "Négyszöglet Kerek Erdÿ" INSERT ÜGYFÉL WHERE NÉV = "Nehagyd Döme" AND FCÍM = "Csorna" Rekord módosítása / törlése: A GET speciális formáját használjuk, ami egyben zárat is jelent. • GET HOLD: zárat teszünk a kiválasztott rekordra, melynek felszabadulásáig más nem férhet hozzá. • REPLACE: módosítás, ami a HOLD-dal képzett zárat is feloldja. •

DELETE: törlés, a zárat ugyanúgy feloldja, mint az elÿbbi utasítás. Példa: 1. Az elÿzÿ ügylet megnöveli Nehagyd Döme kötéseit A megfelelÿ adatbázisbeli módosítás így történhet: GET HOLD LEFTMOST ÜGYNÖK WHERE NÉV = "Nehagyd Döme" AND FCÍM = "Csorna" ÜGYNÖK.KÖTÉS = ÜGYNÖKKÖTÉS + 1000 REPLACE 2. Nehagyd Döme pályát változtat GET HOLD LEFTMOST ÜGYNÖK WHERE NÉV = "Nehagyd Döme" AND FCÍM = "Csorna" DELETE 45 13. tétel Relációs algebra, relációs teljesség 4. Hierarchikus tárolási filozófia Amíg a hálós modellnél a fizikai tárolás alapját a gy r jelentette, addig itt a szervezés alapja a DB rekord. Az alapötlet az, hogy a DB rekordokat egységként kezeljük Ezáltal rekordszinten tükrözÿdik a séma fa-szerkezete A gyökértípusra szervezünk els dleges elérést (pl hash-elést, indexelést, stb.) Például az elÿbbi biztosítási sémánál a gyökér a FIÓK vödörkatalógus

DB-rekord f1 ügyn ügyn . . több lap láncolva A DB rekord több láncolt lapból áll. Fentrÿl lefele a hash-szervezés gyors mozgást biztosít Egy DB rekord tárolása történhet: 1. Preorder fonal szerint: r,a1,a2,b1,b2,c1,c2 r a2 a1 b1 b2 c1 A preorder fonal egy, a preorder sorrendet követÿ mutató. • ez a módszer egy korrekt linearizálását adja az összetett szerkezetnek; • helytakarékos: 1 mutató / rekord; • de a navigáció lassú lehet. 2. Legbaloldalibb gyermek - jobb testvér szerint rekord bal gyermek r a1 0 a2 b1 jobb • 2 mutató / rekord; • de gyorsabb a navigáció. 46 13. tétel Relációs algebra, relációs teljesség 12. Relációs algebra, relációs teljesség 1. Bevezetés A praktikus alkalmazások szempontjából a relációs adatmodell a legfontosabb a modellek közül. Sikerének titka egyszer sége, érthetÿsége, és a hozzá kapcsolódó számos m velet S bár kifejezÿereje jó, hatékonysága hozzá képest

alulmarad. Alapja a síkbeli, kétdimenziós táblázat, a reláció. A reláció a táblákkal analóg, mert a kapcsolatokat ezek segítségével lehet leírni. A reláció elemei a sorok, a táblázat fejlécében pedig az attribútumok szerepelnek. Példa: FILM CÍM Óz . ÉV . SZALAGFAJTA . = r rek. Def.: Reláció A reláció egy síkbeli tábla, ami pedig egy direkt szorzat egy részhalmaza, amelyben a sorok (rekordok) sorrendje lényegtelen. Felfogható úgy is, mint Attribútum -> Érték függvények halmaza, ahol az oszlopok (= attribútumok) sorrendje irreleváns. A fenti példában: FILM ∈ CÍM × ÉV × SZALAGFAJTA × . r(CÍM)="Óz" Def.: Nézet 1. Szintén egy síkbeli táblázat: R A1 A2 . Ak R(A1,A2,.Ak) 2. ~R⊆D1×D2××Dk, ahol Di az Ai értékkészlete (A sorok sorrendje nem számít) 3. A sor egy f{A1,,Ak} ∪Di függvény (Az oszlopok sorrendje nem számít) 47 13. tétel Relációs algebra, relációs teljesség 2. A relációs

adatmodell alapmÿveletei (EF Codd, 70) 1. halmazm veletek: • únió (Jele: ∪) Adott két reláció: R és S. R∪S az R és S sorait jelenti. A m veltnek nincs mindig értelme, ezért megfogalmazhatunk - nem kötelezÿ érvény követelményeket az únióval kapcsolatban: – legyen R és S oszlopszáma egyenlÿ! – esetleg oszlopaik típusa is feleljen meg egymásnak! Példa: R A a a b B a c c S A a a a b D a d c b R∪S A a a b a b ? a c c d b Ahogy a példában is látszik, elÿfordulhat, hogy az únióban hiányozni fog egy attribútumnév (oszlopfejléc). Az ismétlÿdÿ sorok általában nem megengedettek (pl: (a,a) ) az únióban, mivel a relációs világ értékorientált, és a redundanciát igyekszik kiiktatni ott, ahol lehet. • különbség (Jele: ) Adott két reláció: R és S. RS elemei R azon sorai lesznek, amelyek nem szerepelnek S-ben. RS örökli az R oszlopszámát, attribútumait, típusait. Példa: az úniónál bemutatott R-re és S-re RS A b B

c • direkt szorzat (Descartes-szorzat, jele: ×) Adott két reláció: R (k oszlopa és m sora van) és S (l oszlopa és n sora van). R×S-nek (k+l) számú oszlopa lesz, amikor a direkt szorzat-képzés során R sorait kiegészítjük az S soraival az összes lehetséges módon. Tehát R×S-nek m n számú sora lesz Formálisan: R(A1,.Ak) R×S(A1,.Ak,B1,,Bl) S(B1,.,Bl) 48 13. tétel Relációs algebra, relációs teljesség Példa: az úniónál bemutatott R-re és S-re k=l=2 k+l=4 R×S A a B a a c A a . b a . D a . b a . Az alapm veletek közül ez a legnehezebb és leglassabb. Bár polinom idÿben elvégezhetÿ, mégis ez aleginkább idÿigényes m velet. 2. relációs m veletek : • szelekció (Jele: σF(R)2) A szelekció egy adott R relációra és F formulára vonatkozik. σF(R) az R reláció azon sorait jelenti, amelyekre F formula igaz. Örökli a típusokat és attribútumokat. F alakja (Codd eredeti javaslata szerint): AΘB, AΘc, cΘA, ahol: • A és B

attribútumnevek, • c egy konkrét érték, • Θ pedig elemi összehasonlító operátorok halmaza: Θ ∈ {=,≠, <, >,≤,≥}. Ezeket az F formulákat atomoknak nevezzük. Az atomok kombinálhatók a ¬∧∨ jelekkel Példa: σA=D(S) A a b σ(A=B)∨(A≠b)(R) A a a D a b B a c A szelekció eredménye sosem egy elemi objektum, hanem általános esetben egy reláció, azaz sorok kollekciója. • vetítés (projekció) (Jele: Π) A ΠAi1,.Ail(R) vetítés az R vetítését végzi el az Ai1,Ail oszlopokra: – paramétere egy R reláció; – meg kell adni R biznoyos attribútumait is (Ai1,.Ail); – bizonyos oszlopokat elhagy a fenti R relációból; – és megváltoztatja az oszlopok sorrendjét. 2 σ, azaz szigma 49 13. tétel Relációs algebra, relációs teljesség Szemantikája egyszer : 1. vegyük az R Ai1,Ail oszlopait ebben a sorrendben; 2. hagyjuk el R többi oszlopát; 3. hagyjuk el az esetleges ismétlÿdéseket is Példa: ΠA(R) A a b A

relációs alapm veletek relációkat adnak eredményül, ezért ezen relációs m veletek egymással kombinálhatók. Pl: σA<D(R×S), ez elÿször egy Descartes-szorzást, majd egy szelekciót jelöl. 3. A relációs adatmodell további fontos mÿveletei • metszet (Jele: ∩) Adott két reláció: R és S. R∩S sorai azok a sorok lesznek, melyek R-nek és S-nek is sorai. Formálisan: R∩S=R(RS)=S(SR) Példa: az úniónál megismert R-re és S-re R∩S A a a B a c Az attribútumok öröklÿdése itt kétféle lehet. ) • természetes illesztés (összekapcsolás, join) (Jele: Adott két reláció, R és S. Az természetes illesztés m velete bármely két halmazra értelmes operáció. R S kiszámítása attól függ, hogy melyek a közös attribútumnevek a relációkban: R(A1,.Ak,B1,,Bs) S(A1,.Ak,C1,,Cd) vagyis az Ai-k a közös attribútumnevek. – Az R×S-bÿl indulva vesszük azokat a sorokat, amelyekre igaz, hogy R.Ai=SAi – Az eredményt vetítjük rá

R.A1,,RAk,C1,,Cd,B1,,Bs-re Tulajdonságai: – Az így kiadódó R S -nek (k+s+d) számú oszlopa lesz. – Örököl attribútumokat és típusokat is. – k=0 esetén egyszer szorzatm veletet jelent. 50 13. tétel Relációs algebra, relációs teljesség – Kifejezhetÿ alapm veletekkel (a gyakorlatban igyekszünk másként megkapni az egyesítés eredményét): R S = ΠA1,.Ak,B1,,Bs,C1,,Cd(σAi=Ai(R×S)) A vetítésnél nem kell az azonos sorokat törölni. Példa: k=1, s=2,d=1, (k+s+d)=4 R A a a b B b c c S C 2 3 4 D a b x C 2 3 2 R S A a a a B b b c C 2 2 3 D a x b ) • félillesztés (Jele: Technikai szerepe van a lekérdezési optimalizátorokban (elosztott rendszerekben). S). R S = ΠR(R • Általános (Θ Θ) illesztés Adott két reláció: R és S. A az R, B az S reláció attribútuma. R S jelentése: σAΘ B(R×S) AΘB Ebben az esetben tehát nem egyenlÿségre, hanem általános m veletre végezzük el az illesztést. Példa: R S R.C<SC A a

B b R.C 2 D b S.C 3 Def.: Relációs teljesség Egy relációs lekérdezÿ nyelvet relációsan teljesenek nevezünk, ha benne az öt alapm velet (únió, különbség, direkt szorzat, szelekció, vetítés) megvalósítható. Az SQL relációsan teljes. Egyes komoly lekérdezÿ nyelvek ezen minimális követelményeket túl is teljesítik, azaz nem csak relációs, hanem aggregációs m veletekre is képesek. Def.: Aggregáció Az összesítÿ m veleteket, melyek egy relációból elemi értéket állítanak elÿ, aggregációknak nevezzük. Például: AVG (átlag), MIN (minimum), MAX (maximum), CNT (számlálás), SUM (összegzés). Példa: DOLGOZÓ(SzemélyiSzám, Fizetés,.) FCNT Szemszám, AVG Fizetés(DOLGOZÓ) eredménye egy számpár lesz. Megkapjuk a dolgozók számát és az átlagos fizetést. 51 13. tétel Relációs algebra, relációs teljesség 4. NULL értékek problematikája A NULL értékek kitöltetlen attribútum-értékeket jelentenek. Például: TERMEL

(Név,Cím,Termék,Ár) (Rezeda Kázmér,NULL,Zab,300) σCím="Budapest"(TERMEL ) A NULL érték jelentése azonban nem homogén. Jelentheti azt, hogy – létezik ugyan az attribútum-érték, de nem ismerjük (ez a megengedÿ álláspont), vagy hogy – az érték nem létezik (ez a nem megengedÿ álláspont). Mÿveletek NULL értékekkel ) • Baloldali külsÿ illesztés (Jele: Az R S baloldali küls illesztésben R minden sora megjelenik, esetleg NULL értékkel Snél. Példa: R A a a S B b c B b e C d e R S A a a B b c C d NULL Ennek a mÿveletnek az univerzális relációs megközelítésnél van szerepe, ahol az univerzális relációban minden attribútum szerepel. ) • Jobboldali külsÿ illesztés (Jele: Benne fordított a szereposztás R-re és S-re nézve. ) • Teljes külsÿ illesztés (Jele: Benne a teljes R és S megjelenik. Példa: R S A a a NULL B b c e C d NULL e • Külsÿ únió (Jele: ∪k) Részben ∪-kompatibilis relációk

egyesítését jelenti. Példa: DIÁK(Név,Témavezet ,Tanszék) TANÁR(Név,Tanszék,Beosztás) DIÁK ∪k TANÁR eredménye: Név diák tanár Tanszék 52 Beosztás Témavez. 19. tétel Lezárások, fedések, vetített függések . . . . NULL . . NULL Def.: Univerzális reláció Az összes alapreláció (azaz a sémában ténylegesen tárolt reláció) külsÿ úniója az univerzális reláció. 5. E/K séma - relációs séma átalakítás Az átalakításra van egy teljesen gépies út, ami azonban nem adja mindig a legjobb megoldást. Egyed: E(A1,.,Ak) R(A1,,Ak) Reláció Az egyed egy az egyben átalakítható relációvá (k-oszlopos táblává). E A1 . R(A1,.,Ak) Ak Bonyolultabb átalakítás: E1 Em R(A1,.,As, B1,,Bl,, S1,,St) E2 R . E1 kulcsa kulcsa E2 kulcsa Em . . . . Hogyan kaphatunk jó átalakított relációs sémát? • ábrázoljunk minden információ-elemet! • a fontos igényeket kifejez mÿveletek legyenek hatékonyak! Például:

ne kelljen túl sok helyr l összeszedni egy fontos lekérdezés adatait. 13. Sor- és oszlopkalkulus 1. Sorkalkulus A sorkalkulus egy logikai jellegÿ lekérdez formalizmus. Alapja a QUEL-nek, és használatos bels reprezentáns lekérdez nyelvként. A sorkalkulus sorváltozókat használ. Ezek tipikus jelölése: t vagy t(k), ahol k jelöli az oszlopok vagy mez k számát. Ezek a reláció egy sorát jelölik, azaz oda helyettesít dnek be 53 19. tétel Lezárások, fedések, vetített függések t[i]-vel a t sorváltozó i-edik komponensét jelöljük. Példa: R Név Rezeda K. . t=t(2)=(Rezeda K.,F u) t[1]=Rezeda K. t[2]=F u. Cím F u. . Def.: Megengedett formulák I. Alap- vagy prímformulák • R(t): igaz értéket vesz fel, ha t értéke egy R-beli sor. Itt R egy alapreláció, t pedig egy sorváltozó. • t[i]Θs[j]: igaz értéket vesz fel, ha t,s értékeinél a t[i] és s[j] értékek Θ viszonyban vannak. Itt t és s sorváltozók, és Θ ∈ {=,≠, <,

>,≤,≥} • t[i]Θc, illetve • cΘ t[i], ahol c egy érték. Értékük akkor igaz, ha a t sorváltozó értéke Θ kapcsolatban van c-vel. Pl.: t[1]=Rezeda K II. Összetettebb formulák Ha ϕ, és ψ megengedett formulák, akkor ϕ ∨ψ ϕ ∧ψ ϕ¬ is megengedett formulák. Igazság-értékük a szokásos módon döntend el Ha a t sorváltozó is adott, akkor a ∃tϕ is megengedett formula. III. További megengedett formula: ∀tϕ = ¬∃t(¬ϕ) Def.: Kötött és szabad változók Egy sorváltozó kötött, ha kvantor (∃ vagy ∀) vonatkozik rá; és szabad, ha nem kötött. Pl.: i kötött: Σ i f(i) x kötött: ÿf(t) Def.: A sorkalkulus által kifejezett reláció: azon t-k tartoznak bele, amelyekre ϕ(t) teljesül Vagyis a sorkalkulus által kifejezett reláció: {t; ϕ(t)}, ahol t egy sorváltozó, ϕ pedig egy megengedett formula, melynek t az egyetlen szabad változója. Példa: a relációs adatmodell mÿveleteinek leírása a sorkalkulussal Legyen R

(k-oszlopos) és S (s-oszlopos) egy-egy alapreláció. 1. R={t(k), R(t)} S={u(s), S(u)} 2. R és S úniója kifejezhet sorkalkulussal, ha k=s: R∪S={t(k); R(t)∨S(t)}. 3. R és S metszete kifejezhet sorkalkulussal, ha k=s: R∩S={t(k); R(t)∧S(t)}. 54 19. tétel Lezárások, fedések, vetített függések 4. R és S különbsége (nem kell a k=s-et feltételezni!): RS={t(k); R(t)∧¬∃u(s)(S(u)∧u[1]=t[1]∧.∧u[k]=t[k])} 5. R és S direkt szorzata (k≠s): R×S={t(k+s); ∃u(k) ∃v(s)(R(u)∧S(v)∧t[1]=u[1]∧.∧t[k]=u[k]∧ t[k+1]=v[1]∧.∧t[k+s]=v[s])} 6. Szÿrés, szelekció (σF): σA1<3∧A2=c(R) ={t(k); R(t)∧t[1]<3∧t[2]=c}. 7. Vetítés (Π): (m) (k) ΠA1,.,Am(R) ={t ; ∃v (R(v)∧v[1]=t[1]∧∧v[m]=t[m])} Megj.: A 2-7 mÿveleteknél nem lényeges, hogy R és S alapreláció legyen R={t, ϕ(t)}, S={u,ψ(u)}. Tétel: A relációs algebra mÿveletei - az el bbiek alapján - kifejezhet k sorkalkulus segítségével. Ezzel kaptunk egy relációs algebra

sorkalkulus átírási módot. Fordított irányban ez nem megy; a sorkalkulus tehát bizonyos értelemben erÿsebb, mint a relációs algebra. Megj.: Az, hogy egy reláció véges inputtal rendelkezik, öröklÿdÿ tulajdonság Ennek megfelelÿen a relációs algebra véges bemenethez véges kimenetet szolgáltat. A sorkalkulusra ez nem mindig igaz. Pl gondot okoznak a {t(k); ¬R(t)}típusú relációk (ahol R alapreláció), mert nagyon nagy méret lehet az eredményük. Def.: Biztonságos formula DOM(ϕ)={ϕ-ben elÿforduló konstansok, értékek és a ϕ-beli alaprelációk értékei} ϕ megengedett formula. Arra törekszünk, hogy egy formula igazságértéke a DOM-beli értékek alapján eldönthetÿ legyen. Pl.: ϕ(t)=t[1]=3∨R(t), ahol R egy bináris alapreláció DOM(ϕ)={3}∨ΠA1(R)∨ Π2(R) (a második vetítésnél sorszámát megnevezni) elég az ottribútum Az R1={t, ϕ(t)}kifejezés biztonságos, ha: (i) abból, hogy t∈R1, következik, hogy t komponensei

DOM(ϕ)-beliek. (ii) a ϕ tetszÿleges, ∃uψ(u) alakú részformulájára teljesül, hogy ha a ψ(u) igaz (a többi változó akármilyen értékeivel), akkor az u komponensei DOM(ϕ)-beliek. Megj.: (ii) szerint a ∃uψ(u) igazsága az u változó DOM(ϕ)-beli értékeivel vizsgálható Jellegzetes példák biztonságos formulára: 55 19. tétel Lezárások, fedések, vetített függések 1. ∃u(R(u)∧ϕ(u)), ahol R egy alapreláció Itt (ii) automatikusan jó u-ra 2. {t, R(t)∧ϕ}biztonságos, ha ϕ az Def.: Biztonságos sorkalkulus reláció Az a {t; ϕ(t)} reláció, ahol ϕ biztonságos, megengedett formula, aminek t az egyetlen szabad változója. Megj.: az 1-7 relációk mind biztonságosak Tétel: A relációs algebra ekvivalens a biztonságos sorkalkulussal. (nem biz.) 2. Oszlopkalkulus Az oszlopkalkulusban az ún. oszlopváltozók egy mezÿ értékét vehetik fel Ábrázolva: reláció A B . D sorváltozó oszlopváltozó Alapformulák • R(u1u2.uk) egy

k-oszlopos alapreláció, amelyben az ui oszlopváltozók szerepelnek • uΘv,uΘc,cΘu, ahol u és v oszlopváltozók, c egy érték, és Θ elemi összehasonlító operátor. Az építkezés ezekkel az alapformulákkal és a ¬∧∨∀∃ jelekkel történik, ugyanúgy, ahogy a sorkalkulusnál. Def.: Megengedett (kifejezett) reláció az {u1,u2,.,uk; ϕ( u1,u2,,uk)}reláció, ahol a ϕ formulának csak az u1,u2,,uk lehet a szabad változója. Def.: Biztonságos formula Nem más, mint egy biztonságosan kifejezett reláció. Ahogy a sorkalkulusnál is láttuk, úgy itt is megfogalmazható a DOM(ϕ)-vel egy kvantorfeltétel. Tétel: A sorkalkulus ekvivalens3 az oszlopkalkulussal Biz.: Ez egyfajta "szótárral" mutatható meg: • R(t) ↔ R(u1,u2,.,uk), ahol R(t) egy k-változós sorváltozó; • t[i]Θt[j] ↔ uiΘuj; • t(m)ϕ ↔ ∃u1∃u2∃umψ, ahol ψ a ϕ átírása. 3 az ekvivalencia jele: ↔ 56 19. tétel Lezárások, fedések, vetített függések

Tétel: Biztonságos kalkulus ↔ biztonságos oszlopkalkulus ↔ relációs algebra A bizonyítás alapgondolata: A relációs algebra kifejezhetÿ a biztonságos sorkalkulussal, és az elÿbb bemutatott átalakítási "szótár" alapján a sorkalkulusból eljuthatunk a biztonságos oszlopkalkulushoz is. Ez eddigi eredményeinkbÿl következik. De a biztonságos sorkalkulus is kifejezhetÿ a relációs algebra segítségével. Ezt már nehezebb belátni. Az igazolás ötlete: Legyen {t(m), ϕ}egy biztonságos sorkalkulus reláció. Relációs algebrai kifejezést kell találni DOM(ϕ)m∩R-re. De a biztonságosság miatt ez R-vel egyezik meg, és ezzel állításunkat igazoltuk. 14. Relációs lekérdezÿ nyelvek (QBE) 1. A relációs lekérdezÿ nyelvekrÿl általában Két fÿ csoportjuk van: a.) Algebra típusú nyelvek • A relációs algebrát valósítják meg egy az egyben. • ΠA1.Ak (R) ↔ R % A1,,Ak • Felhasználói felületként nem használatosak. •

Valódi felhasználási területük: lekérdezés-feldolgozó rendszerekben történÿ (algebrai) optimalizálás. Kalkulus típusú nyelvek b.) • ezek a legfontosabb felhasználói nyelvek, melyek közül az SQL talán a legfontosabb; • QUEL: az INGRES nyelve; • QBE: képernyÿorientált, oszlopkalkulus-jelleg nyelv. Egy másik csoportosítási szempont szerint pedig beszélhetünk: 1.) Procedurális nyelvekrÿl: a kérdések, igények negfogalmazásakor nem csak a MIT, hanem a HOGYAN kérdésre is válaszolni kell. Az algebra típusú nyelvek tartoznak ide A procedurális nyelveket belsÿ kérdés-reprezentációra használják. (Pl egy SQL-kérdést a lekérdezés-fordító algebrai kifejezéssé alakít át, hogy algebrai azonosságokkal azt optimális alakúvá tehesse.) 2.) Leíró nyelvek: itt csak a MIT számít A kalkulus típusú nyelvek tipikusan ilyenek Ezeket a nyelveket a felhasználók tudják hatékonyan használni. Példa a feladatmegoldásra különbözÿ

eszközökkel Adott a következÿ két reláció: Alkalmazott(Név,Munkakör) Személy(Név,Cím) 57 19. tétel Lezárások, fedések, vetített függések Feladat: adjuk meg a kazánkovácsok címeit! • ennek megoldása oszlopkalkulusban: {c; ∃n Alkalmazott(n,kazánkovács) ∧ Személy(n,c)} Megj.: a kazánkovács string-egyenlÿség vizsgálatot valójában Θ-val kellene leírni • és megoldása relációs algebrában: Személy)) Πcím(σMunkakör=kazánkovács(Alkalmazott Ez valójában egy "recept": – képezzük az Alkalmazott és Személy természetes, név szerinti illesztését (Név, Cím, Munkakör az eredmény); – ebbÿl sz rjük ki azokat a sorokat, ahol a foglalkozás éppen kazánkovács; – majd vetítünk a címre, hiszen csak erre vagyunk kíváncsiak. Gyorsítási lehetÿség: a sz rést elÿbb is elvégezhetjük. Személy) [További gyorsítás: vetítés a Πcím(σMunkakör=kazánkovács(Alkalmazott) névre] 2. Amit a QBE-rÿl tudni

kell A QBE (Query By Example) egy önálló IBM-fejlesztés eredményeként létrejött nyelv. Jellemzÿje, hogy képernyÿ-orientált és direkt manipulációs eszközként funkcionál. Azaz a felhasználó a saját maga által kidolgozott módszereket alkalmazhat általános esetekre. Ehhez a rendszer alapeszköze a reláció-váz (skeleton). A QBE a felszínen oszlopkalkulus-jelleg nyelv, de implicit módon sorvátozókat használ. 2.1 A QBE szintaktikus elemei • A parancsok felépítése: string . – kiíró utasítás: P. – beszúró utasítás: I. – törlÿ utasítás: D. • A változók felépítése: string Példa: Adott a Személy(Név, Cím, Szsz, .) alapreláció Személy Név P. Kiss P. P.Kiss Cím Szsz . megjeleníti az összes Személyt kiírja az összes Kiss nev t P. Több táblás példa: Rendelés Szám Név Kiss Termék búza 58 Mennyiség 19. tétel Lezárások, fedések, vetített függések Termelÿ Tnév . P. Termékné v P. búza

Megadjuk az összes olyan termelÿnév-termék párt, ahol a Kiss nev rendelt valaha is az adott termékbÿl. megrendelÿ 2.2 A QBE lekérdezéseinek szemantikája (1.) A lekérdezés ciklikus az implicit sorváltozókra (ez a példában t1 és t2); (2.) A feltételek minden kiértékelésre ellenÿrzÿdnek Elÿbbi példánkból: t1.Név=Kiss t1.Termék=t2Terméknév Példa: Rendelés Szám Név Kiss P. Termék zab zab Mennyiség x ≥x Azon zab-rendeléseket kapjuk, amelyekben a mennyiség nagyobb, mint a Kiss által rendelt minimális zab-mennyiség. Oszlopkalkulussal megfogalmazva az alábbi kérdések adhatók ki QBE-ben: {a1,.,ak ∃ b1,,bn: R1(c11,,c1i1)∧ ∧ Rm(cm1,,cmin)} Az Ri relációban vagy oszlopváltozó vagy konstans szerepel. A QBE további eszköze a feltétel-doboz (cond. box), amibe olyan feltételek kerülnek, amelyek a táblázatba nem írhatók be. Nincs fix szabály az ismétlÿdÿ sorokra. (Ahogy pl a vetítésnél volt) • ALL.: multihalmaz, az

ismétlÿdés megmarad; • UN.: ismétlÿdés nincs Pl.: Rendelés Szám Név P.UN Termék brokkoli . P.ALL Mennyiség . P.ALL Azok nevét kapjuk meg - egyszeresen -, akik brokkolit rendeltek. Minden (Termék, Mennyiség) párt megkapunk. 59 19. tétel Lezárások, fedések, vetített függések A "szokásos" aggregációk is használhatók, például: (megkapjuk az összes számlaegyenleget) Ügyfél Egyenleg P.AVGALL 2.3 A QBE DDL elemei • Tábladefiníció - példán keresztül mutatjuk be: I. TERMEL I KEY I. TYPE I. DOMAIN I. INVERSION I. Tnév Y CHAR NEVEK N Cím N CHAR CÍMEK N Terméknév Y CHAR TERMÉKNÉV N Ár N FLOAT MENNY N – KEY: "Y" (yes) és "N" (no) bejegyzésekkel kijelöltük, hogy a (Tnév, Terméknév) pár legyen a kulcs. – TYPE: megadtuk az attribútumok típusát – DOMAIN: a megadott bejegyzés korlátozza a változókat, azaz a változóknak saját értékkészletükön belül kell mozogniuk (a Tnév a

NEVEK halmazából veheti fel értékét). – INVERSION: általában specifikálhatunk másodlagos elérési kulcsokat is (most nem éltünk ezzel a lehetÿségünkkel). • Nézetek: hasonlóképp adhatók meg • Táblamódosítás: ez is eleme a QBE-nek, de nem mutatunk rá példát. 2.4 A QBE néhány DML utasítása • Beszúrás: I. kerül a sorinformációs részbe Pl: TERMEL I. Tnév Sasad Sasad Cím Cím Cím Terméknév kutyabenge Ár 50 A Címet elÿre nem tudjuk; a feltehetÿleg már meglévÿ információt kikerestetjük az adatbázisból. • Módosítás: U. kerül a sorinformációs részbe Pl: SZEMÉLY U. Név Szsz xyz.u Cím Akácfa u. A keresés kulcs-attribútumok szerint történik (most: személyi szám), a módosítás pedig csak a nem kulcsmezÿket érinti. 60 19. tétel Lezárások, fedések, vetített függések • Törlés: D. kerül a sorinformációs részbe Pl: SZEMÉLY D. Név Szsz xyz.u Cím Kulcs alapján azonosítja a törlendÿ

sort. A fentiek alapján kimondhatjuk, hogy a QBE relációsan teljes nyelv. (Azaz megvalósítható benne az únió, direkt szozás, vetítés, szelekció (F-et cond. box-ban kell felírni) és különbség (törléssel kell megoldani).) 15. A QUEL lekérdezÿ nyelv 1. A relációs lekérdezÿ nyelvekrÿl általában Két fÿ csoportjuk van: a.) Algebra típusú nyelvek • A relációs algebrát valósítják meg egy az egyben. • ΠA1.Ak (R) ↔ R % A1,,Ak • Felhasználói felületként nem használatosak. • Valódi felhasználási területük: lekérdezés-feldolgozó rendszerekben történÿ (algebrai) optimalizálás. b.) Kalkulus típusú nyelvek • ezek a legfontosabb felhasználói nyelvek, melyek közül az SQL talán a legfontosabb; • QUEL: az INGRES nyelve; • QBE: képernyÿorientált, oszlopkalkulus-jelleg nyelv. Egy másik csoportosítási szempont szerint pedig beszélhetünk: 1.) Procedurális nyelvekrÿl: a kérdések, igények negfogalmazásakor nem csak a

MIT, hanem a HOGYAN kérdésre is válaszolni kell. Az algebra típusú nyelvek tartoznak ide A procedurális nyelveket belsÿ kérdés-reprezentációra használják. (Pl egy SQL-kérdést a lekérdezés-fordító algebrai kifejezéssé alakít át, hogy algebrai azonosságokkal azt optimális alakúvá tehesse.) 2.) Leíró nyelvek: itt csak a MIT számít A kalkulus típusú nyelvek tipikusan ilyenek Ezeket a nyelveket a felhasználók tudják hatékonyan használni. 2. Amit a QUEL-rÿl tudni kell A QUEL sorkalkulus-típusú nyelv. Eredetileg az INGRES nyelve, ami egy, a UNIX és Cvilághoz leginkább illeszkedÿ adatbáziskezelÿ rendszer Az INGRES a UC Berkeley fejlesztése. 61 19. tétel Lezárások, fedések, vetített függések A QUEL relációsan teljes nyelv. A QUEL is beágyazható, tipikus gazdanyelve a C. Példa: ## RANGE OF E IS SZEMÉLY; ## RETRIEVE (X=E.NÉV, Y=ECÍM) WHERE EFIZETÉS=0; ## {Küldjünk X-nek zord levelet az Y címre} A QUEL-részben lehetnek

külsÿ (program) változók. A mag, azaz a {}-ek közti rész minden találatra lefut, és ezzel a QUEL egy lekérdezés-egy rekord típusú nyelv. 2.1 A QUEL DDL-je: adatleíró utasítások (DDS) • Új reláció (tábla) létrehozása: CREATE <relációnév> (<mezÿnév> : <típus> <hossz>);* A * mutatja azt, hogy többoszlopos relációk a szokásos módon létrehozhatók. Típusok: – I1, I4, I8: egészek 1,4,8 byte-on ábrázolva – F4, F8: lebegÿpontos számok 4 ill. 8 byte-on – Cn: n (fix) hosszúságú karaktersorozat – Varchar(n) és Text(n): legfeljebb n-hosszú string – Date: dátum típus – Money: 16 jegy szám, az utolsó 2 jegy tizedesjegy (pénzösszegek tárolására). Tárolási szerkezetek: – ISAM, CISAM: index-szekvenciális (ritka index) [C: compact, azaz kompaktabb, tömörebb, és ezért lassabb változat] – HASH, CHASH – BTREE, CBTREE – HEAP: ez az alapértelmezett szerkezet. • Új indexehozása: INDEX ON

<relációnév> IS <indexnév> (<mezÿnév>); Példa: Adott az ALKALMAZOTT (NÉV, SZSZ, RÉSZLEGNÉV, FIZETÉS) reláció MODIFY ALKALMAZOTT TO BTREE UNIQUE ON SZSZ; [elsÿdleges elérés] INDEX ON ALKALMAZOTT IS NÉV IND (NÉV); MODIFY NÉV IND TO CBTREE ON NÉV; [másodlagos elérés] Az elsÿ MODIFY parancs az ALKALMAZOTT állományt B-fa szervezés vé alakítja. A keresési kulcs az SZSZ személyi szám lesz (ami ráadásul egyedi is). A második MODIFY az állomány másodlagos elérését definiálja (CBTREE szerint). • Reláció ill. index törlése: DROP <tábla- ill. indexnév>; 62 19. tétel Lezárások, fedések, vetített függések 2.2 A QUEL keresÿ-kérdések rendszere (Queries) A keresÿ-kérdések tipikusan három részbÿl tevÿdnek össze: a.) (biztonságos) sorváltozó-specifikáció (ez felel meg az SQL-ben a FROM-nak) RANGE OF <sorváltozónév> IS <alaprelációnév>; . RANGE OF. [Ilyen sorból több is van b.)

elÿtt] Pl.: RANGE OF E IS ALKALMAZOTT; [az elÿzÿ példából] E az alkalmazottakon fut végig. Hivatkozások: ENÉV, ESZSZ, E:RÉSZLEGNÉV b.) kérdés-test (ez felel meg az SQL-ben a SELECT-nek) Meg kell adni RETRIEVE-vel, hogy mi jelenjen meg az eredményben. Pl.: RETRIEVE (EALL); [E összes komponense megjelenik] RETRIEVE (E.NÉV, ERÉSZLEGNÉV); [csak a név és a részleg neve] RETRIEVE UNIQUE (E.FIZETÉS); [kisz rjük a többször elÿforduló adatokat] Idÿleges relációk is kialakíthatók a RETRIEVE INTO kulcsszóval. Pl.: RANGE OF E IS SZEMÉLY; RETRIEVE INTO PASAS (PNÉV=E.NÉV, ) WHERE ENEM=hím; Itt az E.NÉV kifejezés ad értéket a PNÉV attribútumnak Aggregációk Ezek már a korábban megismert AVG, CNT, SUM, MIN, MAX. A különbség csak annyi, hogy a feltételvizsgálat aggregáción belülre tehetÿ, sÿt: csoportosításra is alkalmas. Pl.: RETRIEVE MAX(EFIZETÉS); RETRIEVE MAX(E.FIZETÉS WHERE ECÍM=Fÿ u); RETRIEVE MAX(E.FIZETÉS BY NEM); [GROUP BY]

RETRIEVE MAX(E.FIZETÉS BY NEM WHERE ECÍM=Fÿ u); Az aggregációk egymásba ágyazhatók és szerepelhetnek a ϕ formulában is. Az eredményt maga a RETRIEVE formázza azáltal, hogy attribútumait milyen sorrendben adjuk meg. A rendezés a SORT BY <mezÿk> -kel lehetséges; a rendezést a kérdés-test végére kell tenni. Pl: PASAS SORT BY PNÉV A; [A: ascending, növekvÿ] c.) feltétel(ek) (ez felel meg az SQL-ben a WHERE-nek - itt is így használják) WHERE után a ϕ formulában fogalmazzuk meg a feltételt. ϕ tartalmazhatja az AND (∧), OR (∨), NOT (¬) kulcsszavakat. Továbbá a ϕ-be tehetÿ explicit kvantor is - ilyen például az ANY. Ennek szintaktikája: ANY (<kérdés-test a WHERE nélkül> <feltétel>) Eredménye: • 0, ha nincs ilyen, és • 1, ha van. 63 19. tétel Lezárások, fedések, vetített függések Pl.: ANY(ENÉV WHERE ECÍM=Sármellék)=0; Ez akkor igaz, ha nincs olyan egyed, aki Sármelléken lakik. A WHERE ϕ feltételébe

RETRIEVE is tehetÿ, de csak egy mélységig. ϕ=ϕ1∨ϕ2 2.3 A QUEL DML-je (DMS utasítások) • Törlés: DELETE Szerkezete: RANGE OF E IS . . DELETE E; WHERE ϕ [kiválasztjuk, hogy mit akarunk törölni] • Beillesztés: APPEND TO Szerkezete: APPEND TO SZEMÉLY(Kif1, .); – 16. Az SQL adatbáziskezelÿ nyelvi felület 1. A relációs lekérdezÿ nyelvekrÿl általában Két fÿ csoportjuk van: a.) Algebra típusú nyelvek • A relációs algebrát valósítják meg egy az egyben. • ΠA1.Ak (R) ↔ R % A1,,Ak • Felhasználói felületként nem használatosak. • Valódi felhasználási területük: lekérdezés-feldolgozó rendszerekben történÿ (algebrai) optimalizálás. b.) Kalkulus típusú nyelvek • ezek a legfontosabb felhasználói nyelvek, melyek közül az SQL talán a legfontosabb; • QUEL: az INGRES nyelve; • QBE: képernyÿorientált, oszlopkalkulus-jelleg nyelv. Egy másik csoportosítási szempont szerint pedig beszélhetünk: 1.) Procedurális

nyelvekrÿl: a kérdések, igények negfogalmazásakor nem csak a MIT, hanem a HOGYAN kérdésre is válaszolni kell. Az algebra típusú nyelvek tartoznak ide A procedurális nyelveket belsÿ kérdés-reprezentációra használják. (Pl egy SQL-kérdést a lekérdezés-fordító algebrai kifejezéssé alakít át, hogy algebrai azonosságokkal azt optimális alakúvá tehesse.) 2.) Leíró nyelvek: itt csak a MIT számít A kalkulus típusú nyelvek tipikusan ilyenek Ezeket a nyelveket a felhasználók tudják hatékonyan használni. 64 19. tétel Lezárások, fedések, vetített függések 2. Amit az SQL-rÿl tudni kell Az SQL fÿként oszlopkalkulus-filozófiájú nyelv, de ezen felül egyéb funkciói is vannak, például lehet benne két kifejezés únióját is venni. Az SQL relációsan teljes nyelv Létezik az SQL-nek beágyazott formája is, ami tetszÿleges alkalmazásból elérhetÿvé teszi az adatbázist. (Speciális fogalmak: kurzor, SQLCODE4) Az SQL • szabvány,

amelyet jelenleg csaknem minden relációs adatbáziskezelÿ alkalmaz kisebb-nagyobb módosításokkal; felhasználó közeli nyelv, alkalmas hálózatokon • tömör, adatbáziskezelÿ szerver és kliensek közötti kommunikációra; procedurális programozási nyelv (legalábbis a • nem lekérdezéseknél).5 A nyelv utasításait az alábbi csoportokba oszthatjuk: 1. adatleíró (DDS, Data Definition Statement); 2. lekérdezÿ (Queries) 3. adatmódosító (DMS, Data Manipulation Statement); 4. adatelérést vezérlÿ (DCS, Data Control Statement) utasítások 2.1 Az SQL DDL-je: adatleíró utasítások (DDS) • Új reláció (tábla) létrehozása: CREATE TABLE <táblanév> (<oszlopnév> <típus> [NOT NULL] [,<oszlopnév> <típus> [NOT NULL], . ]); Ha valamely oszlop definíciója tartalmazza a NOT NULL módosítót, akkor a megfelelÿ mezÿben mindig valamilyen legális értéknek kell szerepelnie. • Új nézetek létrehozása: CREATE VIEW

<nézetnév> [(<oszlopnév> [,<oszlopnév> , . ])] AS <lekérdezés6>; A nézetek olyan virtuális táblák, amelyek a fizikai táblákat felhasználva a tárolt adatok más és más logikai modelljét, csoportosítását tükrözik. Felhasználhatók a tárolt információ részeinek elrejtésére, pl. különbözÿ felhasználók más-más nézeteken keresztül szemlélhetik az adatokat. A nézet általában csak olvasható, az adatmódosító m veletekben csak akkor szerepelhet, ha egyetlen táblából keletkezett és nem tartalmaz számított értékeket. A lekérdezésre az egyetlen megkötés, hogy rendezést nem tartalmazhat. Ha nem adunk meg oszlopneveket, akkor a nézetek oszlopai a SELECT után felsorolt oszlopok neveivel azonosak. Meg kell viszont adni az oszlopneveket, ha a SELECT számított értékeket is elÿállít. 4 Lásd: Adatbázisok Laboratórium jegyzet, 1998. 33 oldal: a Pro*C elÿfordító 5 Forrás: Adatbázisok Laboratórium

jegyzet, 1998. (19oldaltól) 6 Lásd késÿbb (Queries) 65 19. tétel Lezárások, fedések, vetített függések • Tábla törlése: DROP TABLE <táblanév>; • Nézet törlése: DROP VIEW <nézetnév>; • Tábladefiníciók módosítása: ALTER TABLE <táblanév> [ADD | MODIFY] <oszlopnév> <típus>; – Az ADD egy új, NULL érték oszlopot illeszt a táblához, – a MODIFY paranccsal pedig egy létezÿ oszlop szélessége növelhetÿ. • Indexek létrehozása: CREATE [UNIQUE] INDEX <indexnév> ON <táblanév> (<oszlopnév> [,<oszlopnév>, . ]); Tulajdonságok: – Az indexek a táblákban való keresést gyorsítják meg. – Az indexeket az adatbáziskezelÿ a táblák minden módosításánál felfrissíti. – Ha egy indexet a UNIQUE kulcsszóval definiáltunk, akkor a rendszer biztosítja, hogy az adott oszlopban minden mezÿ egyedi értéket tartalmazzon. – Lehetséges több oszlopot egybefogó, kombinált

indexek létrehozása is. – Az indexek létrehozásuk után a felhasználó számára láthatatlanok, csak a lekérdezéseket gyorsítják. – Indexeket azokra az oszlopokra érdemes definiálni, amelyek gyakran szerepelnek keresésekben. – Index nélkül minden kéréshez be kell olvasni az egész táblát. De ha a keresési feltételhez van megfelelÿ index, akkor az adatbáziskezelÿ a diszkrÿl csak a valóban szükséges sorokat olvassa be. a keresést, ha csak a keresési – Az indexek akkor is gyorsítják feltétel egy részére vonatkoznak. • Index törlése: DROP INDEX <indexnév>; 2.2 Az SQL lekérdezései A lekérdezések általános szintaxiasa a következÿ: SELECT <jellemzÿk> ezek definiálják az eredménytábla oszlopait FROM <táblák> ezek adják meg a lekérdezésben résztvevÿ táblák nevét [WHERE <logikai kifejezés>] ezzel válogathatunk az eredmény sorai között [GROUP BY <attribútumok>] ez rendezi egymás mellé az

eredménytábla sorait [HAVING <attribútumok>] ezzel a csoportosítás révén keletkezÿ eredménysorokra kiválasztási feltételt írunk elÿ [ORDER BY <attribútumok>] ez határozza meg a megjelenÿ sorok sorrendjét 66 19. tétel Lezárások, fedések, vetített függések Tulajdonságok: • A lekérdezésekben felhasznált Θ operátor többféle lehet; például különbözÿ halmazoperátorok is alkalmazhatók (EXISTS, IN, NOT IN, CONTAINS [ez utóbbi másodrend operátor, nagyon erÿs!]). • A lekérdezésekben használhatók aggregációk is, más néven oszlopfüggvények és eredményeik. Ilyenek: AVG, COUNT, SUM, MIN, MAX A "szokásos" programozási nyelveken ezen oszlopfüggvények eredményét ciklussal kaphatjuk meg. • A lekérdezésekben NULL értékek is felhasználhatók. Pl: WHERE Cim IS NULL • A SELECT-ek egymásba ágyazhatók. A beágyazott lekérdezés vagy egyetlen, vagy több értéket állít elÿ. Több érték egy

halmazt jelent, tehát a halmazm veleteket használhatjuk • Algebra-m veletek: UNION(∪), INTERSECT(∩), MINUS (/). 2.3 Az SQL DML-je: adatmódosító utasítások (DMS) • Adatok bevitele INSERT INTO <táblanév> [(<oszlopnév> [,<oszlopnév>, . ])] VALUES (<kif1>[, <kif2>, .]); Tulajdonságok: – Ha nem adjuk meg az oszlopok nevét, akkor a tábla deklarálásánál megadott sorrendben minden mezÿnek értéket kell adni. – Ha viszont megadtuk az egyes oszlopok neveit, akkor csak azoknak adunk értéket, mégpedig felsorolásuk sorrendjében. A többi mezÿ NULL érték lesz. – Az egyes mezÿknek NULL értéket is adhatunk, ha a deklaráció alapján az adott mezÿnek lehet NULL értéke. – Ha olyan oszlopnak akarunk NULL értéket adni, amelynek nem lehet NULL értéke, akkor a parancsvégrehajtás hibával le fog állni. – Egy ilyen INSERT paranccsal egyszerre csak egy sort tudunk felvenni a táblába. • Adatok törlése DELETE FROM

<táblanév> [WHERE <logikai kifejezés>]; Ha a WHERE hiányzik, akkor a tábla valamennyi sorát, ellenkezÿ esetben csak a logikai kifejezés által kiválasztott sorokat töröljük. • Adatok módosítása UPDATE <táblanév> SET <oszlopnév> = <kifejezés> [, <oszlopnév> = <kifejezés>, .] [WHERE <logikai kifejezés>]; Ha a WHERE hiányzik, akkor a parancs a tábla valamennyi sorában módosít, egyébként csak a logikai kifejezés által kiválasztott sorokat töröljük. 2.4 Az SQL adatelérést vezérlÿ utasításai (DCS) • Jogosultságok definiálása GRANT [DBA | CONNECT | RESOURCES] TO <felhasználó> [, <felhasználó>, .] 67 19. tétel Lezárások, fedések, vetített függések IDENTIFIED BY <jelszó> [, <jelszó>, .]; Ezzel a paranccsal az egyes felhasználóknak az adatbázishozvaló hozzáférési jogát szabályozzuk. A DBA jogosultság az adatbázis adminisztrátorokat definiálja,

akiknek korlátlan joguk van az összes adatbázis objektum felett, nem csak létrehozhatják, módosíthatják, illetve törölhetik ÿket, de befolyásolhatják az objektumok tárolásával, hozzáférésével kapcsolatos paramétereket is. A RESOURCES jogosultsággal rendelkezÿ felhasználók létrehozhatnak, módosíthatnak, illetve törölhetnek új objektumokat. A CONNECT jogosultság csak az adatbáziskezelÿbe való belépésre jogosít. GRANT <jogosultság> [,<jogosultság>, .] ON <tábla- vagy nézetnév> TO <felhasználó> [WITH GRANT OPTION]; a megkapott jogosultság tobábbadható Ezzel a paranccsal az egyes objektumokhoz (táblákhoz, nézetekhez) való hozzáférést szabályozzuk. A <jogosultság> az objektumon végezhetÿ m veleteket adja meg • Tranzakciókezelés A tranzakció az adatbázis módosításának olyan sorozata, amelyet vagy teljes egészében kell végrehajtani, vagy egyáltalán nem. Az adatbáziskezelÿk biztosítják,

hogy mindig vissza lehessen térni az utolsó teljes egészében végrehajtott tranzakció utáni állapothoz. Egy folyamatban lévÿ tranzakciót vagy a COMMIT utasítással zárhatunk le, amely a korábbi COMMIT óta végrehajtott összes módosítást véglegesíti, vagy a ROLLBACK utasítással törölhetjük hatásukat, visszatérve a megelÿzÿ COMMIT kiadásakor érvényes állapotba. • Párhuzamos hozzáférés szabályozása LOCK TABLE <táblanév> [,<táblanév>, .] IN [SHARE | SHARED UPDATE | EXCLUSIVE] MODE [NOWAIT]; (A tábla más által olvasható | más által olvasható és módosítható | kizárólagos hozzáférés .) Ezzel a paranccsal egy felhasználó megadhatja, hogy az egyes táblákhoz más felhasználóknak milyen egyidej hozzáférést engedélyez. Az utasítás végrehajtásánál a rendszer ellenÿrzi, hogy a LOCK utasításban igényelt felhasználási mód kompatibilis-e a táblára érvényben lévÿ kizárással: • Ha megfelelÿ, akkor

akkor az utasítás visszatér és egyéb utasításokat lehet kiadni. • Ha nem, akkor az utasítás várakozik, amíg az érvényes kizárást megszüntetik - ha a parancs nem tartalmazza a NOWAIT módosítót (mert ekkor a LOCK utasítás mindig azonnal visszatér, de visszaadhat hibajelzést is). A táblához a hozzáférést az elsÿ sikeres LOCK utasítás definiálja. 68 19. tétel Lezárások, fedések, vetített függések 17. Funkcionális függések 1. Bevezetés Alapkérdés: melyek a "jó" relációk, amelyeket a tényleges séma szintjén érdemes tárolni? Azaz: mik legyenek az igazi alaprelációk? Hogyan kaphatunk tetszÿleges relációkból "jó" relációkat? Ezekre a kérdésekre válaszol a relációs sémák tervezésének elmélete. A "jó" relációkat nevezzük majd a késÿbbiekben normálformájú relációknak, és azt az átalakítási folyamatot, amivel a tetszÿleges relációból normálformájút készítünk,

normalizálásnak nevezzük. Megszorítások, kényszerek: a lehetséges tábla-tartalmat korlátozzák. • A leírás valóság-részébÿl jönnek, azaz a modell részei; • követelményeknek tekintjük ÿket. A relációs szemlélet szerint ilyen megszorítások lehetnek: • típus-elÿírások; • pl. MAGASSÁG < 380 cm, vagy ÁR ≥ 0; • tartalmazási korlátozás: {DOLGOZÓ.NÉV}⊆{SZEMÉLYNÉV}, vagyis minden dolgozó egyben személy is. Ez a típus-altípus viszony egye esete, de a korlátozás ugyanúgy érvényes itt is. • értékfüggetlen korlátozások: fontos fajtájuk a funkcionális függés. 2. A funkcionális függés Jelölés: Adott az R(A1,.,Ak) relációs séma, ahol R a reláció neve, Ai pedig az i-edik attribútum. Az attribútumoknak fix részhalmazai vannak: X⊆{A1,.,Ak}, ami rövidebben: X⊆R Def.: Funkcionális függés X,Y⊆ R Y funkcionálisan függ X-tÿl az r relációra nézve, ha abból, hogy r két sora X-en megegyezik, következik,

hogy a két sor Y-on is megegyezik. Itt r egy, az R sémához illeszkedÿ valódi reláció. Jelölés: XY teljesül r-en. Példák 1. Adott a TERMEL (Név,Cím,Termék,Ár) rekord, amit a (Név,Termék) pár egyértelm en meghatároz. Egy termelÿnek pedig egy, vagy annál több címe lehet Funkcionális függések: a.) NévCím b.) Név, TermékNév, Cím,Termék, Ár = R (azaz az egész rekordot meghatározza) 69 19. tétel Lezárások, fedések, vetített függések 2. Adott az R(A,B,C) reláció táblája A a a B b c C c c = r rek. r-ben az • ABC függés "üresen" teljesül, az • AC függés nem "üresen" igaz, és a • CB függés nem teljesül. Bennünket a lényegi függések érdekelnek, amelyek általános érvény ek és részei modellünknek. 3. Adott a SZEMÉLY reláció: . Szsz Nem 1. 1. ffi ffi Szemszí n kék kék NemSzemszín: ez nem igazi függés, ezzel szemben a SzszNem már igazi függést jelez. Ez már számunkra is fontos!

Általánosan: adott az (R,F) pár, ahol R egy reláció és F függések egy halmaza. Csak olyan R-hez illeszkedÿ r relációkkal foglalkozunk, melyekben F függései teljesülnek. Ezek a függések azért ilyen kiemelten fontosak számunkra, mert anomáliákat okozhatnak. Pl.: a TERMEL relációban adott NévCím és Név, TermékR függések mellett elÿfordulhat, hogy ha valaki nem termel terméket, akkor nem lesz felvéve a címe sem. Def.: Függÿleges felbontás Az anomáliák elkerülése érdekében használható a függÿleges felbontás technikája. Ekkor nem magát R-et, hanem függÿleges vetületeit tároljuk. Elÿbbi példánkban: R1: ΠNév,Cím(R) R2: ΠNév,Termék,Ár(R) Ezzel a felbontással az anomáliák is eltünnek. Ennek az elÿnynek azonban az az ára, hogy R helyreállítása, az R=R1 R2 természetes illesztés költséges m velet. Felmerül a kérdés, hogy mért nem használható egy másik függÿleges felbontás, például a következÿ: (Név,Cím,Ár)

és (Név, Termék) Ez rossz, mert elvész a Termék és Ár közötti kapcsolat! A révén az összes ár szerepelni fog az összes termék mellett adott nev termelÿ esetén. Azaz: RR R" 70 19. tétel Lezárások, fedések, vetített függések Látható tehát, hogy miben áll a természetes illesztés "mágikus" szerepe: az eredeti reláció visszaállítása vagy vele történik, vagy sehogy. Az elkövetkezendÿkben ezt tételként is meg fogjuk fogalmazni. 3. A funkcionális függés elméleti háttere Def.: Logikai következmény Adott az (R,F) pár. Az XY függés logikai következménye F-nek, ha XY érvényes minden olyan Rsémájú r relációban, ahol az F is érvényes. Jele: F |= XY Ha a logikai következmény fogalma mellé megalkotjuk a levezethetÿség fogalmát is (|), akkor kezünkben lesz az a "kalkulus", ami a normailizáláshoz kell. Ugyanis, ha tökéletesen formalizáljuk a levezetést, akkor elérjük a kit zött |= ≈ |

célt. • | ÿ |= irány: az igazság-tétel mondja majd ki; • |= ÿ| irány: a (Gödel-féle) teljességi tétel mondja ki. Def.: Armstrong-axiómák (R,F)-re A1. Reflexív szabály Y⊆X⊆R ÿ XY A2. Kiegészítési szabály Ha XY és Z⊆R ÿ XZ YZ A3. Tranzitivitási szabály Ha XY és YZ ÿ XZ Def.: Levezethetÿség F-bÿl az UV levezethetÿ, ha az UV függés megkapható F-bÿl az A1-A3 alkalmazásával. Jele: F | UV Tétel: Igazság-tétel F |  XY esetén F |= XY is teljesül. Biz.: ha r-ben igaz A1-A3 "baloldala", akkor a "jobboldala" is igaz lesz A1: X Y r: ( ( )) t1 sor ( )) ( t2 sor Nagy X halmazon megegyeznek ÿ kis Y-on is! A2: X Z Y ( )( )( ) t1 sor ) t2 sor ( )( )( Ha az X és Z halmazai megegyeznek ÿ az Y-ok is! r: A3: X r: Z Y ( )( )( ) t1 sor )( ) t2 sor ( )( Ha az X-ek megegyeznek ÿ az 71 Y-ok is ÿ a Z-k is! 19. tétel Lezárások, fedések, vetített függések Ezzel állításunkat igazoltuk. Def.: Szuperkulcs,

kulcs Az X⊆R attribútum-halmaz szuperkulcs az (R,F)-re nézve, ha F |= XR. Az X⊆R attribútum-halmaz kulcs az (R,F)-re nézve, ha szuperkulcs, de egyetlen valódi része sem szuperkulcs. (X ebben az értelemben "minimális") Példa: Amerikai irányítószámok Adott az R(Város, Utca, Irsz) reláció és az F={Város,UtcaIrsz, IrszVáros}függéshalmaz. Azt állítjuk, hogy: F |  Irsz, Utca Irsz, Utca,Város=R, azaz (Irsz, Utca) kulcs. Levezetése: Irsz Város F alapján Irsz, Utca Város, Utca A2 alapján (Z=Utca) Irsz, Utca Város, Utca, Irsz A2 alapján (Z=Irsz) [Irsz-t nem kell még egyszer beírni!] Tétel: További fontos szabályok 1. Únió-szabály Adott két, azonos baloldalú függés. Ezek jobboldala összevonható Formálisan:{X Y, X Z}|  X YZ. 2. Felbontási szabály Az elÿbbi szabály komplementere. Formálisan:{X Y}|  X Z, ahol Z⊆ ⊆Y. 3. Áltranzitív szabály Formálisan:{X Y, WY Z}|  WX Z. Biz.: az Armstrong-axiómákkal

történik 1. Únió-szabály Mi alapján? 1. XZ ∈F 2. YXYZ A2 (Y a kiegészítÿ halmaz) 3. XY ∈F 4. XYX A2 (X a kiegészítÿ halmaz) 5. XYZ A3 (4. és 2 tranzitivitása) 2. Felbontási szabály 1. XY 2. YZ 3. XZ Mi alapján? ∈F A1 A3 (1. és 2 tranzitivitása) 3. Áltranzitív szabály 1. WYZ Mi alapján? ∈F 72 19. tétel Lezárások, fedések, vetített függések 2. XY 3. XWYW 4. XWZ ∈F A2 (W a kiegészítÿ halmaz) A3 (3. és 1 tranzitivitása) 18. Lezárások, fedések, vetített függések 1. A funkcionális függés elméleti háttere (18 tétel folytatása) Def.: Függéshalmaz lezárása Adott az F függéshalmaz. Ennek lezárása F+, amire igaz, hogy: F+:={X Y; F |  X Y}, azaz F+ az F összes szintaktikus következménye. Ha modellünk része F, akkor F+ is az; ez utóbbi ad teljes képet a függések rendszerérÿl. Ugyanekkor F+ mérete túlságosan nagy, és ezért a gyakorlati alkalmazásokban nemigen alkalmazható. Példa: Adott az

R(A1,.,An,B1,,Bn) reláció és az F={AiBj} függéshalmaz, ahol i,j=1,.,n Azaz n2 db. függésünk van, és F+ kb 22n elembÿl áll, ami nagyon sok és nehezen számolható. F+ tartalmazza az összes olyan XY függést, ahol: • 0≠X⊆{A1,.,An} • 0≠Y⊆{B1,.,Bn} Szerencse, hogy van egy hatékonyan számítható függés-fogalom, ami képesség tekintetében nem marad el a függéshalmaz lezárásától. Ez pedig az: Def.: Attribútumhalmaz lezárása Adott az X⊆R attribútumhalmaz. Ennek lezárása X+(F), amire igaz, hogy: X+(F):={A⊆ ⊆R; F |  X A}; ami szoros összefüggésben áll a levezethetÿséggel. Fontos különbség az elÿzÿ fogalomhoz (függéshalmaz lezárása) képest, hogy míg F+ függésekbÿl, addig X+(F) attribútumokból áll. Állítás*: F | XY ⇔ Y⊆X+(F) Biz.: ÿ irány Tfh. F | XY és A∈Y Be kell látni, hogy: F | XA. √ Ez viszont a felbontási szabály miatt mindig igaz. ⇐ irány Be kell látni, hogy ha Y⊆X+(F), akkor F

| XY. Legyen Y=A1,.,Ak attribútumok együttese 73 19. tétel Lezárások, fedések, vetített függések Felt.: F | XAi, ahol i=1,,k Alkalmazzuk többször az únió-szabályt! XA1 XA2 } XA1 A2 XA1 A2 A3 XA3 . Végül: XA1,A2,.,Ak √ } Tétel: Teljességi tétel Adott az (R,F) pár, és fel szokás tételezni azt, hogy az attribútumok legalább kétérték ek. F |= XY esetén F |  XY is teljesül. (Azaz: a logikai következményrÿl meg lehet gyÿzÿdni.) Biz.: legyenek az attribútumok a {0,1} elemei A bizonyítás alapötlete, hogy (R,F)-hez "modellt" készítünk. r egy kétsoros reláció: X+(F) X biztosan eleme X+(F)-nek (lehet, hogy nem valódi). X r elsÿ sora csupa 1-es 11 . 1 11 . 1 második sora csak X+(F)-ben 1-es, 11 . 1 00 . 0 másutt csupa 0. Nem lényeges az attribútumok alaphalmaza, csak az. hogy az oszlopokban azonos vagy különbözÿ értékek szerepelnek-e. 1. állítás: r-ben teljesülnek F függései, azaz ha VW∈F, akkor VW

teljesül F-en. (Ez jelenti azt, hogy modellt készítettünk (R,F)-hez.) Biz.: Legyen VW∈F Esetszétválasztás: • ha V¬⊆X+(F), akkor az állítás igaz, hiszen nincs r-nek két sora, ami V-n egyezne. √ • ha V⊆X+(F), akkor az Állítás* ÿ iránya miatt: 1. F |  XV 2. VW ∈F miatt 3. F | A3 miatt (1., 2 tranzitivitása)  XW De az Állítás* ⇐ iránya miatt ez egyenérték azzal, hogy W⊆X+(F). √ Tehát két sor megegyezik W-n is, azaz r-ben VW tényleg fennáll. Ezután nézzük a Teljességi tétel érdemi bizonyítását: 2. állítás: F |  XY 74 19. tétel Lezárások, fedések, vetített függések Biz.: Feltétel szerint F|=XY, azaz az XY függés igaz mindenütt, ahol F érvényes. Az 1. állítás szerint r-ben igaz az XY függés X-en két sor egyenlÿ ÿ a két sor Y-on is egyenlÿ, azaz Y⊆ X+(F), abból "nem lóghat ki". Az Állítás* ⇐ iránya szerint pedig F |  XY, ezzel állításunkat igazoltuk. √

Következmény: |= és | egyenérték . Ezért X+(F):={A⊆ ⊆R; F |= X A} is írható, amit ki is használnak automatikus sémaelemzÿkben. Def.: Algoritmus X+(F) számítására Bemenete: az (R,F) ár és az X⊆R attribútumhalmaz. Kimenete: az X+(F) attribútumhalmaz. A módszer iteratív: X0:=X Xi+1:= Xi ∪ {azon A attribútumok, melyekhez van olyan UV∈F függés, hogy U∈ Xi és A∈V} Az iteratív lépések nem csökkentik az X halmazok méretét, ezért: X0⊆X1⊆X2⊆ . ⊆ Xutolsó Xutolsó-t akkor kapjuk meg, amikor X már nem nÿ tovább. Állítás: Xutolsó = X+(F) Biz.: (vázlat) 1. Xutolsó⊆X+(F) Ezt teljes indukcióval látjuk be, Tfh. Xi⊆X+(F) Ez a reflexív szabály miatt igaz. √ • i=0: X0⊆X+(F) • általános esetben be kell látni, hogy F |  XA, ahol A∈Xi. i Az Állítás* szerint: F |  XX van olyan UV∈F, hogy U⊆Xi és A∈V. 1. XXi 2. XiU 3. UV 4. VA 5. UA 6. XU 7. XA igaz A1 miatt ∈F A1 miatt A3 miatt (3. és 4

reflexivitása) A3 miatt (1. és 2 reflexivitása) A3 miatt (6. és 5 reflexivitása) √ 75 19. tétel Lezárások, fedések, vetített függések 2. Xutolsó⊇X+(F) Ennek belátásához - a Teljességi tétel bizonyításához hasonlóan - definiálunk egy r relációt: Xutolsó 11 11 X . . 1 1 11 00 . . 1 0 r elsÿ sora csupa 1-es második sora csak X+(F)-ben 1-es, másutt csupa 0. a.) r-ben F igaz UV∈F • ha U¬⊆Xutolsó, akkor az állítás igaz. √ • ha U⊆Xutolsó, akkor V⊆Xutolsó, mert ellenkezÿ esetben V elemeivel növelhetÿ Xutolsó lenne. √ b.) legyen A∈X+(F) tetszÿleges Be kell látni, hogy A∈Xutolsó. A teljességet és X+(F) definícióját felhasználva: F|=XA. Tehát • r-ben is igaz az XA függés • X-en két sor egyezik ÿ A-n is egyezik ÿ A∈Xutolsó. √ Megj.: a fent vázolt algoritmus implementálható a bemenet, azaz (R,F) hosszában lineáris lépésszámmal. Példa: adott az R(A,B,C,D,E) ötoszlopos reláció és az

F={ABC, BD, CDE} függéshalmaz. Kérdés: AB+(F), azaz most X=AB. Megoldás: Xö=X=AB X1=AB∪CD=ABCD X2=ABCD∪E=ABCDE=R, azaz definíció szerint R szuperkulcsa és kulcs is (R,F). Ez utóbbi (kulcs) tulajdonsághoz meg kell mutatni: valódi része nem szuperkulcs. • Ki kell számolnunk A+(F)-et, ez: A+(F)=A≠R • és B+(F)-et is, ez pedig: B+(F)=BD≠R. Tehát a minimalitási tulajdonság valóban teljesül. Példánk tapasztalatai általánosíthatók: Tétel: Szuperkulcsra és kulcsra • X szuperkulcs ⇔ X+(F)=R. 76 19. tétel Lezárások, fedések, vetített függések • X kulcs ⇔ X+(F)=R, de (XA)+(F)≠R az X egyetlen A elemére sem (ez a minimalizálási feltétel). Az eddig elmondottak alapján a szuperkulcs- és kulcs-tulajdonság hatékonyan tesztelhetÿ a vázolt algoritmussal.7 2. Részletesen a függÿleges felbontásokról Def.: Függÿleges felbontás8 Adott az (R,F) séma. k Ennek egy függÿleges felbontása: ρ = (R1,.,Rk), ahol az Ri ∈ R

vetületekre: ∪Ri = R i=1 Például: R = TERMEL(Név,Cím,Termék,Ár) R1= (Név,Cím) R2= (Név,Termék,Ár) ρ = (R1,R2) egy lehetséges függÿleges felbontás, ahol k=2 A továbbiakban azt az ötletet fogjuk alkalmazni az anomáliák elkerülése érdekében, hogy egy, az (R,F) sémához illeszkedÿ r reláció esetében r helyett az ri:=Π ΠRi(r) relációkat, azaz r függÿleges darabjait, vetületeit fogjuk tárolni. Jelölés: ri:=ΠRi(r) az r reláció függÿleges vetülete r mρ(r):= ri, ahol a sorrend közömbös, mert a természetes illesztés lényegében asszociatív m velet. ~ r2) r3 = r1 ( r2 r3 ) i=1 Pl.: (r1 Példa: (elrettentÿ, azaz rossz felbontást bemutató példa) Adott a következÿ háromoszlopos reláció: r: Név zöldmezÿ zöldmezÿ Termék liszt cukor Ár 70 80 R=(Név,Termék,Ár) ρ=(R1,R2) R1=(Név,Termék) 7 a ZH anyaga idáig tart. Ez a témakör persze még folytatódik :) 8 Jele ρ, azaz ró, ha nem látszana tisztán 77 19.

tétel Lezárások, fedések, vetített függések R2=(Név,Ár) r1:=ΠR1(r) : Név zöldmezÿ zöldmezÿ mρ(r):= r1 Termék liszt cukor r2:=ΠR2(r) : Név zöldmezÿ zöldmezÿ r2 Név zöldmezÿ zöldmezÿ zöldmezÿ zöldmezÿ de mρ(r) ⊃≠ r Termék liszt liszt cukor cukor Ár 70 80 Ár 70 80 70 80 Def.: H séges (veszteségmentes) felbontás Az (R,F) séma egy ρ felbontása h séges (veszteségmentes), ha minden illeszkedÿ r relációra mρ(r) = r. Állítás: adott R,F,ρ,r az elÿbbiek szerint. 1. r ⊆ mρ(r) 2. ΠRi(mρ(r)) = ΠRi(r) = ri 3. mρ(mρ(r)) = mρ(r) Az állítás fontos következménye, hogy ha mρ(r) ⊃≠ r, akkor katasztrofális helyzet áll elÿ, mivel nem állítható helyre az ri vetületekbÿl az eredeti r reláció. 2 alapján nem tudjuk megmondani, hogy mi volt az eredeti reláció: r vagy mρ(r), mivel ezek vetületei azonosak. Tehát: az r visszanyerhetÿ az ri darabokból ⇔ mρ(r) = r. (Ezt F-tÿl remélhetjük) Az eredeti

reláció visszaállítása vagy természetes illesztéssel történhet, vagy sehogy. Biz.: 1. Legyen t∈r, az r reláció egy sora Ekkor ti = t[Ri] ∈ ri, ahol t[Ri] t-nek az Ri oszlopok alá esÿ része. A ti sorok túlélik az illesztés sz réseit és eredményül t-t adják: t ∈ mρ(r). // 2. Az r ⊆ mρ(r) miatt a tartalmazás igaz a vetületekre is: ri = ΠRi(r) ⊆ ΠRi(mρ) Be kell látni, hogy ti = t[Ri] ∈ ΠRi(mρ(r)). t ∈ mρ(r), ami mρ(r) definícióját használva azt jelenti, hogy: ∃ sj ∈ r sorok úgy, hogy sj[Rj] = t[Rj], ahol j = 1,. Speciálisan j = i, és ekkor si[Ri] = t[Ri] = ti, és mert si ∈ r, ezért ti ∈ ri. / 3. mρ(mρ(r)) = k i=1 ΠRi(mρ(r)) = k 2. ri = mρ(r). / i=1 78 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Tétel: Hogyan kapunk h séges felbontást? Legyen (R,F) egy relációs séma, és ρ = (R1,R2) ennek egy felbontása. ρ pontosan akkor h séges, ha • vagy F |= R1 ∩ R2 R1 R2 ∈ F+,

• vagy F |= R1 ∩ R2 R2 R1 ∈ F+. Biz.: ⇐ Tfh. pl F |= R1 ∩ R2 R1 R2 igaz r2 ÿ t ∈ r t ∈ r1 R1 R2 ^ ^ =r s1 s2 ezek az r-beli sorok összeilleszthetÿk (besatírozott részük azonos) R1 ∩ R2 R1 R2 s1 és s2 összeillik, és s1 R1-en lévÿ része azonos t R1-en lévÿ részével. Azaz: s1[R1] = t[R1] és s2[R2] = t[R2]. Mindebbÿl: t = s2, vagyis t ∈ r. / Megj.: a 8 oldali elrettentÿ példában az a baj, hogy a Név nem határoz meg semmit ÿ (vázlat) H a két függés egyike sem áll fenn, akkor a felbontás nem mindig h séges. R1 R2 ^ ^ 11.11 11 00.00 11 . . 11 11 =r 0 1 . 0 . 1 R1 ∩v R2 (R1 ∩ R2)+(F) A csupa 1-es sor ∉ r, de ∈ mρ(r), tehát mρ(r) ⊃≠ r. Ezen felül bizonyítani kell még azt is, hogy r megÿrzi F-et. (Ezt a teljességi tételhez hasonlóan kell belátni.) Példa: R = TERMELÿ(Név,Cím,Termék,Ár) F = (Név Cím, NévTermékÁr) 79 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése,

naplózás 1. egy jó felbontás a következÿ: ρ = (R1=NévCím, R2=NévTermékÁr) Ekkor R1 ∩ R2 = Név és R1 R2 = Cím. Ebben az esetben F |= R1 ∩ R2 R1 R2, sÿt a levezethetÿségen felül az ∈ F is teljesül. És mivel a h séges felbontás tételének feltétele teljesül, ezért ρ egy h séges felbontása R-nek. 2. egy rossz felbontás a következÿ: ρ = (R1=NévTermék, R2=NévCímÁr) Ekkor R1 ∩ R2 = Név. Automatikus tesztelés alá vetve: Név+(F) ⊇ R1 R2 vagy ? ? Név+(F) ⊇ R2 R1 ? Alkalmazzuk a lezárási algoritmust Név+(F)-re! 0. lépés: Név 1. lépés: NévCím ¬⊇ R1 R2 = Termék és NévCím ¬⊇ R2 R1 = CímÁr. Vagyis a felbontás nem h séges Def.: Vetített függések Legyen ρ = (R1,.,Rk) az (R,F) séma egy függÿleges felbontása Πρ(F) = {X Y∈F+, ahol van olyan i, hogy XY ⊆ Ri} egy vetített függés. Def.: Az (R,F) séma ρ felbontása megÿrzi F-et, ha Πρ(F)+ ⊆ (F)+ Megj.: Mivel Πρ(F) ⊆ F+, ezért Πρ(F)+ ⊆ F+

mindig igaz Def.: Függéshalmaz fedése A G függéshalmaz az F függéshalmaz fedése, ha ugyanazt axiomatizálják, azaz G+=F+. (Ez egy szimmetrikus viszony.) Def.: Függéshalmaz minimális fedése A G függéshalmaz az F függéshalmaz minimális fedése, ha 1. G+=F+, azaz G egy fedés; 2. a G-beli függések jobboldalai egyelem ek (a felbontási és únió tételek miatt az XY függést az XAi-kkel helyettesíthetjük, ∪Ai =Y); 3. G-bÿl nem hagyható el függés, azaz ha XA∈G, akkor XA ∉ (G{XA})+, vagyis a többi függésbÿl XA nem állítható elÿ. 4. a G-beli függések baloldalai minimálisak, nem csökkenthet k: ha XA∈G és Y⊂X valódi részhalmaz, akkor YA ∉G minden Y-ra. 80 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Tétel: Tetszÿleges F-hez van G minimális fedés. Sÿt, ilyen G minimális fedés hatékonyan kapható. Biz.: konstruktív F-bÿl indulunk ki, majd fokozatosan biztosítjuk a definíció pontjait.

Kezdetben: G=F. 1. A módosított G egyenérték a korábbival 2. XY ∈G, Y=A1,A2,,Ak helyett XA1, ahol i =1,.,k (a felbontási és únió szabály értelmében) 3. Veszünk egy XA ∈G függést Ha XA ∈ (G{XA})+, akkor XA-t eldobjuk, ellenkezÿ esetben megtartjuk. Praktikusan ez a teszt a következÿképp oldható meg: • A ∈X+(G{XA}) esetén lehet a függést eldobni, és • A ∉X+(G{XA}) esetén pedig meg kell tartani. Elég tehát a lezárás helyett az attribútum-halmaz lezárására tesztelni. 4. Ha XA ∈G és Y⊂≠X, akkor YA∉G Megj.: ha YA∈G és Y⊂X, akkor XA ∈G teljesül a reflexivitás miatt Z: átmenet az X és az Y között Y Z X Nézzük meg azon Y ⊆ X halmazokat, melyekre |XY|=1. Teszt: A ∈Y+(G) teljesül-e? • igen: ekkor XA helyett Y A-val folytatjuk az algoritmust; • nem: ekkor vesszük a következÿ Y-t. Ha X esetén minden Y-ra "nem" a válasz a fenti tesztkérdésre, akkor marad az XA függés. Példa: G minimális fedés

keresésére az elÿbbi algoritmussal Adott az R(A,B,C) reláció és az F = {ABC, AB, BA} függéshalmaz. Keressük F minimális fedését, G-t. Az algoritmus lépései: 2. rendben van 3. szintén rendben van: nincs elhagyható függés Pl. ABC nem elhagyható, mert AB+({AB,BA}) = AB és C∉AB 81 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 4. AB, BA ./ ABC nem minimális baloldalú A+(F) = ABC, és C ∈ ABC, ezért ABC helyett vehetjük az AC-t. Tehát G={AB, BA, AC} Megj.: mivel A és B szerepe szimmetrikus, ezért G = {AB, BA, BC}is minimális fedés. Ennek következménye az, hogy a minimális fedés nem egyértelm . 19. Normálformák (3NF, BCNF), normalizálás 1. Boyce-Codd normálforma (BCNF) Def.: BCNF Az (R,F) relációs séma BCNF, ha minden nem triviális XA∈F+ függés esetén X szuperkulcs, ahol A egy attribútum, A∉X (vagyis A egy, az X attribútum-halmazon kívüli attribútum). Megjegyzések: • a BCNF-ben nincsenek a

szuperkulcson kívülrÿl induló függések; a normálforma a kötelezÿen meglévÿ minimális mennyiség függéssel rendelkezik; • BCNF-nek számít a jó, értelmes, redundancia-mentes reláció; • a legutóbbi példában bemutatott NévCím függés felrúgja a BCNF feltételét, és pont ez okoz anomáliákat. A TERMELÿ reláció tehát nem BCNF, mert Név nem szuperkulcs; • egy kétoszlopos reláció mindig BCNF. Ha ez a két oszlop A és B, akkor két nem triviális függés lehetséges: 1. AB ÿ A szuperkulcs 2. BA ÿ B szuperkulcs Így a reláció mindenképpen BCNF: F tétel.: A BCNF és a h séges felbontás kapcsolatáról Tetszÿleges (R,F) sémának ∃ρ h séges felbontása BCNF relációkra. Megj.: tfh (R1,,Rk) egy h séges felbontása R-nek és (S1,.,Sm) egy h séges felbontása R1-nek Ekkor (S1,.,Sm,R2,,Rk) egy h séges felbontása R-nek Ennek oka az, hogy a természetes illesztés m velete a sorrendre kvázi érzéketlen. A természetes illesztést

elÿször az Si-kre (R1), majd az Ri-kre kell elvégezni. 82 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Biz.: konstruktív 1. Ha R BCNF, akkor az állítás egybÿl igaz ./ 2. Ha R nem BCNF, akkor van nem triviális XA függés, ahol X nem szuperkulcs ρ = (R1=XA, R2=RA) egy felbontás; R helyett ezzel megyünk tovább. 3. Ha R1,R2 nem BCNF, akkor az elÿbbi módon folytassuk a felbontásukat Ezt az eljárást rekurzívan alkalmazva h séges felbontáshoz jutunk. A módszer sikerre vezet, mert: a.) (XA,RA) valódi felbontás, mivel • RA nem egyezik meg az R relációval, mert annál kisebb és • XA sem egyezik meg az R relációval, különben X szuperkulcs lenne. Tehát a reláció csökken ÿ elÿbb-utóbb megállhatunk a kétoszlopos relációknál. b.) a felbontás h séges A fÿtétel megjegyzése miatt elég azt belátni, hogy az (R1=XA, R2=RA) h séges felbontása R-nek. A h ségesség tételének alkalmazásával: • R1 ∩ R2 = X és

• R1 R2 = A. A nem triviális ("bajkeverÿ") X A függés segít (ahol X nem szuperkulcs), mert + XA ∈ F , és az F |= R1 ∩ R2 R1 R2 által teljesül a h ségesség tételének feltétele, azaz a felbontás valóban h séges. .// Példák.: BCNF-re 1. Vegyük kedvenc TERMELÿ(Név,Cím,Termék,Ár) relációnkat! F = (NévTermékCímÁr,NévCím) Ennek a Név Cím függés egy rossz függése: ez sérti a BCNF tulajdonságot, mert a Név nem kulcs, és a függés nem triviális. A fent vázolt algoritmus szerint adódik egy BCNF alakú kétoszlopos ρ: ρ = (NévCím, NévTermékÁr), és ennek a felbontásnak mindkét tagja BCNF, tehát már egyetlen lépésben célt értünk. A felbontás h ségét az elÿbbi tétel garantálja. 2. Egyetemi oktatás példája R(Tanár,Tárgy,Terem,Diák,Jegy,Idÿ) F={TárgyTanár, IdÿTanárTerem, IdÿDiákTerem, IdÿTeremTárgy, TárgyDiákJegy} reláció egy viszonylag realisztikus függés-halmaz A lezárási algoritmussal

egyetlen kulcs adódik: DiákId 83 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Bontsuk fel a nem BCNF formájú R-t ezen kulcs szerint! (A BCNF tulajdonság megsértése olyan függéseknél látható, ahol nincs kulcs a baloldalon.) X A függés szereposztása: Az TanárDiák Jegy (folyt.köv) ez nem BCNF, fel kell bontani! R TanárDiákJegy kulcs: TanárDiák TanárTárgyTeremDiákIdÿ ez nem BCNF, fel kell bontani! a TárgyTanár rossz függés ez már BCNF, nem bomlik tovább TanárTárgy kulcs: Tárgy TárgyTeremDiákIdÿ ez már BCNF, nem bomlik tovább TárgyIdÿTerem nem eleme F-nek, de F+-nak igen; rossz! TárgyTeremIdÿ kulcs: TárgyIdÿ, TeremIdÿ ez már BCNF, nem bomlik tovább TárgyDiákIdÿ kulcs: DiákIdÿ ez már BCNF, nem bomlik tovább Megjegyzések: • A felbontás eredményei a levelekben található komponensek. • A felbontás h séges, mert mindvégig a két részre bontás technikáját alkalmaztuk. • A

felbontásban segít, ha mindig a megfelelÿ rossz függéseket választjuk. Állítás: Nem BCNF formájú relációkra Tfh. adott egy (R,F) séma, ami nem BCNF Ekkor van olyan X ∈Y attribútum, hogy az X A ∈ F+ függés megsérti a Y ∈ F függés és A∈ BCNF-et. Azaz: ha egy reláció nem BCNF, akkor ezt könnyen is be lehet látni. Biz.:(R,F) nem BCNF ÿ van olyan UB ∈ F+ nem triviális függés, ahol U nem szuperkulcs. Ezért B ∈ U+(F) Ez a lezárási algoritmus természetébÿl adódik: van olyan XY ∈ F függés úgy, hogy X⊆U és Y¬⊆U. 84 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Legyen A egy tetszÿleges eleme YU-nak, vagyis A∈YU. Ekkor megállapíthatjuk, hogy: • egyrészt az XA nem triviális függés (A∉X, mert A∉U), • másrészt XA ∈ F+ (a felbontási szabály szerint). X nem szuperkulcs, nem határoz meg minden más attribútumot. Ez abból látszik, hogy U nem szuperkulcs, és mivel X⊆U, így X sem

lehet az. ./ Következmény: Ha F-ben minden függés baloldala szuperkulcs, akkor (R,F) BCNF alakú. 2. Harmadik normálforma (3NF) Példa: Bevezetés a 3NF-hez Az amerikai irányítószámok az F függés-halmaznak megfelelÿen épülnek fel: R(Város,Utca,Irányítószám) F ={VárosUtcaIrányítószám, IrányítószámVáros} Ez az (R,F) séma nem BCNF, pl. az IrányítószámVáros függés sérti a BCNF-et Egy BCNF felbontás lehet a következÿ: ρ = (IrányítószámVáros, IrányítószámUtca). Gond: hogyan ellenÿrizzük a VárosUtcaIrányítószám függést új sor beszúrásakor? Ez a függés "elvész" a daraboláskor, így azt csak a természetes illesztéssel való helyreállítás után ellenÿrizhetjük. A természetes illesztés viszont egy roppant költséges m velet. Def.: Vetített függések Legyen ρ = (R1,.,Rk) az (R,F) séma egy függÿleges felbontása Πρ(F) = {X Y∈F+, ahol van olyan i, hogy XY ⊆ Ri} egy vetített függés. Def.: Az (R,F)

séma ρ felbontása megÿrzi F-et, ha Πρ(F)+ ⊆ (F)+ Megj.: Mivel Πρ(F) ⊆ F+, ezért Πρ(F)+ ⊆ F+ mindig igaz Megjegyzés: az bevezetÿ példához Az R(Város,Utca,Irányítószám) relációnak F-et megÿrzÿ módón nincs valódi felbontása. (A vetítés halmaza csak az IrányítószámVáros függés következményeibÿl áll) Ez arra példa, hogy egy (R,F)-et mikor nem lehet h ségesen, az F-et megÿrzÿ módon BCNF-ekre bontani. És ha már ez nem lehetséges, akkor szükség lenne egy BCNF-nél valamivel gyengébb tulajdonságokkal rendelkezÿ normálformára, ami F-et megÿrizné. Ezért találták ki a 3NF-et. 85 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Def.: Prím attribútum Az (R,F) séma egy A attribútuma prím, ha a sémának van olyan X kulcsa, melynek A eleme, azaz A∈ ∈X. Def.: 3NF Az (R,F) séma harmadik normálformájú - röviden 3NF -, ha minden XA ∈ F+ nem triviális függésnél X vagy szuperkulcs vagy A

prím attribútum. Észrevételek: 1. Ha (R,F) BCNF, akkor egyben 3NF is (nem érdekes, hogy A milyen attribútum) 2. Van 3NF alakú (R,F) séma, ami nem BCNF (Pl a bevezetÿ példa, ahol a Város prím attribútum.) Tehát a két NF viszonya: BCNF A 3NF a tágabb, engedékenyebb NF. 3NF Def.: X+(Πρ(F)) számításának algoritmusa • Z:=X • amíg Z változik, DO FOR i=1 TO k DO k: a felbontás elemeinek száma, ρ = (R1,.,Rk) + Z:=Z∪ ∩Ri). ∪((Z∩ ∩Ri) (F)∩ Az algoritmus helyességét nem bizonyítjuk, de az nyilvánvalóan igaz, hogy: • Zutolsó ⊆ Πρ(F)+ (ez triviális), illetve • Zutolsó ⊇ Πρ(F)+ (ezt nem bizonyítjuk). Példa: az elÿbbi algoritmusra R(A,B,C,D) egy négyoszlopos reláció. ρ = (AB,BC,CD) ennek egy felbontása. F = (AB, BC, CD, DA) azaz minden mindent meghatároz, tehát ez lényegében egy egyoszlopos mesterséges reláció nem gyakorlati példa. Nyilván DA ∈ F+, mert DA ∈ F is teljesül. Ellenÿrizhetÿ a vetületeken is,

mint DC, CB, BA következménye. Kérdés: A∈D+(Πρ(F)) teljesül-e? Ki tud-e jönni A a függések révén? Az algoritmus: Z0 = D 86 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Z1 = D ∪ (Z ∩ CD)+(F) ∩ CD = CD Z2 = CD ∪ (CD ∩ BC)+(F) ∩ BC = BCD Z3 = ABCD Azaz a válasz a kérdésre: igen, A∈D+(Πρ(F))! Def.: Függéshalmaz fedése A G függéshalmaz az F függéshalmaz fedése, ha ugyanazt axiomatizálják, azaz G+=F+. (Ez egy szimmetrikus viszony.) Def.: Függéshalmaz minimális fedése A G függéshalmaz az F függéshalmaz minimális fedése, ha 1. G+=F+, azaz G egy fedés; 2. a G-beli függések jobboldalai egyelem ek (a felbontási és únió tételek miatt az XY függést az XAi-kkel helyettesíthetjük, ∪Ai =Y); 3. G-bÿl nem hagyható el függés, azaz ha XA∈G, akkor XA ∉ (G{XA})+, vagyis a többi függésbÿl XA nem állítható elÿ. 4. a G-beli függések baloldalai minimálisak, nem csökkenthet k: ha XA∈G és

Y⊂X valódi részhalmaz, akkor YA ∉G minden Y-ra. Tétel: Tetszÿleges F-hez van G minimális fedés. Sÿt, ilyen G minimális fedés hatékonyan kapható. Biz.: konstruktív F-bÿl indulunk ki, majd fokozatosan biztosítjuk a definíció pontjait. Kezdetben: G=F. 1. A módosított G egyenérték a korábbival 2. XY ∈G, Y=A1,A2,,Ak helyett XA1, ahol i =1,.,k (a felbontási és únió szabály értelmében) 3. Veszünk egy XA ∈G függést Ha XA ∈ (G{XA})+, akkor XA-t eldobjuk, ellenkezÿ esetben megtartjuk. Praktikusan ez a teszt a következÿképp oldható meg: • A ∈X+(G{XA}) esetén lehet a függést eldobni, és • A ∉X+(G{XA}) esetén pedig meg kell tartani. Elég tehát a lezárás helyett az attribútum-halmaz lezárására tesztelni. 4. Ha XA ∈G és Y⊂≠X, akkor YA∉G Megj.: ha YA∈G és Y⊂X, akkor XA ∈G teljesül a reflexivitás miatt Z: átmenet az X és az Y között 87 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás

Y Z X Nézzük meg azon Y ⊆ X halmazokat, melyekre |XY|=1. Teszt: A ∈Y+(G) teljesül-e? • igen: ekkor XA helyett Y A-val folytatjuk az algoritmust; • nem: ekkor vesszük a következÿ Y-t. Ha X esetén minden Y-ra "nem" a válasz a fenti tesztkérdésre, akkor marad az XA függés. Példa: G minimális fedés keresésére az elÿbbi algoritmussal Adott az R(A,B,C) reláció és az F = {ABC, AB, BA} függéshalmaz. Keressük F minimális fedését, G-t. Az algoritmus lépései: 2. rendben van 3. szintén rendben van: nincs elhagyható függés Pl. ABC nem elhagyható, mert AB+({AB,BA}) = AB és C∉AB 4. AB, BA ./ ABC nem minimális baloldalú A+(F) = ABC, és C ∈ ABC, ezért ABC helyett vehetjük az AC-t. Tehát G={AB, BA, AC} Megj.: mivel A és B szerepe szimmetrikus, ezért G = {AB, BA, BC}is minimális fedés. Ennek következménye az, hogy a minimális fedés nem egyértelm . F tétel: A 3NF és a h séges felbontás kapcsolatáról Egy tetszÿleges (R,F)

sémának van h séges, F-et megÿrzÿ felbontása 3NF relációkra. Biz.: konstruktív Legyen G az F minimális fedése. Tfh. G = {X1A1,,XkAk}alakú Ekkor legyen ρ = (X1A1,.,XkAk,X) egy k+1 komponens felbontás, ahol X az (R,F) séma egy kulcsa. 1. ρ megÿrzi G-t (és így F-et is) Be kell látni, hogy a vetület-függések összessége kiadja az egészet: Πρ(G)+=G+. Πρ(G)⊇G, pl. XiAi ∈G látható az Ri = XiAi darabban 88 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 2. A kapott függÿleges darabok 3NF-ek X kulcs ÿ nincs benne semmilyen függés ./ Tfh. XiAi nem 3NF, és ennek YB ∈G+ egy rossz függése a.) B=Ai Ekkor Y valódi része Xi-nek (ellenkezÿ esetben nem lenne rossz függés), mert Xi szuperkulcsa Ai-nek. YAi ∈G+ ellentmondana G minimális fedés voltának (a 4. feltétel miatt) b.) B≠Ai, azaz B ∈Xi B nem lehet prím attribútum, mert akkor az YB nem lenne rossz függés. • Tehát Xi nem kulcsa XiAi -nek, mert akkor B

prím attribútum volna; • de Xi szuperkulcs, vagyis van benne egy valódi rész (pl. U), ami kulcsa XiAi nek Ezért UAi ∈G+, ami ismét ellentmond G minimális fedésének, azaz a definíció 4. pontjának 3. ρ h séges felbontás Be kell látni, hogy s = mρ(r) = r minden r-re. Ha ez nem igaz, akkor van olyan r, hogy s = mρ(r) ⊃≠ r. Πx(s) = Πx(r) s ⊃ r csak úgy lehet, ha van s-nek egy t1 és t2 sora úgy, hogy t1[X] = t2[X] és t1≠ t2. Legyen H = {A∈R; t1[X] = t2[X]}attribútumhalmaz. H ⊇ X, de H≠R, mert t1≠ t2. A H ⊇ X tulajdonságból eredÿen H szuperkulcsa (R,F)-nek és (R,G)-nek. HR∈G+ (és H+(G) = R). Ezért van olyan UB ∈G függés, amire U ⊆ H, B ∉H. UB = XiAi alkalmas i-re. t1, t2 ∈ mρ(r), és ezért van olyan t1, t2 ∈ r, hogy: t1[UB] = t1[UB] és t2[UB] = t2[UB]. Elÿször: t1[U] = t2[U] t1[U] = t1[U] = t2[U] = t2[U]. def. U⊆H t1, t2 ∈ r és egyeznek U-n, s ekkor UB∈G miatt B-n is egyeznek. Ez azonban lehetetlen, mert: t2[B] =

t2[B] = t1[B] = t1[B]. És ez ellentmond B ∉ H-nak def. elÿzÿ def. Ezzel állításunkat igazoltuk. 89 √ 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 3. Alacsonyabb szint - gyakorlati szempontból nem lényeges - normálformák Def.: 1NF Az attribútum-értékek egyszer ek (elemiek, nem oszthatóak). Atrribútum-érték nem lehet halmaz, így egy másik reláció sora sem. Megj.: Újabban - az elmúlt 6-7 évben - megjelentek 1NF-et tagadó intelligens alkalmazások, melyek nem az adatok tömegével, hanem a struktúrájával manipulálnak. Példa: 1NF-re Épület Alap A1 Padlás P1 Padlás Cserép Alpesi . Forma Dór Új típusú m veletek: • ZOOM, UNNEST: P1 "kibontása" • NEST: az elÿbbiek fordítottja Megjegyzés: a (-z eddig tárgyalt) normálformák egymásba ágyazódása így fest: 3NF 1NF 20. Többérték függések, 4NF Példa: Bevezetÿ a többérték függésekhez Adott a következÿ háromoszlopos

reláció:9 Név Kiss Kiss Kiss Kiss 9 Projekt A B A B Munkatárs Lalagé Lalagé Aniela Aniela ezeket az . érdekes neveket nem én találtam ki! (BJ) 90 . 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Nagy . B . Aniela . Ez a reláció BCNF alakú, mégis tartalmaz redundáns elemeket és anomáliák forrását hasonlóakat, mint amilyenek a hagyományos függéseknél tapasztalhatók. Természetes felfogás szerint a fenti feladatot két táblával oldanánk meg: Név Kiss Kiss Nagy Projekt A B B Név Kiss Kiss Nagy Def.: Többérték függés Adott X és Y, két attribútum-halmaz. X többérték en meghatározza Y-t (r-ben), ha t1,t2 ∈ r és t1[X] = t2[X] esetén van t3,t4 ∈ r úgy, hogy: • t1[XY] = t3[XY], t2[XY] = t4[XY] és • t1[RXY] = t4[RXY], t2[RXY] = t3[RXY]. Jelölés: X Ábrázolva: X > Y Y RXY t1 t2 t3 t4 A bevezetÿ példában ilyen többérték függés: • Név > Projekt • Név > Munkatárs • Név

> Projekt,Munkatárs Vagy egy korábbi példából: Tárgy > TeremIdÿ. Def.: Triviális függések • Ha Y⊆X, akkor X > Y. t1, t2-höz t3 = t1 és t4= t2 jó. • Ha X∪Y=R, akkor X > Y. t1, t2-höz t3 = t1 és t4= t2 szintén jó. (RXY = 0) • Ha XY=R, akkor X > Y. 91 Munkatárs Aniela Lalagé Aniela 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Ez egy fontos speciális eset, ami azt mutatja meg, hogy ez a többérték függés - amit sorgenerálónak is nevezhetünk - tágabb, mint az egyenl ség-generálónak is mondható funkcionális függés. Megállapítások a többérték függésekkel kapcsolatban • Az (R,F) sémában F hagyományos és többérték függések halmaza. • Definiálható a |= (logikai következmény) és a | (szintaktikai következmény) fogalma. Ezekre a már megismert 8 alapszabály - A1, A2, A3 és 5 másik - vonatkozik Pl.: {XY}|= X > Y vagy {XY}| X > Y {X > Y}| X > (RXY) t1,

t2-höz t4t3 lesz jó: X Y RXY t1 t2 t3 t4 • Igaz a teljességi tétel (belátni kicsit körülményes, de nem nehéz): |= ~ |. • Itt is értelmezhetÿ F+, de sajnos X+(F) nem. • Itt is lehet beszélni felbontásról, h ségességrÿl általános (R,F)-re. • Nehezebben algoritmizálható, mint a BCNF. (Kérdés, hogy megéri-e a fáradtságot?) Def.: Negyedik normálforma, 4NF Az (R,F) séma 4NF, ha tetszÿleges nem triviális X > Y ∈ F+ esetén X szuperkulcs (a régi értelemben). Következmények: 1. Ha (R,F) 4NF, akkor BCNF is 2. Kétoszlopos reláció biztosan 4NF (azaz nincs benne nem triviális > Tétel: Többérték függéseket tartalmazó séma h séges felbontása Legyen ρ =(R1,R2) az (R,F) séma egy felbontása. R2R1 ∈F+. ρ pontosan akkor h séges, ha R1∩R2 > ). Megj.: Mivel R1∩R2 > R1R2 ∈F+ is igaz, ezért nem kell a "vagy" ág A bizonyítás hasonló a már ismertetetthez, de most mellÿzzük. F tétel: A 4NF és a h

séges felbontás kapcsolatáról Tetszÿleges (R,F) sémának van h séges felbontása 4NF darabokra. Biz.: algoritmust adunk konstruktív bizonyításként Ahogy a BCNF-nél, itt is elég a nem 4NF relációknak valódi felbontást találni. 92 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 1. Ha (R,F) 4NF, akkor kész vagyunk √ + 2. Ha nem, akkor van X > Y ∈ F rossz függés Legyen R1 = XY és R2 = R(XY). (Megjegyzés: > -ra nincs únió és felbontási szabály! Valamint ha Y=A∈X, akkor R2=XA.) R1 valódi, mert XY≠R. R2 is valódi, mert Y≠⊂X. R1∩R2 = XY∩(R(XY)) R1R2 = RXY X Y R X > RXY -bÿl a komplementálás miatt következik, hogy X > R1∩R2 > R2 R1. Ezzel állításunkat igazoltuk √ Y esetén: Példa: 4NF-re és h séges felbontásra R(Név,Projekt,Munkatárs) F = {Név > Projekt, Név > Munkatárs}. Ez (még) nem 4 NF séma; a Név nem szuperkulcs. A felbontás a Név > Projekt rossz függés

alapján lehetséges: ρ = (R1=NévProjekt, R2=NévMunkatárs), ami már 4NF-eket tartalmaz. A tranzakciókezelés alapfogalmai: zárak, pattok, sorosíthatóság, egyszer tranzakció modell 21. 1. Alapfogalmak A többfelhasználós m ködés során több felhasználó egyidÿben használja az adatbázist. Pl: banki tranzakciók, repülÿgépes helyfoglalás, on-line katalógusok, stb. Def.: Tranzakció Ebben a környezetben alapfogalom a tranzakció (processz, folyamat), ami egy program futását jelenti. A tranzakció atomi, azaz oszthatatlan tevékenységet jelöl Atomi, mert a tranzakciónak: • vagy teljes a hatása az adatokon, • vagy semmilyen hatással nincs rájuk. 93 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Példa: banki m velet, mint tranzakció (A átutal 50 egységet B-nek) A=A-50, számla terhelése B=B+50. jóváírás Ha a két m velet között a rendszer "fejreáll", akkor a könyvelésbe hiba csúszik, mert a

terhelés már megtörtént, de a jóváírás még nem. Az egész folyamatot egy egységként kell tehát kezelni. A legtöbb többfelhasználós rendszer ezért biztosít is ilyen "zárójeleket", hogy a tranzakció-egységek oszthatatlanok legyenek: trbegin = { és } = trend. Def.: Abort Akkor jut szerephez, ha néhány - önmagában helyes - tranzakció (a továbbiakban: T) "összeakad", holtpontra jut. Hogy befejezhessék a munkájukat, egyiküket le kell állítani, abortálni kell. Pl.: T1 és T2 önmagukban helyes tranzakciók, de együtt helytelen m ködést mutatnak Tipikusan ugyanazt az A adatot használják az adatbázisban: idÿ T1: READ A READ A T2: A++ WRITE A WRITE A A++ Baj: A értéke csak 1-el nÿ! Def.: Zárak (lock) Az elÿbbi probléma egy megoldási lehetÿsége a zárak alkalmazása. • A zár adategységhez kötÿdÿ fogalom; az adategységen a zárat "valakinek" el kell helyezni. (Adategység lehet a DB egy sora, egy egész

tábla vagy csupán egy mezÿ is Méretének megválasztása érinti a tranzakciós teljesítményt és az abort-ok számát is.) • A tranzakció lépései között: –a zár képzése a LOCK A, –a zár elengedése, feloldása az UNLOCK A utasítással történik. Pl.: T1: LOCK A --- .dolgozik A-val itt tart zárat A-n UNLOCK A --- Amíg T1 zárat tart A-n, addig más T-k csak korlátozottan (esetleg egyáltalán nem) férhetnek A-hoz, várakozniuk kell a zár felszabadulásáig. Def.: Ütemezÿ (scheduler) A DBMS-ben a tranzakciókezelés problémáival az ütemezÿ foglalkozik. Ez a DBMS azon része, amely az adatelérési igényeket kezeli adott jogosultságok szerint. Fÿ tevékenységei: • váratja / továbbengedi T-t; • zárakat ad ki / old fel; 94 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás • abortálja T-t. Def.: Protokoll Szabályrendszer, melyet ha a résztvevÿ T-k betartanak, akkor bizonyos kedvezÿ jelenségek érhetÿk,

illetve bajok kerülhetÿk el. Def.: Patt (patthelyzet, holtpont, deadlock) T-k egy csoportjából senki sem tud továbblépni, mert mindegyik egy olyan zárra vár, amit egy másik T tart. A patt tehát a zárak tartásának egy lényeges problémája Pl.: legegyszer bb formájában: idÿ T1: LOCK A LOCK B T2: itt patt lép fel! LOCK B LOCK A A pattok felismerése várakozási gráffal lehetséges, ami egy dinamikus - idÿben változó objektum. Az irányított gráf • csúcsai: T1,.,Tn az aktív tranzakciók; • élei: Ti Tj, ha van olyan Ai adategység, amin Ti épp zárat tart, Tj pedig dolgozni szeretne rajta (vagyis Tj LOCK-ot kér A-ra). Tétel: Pattok kialakulásának szükséges és elégséges feltétele Pontosan akkor nincs patt egy adott idÿpillanatban, ha a várakozási gráf DAG (körmentes). Biz.: • Ha a gráf DAG, akkor ∃ topologikus rendezése: Ti1,.,Tin, és ez egy lefutási sorrendet biztosít a T-k számára. (Ti1 léphet, mert nem vezet bele él) • Ha

a gráf nem DAG, akkor van benne irányított kör, amelyben a T-k patthelyzetben vannak. Def.: Pattok orvoslása 1. Várakozási gráf figyelése, és szükség szerint abort Az ütemezÿ az esetleges patt ciklusból egy vagy több tranzakciót kiiktat, ezáltal a többi T futhat tovább. 2. Rendezés (<) az adategységeken Szabály: T a zárakat a < rendezés szerint növekvÿ sorrendben kéri. A módszer árnyoldala, hogy interaktív rendszerekben ezt nem mindig tudják teljesíteni. 3. A T tranzakció egyszerre kéri az összes szükséges zárat . Az adatokon végzendÿ munkát T csak ezután kezdi Az elÿbbi módszernél felmerült gondok lépnek itt is fel. 95 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Def.: Éhezés (livelock) T állandóan vár, mert mindig más kapja meg a neki kellÿ zárat. A megoldás ötlete: a várakozókat sorba (queue, FIFO) kell tenni. Def.: Ütemezések Az (egyetlen) ütemezÿhöz aktív T-k utasításai

érkeznek. Pl.: T1,T2,T3 T2: READ B, T3: LOCK C, T1: WRITE D, T2: . az utasítások egymásutánja Def.: Soros ütemezés Elÿször Ti1, Ti2, ., és végül Tik utasításai hajtódnak végre Ebben a rendszerben nincs keveredés a T-k utasításai között, de ez a módszer alacsony tranzakciós teljesítményt ad. Def.: Sorosítható ütemezés Olyan ütemezés, mely hatását tekintve ekvivalens egy soros ütemezéssel. Vagyis a sorosítható ütemezés a T1,.,Tk tranzakciók utasításainak egy olyan sorozatba rendezése, amelyben minden Ti teljesen lefut, és hatása minden adaton megegyezik egy Ti1,.,Tik alakú soros ütemezés végrehajtásával Célunk az elkövetkezendÿkben, hogy biztosítsuk a sorosíthatóságot. Ez nehezebb feladat, mint a pattmentesítés, és függ az alkalmazott tranzakciós modelltÿl is. 2. Tranzakciós modellek Def.: Egyszer tranzakció modell LOCK A és UNLOCK A alkalmazását jelenti. Ha T megkapja a "kemény" zárat A-ra, akkor a

többi T≠T tranzakció semmit sem tehet A-val. Tranzakció: szabályos LOCK, UNLOCK párok sorozata, T: LOCK A,.,UNLOCK A. A LOCK és UNLOCK között található A kritikus intervalluma Feltehetjük, hogy itt Aval valami egyedi történik: olvassák vagy írják Ebbÿl következÿen vannak bizonyos konzisztencia-szabályok. Pl.: idÿ T1: LOCK A, UNLOCK A LOCK A, UNLOCK A T2: Ez nem ugyanaz, mintha T1-et és T2-t felcserélnénk. Egy ezzel ekvivalens soros ütemezésben a T1-nek meg kell elÿznie T2-t. (A zárak között egyedi események zajlanak.) Def.: Precedencia gráf 96 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Ez egy olyan gráf, melynek pontjai az aktív T-k. TiTj éle a gráfnak az adott ütemezésre vonatkozóan, ha van olyan A adategység, hogy: Ti: LOCK A Ti: UNLOCK A Tj: LOCK A Tétel: Sorosítható ütemezésre Az S ütemezés sorosítható ⇔ az ütemezés precedencia gráfja DAG. Biz.: • Ha a G gráf egy DAG, akkor a

csúcsoknak van egy Ti1,.,Tik topologikus rendezése Az ennek megfelelÿ soros ütemezés Ti1, Ti2, majd Tik összes utasítását végzi el. Ez ekvivalens S-sel. • Ha G-ben van irányított kör, akkor az itt érintett T-k közül egyik sem lehet elsÿ a soros ekvivalensben, tehát nincs soros ekvivalens. Megj.:A sorosíthatóság biztosításáról 1. A pattkezeléshez hasonlóan járunk el, de a sok abort rontaná a tranzakciós teljesítményt. 2. Kétfázisú protokoll: a zárkérések megelÿznek minden zárelengedést Vagyis T addig nem enged el zárat, amíg további zárat kérni szándékozik. A T munkája így fest: . zárkérések, z(T), feldolgozás, zár elengedések, Def.: T zárpontja Az elsÿ olyan idÿpillanat, amikor T már minden zárát megkapta. Jele: z(T) Állítás: A kétfázisú protokollt követÿ T-kbÿl álló S ütemezés sorosítható. Biz.: indirekte tfh a G precedencia gráfban van irányított kör 22. Az RLOCK/WLOCK-modell Hierarchikus

szerkezetek zárolása 1. Egy finomabb tranzakciós modell: az RLOCK / WLOCK modell Def.: RLOCK / WLOCK modell Ebben a modellben kétféle lock használatos: • RLOCK: soft, megengedÿ, share típusú zárolás. T: RLOCK A esetén T csak olvassa A-t, ami nem zárja ki, hogy más T=T tranzakciók is olvashassák A-t. A-n egyszerre több T-nek is lehet RLOCK-ja • WLOCK: hard, kizáró, exclusive típusú zárolás. 97 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás T: WLOCK A esetén T olvassa és írja is A-t, ami kizárja, hogy más T=T tranzakciók is használhassák A-t. A-n több zár nem lehet egyszerre Az egyszer tranzakció modellt úgy is felfoghatjuk, mint egy olyan rendszert, amiben csak WLOCK van. UNLOCK A mindkét típusú zárat feloldja. Def.: Tranzakció szemantikája Két ütemezés ekvivalens, ha: a.) ugyanazokat az értékeket olvassák RLOCK-nál; b.) ugyanazokat az értékeket rendelik minden adategységhez Def.: Precedencia vagy

sorosítási gráf az RLOCK / WLOCK modellben A gráfban T1T2 (T1≠ T2) él, ha: 1. T1: RLOCK A T1: UNLOCK A nincs A T2: WLOCK A T2 feltétlenül T1után kell, hogy következzen, mert T1-nek T2-tÿl független A értéket kell olvasnia. 2. T1: WLOCK A T1: UNLOCK A nincs A T2: WLOCK A T2-nek azért kell T1után következnie, mert a szekvencia végén T2-tÿl függÿ A értéknek kell maradnia A-ban. 3. T1: WLOCK A T1: UNLOCK A nincs WLOCK A T2: RLOCK A T2-nek olyan A értéket kell olvasnia, amit T1 állított elÿ, így T2-nek T1 után kell következnie. A gráfban T1T2 (T1≠ T2) nem él, ha: T1: RLOCK A . T1: UNLOCK A T2: RLOCK A Ez okozza valójában a hatékonyságnövekedést, mert nem kell élt felvenni T1 és T2 közé. Tétel: A WLOCK / RLOCK ütemezés sorosíthatóságáról Az S ütemezés sorosítható ⇔ a G precedencia gráf DAG. Biz.: analóg az egyszer tranzakció modell hasonló tételével Def.: Kétfázisú tranzakció Egy RLOCK / WLOCK modell szerinti

tranzakció kétfázisú, ha minden RLOCK és WLOCK megelÿzi az elsÿ UNLOCK-ot. Tétel: A kétfázisú WLOCK / RLOCK ütemezés sorosíthatóságáról Ha egy ütemezésben csak kétfázisú, RLOCK / WLOCK modell szerinti tranzakciók vannak, akkor az ütemezés sorosítható. Biz.: analóg az egyszer tranzakció modell hasonló tételével Def.: Zár kompatibilitási mátrix 98 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Az RLOCK / WLOCK bevezetésével elérhetÿ elÿnyök gondolata alapján további zármódok is definiálhatók. Ettÿl nyilván akkor várhatunk további hatékonyságnövekedést, ha az értelmezett zár-módok között minél több olyan van, amely egy adategységen egyidej leg tartható fenn, azaz összeférhetÿk, kompatibilisek. A zár-módok közti összeférhetÿséget a zár kompatibilitási mátrixban szokás ábrázolni. Pl.1: zárkérés RLOCK WLOCK meglévÿ zár az RLOCK Igen Nem adategységen WLOCK Nem Nem Egy

(i,j) mátrixelem "Igen", ha egy, az adatelemen lévÿ adott típusú zár mellett az új zárkérés is elfogadható, és "Nem" akkor, ha az új zárkérés nem teljesíthetÿ. Pl.2: Tfh INCR A az A értékét olvasás nélkül növeli eggyel: RLOCK WLOCK INCR RLOCK Igen Nem Nem WLOCK Nem Nem Nem INCR Nem Nem Igen Ha ismerjük az alkalmazott zárak kompatibilitási mátrixát, akkor ennek segítségével könnyen megrajzolhatjuk a sorosítási gráfot is: fel kell venni a T1T2 élt, ha T1 valamely A adategységet i módban zárolt, majd elengedett és utána elÿször T2 zárolja j módban, és a zár kompatibilitási mátrixban aij="Nem". 2. Zárak hierarchikus szerkezetekben Bevezetés Mindeddig az említett zárkezelési mechanizmusok tökéletesen függetlenek voltak attól, hogy az adategységek milyen struktúrába szervezettek, ill. szervezettek-e egyáltalán Pedig ennek a járulékos információnak a felhasználása a zárkezelés

hatékonyságát tovább növelheti. Kitüntetett jelentÿsége van annak az esetnek, amikor az adategységek valamilyen hierarchiába vannak szervezve, pl.: • hierarchikus adatbázis rekordjairól van szó; • egy B-fa elemeit dolgozzuk fel; • egymásba ágyazott adatelemekkel van dolgunk Kihasználva a hierarchikus szerkezetet, lehetÿségünk van arra, hogy egy adategység zárolása esetén minden, a hierarchiában alacsonyabban lévÿ adategységet is egyidej leg zároljunk. Jól kihasználható ez egymásba ágyazott adatelemek esetén, például relációs adatbázisoknál (figyelmeztetÿ protokoll); de más hierarchiáknál ez nem feltétlenül célravezetÿ - pl. B-fáknál (fa protokoll) 99 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Def.: Fa protokoll Az egyszer tranzakció modellt követjük (LOCK, UNLOCK); az adategységek egy gyökeres, irányított fa csúcsai. Egy csomópont zárolása nem jelenti a gyerekek zárolását is A fa

protokoll nem kétfázisú. Szabályai: (egy T követi a fa protokollt, ha) 1. egy tranzakció az elsÿ LOCK-ot akárhova teheti; 2. további LOCK-ok csak akkor helyezhetÿk el, ha az adategység szülÿjére ugyanaz a tranzakció már rakott zárat; 3. egyazon tranzakció kétszer ugyanazt az adategységet nem zárolhatja Pl.: (egy T insert m veletet hajt végre egy B-fán) A LOCK A LOCK B UNLOCK A LOCK E B D C E F G Tétel: A fa protokollos ütemezés sorosíthatóságáról A fa protokollnak eleget tevÿ legális S ütemezések sorosíthatók. (nem biz.) Def.: Figyelmeztetÿ protokoll Az egyszer tranzakció modellt követjük (LOCK, UNLOCK); az adategységek egy gyökeres, irányított fa csúcsai. Egy csomópont zárolása a gyerek csomópontok zárolását is jelenti (implicit lock). Ez utóbbi feltételezés azonban azt is eredményezheti, hogy két tranzakció tart fenn egyidej leg zárat ugyanazon az adategységen. A jelenség neve zárkonfliktus, amit alkalmaz

szabályok megtartásával el kell kerülni. A figyelmeztetÿ protokoll zárm veletei: • LOCK A: zárolja A-t és valamennyi leszármazottját. Két különbözÿ T nem tarthat fenn egyidej leg zárat ugyanazon az adategységen. • WARN A: A-ra figyelmeztetést (warning) rak. Ekkor A-t más T nem zárolhatja • UNLOCK A: eltávolítja a zárat és figyelmeztetést A-ról. A protokoll szabályai ugyanazok, mint az egyszer tranzakció modellben, továbbá: 1. egy T elsÿ m velete kötelezÿen a "LOCK gyökér" vagy "WARN gyökér" 2. LOCK A vagy WARN A akkor helyezhetÿ el, ha A szülÿjén már van WARN 3. UNLOCK A akkor lehetséges, ha az A gyerekein már nincs LOCK vagy WARN 4. kétfázisú: az elsÿ UNLOCK után már nem következhet LOCK vagy WARN Tétel: A figyelmeztetÿ protokollos ütemezés sorosíthatóságáról 100 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás A figyelmeztetÿ protokollt követÿ legális ütemezések

konfliktusmentesek és sorosíthatók. Megj.: A figyelmeztetÿ protokoll kompatibilitási mátrixa formálisan megegyezik az RLOCK / WLOCK kompatibilitási mátrixszal, valamint az RLOCK / WLOCK nyomán bevezethetÿ az RWARN / WWARN modell, ami a tranzakciós teljesítmény növekedését eredményezheti. Def.: DAG protokoll Tfh. az adategységek DAG-gal ábrázolhatók A DAG protokollban az egyszer tranzakció modellt használjuk, a következÿkkel kiegészítve: 1. a T-k elsÿ LOCK-ja tetszÿleges; 2. ezután egy T csak akkor adhat ki LOCK A-t, ha épp zárat tart A valamelyik "megelÿzÿjén", és valamikor zárat tartott az A összes megelÿzÿjén. Ez nehéz feladat! A DAG protokoll az elÿbbiekhez hasonlóan sorosítható. 23. Idÿbélyeges módszerek egy processzoros környezetben 1. Bevezetés Az idÿbélyeges tranzakciókezelés a tranzakciók sorosíthatósága biztosításának egy másik módja. Akkor praktikus elsÿsorban, ha a tranzakciók között kevés a

potenciális sorosítási konfliktus. Az idÿbélyeges tranzakciókezelés során az adategységekhez egy - vagy néhány - járulékos adatot rendelünk hozzá (idÿbélyeg). Segítségével eldönthetÿ, hogy egy tranzakció adott adategységre vonatkozó kérése sérti-e a sorosíthatóságot. Ha igen, akkor a tranzakciót abortálni kell. Alapvetÿen agresszív protokoll Def.: Idÿbélyeg Az idÿbélyeg olyan érték, amelyet minden tranzakcióhoz szigorú egyediséget biztosítva rendelünk hozzá és mely arányos (legegyszer bb esetben azonos) a tranzakció kezdÿidejével. Jele: t(T). Tulajdonságok: 1. Az idÿbélyegek a tranzakcióknak egy egyértelm sorrendjét határozzák meg (Fontos, hogy T≠T-re t(T)≠t(T).) 101 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 2. Képzelhetjük úgy, mintha a tranzakciók a kezdÿidejükben (csaknem) zérus idÿ alatt futnának le. 3. Fontos, hogy a kb egyszerre induló T-k közül senkinek se legyen

nagyon kicsi t-je a többiekhez képest. Ezek miatt a kezdÿidÿk növekvÿ sorrendjébe állítva a tranzakciókat ez lehet egy soros ekvivalens ütemezés. Ha tehát az idÿbélyeges ütemezÿ gondoskodik arról, hogy csak olyan m veleteket engedélyezzen, amely a tranzakciók növekvÿ idÿbélyegével ekvivalens soros ütemezés hatásaival egyezik meg, akkor a tranzakciók indulási sorrendje valóban egy soros ekvivalens ütemezés lesz. 2. A módszer m ködése Def.: Az idÿbélyeges ütemezÿ m ködése 1. Megvizsgálja minden írás-olvasás elÿtt a hivatkozott adategység idÿbélyegét; 2. ha ez a sorosítási szabályokkal összhangban van, akkor az adategység idÿbélyegét felülírja a m veletet végrehajtó tranzakció idÿbélyegével, és ha nincs összhangban vele, akkor pedig abortálja a tranzakciót. Pl.: ha t(T1)=100, t(T2)=80, t(T3)=120, akkor az ütemezés a csupa T2 csupa T1 csupa T3-mal ekvivalens. Megjegyzés: elképzelhetÿ, hogy egy ütemezés

sorosítható • idÿbélyegesen, de zárakkal nem • idÿbélyegesen is és zárakkal is • idÿbélyegesen nem, de zárakkal igen • idÿbélyegesen sem és zárakkal sem. Def.: Idÿbélyeges tranzakciókezelés R/W modellben r(A): az adategység olvasási ideje, annak a transzformációnak az idÿbélyege, amely utoljára olvasta az A adategységet. Formálisan: r(A) = max{t(T); T olvasta A-t} w(A): az adategység írási ideje, annak a transzformációnak az idÿbélyege, amely utoljára írta az A adategységet. Formálisan: w(A) = max{t(T); T írta A-t} Ha még nem olvasták/írták az adatot, akkor egy kezdÿértéket állítunk be:t-∞-t, de 0-t is használhatunk. Az ütemezÿ azt nézi, hogy a t(Ti1)<.<t(Tik) soros sorrendhez képest van-e ellentmondásos tranzakció. Annál a tranzakciónál abortál, ahol elÿször észleli a növÿ kezdÿidÿ szerinti sorrend megsértését. Ha egy T tranzakció egy A adategységhez fordul, akkor 4 konfliktushelyzet adódhat: 1.

t(T) < w(A) és T olvasni akarja A-t Abort T a következménye annak, hogy egy késÿbb indult tranzakció már írta A-t, tehát nem olvashatjuk. (A t(T) ≥ w(A) természetesen mindig lekezelhetÿ, és r(A):=t(T).) 2. t(T) < r(A) és T írni akarja A-t Abort T a következménye annak, hogy egy késÿbb indult tranzakció már olvasta A-t, tehát nem írhatjuk. (A t(T) ≥ r(A) természetesen mindig lekezelhetÿ, és w(A):=t(T).) A következÿ két konfliktushelyzet már nem okoz Abortot: 102 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 3. t(T) < r(A) és T olvasni akarja A-t T olvassa A-t, de r(A) nem változik Egy késÿbb induló tranzakció már olvasta A-t, de ettÿl még T is kiolvashatja, de az idÿbélyeget a késÿbbi értéken kell hagyni. 4. t(T) < w(A) és T írni akarja A-t Ekkor figyelmen kívül hagyjuk, hogy az írási m veletet; T továbblép A írása nélkül. Az idÿbélyeges ütemezÿ a fentiek értelmében, ha T

érkezik az A adategységhez, akkor: • 1. és 2 esetben: abort T-t ad ki; • 4. esetben minden további nélkül továbblép, semmi akció nem történik; • a fennmaradó összes többi esetben el lehet végezni az írást/olvasást és 3. kivételével az ütemezÿ a m veletnek megfelelÿen módosítja r(A) ill. w(A) értékét Az idÿbélyeg tesztelése és maga a m velet oszthatatlan kell, hogy legyen! Példa idÿbélyeges ütemezésre t(T1) = 20 t(T2) = 10 T1 = READ A, T2 = READ A, T1 = WRITE C, T2 = WRITE C, T2 = READ A, T2 = WRITE A a beérkezÿ T-k sorrendje. A fenti utasítássorozatot akarjuk végrehajtani. Kezdetben minden kezdÿidÿ 0: w(A) = r(A) = w(C) = r(C) = 0. Az ütemezés folyamata a következÿ: 1. T1 olvashatja A-t: r(A) = 20 lesz 2. T2 olvashatja A-t (a jövÿben olvasás "történt", de ez nem zavaró): r(A) = 20 marad 3. T1 írhatja C-t: w(C) = 20 lesz 4. T2 írni akarja C-t, most a 4 típusú helyzet következett be T2 nem ír, w(C) marad,

továbblépünk. 5. T2 olvashatja A-t: r(A) = 20 marad 6. T2 írni akarja A-t, de 2 miatt abortálni kell T2-t Ugyanis A-t már a jövÿben olvassa valaki. A m ködés szorosan kapcsolódik a kezdÿidÿkhöz. Pl ha ugyanebben a példában r(C)=25 lenne, akkor az abort már a 3. utasításnál bekövetkezne Az idÿbélyeges ütemezés tehát nem tesz semmit a baj elkerülésére, de ha az bekövetkezik, akkor aborttal oldja fel a helyzetet. Megjegyzés az idÿbélyegek tárolásáról Gond az, hogy esetleg sok r(A) és w(A) bejegyzés van a rendszerben. Ötlet: legyen t-∞∞ = min{t(T), ahol T aktív}. Vagyis van egy idÿhorizontunk, ami "alatt" nem tároljuk az idÿket; vagyis elég azokat az r(A) és w(A) idÿket tárolni, melyek t-∞-nél nagyobbak (vagy egyenlÿek vele), azaz aktívak. 103 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Ez a módszer jól illeszkedik az ellenÿrzÿ pontos technikához, ahol az ellenÿrzÿ pontok jó

jelölteket adnak a t-∞ képzéséhez. Alapértelmezés szerint, ha nincs érvényes r(A) ill. w(A) érték, akkor azt t-∞-nek vesszük A kezdÿidÿk kiosztásánál nem jó, ha valamelyik T nagyon "lemarad", mert ez a tranzakció szükségtelenül várakozhat, és ezért konfliktushelyzetekbe is bonyolódhat. Fontos ezért a kezdÿidÿk közelítÿ szinkronizációja. Megjegyzés az idÿbélyeges naplózásról és visszaállításról Az abortok, piszkos adatok és lavinák itt ugyanúgy problémát okozhatnak, mint az egyszer tranzakció modellben. (Az idÿbélyeges módszerek agresszívek, nem olyan konzervatívak, mint a zárat használó kétfázisú protokollok. Bár az is igaz, hogy a zárat használó módszerek ötletes módosításokkal idÿbélyegessé tehetÿk.) A megoldást itt egy idÿbélyeges szigorú protokoll adja. • Ebben az esetben is ugyanúgy használjuk a naplót, mint korábban, de a zárak nem játszanak szerepet ennek módosításában,

minden a "tiszta" akciókon múlik. • Az írások elÿször a naplóban rögzítÿdnek, majd a napló a stabil tárba íródik. • A COMMIT is elÿször a naplóba kerül bele, majd a napló a stabil tárba íródik. • Végül következnek a tényleges DB-írások. Fontos, hogy a COMMIT elÿtt meg kell történnie az idÿbélyeg-ellenÿrzéseknek, mert különben a COMMIT nem lenne korrekt. Példa az idÿbélyeges naplózás problémáira t(T) = 100 érkezik. T: WRITE A és w(A) = 80. Ez egyelÿre jogos akciónak látszik. De elképzelhetÿ, hogy a tényleges írás elÿtt valaki már w(A) = 110-zel ír. Ez egy abort-helyzet lenne T-re, amit késÿn, csak a COMMIT után fedeznénk fel. Az ellenÿrzés elvégzéséig zárat kell tartani A-n! Kétféle megoldás adódik: 1. Tfh T az A-t írja vagy olvassa Akkor végezzük az ellenÿrzést, amikor T ténylegesen A-hoz fordul, vagy 2. közvetlenül a COMMIT - a befejezÿ lépés - elÿtt Mindkét esetben az ellenÿrzés

kezdetétÿl az esetleges tényleges írásig zárat kell tenni Ara. A két technika jellemzÿje: 1. hosszabb zárak, kevesebb abort; 2. rövidebb zárak, de több abort (ez az optimista stratégia) 3. Verziókezelés idÿbélyeges modellben Def.: Verziókezelés Szoros rokonságot mutat az idÿbélyeg-kezeléssel, de attól függetlenül is létezik. 104 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Számos alkalmazásnál fontos a régi változatok megÿrzése (pl. kórházak betegnyilvántartása). Az adatbázisok "történelme" sok mindenre felhasználható; pl kereskedelmi adatbázisoknál a szakemberek adatbányászattal szereznek információt a fogyasztói szokásokról. De lehet, hogy maga az alkalmazás követeli meg a verziók tárolását Más ok az, hogy a régi változatok tárolásával sokszor (idÿben) hatékonyabb megoldások kaphatók. Ez tulajdonképpen egy táridÿ motivációjú ötlet A verziókezelés gyakran nagyon

helyigényes; gyakran említik együtt az optikai táras tárolással, mert olyan méret a tárolandó adatmennyiség. Def.: Idÿbélyeges verziókezelés Ez az idÿbélyeges módszer kiegészítése. Ötlete: minden egyes íráskor egy teljesen új A példányt hozunk létre a T tranzakció kezdÿidejével, a már meglévÿ A példányokkal nem törÿdve. • Vagyis ha T írná A-t, akkor új A példányt készít, amelyre w(A) = t(T) lesz. • Ha T olvasni akarja A-t, akkor kérdés, hogy melyik verziót olvassa. Azt a példányt kell nézni, amelyre w(A) ≤ t(T), és az ennek a feltételnek megfelelÿ példányok közül azt kell választani, amelyre w(A) maximális. Ha nincs ilyen példány, akkor az olvasási igény nem teljesíthetÿ. Ebben a rendszerben egyetlen tranzakciós abort-ok van: ha T írná A-t, és van olyan Ai verzió, melyre: w(Ai) < t(T) < r(Ai). (w(Ai)-t T, r(Ai)-t T állított be) Ez a baj nem orvosolható, mert a T tranzakció T-tÿl vagy korábbi

tranzakciótól olvasott, pedig T-tÿl vagy késÿbbitÿl kellett volna olvasnia. A helyzet ellentmondásossága abort-hoz vezet. A módszer elÿnye, hogy az abort-helyzetek ritkulnak és nagyobb a tranzakciós teljesítmény. Hátránya: • sok helyet igényel (bár a tárak ára csökkenÿ tendenciát mutat manapság); • bonyolult az algoritmika (beleértve a szükségtelen verziók menedzselését); • bonyolult helyreállítás szükséges (szigorú protokoll kell). A tranzakciók újraindításának ("összeakadás" esetén) módszere az, hogy alkalmas véletlen - várakozási idÿ után indítjuk újra a tranzakciókat. (Pl: Ethernet-protokoll, vagy az éhezÿ filozófusok problémája.) 24. Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 1. Bevezetés Eddig nem foglalkoztunk azokkal a problémákkal, amelyek akkor lépnek fel, ha egy tranzakció nem fut le teljesen, valamely ok miatt idÿ elÿtt befejezÿdik. Ezek a lehetséges okok a következÿk:

105 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 1. a tranzakció félbeszakad (programhiba T-ben); 2. az ütemezÿ pattot lát és "kilövi" T-t; 3. az ütemezÿ sorosíthatatlanság miatt kilövi T-t, ezáltal biztosítja a sorosíthatóságot (ez agresszív ütemezÿknél gyakoribb, a tranzakciós teljesítményt az abortok révén növelik); 4. rendszerhiba lép fel (az illékony tár: belsÿ memória, cache, stb sérül); 5. a háttértár tartalma (is) megsérül (a stabil tár sérül: média hiba) Mi a 2. és 3 esetekkel foglalkozunk; célunk a DB visszaállítása valamilyen konzisztens állapotba. Def.: Konzisztens állapot Az adatbázisnak olyan állapota, amely csak teljesen lefutott tranzakciók hatását tükrözi. Def.: Piszkos adat Olyan adat, amely egy késÿbb abortált T által íródott a DB-be. Ezt az adatot más (sikeres) T-k a tranzakciók atomisága miatt az író T abortálásáig felhasználhatták. Így a

visszaállítást ezekben a T-kben is végre kell hajtani. Def.: Lavina (cascading rollback) A piszkos adat az adatbázisból mihamarabb eltávolítandó. Azonban - ahogy az elÿbb kimondtuk - elÿfordulhat, hogy egy másik tranzakció olvassa a piszkos adatot, és ez a tranzakció már sikeres. Ennek ellenére eredménye nem feltétlenül tekinthetÿ helyesnek, így az adatbázisból ez is eltávolítandó. A jelenség iteráltan is elÿfordulhat, ekkor a neve: lavina Def.: Kész (commit) pont Az az idÿpillanat, amikor egy tranzakció futása során már minden befejezÿdött, ami a bevezetÿben felsorolt okok miatti abortját eredményezheti. Gyakorlatilag ez azt jelenti, hogy a tranzakció már minden számítást elvégzett, és minden zárat megkapott. Ekkor egy COMMIT utasítás szokott következni, de ez az idÿpont még nem feltétlenül azonos azzal, amikor minden eredmény már véglegesítve is lett. Ehhez további m veletek is szükségesek lehetnek. Ha viszont a

tranzakció nem jutott el eddig a pontig, és ekkor abort következik be, akkor a tranzakciónak minden esetleges hatását törölni kell az adatbázisból. Tehát tranzakció csak commit után írhat a DB-be 106 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Példa az elÿzÿekre: (az idÿ lefelé telik) T2 T1 LOCK A READ A A:=A+100 WRITE A LOCK B UNLOCK A LOCK A READ A A:=A*A READ B WRITE A COMMIT UNLOCK A B:=B/A Tfh. T1 utolsó sorában "elszáll" a rendszer Ekkor nincs se patt, se sorosíthatósági probléma, de mégis baj történik, mert T2 piszkos A-t olvasott. T1 hatását (A-t írta) el kell tüntetni, és T1 zárját B-n fel kell oldani. A problémára részleges orvosságot a szigorú kétfázisú protokoll ad. 2. Megoldások Def.: Szigorú (strict) kétfázisú protokoll Ez az igen gyakori protokoll. Egy tranzakció ezt a protokollt követi, ha kétfázisú, továbbá: 1. nem ír az adatbázisba, amíg kész pontját el nem

érte (csak COMMIT után ír a DBbe) Ez a szabály ahhoz kell, hogy ne kelljen az adatbázist helyreállítani, ha egy tranzakció abortál (csak redo kell); 2. zárait csak az adatbázisba való írás után engedi el Ez szabály biztosítja valójában azt, hogy piszkos adatot ne lehessen olvasni, tehát elkerüljük a lavinákat, ami kifejezetten elÿnyös. Azaz az események pontos sorrendje: COMMIT, írás a DB-be, zárak elengedése. Mindez természetesen csak akkor igaz, ha nem kell rendszerhibákkal is számolni, amelyek az írási folyamat megzavarásával eredményezhetik, hogy piszkos adat kerül az adatbázisba. Ez ellen azonban más módszerekkel kell védekezni (lásd késÿbb: naplózás). Tétel: A szigorú kétfázisú protokoll sorosíthatóságáról A szigorú kétfázisú protokollt követÿ tranzakciókból álló ütemezések sorosíthatók és lavinamentesek. 107 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Biz.: az ütemezés

sorosítható, mert kétfázisú; továbbá lavinamentes, mert nincs lehetÿség piszkos adat olvasására. Def.: Agresszív protokoll Egy protokoll agresszív, ha megpróbál olyan gyorsan lefutni, amennyire csak lehetséges, nem törÿdve azzal, hogy ez esetleg aborthoz is vezethet (keveset törÿdik a zártáblák kezelésével, a zárakra várakozó sorok karbantartásával, pattok érzékelésével és feloldásával, zárak odaítélhetÿségének vizsgálatával.) Mindezért több T-t tud idÿegység alatt elvégezni, de több az abortok száma is. Def.: Konzervatív protokoll Egy protokoll konzervatív, ha megkísérli elkerülni az olyan tranzakciók futtatását, amelyek nem biztos, hogy eredményesek lesznek (sokat foglalkozik az agresszív protokolloknál említett dolgokkal). Azaz igyekszik minél kevesebb aborttal megoldani a feladatát. Ennek eredménye a nagyobb overhead, a kevesebb abort, a kisebb T/idÿ arány. Tehát az egyes protokollok között a tranzakciós

teljesítményben van elsÿsorban különbség. Az egyes típusok (agresszív vagy konzervatív) alkalmazása az "összeakadások" esélyétÿl függ: • ha ez nagy, akkor válasszunk konzervatív protokollt; • de ha kicsi, akkor agresszív protokollra is jó lesz. Példa egy nagyon konzervatív protokollra Az ezt követÿ tranzakció: 1. szigorú kétfázisú; (emiatt sorosítható és lavinamentes) 2. az összes zárat elÿre kéri és csak akkor indul, ha már az összeset megkapta; (emiatt pattmentes) 3. csak akkor kapja meg zárjait, ha már elÿtte senkinek sem kellenek a sorban (Emiatt éhezésmentes.) Az elÿnyök ára, hogy 2. és 3 miatt nagy lehet a késleltetés, amíg egyáltalán a tranzakció elindulhat; 2. és 1 miatt más tranzakciókat is szükségtelenül késleltet (konvoj hatás); 2. miatt elÿre ismerni kell(ene) valamennyi zárat Példa egy nagyon agresszív protokollra Nagyon agresszív egy protokoll, ha a zárakat közvetlenül írás vagy

olvasás elÿtt kéri. Amennyiben a zárakat csak azután engedi el, hogy valamennyit megkapta, akkor egyszer en sorosítható, ellenben a sorosíthatóság biztosítása is külön probléma. Patt és éhezés is lehetséges, viszont a tranzakciók igen gyorsan lefuthatnak és a többi tranzakciót is kevéssé fogják vissza. Ha kevés a tranzakciók által közösen használt adat, akkor kicsi a nem sorosítható ütemezés, patt és éhezés veszélye, ilyenkor az agresszív protokollok hatékonyabbak. 108 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 3. A helyreállítás problémája rendszerhibák esetén Bevezetés A rendszerhibák elleni védekezés általános módszere a naplózás (journal, log). A napló a mi értelmezésünk szerint az adatbázison végrehajtott változások története. Erre nagyon odafigyelünk, gondosan és rendszeresen mentjük bele a változásokat. Szerkezete, tartalma a rendszeres visszaállításokat segíti. A

napló szerkezete, bejegyzései: 1. T kezdte meg m ködését Formálisan: (<T azonosító>, begin) 2. T írja A-t Formálisan: (<T azonosító>, A adategység, új érték, régi érték) Ha A túl nagy, akkor helyette akcióleírás szerepel a naplóban (hogyan kell az adategység új értékét elÿállítani). 3. (Bizonyos esetekben) T olvassa A-t Formálisan: (<T azonosító>, olvasott A értéke) 4. T eléri kész pontját Formálisan: (<T azonosító>, commit) 5. T abortál Formálisan: (<T azonosító>, abort) A napló ilyen bejegyzések idÿrendi sorozata. Def.: Az újra (redo) protokoll Olyan tranzakciókezelést valósít meg, amely rendszerhiba (és tranzakcióhiba) után szükségtelenné teszi az undo m veletet, csak redo kell. A protokoll a szigorú kétfázisú protokoll kiegészítése, finomítása; két része a redo naplózás és a redo helyreállítás. A redo naplózás lépései: 1. (T, begin) a naplóba 2. (T, A, <A új

értéke>) a naplóba, ha T megváltoztatja valamely A adategység értékét 3. (T, commit) a naplóba, ha T elérte commit (kész) pontját 4. a napló mindazon oldalainak stabil tárba írása, amikkel ez még nem történt meg (Az a tranzakció lett véglegesítve, ami eljutott ennek a pontnak a végéig.) 5. A értékeknek tényleges beírása az adatbázisba (az érintett blokkokat be kell hozni a memóriába, az írást elvégezni. A megváltozott oldalak visszaírása a háttértárra már opcionális.) 6. zárak elengedése (más tranzakciók csak ezután férnek hozzá a T által megváltoztatott adatokhoz, így nincs lavinaeffektus sem). Baj esetén van szükség a redo visszaállítási algoritmusára. A rendszer "szétesése" után a napló stabil tárban lévÿ része alapján a DB visszaállítása lehetséges egy konzisztens állapotba. A redo visszaállítási algoritmus lépései: 1. valamennyi zár felszabadítása 2. napló vizsgálata visszafelé:

feljegyezzük azon tranzakciókat, amelyekre találunk (T, commit) bejegyzést a naplóban 3. addig megyünk visszafelé a naplóban, amíg ameddig nem találunk egy konzisztens állapotot 4. a 2 pontnak megfelelÿ tranzakciókra vonatkozó bejegyzések segítségével az DB-ben található értékeket felülírjuk az újakkal. 109 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás A redo helyreállítás eredményeként a 2. pontnak megfelelÿ tranzakciók hatása megmarad, a többié elvész és az adatbázis egy újabb konzisztens állapotba kerül. Ha a redo helyreállítás elszáll, akkor egyszer en megismétlendÿ, hiszen a 4. pontban végzett m veletek hatása az adatbázisra idempotens. Def.: Ellenÿrzési pont (checkpoint) A redo helyreállításnál könnyen elÿfordulhat, hogy igen régi idÿpontra kell a naplóban visszafelé menni ahhoz, hogy alkalmas idÿpontot találjunk a helyreállítás megkezdésére. Ezen a problémán segítenek az

ellenÿrzési pontok, amikor kikényszerítik az adatbázisnak egy konzisztens állapotát.: 1. Ideiglenesen megtiltjuk új tranzakció indítását és megvárjuk, amíg minden tranzakció befejezÿdik vagy abortál. 2. Megkeressük azokat a memóriablokkokat, amelyek módosultak, de még nem kerültek a háttértárba kiírásra. 3. Ezeket a blokkokat visszaírjuk a háttértárra 4. Az ellenÿrzési pont tényét naplózzuk 5. A naplót kiírjuk háttértárra Elÿnye az, hogy a redo helyreállításnál csak a legutóbbi ellenÿrzési pontig kell a naplóban visszamenni; emiatt a napló korábbi részei eldobhatók (amennyiben más érv ez ellen nem szól); és csökkenti a lavinák számát is. Hátránya, hogy csökkenti a tranzakciós teljesítményt (többlet írások a háttértárra, tranzakció indítások késleltetése). Ütemezése lehetséges: • adott idÿ eltelte után; • adott számú tranzakció lefutása után; • kombinálva az elÿzÿ kettÿt. Mivel az

ellenÿrzési pontokra elsÿsorban a helyreállításkor van szükség - ez pedig ritka eseménynek számít -, ezért ellenÿrzési pontokat is viszonylag ritkán iktatnak be. Következmény: a helyreállítás tovább tart. Tn . T1 T2 T3 . z(Tn) < z(T1) < z(T2) < z(T3) Az összes egyenlÿtlenség együtt nem teljesülhet. További állítások: 1. A következÿ zárpont szerinti növÿ soros ütemezés S-sel ekvivalens 2. Tfh T1 nem kétfázisú Ekkor megadható egy kétfázisú T2 és a két T-nek egy olyan S ütemezése, ami nem sorosítható. Megj.:További modellekkel a köv tételekben ismerkedünk meg 110