1. Az adatbázis fogalma, fontosabb összetevÿi, felhasználási módjai

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.2.1. Ú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.2.2.

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

Hatékony tárolás, kezelés, hozzáférés

1.2.4. 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.2.5. 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.


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


ÿ 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


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

Naiv felhasználó

Egyszer lekérdezéseket intéz a rendszerhez vagy alkalmazói programokat indít. 1.4.2.

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

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


(Itt húzhatunk egy képzeletbeli vonalat, mert nagy az ugrás a szakmai felkészültségben:) 1.4.4.

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

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

Programozás:

ORACLE/SQL és alkalmazása (a Szg.labor 6 keretében) 1.5.3.

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


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

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

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

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

Az osztálydeklaráció formája az ODL-ben: 6

4. tétel


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


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.2.6. 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.2.7.

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.2.7.1. 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.2.7.2. 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í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.2.8.

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


ÿ 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.3.1. Valósághÿ modellezés ÿ a fontos adatelemek és ÿ a fontos kapcsolatok is legyenek benne a modellben! 2.3.2. 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


ÿ 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.3.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.

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 (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 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


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


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


Ö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


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


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


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


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


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


ÿ 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


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


ÿ 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


Ö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


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


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


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


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


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


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


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 : 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


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 (User's 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


• 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ÉLY.FIZ 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 • GET <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 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 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 : a kapcsolatkurrens gy r jének a szülÿjére mutat. 4. FIND {FIRST/NEXT} IN CURRENT 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


• Beillesztés: STORE . 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 ... Ezzel r bekerül a kapcsolatok kurrens gy r jébe. • Törlés: REMOVE T FROM ... . Ezzel r kikerül a kapcsolatokból. • Rekord törlése: DELETE . 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 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


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


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 ::= 41

12. tétel


::= 1. Mezÿk: név, szint, típus, hossz 2. Hely a fában: • ROOT (gyökér) • PARENT (szülÿ) 3. Virtualitás • virtuális: igen / nem • hol az eredetije VIRTUAL IN 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


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 WHERE 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. ::= .<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 Itt a jobbra lépés a típus megtartásával történik. WHERE 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


Rekord beillesztése: • A rekordot a sablonjában összerakjuk, • majd kiadjuk a következÿ utasítást: STORE / INSERT WHERE 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ÖK.KÖ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


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


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


2. A relációs adatmodell alapmÿveletei (E.F. 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. R\S elemei R azon sorai lesznek, amelyek nem szerepelnek S-ben. R\S örökli az R oszlopszámát, attribútumait, típusait. Példa: az úniónál bemutatott R-re és S-re R\S

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


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


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
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\(R\S)=S\(S\R) 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=S.Ai. – Az eredményt vetítjük rá R.A1,...,R.Ak,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


– 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<S.C

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


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


4. R és S különbsége (nem kell a k=s-et feltételezni!): R\S={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


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


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


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


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=t2.Termé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


A "szokásos" aggregációk is használhatók, például: (megkapjuk az összes számlaegyenleget) Ügyfél

Egyenleg P.AVG.ALL

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


• 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


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=E.CÍM) WHERE E.FIZETÉ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 (<mezÿnév> : );* 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 IS (<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 ; 62

19. tétel


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 ; ... 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: E.NÉV, E.SZSZ, 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 (E.ALL); [E összes komponense megjelenik] RETRIEVE (E.NÉV, E.RÉ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 E.NEM='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(E.FIZETÉS); RETRIEVE MAX(E.FIZETÉS WHERE E.CÍM='Fÿ u.'); RETRIEVE MAX(E.FIZETÉS BY NEM); [→GROUP BY] RETRIEVE MAX(E.FIZETÉS BY NEM WHERE E.CÍ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 P.NÉ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 ( ) Eredménye: • 0, ha nincs ilyen, és • 1, ha van. 63

19. tétel


Pl.: ANY(E.NÉV WHERE E.CÍ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


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, SQLCODE.4) 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 ( [NOT NULL] [, [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 [( [, , ... ])] AS ; 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. (19.oldaltól)

6

Lásd késÿbb (Queries) 65

19. tétel


• Tábla törlése: DROP TABLE ; • Nézet törlése: DROP VIEW ; • Tábladefiníciók módosítása: ALTER TABLE [ADD | MODIFY] ; – 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 ON ( [,, ... ]); 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 ; 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 ezek adják meg a lekérdezésben résztvevÿ táblák nevét [WHERE ] ezzel válogathatunk az eredmény sorai között [GROUP BY ] ez rendezi egymás mellé az eredménytábla sorait [HAVING ] ezzel a csoportosítás révén keletkezÿ eredménysorokra kiválasztási feltételt írunk elÿ [ORDER BY ] ez határozza meg a megjelenÿ sorok sorrendjét

66

19. tétel


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 [( [,, ... ])] VALUES ([, , ...]); 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 [WHERE ]; 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 SET = [, = , ...] [WHERE ]; 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 [, , ...] 67

19. tétel


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 TO [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 [,, ...] 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


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ÉLY.NÉ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: X→Y 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év→Cím b.) Név, Termék→Név, Cím,Termék, Ár = R (azaz az egész rekordot meghatározza) 69

19. tétel


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 • AB→C függés "üresen" teljesül, az • A→C függés nem "üresen" igaz, és a • C→B 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

Nem→Szemszín: ez nem igazi függés, ezzel szemben a Szsz→Nem 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év→Cím és Név, Termék→R 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


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 X→Y függés logikai következménye F-nek, ha X→Y érvényes minden olyan Rsémájú r relációban, ahol az F is érvényes. Jele: F |= X→Y. 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 ÿ X→Y A2. Kiegészítési szabály Ha X→Y és Z⊆R ÿ XZ →YZ A3. Tranzitivitási szabály Ha X→Y és Y→Z ÿ X→Z Def.: Levezethetÿség F-bÿl az U→V levezethetÿ, ha az U→V függés megkapható F-bÿl az A1-A3 alkalmazásával. Jele: F | U→V. Tétel: Igazság-tétel F |  X→Y esetén F |= X→Y 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


Ezzel állításunkat igazoltuk. Def.: Szuperkulcs, kulcs Az X⊆R attribútum-halmaz szuperkulcs az (R,F)-re nézve, ha F |= X→R. 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,Utca→Irsz, Irsz→Vá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. X→Z ∈F 2. YX→YZ A2 (Y a kiegészítÿ halmaz) 3. X→Y ∈F 4. X→YX A2 (X a kiegészítÿ halmaz) 5. X→YZ A3 (4. és 2. tranzitivitása) 2. Felbontási szabály 1. X→Y 2. Y→Z 3. X→Z

Mi alapján? ∈F A1 A3 (1. és 2. tranzitivitása)

3. Áltranzitív szabály 1. WY→Z

Mi alapján? ∈F 72

19. tétel

Lezárások, fedések, vetített függések 2. X→Y 3. XW→YW 4. XW→Z

∈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={Ai→Bj} 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 X→Y 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 | X→Y ⇔ Y⊆X+(F) Biz.: ÿ irány Tfh. F | X→Y és A∈Y. Be kell látni, hogy: F | X→A. √

Ez viszont a felbontási szabály miatt mindig igaz.

⇐ irány Be kell látni, hogy ha Y⊆X+(F), akkor F | X→Y. Legyen Y=A1,...,Ak attribútumok együttese. 73

19. tétel

Lezárások, fedések, vetített függések Felt.: F | X→Ai, ahol i=1,...,k. Alkalmazzuk többször az únió-szabályt! X→A1 X→A2 } X→A1 A2 X→A1 A2 A3 X→A3 ... Végül: X→A1,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 |= X→Y esetén F |  X→Y 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 V→W∈F, akkor V→W teljesül F-en. (Ez jelenti azt, hogy modellt készítettünk (R,F)-hez.) Biz.: Legyen V→W∈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 |  X→V 2. V→W ∈F miatt 3. F | A3 miatt (1., 2. tranzitivitása)  X→W 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 V→W tényleg fennáll. Ezután nézzük a Teljességi tétel érdemi bizonyítását: 2. állítás: F |  X→Y 74

19. tétel


Biz.: Feltétel szerint F|=X→Y, azaz az X→Y függés igaz mindenütt, ahol F érvényes. Az 1. állítás szerint r-ben igaz az X→Y 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 |  X→Y, 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 U→V∈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 |  X→A, ahol A∈Xi. i Az Állítás* szerint: F |  X→X van olyan U→V∈F, hogy U⊆Xi és A∈V. 1. X→Xi 2. Xi→U 3. U→V 4. V→A 5. U→A 6. X→U 7. X→A

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


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. U→V∈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|=X→A. Tehát • r-ben is igaz az X→A 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={AB→C, B→D, CD→E} 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


• X kulcs ⇔ X+(F)=R, de (X\A)+(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


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


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 X→Y függést az X→Ai-kkel helyettesíthetjük, ∪Ai =Y); 3. G-bÿl nem hagyható el függés, azaz ha X→A∈G, akkor X→A ∉ (G\{X→A})+, vagyis a többi függésbÿl X→A nem állítható elÿ. 4. a G-beli függések baloldalai minimálisak, nem csökkenthet k: ha X→A∈G és Y⊂X valódi részhalmaz, akkor Y→A ∉G minden Y-ra.

80

25. tétel


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. X→Y ∈G, Y=A1,A2,...,Ak helyett X→A1, ahol i =1,...,k (a felbontási és únió szabály értelmében) 3. Veszünk egy X→A ∈G függést. Ha X→A ∈ (G\{X→A})+, akkor X→A-t eldobjuk, ellenkezÿ esetben megtartjuk. Praktikusan ez a teszt a következÿképp oldható meg: • A ∈X+(G\{X→A}) esetén lehet a függést eldobni, és • A ∉X+(G\{X→A}) 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 X→A ∈G és Y⊂≠X, akkor Y→A∉G. Megj.: ha Y→A∈G és Y⊂X, akkor X→A ∈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 |X\Y|=1. Teszt: A ∈Y+(G) teljesül-e? • igen: ekkor X→A 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 X→A 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 = {AB→C, A→B, B→A} 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. AB→C nem elhagyható, mert AB+({A→B,B→A}) = AB és C∉AB. 81

25. tétel


4. A→B, B→A ./ AB→C nem minimális baloldalú A+(F) = ABC, és C ∈ ABC, ezért AB→C helyett vehetjük az A→C-t. Tehát G={A→B, B→A, A→C} Megj.: mivel A és B szerepe szimmetrikus, ezért G' = {A→B, B→A, B→C}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 X→A∈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év→Cí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. A→B ÿ A szuperkulcs 2. B→A ÿ 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


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 X→A függés, ahol X nem szuperkulcs. ρ = (R1=XA, R2=R\A) 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,R\A) valódi felbontás, mivel • R\A 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=R\A) 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 + X→A ∈ 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ék→CímÁr,Név→Cí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árgy→Tanár, IdÿTanár→Terem, IdÿDiák→Terem, IdÿTerem→Tárgy, TárgyDiák→Jegy}

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árgy→Taná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ÿ


TárgyDiákIdÿ kulcs: DiákIdÿ


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 U→B ∈ 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 X→Y ∈ F függés úgy, hogy X⊆U és Y¬⊆U. 84

25. tétel


Legyen A egy tetszÿleges eleme Y\U-nak, vagyis A∈Y\U. Ekkor megállapíthatjuk, hogy: • egyrészt az X→A nem triviális függés (A∉X, mert A∉U), • másrészt X→A ∈ 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árosUtca→Irányítószám, Irányítószám→Város} Ez az (R,F) séma nem BCNF, pl. az Irányítószám→Vá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árosUtca→Irá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ám→Vá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


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 X→A ∈ 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 = (A→B, B→C, C→D, D→A) azaz minden mindent meghatároz, tehát ez lényegében egy egyoszlopos mesterséges reláció nem gyakorlati példa. Nyilván D→A ∈ F+, mert D→A ∈ F is teljesül. Ellenÿrizhetÿ a vetületeken is, mint D→C, C→B, B→A 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


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 X→Y függést az X→Ai-kkel helyettesíthetjük, ∪Ai =Y); 3. G-bÿl nem hagyható el függés, azaz ha X→A∈G, akkor X→A ∉ (G\{X→A})+, vagyis a többi függésbÿl X→A nem állítható elÿ. 4. a G-beli függések baloldalai minimálisak, nem csökkenthet k: ha X→A∈G és Y⊂X valódi részhalmaz, akkor Y→A ∉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. X→Y ∈G, Y=A1,A2,...,Ak helyett X→A1, ahol i =1,...,k (a felbontási és únió szabály értelmében) 3. Veszünk egy X→A ∈G függést. Ha X→A ∈ (G\{X→A})+, akkor X→A-t eldobjuk, ellenkezÿ esetben megtartjuk. Praktikusan ez a teszt a következÿképp oldható meg: • A ∈X+(G\{X→A}) esetén lehet a függést eldobni, és • A ∉X+(G\{X→A}) 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 X→A ∈G és Y⊂≠X, akkor Y→A∉G. Megj.: ha Y→A∈G és Y⊂X, akkor X→A ∈G teljesül a reflexivitás miatt. Z: átmenet az X és az Y között

87

25. tétel


Y

Z

X

Nézzük meg azon Y ⊆ X halmazokat, melyekre |X\Y|=1. Teszt: A ∈Y+(G) teljesül-e? • igen: ekkor X→A 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 X→A 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 = {AB→C, A→B, B→A} 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. AB→C nem elhagyható, mert AB+({A→B,B→A}) = AB és C∉AB. 4. A→B, B→A ./ AB→C nem minimális baloldalú A+(F) = ABC, és C ∈ ABC, ezért AB→C helyett vehetjük az A→C-t. Tehát G={A→B, B→A, A→C} Megj.: mivel A és B szerepe szimmetrikus, ezért G' = {A→B, B→A, B→C}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 = {X1→A1,...,Xk→Ak}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. Xi→Ai ∈G látható az Ri = XiAi darabban. 88

25. tétel


2. A kapott függÿleges darabok 3NF-ek. X kulcs ÿ nincs benne semmilyen függés ./ Tfh. XiAi nem 3NF, és ennek Y→B ∈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. Y→Ai ∈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 Y→B 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 U→Ai ∈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. H→R∈G+ (és H+(G) = R). Ezért van olyan U→B ∈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 U→B∈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


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! (B.J.) 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[R\XY] = t4[R\XY], t2[R\XY] = t3[R\XY]. Jelölés: X Ábrázolva: X

> Y

Y

R\XY

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ó. (R\XY = 0) • Ha X→Y=R, akkor X > Y.

91

Munkatárs Aniela Lalagé Aniela

25. tétel


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.: {X→Y}|= X > Y vagy {X→Y}| X > Y {X > Y}| X > (R\XY) t1, t2-höz t4t3 lesz jó: X

Y

R\XY

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. R2\R1 ∈F+. ρ pontosan akkor h séges, ha R1∩R2 >

).

Megj.: Mivel R1∩R2 > R1\R2 ∈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


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\(X\Y). (Megjegyzés: > -ra nincs únió és felbontási szabály! Valamint ha Y=A∈X, akkor R2=X\A.) R1 valódi, mert XY≠R. R2 is valódi, mert Y≠⊂X. R1∩R2 = XY∩(R\(X\Y)) R1\R2 = R\XY

X

Y

R

X > R\XY -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


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


• 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


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


Ez egy olyan gráf, melynek pontjai az aktív T-k. Ti→Tj é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


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 T1→T2 (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 T1→T2 (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


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 T1→T2 é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


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


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


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)<...
25. tétel


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


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


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ár→idÿ 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


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


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


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


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: (, begin). 2. T írja A-t. Formálisan: (, 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: (, olvasott A értéke). 4. T eléri kész pontját. Formálisan: (, commit). 5. T abortál. Formálisan: (, 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 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


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

1. Az adatbázis fogalma, fontosabb összetevÿi, felhasználási módjai

Recommend Documents