Informatika | Adatbázisok » BME-VIK Adatbázisok vizsgatételek

Adatbázisok Tartalomjegyzék ADATBÁZISOK BME, VIK MI 3. évf, 1999 tavaszi félév elõadó: dr. Rónyai Lajos TARTALOMJEGYZÉK1 I. BEVEZETÉS 1. Az adatbázis fogalma, fontosabb összetevõi, felhasználási módjai 2. Az adatbázisok fejlõdési trendjei II. ADATMODELLEZÉS 3. Az ODL-modellezõ nyelv 4. Az egyed-kapcsolat modell 5. Egyed-kapcsolat sémák átalakítása relációs, hálós és hierarchikus sémákká III. ADATBÁZISOK FIZIKAI SZERVEZÉSE 6. Az alapvetõ fizikai tárolási szerkezetek összehasonlítása 7. Hashelés és ritka indexes szervezési módszerek 8. B-fák és sûrû indexek IV. A HÁLÓS ADATMODELL 9. Tárolási struktúrák és sémakezelés hálós adatbázisokban 10. Lekérdezés és adatkezelés hálós adatbázisokban V. A HIERARCHIKUS ADATMODELL 11. Sémakezelés és tárolási struktúrák hierarchikus adatbázisokban 12. Lekérdezés és adatkezelés hierarchikus adatbázisokban VI. A RELÁCIÓS ADATMODELL 13. Relációs algebra, relációs

teljesség 14. Sor- és oszlopkalkulus VII. RELÁCIÓS LEKÉRDEZÕ NYELVEK 15. Relációs lekérdezõ nyelvek (ISBL, QBE) 16. A QUEL lekérdezõ nyelv 17. Az SQL adatbáziskezelõ nyelvi felület VIII. RELÁCIÓS SÉMÁK TERVEZÉSE 18. Funkcionális függések 19. Lezárások, fedések, vetített függések 20. Normálformák (3NF, BCNF), normalizálás 21. Többértékû függések, 4NF IX. TRANZAKCIÓKEZLÉS 22. A tranzakciókezelés alapfogalmai: zárak, pattok, sorosíthatóság, egyszerû tranzakció modell 23. Az RLOCK/WLOCK-modell Hierarchikus szerkezetek zárolása 24. Idõbélyeges módszerek egy processzoros környezetben 25. Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 26. Elosztott tranzakciók Zárképzési technikák 1 A tartalomjegyzékben a fejezetek számai a vizsgára kiadott tételsorban szereplõ tételek sorszámait jelentik. Az észrevételeket a szerzõ (Bognár Júlia) a következõ e-mail címen várja: s8629bog@ural2.hszkbmehu 1

Adatbázisok Tartalomjegyzék 27. Elosztott "Kész"-protokoll, blokkolás 28. Relációs kérdések kiértékelése; általános optimalizálási elvek, algebrai optimalizálás 2 1. tétel módjai Az adatbázis fogalma, fontosabb összetevői, felhasználási Az adatbázis fogalma, fontosabb összetevői, felhasználási módjai 1. tétel módjai Az adatbázis fogalma, fontosabb összetevői, felhasználási 3. A DBMS vázlatos modellje sémaműveletek lekérdezések 1. Adatbáziskezelő rendszer (DBMS - DataBase Management System) "lekérdezés" processzor tranzakciókezelő 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. 2. A DBMS felhasználásával szembeni követelmények 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. 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.) 3. Hatékony tárolás,

kezelés, hozzáférés 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). 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. adatműveletek 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: a.) lekérdező nyelven (QL) megfogalmazott kérdésekkel (pl SQL), vagy b.) 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: (1.) 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!) (2.) 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 1. tétel módjai Az adatbázis fogalma, fontosabb összetevői, felhasználási 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 SELECT név FROM ügyfél WHERE egyenleg < 0 AND nemzetiség = DOGON 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). 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, 1. tétel módjai Az adatbázis fogalma, fontosabb összetevői, felhasználási 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. 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 folyamat Szerver folyamat 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ó 4. A DBMS-sel kapcsolatos tevékenységek szintjei 1. Naiv felhasználó Egyszerű lekérdezéseket intéz a rendszerhez vagy alkalmazói programokat indít. 1. tétel módjai Az adatbázis fogalma, fontosabb összetevői, felhasználási 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. 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. (Itt húzhatunk egy képzeletbeli vonalat, mert nagy az ugrás a szakmai felkészültségben:) 4. DBMS-megvalósító Tudja, hogyan kell DBMS-t készíteni, ami már komoly, specializált tudást igényel. 5. Amivel mi foglalkozunk 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) 2. Programozás: ORACLE/SQL és alkalmazása (a Szglabor 6 keretében) 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. tétel Az adatbázisok fejlődési trendjei 2. tétel SELECT termék FROM termelő WHERE mennyiség > 100 Az adatbázisok fejlődési trendjei Az adatbázisok fejlődési trendjei Mi jelenjen meg a végeredményben (melyik oszlop)? Honnan vegyük az adatokat (melyik táblából)? Mi a feltétel (melyik sorok kellenek)? A szelektor kérdés eredménye a "bivalytej" lesz, vagyis az SQL jelen esetben olyan sorhalmazt (strukturált adathalmazt) ad vissza, amely egy

elemből áll (feltéve, hogy a tábla első 3 sorát nézzük csak). 1. A kezdetek Az első DBMS termékek a 60-as évek végén jelentek meg. Ezek a file-kezelőkből alakultak ki, azok szerves folytatásaként. Az első rendszerek sajátosságai: • sok kis adatelemmel dolgoztak • nagy számú, de egyedenként kevés adatot érintő művelettel dolgoztak. Pl.: repülőjárat-helyfoglalás, banki rendszerek, számlázás, vállalati nyilvántartások. Az első adatmodellek • Hierarchikus modell: kiszorulóban van, ami részint fogalmi gyengeségének következménye. • Hálós modell: szorosan kötődik a COBOL nyelvhez. A modell kezelésére a CODASYL szabvány tartalmaz ajánlásokat. A hálós modell előfordul magyar banki rendszerekben is. 2. Egyre kisebb rendszerek: ez az irányzat a PC-knek, a munkaállomásoknak és a relációs megközelítésnek az ötvözete. A rendszerek ugyan "kicsik", de egyre nagyobb mennyiségű adatot kezelnek. Fontos tényező

bennük a relációs adatbázis "felszíni", kezelői egyszerűsége 3. Egyre nagyobb rendszerek: ezek a tipikusan terra byte-os (1012 byte) alkalmazások, melyek nagy szervezetek adatait kezelik. Bonyolultabb adatformákat használnak (például digitalizált filmek tárolhatók egy-egy rekordban). A DBMS-ek fizikai eszközei: • elsődleges tárolás: belső memória; • másodlagos tárolás: lemez (-köteg), elérési ideje 10-20 msec; • harmadlagos tárolás: távoli tárak, CD, elérési idejük pár sec. Megemlítendő még az adatbázis-kezelésben a párhuzamos feldolgozás is, mely • cél-architektúrákon, -gépeken, ill. • elosztott rendszereken, bonyolult algoritmusok segítségével valósul meg. 2. A közelmúlt és jelen 1. Relációs adatmodell: E F Codd 1970-es dolgozata - melyben a relációs adatmodellezés alapjait dolgozta ki - forradalmi elveket fektetett le a DBMS-ekkel kapcsolatban. (Az IBM árult először relációs rendszereket.) A

modellben • az adatokat relációk (síkbeli táblák) formájában képzeljük el; • a lekérdezés magas szintű nyelven zajlik (Ma főleg az SQL-en). Pl.: TERMELŐ tábla NÉV Napsugár Kft. Napsugár Kft. Kunság Rt. CÍM Fő u. 33 Fő u. 33 Ó u. 12 TERMÉK cibere padlizsán bivalytej MENNYISÉG 4 99 1100 . . . . . . . . . . . . Az összetartozó adatnégyeseket táblázatban tároljuk. A sorok rekordoknak, az oszlopok névvel és típussal rendelkező attribútumoknak felelnek meg. Egy SQL kérdést a következőképpen lehet megfogalmazni: 3. Adatbázisok közeljövője 1. Típusok, osztályok, objektumok megjelenése DB környezetben Kialakulásának oka az objektumos módszerek és nyelvek térhódítása a programozásban. (Pl. SmallTalk, C++, Java) Objektumorientált (OO) terminológia, fontosabb alapfogalmak: • gazdag típusrendszer – elemi típusok: (egészek, lebegőpontos számok, mutatók, stringek, stb.) – rekordstruktúrák –

kollekció-típusok: ! lista, a tömb, egyszerű típusú elemek kollekciója, vagy ! halmaz (pl.: {2,7,6}={2,6,7}) - az elemek sorrendje közömbös, ! multihalmaz (pl.: {2,7,6,2}={2,2,6,7}) - megengedett az elemek ismétlődése is • osztályok, objektumok Egy osztályt így írhatunk le: osztály = típus + tulajdonságok típusok függvények (metódusok) Az objektumok az osztályok konkrét előfordulásai, melyeket az OID - az objektumazonosító - különböztet meg egymástól, így rendkívül fontos tényező. Az OID egy 2. tétel Az adatbázisok fejlődési trendjei hagyományos rendszerben egy mutató a memóriabeli előfordulásra, de a mai DBMS-ekben lehet összetettebb szerkezetű is, hiszen meg kell mutatnia, hogy az objektum mely elosztott site-on helyezkedik el, azon belül hol található, stb. Az adatbázis szemlélettel - mely szerint az egyforma rekordok egyszer tárolódnak szemben az objektumos szemlélet legfontosabb különbsége az, hogy

létezhetnek egyforma objektum-példányok. • metódusok: az egyes osztályok objektumain ható függvények. Pl.: egy személy életkorát a mai napon megadó metódus: C osztály := Személy mai Életkor (a: Személy); Az osztály objektumait csak metódusokon keresztül érhetjük el, ezzel rendeztük a hozzáférések rendszerét. Ez a mód a "tokba foglalás" (encapsulation); a fenti példában azt jelenti, hogy a C osztály objektumait csak a C metódusain keresztül használ(hat)juk. • osztályhierarchiák, öröklődés: egy C osztály lehet a D osztály alosztálya, "specializációja", vagyis C örökli D tulajdonságait és metódusait. Minden ügyfél egyben személy is. Pl.: C = Ügyfél D = Személy A fenti példában látott öröklődés csak akkor hasznos, ha adatbázisunkban nem minden személy ügyfél (mert ekkor nem kéne a kettőt megkülönböztetni és elég lenne csak az Ügyfél osztályt megtartani). } 2. Megszorítások és

triggerek Ezek egy DBMS aktív elemei, melyek mindig elérhetőek és ha kell, végre is hajtódnak. A modern DBMS-ekben igen sok aktív elem található. a.) megszorítás (kényszer, constraint): olyan, a DB-re vonatkozó állítás, amelynek igazságát a rendszer megköveteli, kikényszeríti. Ilyen megszorítások a rendszerben deklarálhatók. Pl.1: a Személynél a személyi szám a kulcs, amivel az emberek megkülönböztethetők egymástól. Megszorítás: két személynek nem lehet azonos személyi száma Az azonos személyi szám ellenőrzése minden új rekord felvételénél megtörténik, és egyezés esetén a rendszer hibajelzéssel válaszol, a rekord ekkor nem felvehető (fel kell kínálni a javítás lehetőségét). Pl.2: megszorítás az is, ha a banki egyenleg nem mehet 0 alá Ezek a megszorítások a DB konzisztenciájában fontos szerepet játszanak. b.) trigger: kódrészlet, amely bizonyos feltétel(ek) bekövetkezésekor automatikusan végrehajtódik.

Triggerekkel az alkalmazásokhoz kapcsolódó teendők könnyen elvégezhetők (A triggerek hasonlítanak az operációs rendszerek - pl. a UNIX - démonjaihoz) Pl.: – járat törlésekor automatikusan figyelmeztetni kell az operátort; – havi zárás adatgyűjtését trigger váltja ki a nap végén vagy a hónap utolsó napján. 3. Multimédia-adatok kezelése A multimédia tárgykörébe sokféle adatforma - pl. video, audio, radarkép, szöveg - esik Jellemzően • sokkal nagyobb és összetettebb adatokat, • nehezebb elemi műveleteket kell kezelni (pl. két egész szám összehasonlítása egyszerű, de két (bit)képé már jóval nehezebb), 2. tétel Az adatbázisok fejlődési trendjei • esetenként pedig óriási rekordokat kell feldolgozni. Mindez szemléletváltáshoz vezet, így például egy teljes könyv is tekinthető egyedi rekordnak. 4. Adathalmazok egységesítése A törekvés alapja az, hogy szeretnénk sokféle, sok helyen lévő adatot egységesen

látni, ami nagyon nagy munkát jelent. Tipikusan ez az elv vezeti a WorldWideWeb-et, melynek böngészői egységes látásmód kialakítására törekszenek. Másik jó példa egy nemzetközi nagyvállalat, melynek különböző részlegei vannak (pl. az amerikai Sears cég). Gondot okozhat az, hogy az egyes részlegek eltérően kezelnek adatokat így például már mértékegységeket használnak Egyetlen közös adatbázissal többnyire nem lehet megoldani a problémát, ehelyett egy egységes felületet kell tenni a részlegek fölé: ezáltal több DB tartalmát kezelik egy nézetből. Az egységesítés ötlete az adattárház (repository): DB1 egyirányú kapcsolat DB2 . . . DBn adattárház időszakos átalakítás, egységesítés Például az éjszaka folyamán a nagyvállalat egységeinek különböző mértékegységekben nyilvántartott árukészletét közös egységbe számolják át. Ezt a tájékoztató adatmennyiséget az adattárház bizonyos ideig - pl. egy

hétig - tárolja Erre a rendszerre jellemző tehát a batchjellegű feldolgozás Mivel az adattárházban óriási adathalmazt kezelnek egy felület alatt, ezért nagyon fontos a körültekintő elemzés és tervezés - hogy az adatokat hatékonyan kezelhessék. Ehhez a témakörhöz kapcsolható az adatbányászat (data mining), ami különböző statisztikai, és mesterséges intelligencia által adott eszközökkel és módszerekkel igyekszik összefüggéseket (dependencies) találni a nagy adathalmazokban. Például egy áruházi adatbázis sokat elárul a fogyasztói szokásokról. 3. tétel Az ODL-modellező nyelv 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.) 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 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. obj. DB a valóság egy darabja relációk E/K 2. Az ODL (Object Definition Language) módszertan Az ODL elemei: 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. 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.) Az osztálydeklaráció formája az ODL-ben:

interface < Osztálynév > { < jellemzők listája > }; Az "interface" kulcsszó az ún. osztálykonstruktor Példák 1. filmes példa Az adatmodellezés egyes eszközeinek kapcsolata és eredménye: ODL Az ODL-modellező nyelv – 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. Az ODL-modellező nyelv a valóság egy darabja 3. tétel relációs DB 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 3. tétel Az ODL-modellező nyelv • egy objektum képe ennek megfelelően: OID + {"Az erőszak vége", 1998, 122, színes} 3. tétel Az ODL-modellező nyelv 2. színészes példa

(kapcsolat a Színész oldaláról) relationship Set < Film > szerepel benne; reverse Film: szereplők; 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 mező típusa attribútumnév mező neve 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; 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 3. konkrét adatokkal a kapcsolatok így néznek ki: Film Berlin fölött az ég Távol s mégis közel Távol s mégis közel Columbo Színész Bruno Ganz Bruno Ganz Peter Falk Peter Falk

Tanulság: egy színész több filmhez is tartozhat, ill. egy filmhez több színész tartozik Kapcsolatok osztályozása Két osztály - pl. C és D - közötti kapcsolat lehet: a.) egy-több (sok-sok, N:N) típusú: egy C osztálybeli objektumhoz az adott kapcsolatra nézve a D-ből több tartozhat, és fordítva. köztük a "szereplők", "szerepel benne" kapcsolatok N:N típusúak Pl.: C = Film D= Színész 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.) } b.) 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 Cbelihez is tartozhat). köztük a "gyártó" kapcsolat N:1 típusú Pl.: C = Film D = Stúdió 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ó D-nél. } c.) egy-több (egy-sok, 1:N) típusú: ez az N:1 kapcsolat fordítottja d.) egy-egy (1:1) típusú: egy C osztálybeli objektumhoz az adott kapcsolatra nézve legfeljebb egy D-beli tartozhat, és fordítva. köztük az "elnök" kapcsolat 1:1 típusú, feltéve, hogy egy stúdiónak Pl.: C = Stúdió 3. tétel Az ODL-modellező nyelv D = Személy 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. 3. tétel Az ODL-modellező nyelv 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; relationship Színész színész; relationship Film film;} 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ó. Alaptípusok: ide tartoznak az 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) Típuskonstruktorok: ezek adják az ODL építkezési szabályait. Tegyük fel, hogy T egy típus 1. Set < T > típus értéke T típusú elemek véges halmaza Pl.: Szereplők halmaza a Filmnél 2. Bag < T > típus értéke T típusú elemek véges multihalmaza, vagyis a halmazban lévő elemek multiplicitással rendelkezhetnek (az ismétlődés megengedett). Akkor használják, amikor a Set nem alkalmazható. 3. List <T > típus értéke T típusú elemek véges - esetleg üres - listája A Set-től annyiban különbözik, hogy benne fontos az elemek helye, sorszáma. Pl.: string = List < char > 4. Array < T, i > típus értéke T típusú elemek i-hosszú tömbje 5. Rekordkonstruktor Adott a T1, ., Tn (attribútum) típus-sorozat és az f1, ., fn mezőnév-sorozat Ekkor a Struct N {T1 f1, T2 f2, . , Tn fn} egy N nevű, n komponensű rekordstruktúra Az i. komponens (mező)

típusa T1, neve fi Pl. A Színésznél a Cím egy kétkomponensű struktúra (rekord) Az 1.-4 típuskonstruktorok az ún kollekció-operátorok Ezek valamilyen homogén összességet definiálnak, amelyekben eltérő lehet az, hogy megengednek-e ismétlődést vagy hogy fontos-e a pozíció, stb. Az attribútumok típusa lehet: • atomi típus, • atomi típusokból álló struktúra, • vagy egy, az előzőekre alkalmazható konstruktor 1.-5 közül Példa: Array < Struct T . {string név, integer tömeg}, 3 > 3. tétel Az ODL-modellező nyelv A kapcsolat típusa lehet: • interface típus • egy, interface típusra alkalmazott konstruktor 1.-4 közül 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.) 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: 3. tétel Az ODL-modellező nyelv 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ó. 3. tétel Az ODL-modellező nyelv • 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 1. filmes példa interface Film (key (cím, év)) {-}; 2. 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; 3. Adatmodellezési alapelvek 3. tétel Az ODL-modellező nyelv 1. Valósághű modellezés • a fontos adatelemek és •

a fontos kapcsolatok is legyenek benne a modellben! 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: • 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. tétel Az egyed-kapcsolat modell 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.) 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ő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 Az egyed-kapcsolat modell 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 egyed-kapcsolat modell a valóság egy darabja 4. tétel 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 obj. DB év Film a valóság egy darabja relációk relációs DB hossz szalagFajta E/K 2. Az Egyed/Kapcsolat (E/K) modell Nevezik még Tárgy/Kapcsolat, vagy Entitás-relációs modellnek is. 3. Kapcsolatok 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 ) 4. tétel Az egyed-kapcsolat modell 4. tétel Az egyed-kapcsolat modell Rajzban a kapcsolat nevét rombuszba foglaljuk: 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. E1 R Em E2 . . E3 . Tapasztalat: kapcsolatnak is lehet attribútuma. (Bár ez új egyedhalmaz felvételével kiváltható.) Példák 1. a Film-Színész kapcsolat: cím év Film hossz név Szereplők lakcím Színész 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 szalagFajta R E2 N:1 kapcsolat Megj.: az ODL-ben a lakcím rekordként volt definiálva Itt ez nem megy! E1 2. Nemzetközi munkamegosztás R E2 Ország Termel E1 Termék Egy cég termékeit több országban is termelheti / értékesítheti. Ez egy m=3 komponensű kapcsolat. 3. a filmes példa

továbbfejlesztése gázsi Film Szerződés Stúdió Színész Pl.: Gyermek -Anya kapcsolat ("anyja") csak egy nyíl N:N kapcsolat Cég Pl.: Személy Stúdióvezetó kapcsolat ("elnök") mindkét végén nyíl 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. 4. tétel Az egyed-kapcsolat modell R E2 => Az egyed-kapcsolat modell Öröklődés, alosztályok az E/K modellben Tfh. az E1 egyedhalmaz szűkítése az E2-nek Ezt jelölhetjük ezekkel: Sokágú kapcsolat átalakítása kétágú (több-egy)

kapcsolattá Menete: E1 4. tétel E1 is-a vagy az egy is-a vagy az egy . . E1-k . R E2 E2-k . Ek-k Példa: Film, Rajzilm, Krimifilm 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 Film Szerződés S Stúdió magyar Az alárendelt egyedhalmaz örökli felmenői attribútumait. Egy "objektum" nem feltétlen egy "osztályyhoz" tartozik. . . Sz angol F cím év szalagFajta 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.

gázsi 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. 4. tétel Az egyed-kapcsolat modell Pl. a Filmet a címe és a gyártási éve azonosítja, tehát itt a (cím,év) pár az elsődleges kulcs (amit aláhúzással jelölünk). év hossz szalagFajta 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. Gyártó Elnök Része Flotta <= 3 F R 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. A kapcsolat fokának korlátozása Pl.: Hajóraj E szám Stúdió Vezeti 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): Példa: szervezeti egységek részegységekből - csoportokból - épülnek fel. A csoportokat számukkal írjuk le (ez egyetlen attribútumuk): 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ó Egy több komponensű kapcsolat átalakításakor a kapcsoló rekordot így jelöljük: • az E

azonosítására szolgáló F-beli attribútumok elemei F kulcsának is. 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 Az egyed-kapcsolat modell Ennek az azonosításban résztvevő kapcsolatait pedig így: Film cím 4. tétel (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. 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 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; 4. tétel Az egyed-kapcsolat modell • 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. 5. tétel sémákká Egyed-kapcsolat sémák átalakítása relációs, hálós és hierarchikus 5. 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 . R(A1,.,As, B1,,Bl,, S1,,St) 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. 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 1 ez egy innen onnan összeszedett tétel a témával kapcsolatban ezt találtam! 5. tétel sémákká Egyed-kapcsolat sémák átalakítása relációs, hálós és hierarchikus 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. 5. tétel sémákká Egyed-kapcsolat sémák átalakítása relációs, hálós és hierarchikus szcím Szállító SZ Á Szállító Egyed-kapcsolat sémák átalakítása relációs, hálós és hierarchikus 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

Hálós E/K sznév 5. tétel sémákká 2. Hierarchia -> hálós séma Ár TERÁR Ár egys ár Termék TERREND SZEMREND C Személy Rendelés cím egyenleg 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 B A D C B A C vA D vA vC B E vD vB D 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.) menny Megrendelő név A Rendelés termék szám B C D E vE 6. tétel Az alapvető fizikai tárolási szerkezetek összehasonlítása 6. tétel Az alapvető fizikai tárolási szerkezetek összehasonlítása Ez a struktúra kizárólag fix hosszúságú mezőkkel így írható le: Az alapvető fizikai tárolási szerkezetek összehasonlítása 1. Alapfogalmak

szerző cím fix fix . 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 fej rek1 . rekn • 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 – 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 mező2 fix fix . 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: blokk / rekord • szöveg mutató szöveg maradék • mutató (pointer): bejegyzés, ami egy blokk / rekord címét tartalmazza • Cím Év . Cím szerző cím szöveg fix fix változó A rekordban szerepelhetnek azért fix hosszúságú mezők is, ha ezek hosszára található valamilyen ésszerű felső korlát. . 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: . – 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. Film Szereplő1 Év Film . Szereplő mutató . Szereplő-lista 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: 6. tétel Cím Év . Az alapvető fizikai tárolási szerkezetek összehasonlítása 6. tétel Film Szereplő1 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. . 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). • A sikeres keresés általánosan a blokkok felét érinti; • a sikertelen keresés általánosan az összes blokkot megnézi. Az alapvető fizikai tárolási szerkezetek összehasonlítása 7. tétel Hashelés és ritka indexes szervezési

módszerek Hashelés és ritka indexes szervezési módszerek 7. tétel Hashelés és ritka indexes szervezési módszerek Ö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 1. Adatbázisok alapvető fizikai szervezési elvei 0 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 1 1 azon rekordokat tárolja, melyekre h(K) = 00. vödör1 00. mindegy 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. 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) Kezdőállapot: 0 1 vödör1 0. A rendszer fenntart egy-egy vödröt a 0val és 1-gyel kezdődő hash-függvényű lapoknak. 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 Ábrázolva: 0 . vödör . . 0 . i. . . . B1 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 0 1 1 vödör3 1. vödör1 00. 0 1 vödör21 010. vödör22 011. 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). 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 7. tétel Hashelés és ritka indexes szervezési módszerek 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. . . . 111. d 3 vödör d 2 vödör 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: 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 Fő állomány Rekordok rendezettségi sorrendje (a sorrendben

lehetnek, sőt, jó indexeknél vannak is hézagok) Az index rekord felépítése: Kulcs Mutató általában egy lapra mutat (ez lehet az index [bonyolultabb] vagy a főállomány [egyszerűbb] egy lapja) index rekord m K rek1 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. Az index rekordokból - kis méretük miatt - sok férhet el egy lapon. Hashelés és ritka indexes szervezési módszerek K 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. 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. 7. tétel K rek2 . . a fő állomány egy lapja K az első (legkisebb) kulcsérték a mutatott lapon. 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, m-et követve megkapjuk az "esélyes lapot", ahol K rekordja talán megtalálható feltéve, hogy egyáltalán része a szerkezetnek. A ritka indexrekordok között - kihasználva a rendezettséget - kereshetünk (feltéve, hogy N db index lap van): • lineáris kereséssel: az index állományt az elejétől kezdve szekvenciálisan járjuk be. A keresés időigénye az index lapok

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

lapvágást okozhat. lapvágás új rek. • törlés: a lapvágás inverzét, a lapösszevonást kell alkalmazni szükség esetén. • tólig: a szervezés támogatja ezt a műveletet, ami adott kulcs-értékek közötti rekordok kilistáztatására szolgál. igazi rekordkulcs Az indexelés fajtái: A stratégia következménye, hogy a lapok legalább félig telítve lesznek a főállományban. Ha a fő állomány tömör, akkor a fenti műveletek nehézségekbe ütköznek. Ezért találták ki a módszer statikus változatát (kötött rekordokra). 7. tétel Hashelés és ritka indexes szervezési módszerek b.) Egyszintes ritka indexelés - statikus változat Itt az index állomány előre elkészül; az index rekord pedig nem a főállomány egy lapjára, hanem egy "lap-oszlopára", listájára mutat. index állomány A B . Itt nincs szükség vágásra és összevonásra; a fő állomány rekordja nem mozdul és az index sem változik. . 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. További módszerek: (a köv. tétel anyaga) c.) Többszintes indexelés d.) Sűrű indexelés 8. tétel B-fák és sűrű indexek 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. 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. Index állomány 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.

8. tétel B-fák és sűrű indexek 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! Az index rekord felépítése: Kulcs Mutató rek1 rek2 rekn igazi rekordkulcs általában egy lapra mutat (ez lehet az

index [bonyolultabb] vagy a főállomány [egyszerűbb] egy lapja) . fő állomány A sűrű indexelés célja, hogy a kötött fő állományt felszabadítsuk: 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! Index állomány Index állomány Fő állomány A felső index állomány ritka indexe az alatta lévőnek. 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. A dinamikus többszintű indexek B-fákkal valósíthatók meg. Az index állomány szintek ún. gyökér szint index fát alkotnak: Index fa Fő állomány i. index szint utolsó index szint 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 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. 8. tétel B-fák és sűrű indexek 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ú 8. tétel B-fák és sűrű indexek 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. 9. tétel adatbázisokban Tárolási struktúrák és sémakezelés hálós Tárolási struktúrák és sémakezelés hálós adatbázisokban 9. tétel adatbázisokban Tárolási struktúrák és sémakezelés hálós 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 1. Bevezetés

sznév 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. szcím Szállító SZ Á Szállító Ár TERÁR Ár 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.) egys ár Termék TERREND Rendelés termék SZEMREND Egy - elvi és gyakorlati szempontból is nagy jelentőségű - klasszikus hálós adatbázis-kezelő rendszer az IDMS nevet viseli. Rendelés szám 2. A hálós adatmodell elemei Megrendelő I. 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 Személy menny 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 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. név cím egyenleg II. Hálós DDL 1. 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 9. tétel adatbázisokban Tárolási struktúrák és sémakezelés hálós 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 (szülő) MEMBER (gyermek) 2. 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 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ó Tárolási struktúrák és sémakezelés hálós Dolgozó Dolgozik Dolgozó DP Projekt átalakítva: Projekt A DP rekordban két mutató mező van. Az ORDER IS. sor folytatása lehet: – SORTED: a gyermekeken rendezési reláció adott, erre nézve rendezetten kell a gyűrű elemeit tárolni. (Pl egy szállítóhoz a termék-rekordok ár szerint növekvő sorrendben tárolódnak.) – FIRST: a gyermek a gyűrűben az első helyre kerül. – NEXT: a gyermek a kurrens pozíció utáni helyre kerül. – LAST: a gyermek a gyűrűben az utolsó helyre kerül.

SET SELECTION: új gyermek-rekord érkezésekor ennek értéke mutatja meg, hogy a gyermek gyűrűbe illesztése hogyan történjen meg. Két lehetőség: – MANUAL: ahogy tetszik, azaz a felhasználó dönt. Pl: SZ Á – AUTOMATIC: az új gyermek típusú rekord automatikusan bekerül egy gyűrűbe. Alesetek: ! THRU OWNER USING <kulcs>: tulajdonoson (apán) keresztül történik a beillesztés, valamilyen kulcsérték alapján. (Abba a gyűrűbe, melynek apját a kulcs azonosítja.) ! THRU CURRENT (<set-név>): a születő rekord a kapcsolat "kurrens", aktuális gyűrűjébe kerül. Megtartási kényszer (RETENTION) Azt mutatja meg, hogy egy gyermek mennyire vehető ki a kapcsolatból. Lehetőségek: • FIXED: a gyermek nem vehető ki a kapcsolatból, azaz a gyűrűből. A gyermek e gyűrűt csak törléssel hagyhatja el. Pl: esetleg TERÁR • OPTIONAL: nincs korlátozás, pl. ilyen a SZEMREND • MANDATORY: egyfajta átvihetőséget jelent, amikor a gyermek

típusú rekord átvihető másik gyűrűbe, de egyúttal nem létezhet gyűrű nélkül. Rezeda Kázmér Termék rend1 Ár 9. tétel adatbázisokban ár-rekord: érdemi rész A gyűrű séma szinten tervezhető. 2. Dolgozó-Projekt modell (lásd: 2 melléklet) rend2 . rendn sz mut t mut átlalában annyi mező van itt, ahány kapcsolatban gyermek az illető Mintapélda: az E/K - hálós átalakításnál látott modell DDL-szerű sémája (több részletet mellőzve): 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. 9. tétel adatbázisokban Tárolási struktúrák és sémakezelés hálós 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 SORTED. ORDER IS NEXT. OWNER IS SZÁLLÍTÓ. OWNER IS TERMÉK. MEMBER IS ÁR. MEMBER IS ÁR. SET SELECTION IS MANUAL. SET SELECTION IS AUTOMATIC ASCENDING KEY IS TNÉV. THRU OWNER USING TNÉV. RETENTION IS MANDATORY. RETENTION IS MANDATORY. (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 (DBTG) SET SZEMREND. ORDER IS LAST. OWNER IS SZEMÉLY. MEMBER IS RENDELÉS. SET SELECTION IS MANUAL. RETENTION IS OPTIONAL. 10. tétel Lekérdezés és adatkezelés hálós adatbázisokban Lekérdezés és adatkezelés hálós adatbázisokban 10. tétel Lekérdezés és adatkezelés hálós adatbázisokban • Rekord sablonok: minden T rekord típushoz

helyet jelent egy rekord leírására. Pl.: SZEMÉLY(NÉV, FIZETÉS, CÍM) Személy-keret: NÉV FIZETÉS CÍM külvilág DB 1. Bevezetés A hálós adatmodell a CODASYL DBTG (Comittee On Data Systems Languages - Data Base Task Group) bizottság munkájának eredménye. A CODASYL bizottság a 70-es években dolgozta ki a hálós adatkezelés alapelveit és foglalta össze a DBTG-ajánlásban. Az ANSI az ajánlást a 80-as években standarddá tette. A DBTG-ajánlás részei: • hálós DDL • DML és extra kiegészítések (például egy, a jó hatékonyságú DB-k létrehozásában fontos szerepet játszó hasznos adatszerkezet.) Most ezekről lesz szó Egy - elvi és gyakorlati szempontból is nagy jelentőségű - klasszikus hálós adatbázis-kezelő rendszer az IDMS nevet viseli. 2. A hálós DML A futtatási környezet egy nagyon szigorú interface által van meghatározva. Ez az UWA (Users Work Area), ami három részből áll: kurrencia mutatók rekord sablonok program

változók főleg COBOL változók, mivel a COBOL az ajánlás fő gazdanyelve. 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). Tehát a rekord sablon a rekord kitöltésére szolgáló közbülső hely; a rekord ezen

közbülső helyen keresztül kapcsolódik a DB-hez és a külvilághoz. Hivatkozás mezőre: Pl. SZEMÉLYFIZ vagy FIZ IN SZEMÉLY (egy más dialektus szerint). DML utasítások: a gyűrűkben való mászkálás bennük erősen támogatott. • GET • GET <rekordnév> • GET <rekordnév> <mezők> • GET <mezők> Ezek lényegében ugyanazt jelentik, ennek megfelelően a rekord, amire vonatkoznak, minden ugyanaz, csak az eredmény megjelenítése lesz más. A programkurrens alapján egyértelmű, hogy melyik rekordról van szó. A GET parancs-változatok jelentése: a CRU által mutatott rekord a saját sablonjába másolódik. A paraméterek csak hibaellenőrzésre szolgálhatnak • Az érdemi utasítások a kurrencia mutatókat kezelik. Erre szolgálnak a FIND utasítások: - itt X egy változó 1. FIND <rekordtípus> BY DBKEY X Pl.: X = CURRENT OF TERMÉK FIND TERMÉK BY DBKEY X. A FIND hatása: X mindennek kurrense lesz, amire csak nézve értelmes

lehet, valamint az általa elért rekord mindennek kurrense lesz, szintén, aminél ez értelmes (CRU, saját típusának és minden kapcsolatának kurrense). 2. FIND <rekordtípus> BY CALC KEY A kulcsmezők a típus sablonjából származnak. Írás a sablonba: SZEMÉLY.SZNÉV = Klopédia FIND SZEMÉLY BY CALC KEY GET Ez egy rekordtípuson belül a szokásos műveleteket jelenti, plusz mutatók mentén végzett mozgást is. Jellegzetes hálós műveletnek számít a nyilak mentén végzett navigáció 3. FIND OWNER OF CURRENT <kapcsolatnév>: a kapcsolatkurrens gyűrűjének a szülőjére mutat. 4. FIND {FIRST/NEXT}<rektípus> IN CURRENT <kapcsnév> USING <mezőlista>: A kitöltött mezők alapján (sablonból) szűr. Ha egy rekordtípus nincs a kapcsolatok között, de ennél is szeretnénk alkalmazni a NEXT és FIRST műveletét, akkor a megoldást a szinguláris halmaz (OWNER SYSTEM) felvétele jelenti. Itt a MEMBER (gyermek) rekordjai egyetlen

gyűrűt alkotnak Pl.: az összes személy egy gyűrűben fog szerepelni a következő utasítás hatására: SET MINDENKI OWNER SYSTEM MEMBER SZEMÉLY 10. tétel Lekérdezés és adatkezelés hálós adatbázisokban • Beillesztés: STORE <rekordtípus>. A T típusú sablon tartalma a DB-be kerül, és mindenek kurrense lesz, aminek csak lehet. Pl. r létező, T típusú rekord, CRU INSERT T INTO <kapcsolatnév1> . <kapcsolatnévn> Ezzel r bekerül a kapcsolatok kurrens gyűrűjébe. • Törlés: REMOVE T FROM <kapcsolatnév1> . <kapcsolatnévn> Ezzel r kikerül a kapcsolatokból. • Rekord törlése: DELETE <rekordtípus>. Itt a program-, és nem az apa kurrenciák szűnnek meg. (Ellenkező esetben a gyermekek árván maradhatnának) • Erős törlés: DELETE <rekordtípus> ALL. Ez rekurzíve töröl, ami azt jelenti, hogy az apa fiaira is rekurzíve meghívódik. Azon gyűrűket törli, melyeknek az apa a tulajdonosa A hálós DML

jellegzetességei • kurrenciák által vezérelt • "egyszerre egy rekord"-típusú nyelv, ebben az SQL-hez képest sokkal kényelmetlenebb, mert az képes táblát utasítás eredményeként visszaadni. 11. tétel adatbázisokban Sémakezelés és tárolási struktúrák hierarchikus 11. tétel adatbázisokban Sémakezelés és tárolási struktúrák hierarchikus Sémakezelés és tárolási struktúrák hierarchikus adatbázisokban És ugyanez hierarchikusan: a színész redundanciát hordoz A navigáció mindig fentről lefelé történik. Film 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. Színész Érdemes a gyökeret VRT-nek (virtuális rekordtípusnak) választani. VRT (virtuális rekordtípus) Színész Film VRT (virtuális rekordtípus) Általánosan: E1 e1,e2,. E2 f1,f2,. e2 e1 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: ORSZÁG rekordtípus kapcsolat TELEPÜLÉS f2 f4 A rekordok szintjén megjelennek a fák. Def.: Adatbázis rekord 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. 1. Hálós séma -> hierarchia Példa több-több kapcsolatra és hierarchikus megoldására: Szerepel f2 Á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: MEGYE Film rekordtípusok f1 Színész A A D 11. tétel B adatbázisokban Sémakezelés és tárolási struktúrák hierarchikus C B E vD vB C D E vE 11. tétel

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

virtuális: igen / nem • hol az eredetije VIRTUAL <rekordnév> IN <fanév> Példa: (3. melléklet) Fiók Ügynök 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 4. Hierarchikus DML (DL/I) köv tétel 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban 12. tétel <feltétel> ::= <rekordnév>.<mezőnév> Θ érték Θ ∈ {<,≤, >,≥,≠} elemi összehasonlító műveletek A feltételek kombinálhatók: AND, OR, NOT. 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. 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. 01 Ü É 3. Hierarchikus DML (DL/I) Elég hatékonyan működik, viszont bizonyos dolgokat elég nehéz benne kifejezni. Lekérdezések: • GET LEFTMOST <T rekordtípus> WHERE <feltétel> Egy konkrét adatbázis felfogható úgy, mint egy rekordokból álló irányított erdőt. Ebben az erdőben értelmes a "balról-jobbra" kérdés, de a feltétel nem lehet akármilyen. Típusfa: • Csak T-re és felmenőire (melyek ezen az úton vannak) tartalmazhat feltételt. ! T Lekérdezés és adatkezelés hierarchikus adatbázisokban 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. Vigyázni kell

azonban, mert a jobbra lépés során elhagyhatja a szülőt vagy akár magát a rekordtípust is. • GET NEXT <rekordtípus> Itt a jobbra lépés a típus megtartásával történik. WHERE <feltétel> itt is megadható Pl.: ! ! ! NEXT hatása: a szülő nem változik ! ! ! NEXT hatása: a szülő is megváltozik. 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. 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban 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. 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban 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 rekord-szinten 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 Rekord beillesztése: • A rekordot a sablonjában összerakjuk, • majd kiadjuk a következő utasítást: STORE / INSERT <rekordtípus> WHERE <feltétel> Az utasítás beilleszti a rekordot a

legbaloldalibb alkalmas helyre. Példa: Új ügyfelet adunk a csornai Nehagyd Dömének. ÜGYFÉL.ÜNÉV = "Zsebenci Klopédia" ÜGYFÉL.ÜCÍM = "Négyszögletű Kerek Erdő" INSERT ÜGYFÉL WHERE NÉV = "Nehagyd Döme" AND FCÍM = "Csorna" Rekord módosítása / törlése: A GET speciális formáját használjuk, ami egyben zárat is jelent. • GET HOLD: zárat teszünk a kiválasztott rekordra, melynek felszabadulásáig más nem férhet hozzá. • REPLACE: módosítás, ami a HOLD-dal képzett zárat is feloldja. • DELETE: törlés, a zárat ugyanúgy feloldja, mint az előbbi utasítás. Példa: 1. Az előző ügylet megnöveli Nehagyd Döme kötéseit A megfelelő adatbázisbeli módosítás így történhet: GET HOLD LEFTMOST ÜGYNÖK WHERE NÉV = "Nehagyd Döme" AND FCÍM = "Csorna" ÜGYNÖK.KÖTÉS = ÜGYNÖKKÖTÉS + 1000 REPLACE 2. Nehagyd Döme pályát változtat GET HOLD LEFTMOST ÜGYNÖK WHERE NÉV =

"Nehagyd Döme" AND FCÍM = "Csorna" Egy DB rekord tárolása történhet: 1. Preorder fonal szerint: r,a1,a2,b1,b2,c1,c2 r a1 a2 b1 a3 b2 c1 c2 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 jobb testvér r a1 0 a 2 b1 a 3 • 2 mutató / rekord; • de gyorsabb a navigáció. 13. tétel Relációs algebra, relációs teljesség Relációs algebra, relációs teljesség 13. tétel 2. A relációs adatmodell alapműveletei (EF Codd, 70) 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. 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: Példa: FILM R CÍM Óz . Relációs algebra, relációs teljesség É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 A a a b B a c c S A a a a b D a d c b R∪S A a a b a b ? a c c d b Ahogy a példában is látszik, előfordulhat, hogy az únióban hiányozni fog egy attribútumnév (oszlopfejléc). Az ismétlődő sorok általában nem megengedettek (pl: (a,a) ) az únióban, mivel a relációs világ értékorientált, és a redundanciát igyekszik kiiktatni ott, ahol lehet. • különbség (Jele: ) Adott két reláció: R és S. RS elemei R azon sorai lesznek, amelyek nem szerepelnek S-ben. RS örökli az R oszlopszámát, attribútumait, típusait. 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) Példa: az úniónál bemutatott R-re és S-re RS A b B c • direkt szorzat (Descartes-szorzat, jele: ×) Adott két reláció: R (k oszlopa

és m sora van) és S (l oszlopa és n sora van). R×S-nek (k+l) számú oszlopa lesz, amikor a direkt szorzat-képzés során R sorait kiegészítjük az S soraival az összes lehetséges módon. Tehát R×S-nek m!n számú sora lesz Formálisan: R(A1,.Ak) R×S(A1,.Ak,B1,,Bl) S(B1,.,Bl) 13. tétel Relációs algebra, relációs teljesség Példa: az úniónál bemutatott R-re és S-re k=l=2 k+l=4 R×S A a B a a c A a . b a . 2. hagyjuk el R többi oszlopát; 3. hagyjuk el az esetleges ismétlődéseket is 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)1) 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) D a b A a a 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. Szemantikája egyszerű: 1. vegyük az R Ai1,Ail oszlopait ebben a sorrendben; 1 σ, azaz szigma 13. tétel Relációs algebra, relációs teljesség 13. tétel Relációs algebra, relációs teljesség 13. tétel Példa: ΠA(R) Relációs algebra, relációs

teljesség D a b A a b A relációs alapműveletek relációkat adnak eredményül, ezért ezen relációs műveletek egymással kombinálhatók. Pl: σA<D(R×S), ez először egy Descartes-szorzást, majd egy szelekciót jelöl. 3. A relációs adatmodell további fontos műveletei • természetes illesztés (összekapcsolás, join) (Jele: ) Adott két reláció, R és S. Az természetes illesztés művelete bármely két halmazra értelmes operáció. R S kiszámítása attól függ, hogy melyek a közös attribútumnevek a relációkban: R(A1,.Ak,B1,,Bs) S(A1,.Ak,C1,,Cd) vagyis az Ai-k a közös attribútumnevek. – Az R×S-ből indulva vesszük azokat a sorokat, amelyekre igaz, hogy R.Ai=SAi – Az eredményt vetítjük rá R.A1,,RAk,C1,,Cd,B1,,Bs-re Tulajdonságai: – Az így kiadódó R S -nek (k+s+d) számú oszlopa lesz. – Örököl attribútumokat és típusokat is. – k=0 esetén egyszerű szorzatműveletet jelent. – 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 C a a b c 2 3 b S a x b S A a B a c B D 2 2 3 • Á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) Példa: R Az attribútumok öröklődése itt kétféle lehet. A C b b c Ebben az esetben tehát nem egyenlőségre, hanem általános műveletre végezzük el az illesztést. Példa: az úniónál megismert R-re és S-re R B a a a • félillesztés (Jele: ) Technikai szerepe van a lekérdezési optimalizátorokban (elosztott rendszerekben). R S = ΠR(R S). R.C<SC A a a A 2 AΘB • metszet (Jele: ∩) Adott két reláció: R és S. R∩S sorai azok a sorok lesznek, melyek R-nek és S-nek is sorai. Formálisan: R∩S=R(RS)=S(SR) R∩S x C 2 3 c 4 R S 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. 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Ő) 13. tétel Relációs algebra, relációs teljesség 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 S-nél. 13. tétel 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á). A1 A a a S B b c B b e C d e R S A a a B b c C d • 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. S A a a NULL B b c e E1 Em E2 R R(A1,.,As, B1,,Bl,, S1,,St) 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. 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 . . Bonyolultabb átalakítás: . C d diák tanár R(A1,.,Ak) Ak . Példa: R . 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. E Példa: R Relációs algebra, relációs teljesség Tanszék . . Beosztás NULL . Témavez. . 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ó. 14. tétel Sor- és oszlopkalkulus 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 t[i]-vel a t sorváltozó i-edik komponensét jelöljük. Példa: R Név Rezeda K. . Cím Fő u. . t=t(2)=(Rezeda K.,Fő u) t[1]=Rezeda K. t[2]=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) 14. tétel Sor- és oszlopkalkulus 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)}. 4. R és S különbsége (nem kell a k=s-et feltételezni!): RS={t(k); R(t)∧¬∃u(s)(S(u)∧u[1]=t[1]∧.∧u[k]=t[k])} 5. R és S direkt szorzata (k≠s): R×S={t(k+s); ∃u(k) ∃v(s)(R(u)∧S(v)∧t[1]=u[1]∧.∧t[k]=u[k]∧ t[k+1]=v[1]∧.∧t[k+s]=v[s])} 6. Szűrés, szelekció (σF): σA1<3∧A2=c(R) ={t(k); R(t)∧t[1]<3∧t[2]=c}. 7. Vetítés (Π): (m) (k) ΠA1,.,Am(R) ={t ; ∃v (R(v)∧v[1]=t[1]∧∧v[m]=t[m])} Megj.: A 2-7 műveleteknél nem lényeges, hogy R és S alapreláció legyen R={t, ϕ(t)}, S={u,ψ(u)}. Tétel: A relációs algebra műveletei - az előbbiek alapján - kifejezhetők sorkalkulus segítségével. Ezzel kaptunk egy relációs algebra sorkalkulus

átírási módot. Fordított irányban ez nem megy; a sorkalkulus tehát bizonyos értelemben erősebb, mint a relációs algebra. Megj.: Az, hogy egy reláció véges inputtal rendelkezik, öröklődő tulajdonság Ennek megfelelően a relációs algebra véges bemenethez véges kimenetet szolgáltat. A sorkalkulusra ez nem mindig igaz. Pl gondot okoznak a {t(k); ¬R(t)}típusú relációk (ahol R alapreláció), mert nagyon nagy méretű lehet az eredményük. Def.: Biztonságos formula DOM(ϕ)={ϕ-ben előforduló konstansok, értékek és a ϕ-beli alaprelációk értékei} ϕ megengedett formula. Arra törekszünk, hogy egy formula igazságértéke a DOM-beli értékek alapján eldönthető legyen. 14. tétel Sor- és oszlopkalkulus 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: 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.) 14. tétel 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 ekvivalens1

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. ----------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. 2. Oszlopkalkulus Az oszlopkalkulusban az ún.

oszlopváltozók egy mező értékét vehetik fel Ábrázolva: reláció A B . Sor- és oszlopkalkulus 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. 1 az ekvivalencia jele: ↔ 15. tétel Relációs lekérdező nyelvek (QBE) Relációs lekérdező nyelvek (QBE) 15. tétel Relációs lekérdező nyelvek (QBE) – 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] 1. A relációs lekérdező nyelvekről általában 2. Amit a QBE-ről tudni kell 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. 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. 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) 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; 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 kiírja a Kiss-ek neveit, címeit P. Több táblás példa: Rendelés Szám Név Kiss Termelő Tnév . P. Termék búza Mennyiség Termékné v P. búza Megadjuk az összes

olyan termelőnév-termék párt, ahol a Kiss nevű megrendelő rendelt valaha is az adott termékből. 2.2 A QBE lekérdezéseinek szemantikája (1.) A lekérdezés ciklikus az implicit sorváltozókra (ez a példában t1 és t2); (2.) A feltételek minden kiértékelésre ellenőrződnek Előbbi példánkból: t1.Név=Kiss t1.Termék=t2Terméknév 15. tétel Relációs lekérdező nyelvek (QBE) Példa: Rendelés Szám Név Kiss Termék zab zab P. Mennyiség x ≥x Azon zab-rendeléseket kapjuk, amelyekben a mennyiség nagyobb, mint a Kiss által rendelt minimális zab-mennyiség. 15. tétel Relációs lekérdező nyelvek (QBE) – 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. 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 2.4 A QBE néhány DML utasítása • Beszúrás: I. kerül a sorinformációs részbe Pl: Mennyiség TERMELŐ I. . P.ALL A Címet előre nem tudjuk; a feltehetőleg már meglévő információt kikerestetjük az adatbázisból. Pl.:

Rendelés Szám Név P.UN Termék brokkoli . P.ALL Azok nevét kapjuk meg - egyszeresen -, akik brokkolit rendeltek. Minden (Termék, Mennyiség) párt megkapunk. A "szokásos" számlaegyenleget) Ügyfél aggregációk is használhatók, például: (megkapjuk az összes Tnév Sasad Sasad Cím Cím Cím Terméknév kutyabenge Ár 50 • 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. Egyenleg P.AVGALL • Törlés: D. kerül a sorinformációs részbe Pl: 2.3 A QBE DDL elemei SZEMÉLY D. • 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 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).) 16. tétel A QUEL lekérdező nyelv 16. tétel A QUEL lekérdező nyelv 2.1 A QUEL DDL-je: adatleíró utasítások (DDS) 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. A QUEL relációsan teljes nyelv. A QUEL is beágyazható, tipikus gazdanyelve a C. Példa: ## RANGE OF E IS SZEMÉLY; ## RETRIEVE (X=E.NÉV, Y=ECÍM) WHERE EFIZETÉS=0; ## {Küldjünk X-nek zord

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

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

alkalmazottakon fut végig. Hivatkozások: ENÉV, ESZSZ, E:RÉSZLEGNÉV 16. tétel A QUEL lekérdező nyelv 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. [E összes komponense megjelenik] Pl.: RETRIEVE (EALL); RETRIEVE (E.NÉV, ERÉSZLEGNÉV); [csak a név és a részleg neve] RETRIEVE UNIQUE (E.FIZETÉS); [kiszűrjük a többször előforduló adatokat] Időleges relációk is kialakíthatók a RETRIEVE INTO kulcsszóval. Pl.: RANGE OF E IS SZEMÉLY; RETRIEVE INTO PASAS (PNÉV=E.NÉV, ) WHERE ENEM=hím; Itt az E.NÉV kifejezés ad értéket a PNÉV attribútumnak Aggregációk Ezek már a korábban megismert AVG, CNT, SUM, MIN, MAX. A különbség csak annyi, hogy a feltételvizsgálat aggregáción belülre tehető, sőt: csoportosításra is alkalmas. Pl.: RETRIEVE MAX(EFIZETÉS); RETRIEVE MAX(E.FIZETÉS WHERE ECÍM=Fő u); [GROUP BY] RETRIEVE MAX(E.FIZETÉS BY NEM); RETRIEVE MAX(E.FIZETÉS BY NEM

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

utasítások) • Törlés: DELETE Szerkezete: RANGE OF E IS . 16. tétel . DELETE E; WHERE ϕ A QUEL lekérdező nyelv [kiválasztjuk, hogy mit akarunk törölni] • Beillesztés: APPEND TO Szerkezete: APPEND TO SZEMÉLY(Kif1, .); – 17. tétel Az SQL adatbáziskezelő nyelvi felület 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. 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, SQLCODE1) Az SQL • szabvány, amelyet jelenleg csaknem minden relációs

adatbáziskezelő alkalmaz kisebb-nagyobb módosításokkal; • tömör, felhasználó közeli nyelv, alkalmas hálózatokon adatbáziskezelő szerver és kliensek közötti kommunikációra; • nem procedurális programozási nyelv (legalábbis a lekérdezéseknél).2 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 • Új reláció (tábla) létrehozása: CREATE TABLE <táblanév> (<oszlopnév> <típus> [NOT NULL] [,<oszlopnév> <típus> [NOT NULL], . ]); á d Ad bá i k b ói j 1998 33 ld l Az SQL adatbáziskezelő nyelvi felület Ha valamely oszlop definíciója tartalmazza a NOT NULL módosítót, akkor a megfelelő mezőben mindig valamilyen legális értéknek kell szerepelnie. • Új nézetek létrehozása: CREATE VIEW

<nézetnév> [(<oszlopnév> [,<oszlopnév> , . ])] AS <lekérdezés3>; 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. • Tábla törlése: DROP TABLE <táblanév>; • Nézet törlése: DROP VIEW <nézetnév>; • Tábladefiníciók

módosítása: ALTER TABLE <táblanév> [ADD | MODIFY] <oszlopnév> <típus>; – Az ADD egy új, NULL értékű oszlopot illeszt a táblához, – a MODIFY paranccsal pedig egy létező oszlop szélessége növelhető. • Indexek létrehozása: CREATE [UNIQUE] INDEX <indexnév> ON <táblanév> (<oszlopnév> [,<oszlopnév>, . ]); Tulajdonságok: – Az indexek a táblákban való keresést gyorsítják meg. – Az indexeket az adatbáziskezelő a táblák minden módosításánál felfrissíti. – Ha egy indexet a UNIQUE kulcsszóval definiáltunk, akkor a rendszer biztosítja, hogy az adott oszlopban minden mező egyedi értéket tartalmazzon. – Lehetséges több oszlopot egybefogó, kombinált indexek létrehozása is. – Az indexek létrehozásuk után a felhasználó számára láthatatlanok, csak a lekérdezéseket gyorsítják. – Indexeket azokra az oszlopokra érdemes definiálni, amelyek gyakran szerepelnek keresésekben. –

Index nélkül minden kéréshez be kell olvasni az egész táblát. De ha a keresési feltételhez van megfelelő index, akkor az adatbáziskezelő a diszkről csak a valóban szükséges sorokat olvassa be. – Az indexek akkor is gyorsítják a keresést, ha csak a keresési feltétel egy részére vonatkoznak. • Index törlése: DROP INDEX <indexnév>; 2.1 Az SQL DDL-je: adatleíró utasítások (DDS) 1 17. tétel *C lőf dí ó 2.2 Az SQL lekérdezései A lekérdezések általános szintaxiasa a következő: ezek definiálják az eredménytábla oszlopait SELECT <jellemzők> 17. tétel Az SQL adatbáziskezelő nyelvi felület ezek adják meg a lekérdezésben résztvevő táblák nevét FROM <táblák> [WHERE <logikai kifejezés>] ezzel válogathatunk az eredmény sorai között [GROUP BY <attribútumok>] ez rendezi egymás mellé az eredménytábla sorait [HAVING <attribútumok>] ezzel a csoportosítás révén keletkező

eredménysorokra kiválasztási feltételt írunk elő [ORDER BY <attribútumok>] ez határozza meg a megjelenő sorok sorrendjét 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 (/). 17. tétel Az SQL adatbáziskezelő

nyelvi felület • Jogosultságok definiálása GRANT [DBA | CONNECT | RESOURCES] TO <felhasználó> [, <felhasználó>, .] IDENTIFIED BY <jelszó> [, <jelszó>, .]; Ezzel a paranccsal az egyes felhasználóknak az adatbázishozvaló hozzáférési jogát szabályozzuk. A DBA jogosultság az adatbázis adminisztrátorokat definiálja, akiknek korlátlan joguk van az összes adatbázis objektum felett, nem csak létrehozhatják, módosíthatják, illetve törölhetik őket, de befolyásolhatják az objektumok tárolásával, hozzáférésével kapcsolatos paramétereket is. A RESOURCES jogosultsággal rendelkező felhasználók létrehozhatnak, módosíthatnak, illetve törölhetnek új objektumokat. A CONNECT jogosultság csak az adatbáziskezelőbe való belépésre jogosít. GRANT <jogosultság> [,<jogosultság>, .] ON <tábla- vagy nézetnév> TO <felhasználó> [WITH GRANT OPTION]; a megkapott jogosultság tobábbadható Ezzel a

paranccsal az egyes objektumokhoz (táblákhoz, nézetekhez) való hozzáférést szabályozzuk. A <jogosultság> az objektumon végezhető műveleteket adja meg 2.3 Az SQL DML-je: adatmódosító utasítások (DMS) • Tranzakciókezelés • Adatok bevitele INSERT INTO <táblanév> [(<oszlopnév> [,<oszlopnév>, . ])] VALUES (<kif1>[, <kif2>, .]); 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. Tulajdonságok: – Ha nem adjuk meg

az oszlopok nevét, akkor a tábla deklarálásánál megadott sorrendben minden mezőnek értéket kell adni. – Ha viszont megadtuk az egyes oszlopok neveit, akkor csak azoknak adunk értéket, mégpedig felsorolásuk sorrendjében. A többi mező NULL értékű lesz – Az egyes mezőknek NULL értéket is adhatunk, ha a deklaráció alapján az adott mezőnek lehet NULL értéke. – Ha olyan oszlopnak akarunk NULL értéket adni, amelynek nem lehet NULL értéke, akkor a parancsvégrehajtás hibával le fog állni. – Egy ilyen INSERT paranccsal egyszerre csak egy sort tudunk felvenni a táblába. • Adatok törlése DELETE FROM <táblanév> [WHERE <logikai kifejezés>]; Ha a WHERE hiányzik, akkor a tábla valamennyi sorát, ellenkező esetben csak a logikai kifejezés által kiválasztott sorokat töröljük. • Adatok módosítása UPDATE <táblanév> SET <oszlopnév> = <kifejezés> [, <oszlopnév> = <kifejezés>, .] [WHERE

<logikai kifejezés>]; Ha a WHERE hiányzik, akkor a parancs a tábla valamennyi sorában módosít, egyébként csak a logikai kifejezés által kiválasztott sorokat töröljük. 2.4 Az SQL adatelérést vezérlő utasításai (DCS) • Párhuzamos hozzáférés szabályozása LOCK TABLE <táblanév> [,<táblanév>, .] IN [SHARE | SHARED UPDATE | EXCLUSIVE] MODE [NOWAIT]; (A tábla más által olvasható | más által olvasható és módosítható | kizárólagos hozzáférésű.) Ezzel a paranccsal egy felhasználó megadhatja, hogy az egyes táblákhoz más felhasználóknak milyen egyidejű hozzáférést engedélyez. Az utasítás végrehajtásánál a rendszer ellenőrzi, hogy a LOCK utasításban igényelt felhasználási mód kompatibilis-e a táblára érvényben lévő kizárással: • Ha megfelelő, akkor akkor az utasítás visszatér és egyéb utasításokat lehet kiadni. • Ha nem, akkor az utasítás várakozik, amíg az érvényes kizárást

megszüntetik - ha a parancs nem tartalmazza a NOWAIT módosítót (mert ekkor a LOCK utasítás mindig azonnal visszatér, de visszaadhat hibajelzést is). A táblához a hozzáférést az első sikeres LOCK utasítás definiálja. 18. tétel Funkcionális függések 18. tétel Funkcionális függések 2. Adott az R(A,B,C) reláció táblája Funkcionális függések 1. Bevezetés Alapkérdés: melyek a "jó" relációk, amelyeket a tényleges séma szintjén érdemes tárolni? Azaz: mik legyenek az igazi alaprelációk? Hogyan kaphatunk tetszőleges relációkból "jó" relációkat? Ezekre a kérdésekre válaszol a relációs sémák tervezésének elmélete. A "jó" relációkat nevezzük majd a későbbiekben normálformájú relációknak, és azt az átalakítási folyamatot, amivel a tetszőleges relációból normálformájút készítünk, normalizálásnak nevezzük. Megszorítások, kényszerek: a lehetséges tábla-tartalmat

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

Jelölés: XY teljesül r-en. Példák 1. Adott a TERMELŐ(Név,Cím,Termék,Ár) rekord, amit a (Név,Termék) pár egyértelműen meghatároz. Egy termelőnek pedig egy, vagy annál több címe lehet Funkcionális függések: a.) NévCím b.) Név, TermékNév, Cím,Termék, Ár = R (azaz az egész rekordot meghatározza) A a a B b c C c c = r rek. r-ben az • ABC függés "üresen" teljesül, az • AC függés nem "üresen" igaz, és a • CB függés nem teljesül. Bennünket a lényegi függések érdekelnek, amelyek általános érvényűek és részei modellünknek. 3. Adott a SZEMÉLY reláció: . Szsz Nem Szemszí n 1. ffi kék 1. ffi kék NemSzemszín: ez nem igazi függés, ezzel szemben a SzszNem már igazi függést jelez. Ez már számunkra is fontos! Általánosan: adott az (R,F) pár, ahol R egy reláció és F függések egy halmaza. Csak olyan R-hez illeszkedő r relációkkal foglalkozunk, melyekben F függései teljesülnek. Ezek a

függések azért ilyen kiemelten fontosak számunkra, mert anomáliákat okozhatnak. Pl.: a TERMELŐ relációban adott NévCím és Név, TermékR függések mellett előfordulhat, hogy ha valaki nem termel terméket, akkor nem lesz felvéve a címe sem. Def.: Függőleges felbontás Az anomáliák elkerülése érdekében használható a függőleges felbontás technikája. Ekkor nem magát R-et, hanem függőleges vetületeit tároljuk. Előbbi példánkban: R1: ΠNév,Cím(R) R2: ΠNév,Termék,Ár(R) Ezzel a felbontással az anomáliák is eltünnek. Ennek az előnynek azonban az az ára, hogy R R2 természetes illesztés költséges művelet. helyreállítása, az R=R1 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". 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 18. tétel Funkcionális függések 3. A funkcionális függés elméleti háttere Def.: Logikai következmény Adott az (R,F) pár. Az XY függés logikai következménye F-nek, ha XY érvényes minden olyan R-sémájú r relációban, ahol az F is érvényes. Jele: F |= XY Ha a logikai következmény fogalma mellé megalkotjuk a levezethetőség fogalmát is (|), akkor kezünkben lesz az a "kalkulus", ami a normailizáláshoz kell. Ugyanis, ha tökéletesen formalizáljuk a levezetést, akkor elérjük a kitűzött |= ≈ | célt. • | ⇒ |= irány: az igazság-tétel mondja majd ki; • |= ⇒| irány: a (Gödel-féle) teljességi tétel mondja ki. Def.: Armstrong-axiómák (R,F)-re A1. Reflexív szabály Y⊆X⊆R ⇒ XY A2.

Kiegészítési szabály Ha XY és Z⊆R ⇒ XZ YZ A3. Tranzitivitási szabály Ha XY és YZ ⇒ XZ Def.: Levezethetőség F-ből az UV levezethető, ha az UV függés megkapható F-ből az A1-A3 alkalmazásával. Jele: F | UV. Tétel: Igazság-tétel F |  XY esetén F |= XY is teljesül. Biz.: ha r-ben igaz A1-A3 "baloldala", akkor a "jobboldala" is igaz lesz A1: X Y r: ( ( )) t1 sor ( t2 sor ( )) Nagy X halmazon megegyeznek ⇒ kis Y-on is! A2: X Z Y ( )( )( )t1 sor ( )( )( )t2 sor Ha az X és Z halmazai megegyeznek ⇒ az Y-ok is! r: X A3: r: Z Y ( )( )( )t1 sor ( )( )( )t2 sor Ha az X-ek megegyeznek ⇒ az Y-ok is ⇒ a Z-k is! Ezzel állításunkat igazoltuk. 18. tétel Funkcionális függések Def.: Szuperkulcs, kulcs Az X⊆R attribútum-halmaz szuperkulcs az (R,F)-re nézve, ha F |= XR. Az X⊆R attribútum-halmaz kulcs az (R,F)-re nézve, ha szuperkulcs, de egyetlen valódi része sem szuperkulcs. (X ebben az értelemben

"minimális") Példa: Amerikai irányítószámok Adott az R(Város, Utca, Irsz) reláció és az F={Város,UtcaIrsz, IrszVáros}függéshalmaz. Azt állítjuk, hogy: F |  Irsz, Utca Irsz, Utca,Város=R, azaz (Irsz, Utca) kulcs. Levezetése: Irsz Város F alapján Irsz, Utca Város, Utca A2 alapján (Z=Utca) Irsz, Utca Város, Utca, Irsz A2 alapján (Z=Irsz) [Irsz-t nem kell még egyszer beírni!] Tétel: További fontos szabályok 1. Únió-szabály Adott két, azonos baloldalú függés. Ezek jobboldala összevonható Formálisan:{X Y, X Z}|  X YZ. 2. Felbontási szabály Az előbbi szabály komplementere. Formálisan:{X Y}|  X Z, ahol Z⊆ ⊆Y. 3. Áltranzitív szabály Formálisan:{X Y, WY Z}|  WX Z. Biz.: az Armstrong-axiómákkal történik Mi alapján? 1. Únió-szabály 1. XZ ∈F 2. YXYZ A2 (Y a kiegészítő halmaz) 3. XY ∈F 4. XYX A2 (X a kiegészítő halmaz) 5. XYZ A3 (4. és 2 tranzitivitása) 2. Felbontási szabály 1. XY 2. YZ 3. XZ

Mi alapján? ∈F A1 A3 (1. és 2 tranzitivitása) 3. Áltranzitív szabály 1. WYZ 2. XY 3. XWYW 4. XWZ Mi alapján? ∈F ∈F A2 (W a kiegészítő halmaz) A3 (3. és 1 tranzitivitása) 19. tétel Lezárások, fedések, vetített függések 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: Y; F |  X Y}, azaz F+ az F összes szintaktikus következménye. F+:={X Ha modellünk része F, akkor F+ is az; ez utóbbi ad teljes képet a függések rendszeréről. Ugyanekkor F+ mérete túlságosan nagy, és ezért a gyakorlati alkalmazásokban nemigen alkalmazható. Példa: Adott az R(A1,.,An,B1,,Bn) reláció és az F={AiBj} függéshalmaz, ahol i,j=1,.,n Azaz n2 db. függésünk van, és F+ kb 22n elemből áll, ami nagyon sok és nehezen számolható. F+ tartalmazza az összes olyan XY függést, ahol: •

0≠X⊆{A1,.,An} • 0≠Y⊆{B1,.,Bn} Szerencse, hogy van egy hatékonyan számítható függés-fogalom, ami képesség tekintetében nem marad el a függéshalmaz lezárásától. Ez pedig az: Def.: Attribútumhalmaz lezárása Adott az X⊆R attribútumhalmaz. Ennek lezárása X+(F), amire igaz, hogy: ⊆R; F |  X A}; ami szoros összefüggésben áll a levezethetőséggel. X+(F):={A⊆ Fontos különbség az előző fogalomhoz (függéshalmaz lezárása) képest, hogy míg F+ függésekből, addig X+(F) attribútumokból áll. Állítás*: F | XY ⇔ Y⊆X+(F) Biz.: ⇒ irány Tfh. F | XY és A∈Y Be kell látni, hogy: F | XA. Lezárások, fedések, vetített függések A bizonyítás alapötlete, hogy (R,F)-hez "modellt" készítünk. r egy kétsoros reláció: X+(F) X biztosan eleme X+(F)-nek (lehet, hogy nem valódi). X r első sora csupa 1-es 11 . 1 11 . 1 második sora csak X+(F)-ben 1-es, 11 . 1 00 . 0 másutt csupa 0. Nem lényeges az

attribútumok alaphalmaza, csak az. hogy az oszlopokban azonos vagy különböző értékek szerepelnek-e. 1. állítás: r-ben teljesülnek F függései, azaz ha VW∈F, akkor VW teljesül F-en. (Ez jelenti azt, hogy modellt készítettünk (R,F)-hez.) Biz.: Legyen VW∈F Esetszétválasztás: • ha V¬⊆X+(F), akkor az állítás igaz, hiszen nincs r-nek két sora, ami V-n egyezne. √ • ha V⊆X+(F), akkor az Állítás* ⇒ iránya miatt:  XV 1. F | ∈F miatt 2. VW  XW A3 miatt (1., 2 tranzitivitása) 3. F | De az Állítás* ⇐ iránya miatt ez egyenértékű azzal, hogy W⊆X+(F). √ Tehát két sor megegyezik W-n is, azaz r-ben VW tényleg fennáll. Ezután nézzük a Teljességi tétel érdemi bizonyítását: 2. állítás: F |  XY Ez viszont a felbontási szabály miatt mindig igaz. √ ⇐ irány Be kell látni, hogy ha Y⊆X+(F), akkor F | XY. Legyen Y=A1,.,Ak attribútumok együttese Felt.: F | XAi, ahol i=1,,k Alkalmazzuk többször az

únió-szabályt! XA1 XA2 } XA1 A2 XA1 A2 A3 XA3 . Végül: XA1,A2,.,Ak √ Tétel: Teljességi tétel Adott az (R,F) pár, és fel szokás tételezni azt, hogy az attribútumok legalább kétértékűek. F |= XY esetén F |  XY is teljesül. (Azaz: a logikai következményről meg lehet győződni.) } 19. tétel Biz.: Feltétel szerint F|=XY, azaz az XY függés igaz mindenütt, ahol F érvényes Az 1. állítás szerint r-ben igaz az XY függés X-en két sor egyenlő ⇒ a két sor Y-on is egyenlő, azaz Y⊆ X+(F), abból "nem lóghat ki". Az Állítás* ⇐ iránya szerint pedig F |  XY, ezzel állításunkat igazoltuk. √ Következmény: |= és | egyenértékű. Ezért X+(F):={A⊆ ⊆R; F |= X A} is írható, amit ki is használnak automatikus séma-elemzőkben. Def.: Algoritmus X+(F) számítására Bemenete: az (R,F) ár és az X⊆R attribútumhalmaz. Kimenete: az X+(F) attribútumhalmaz. A módszer iteratív: X0:=X Xi+1:= Xi ∪ {azon A

attribútumok, melyekhez van olyan UV∈F függés, hogy U∈ Xi és A∈V} Az iteratív lépések nem csökkentik az X halmazok méretét, ezért: X0 X1 X2 Xutolsó 19. tétel Lezárások, fedések, vetített függések 19. tétel Xutolsó-t akkor kapjuk meg, amikor X már nem nő tovább. Állítás: Xutolsó = X+(F) Biz.: (vázlat) 1. Xutolsó⊆X+(F) Ezt teljes indukcióval látjuk be, Tfh. Xi⊆X+(F) Ez a reflexív szabály miatt igaz. √ • i=0: X0⊆X+(F) • általános esetben be kell látni, hogy F |  XA, ahol A∈Xi. i Az Állítás* szerint: F |  XX van olyan UV∈F, hogy U⊆Xi és A∈V. igaz 1. XXi A1 miatt 2. XiU ∈F 3. UV A1 miatt 4. VA A3 miatt (3. és 4 reflexivitása) 5. UA A3 miatt (1. és 2 reflexivitása) 6. XU A3 miatt (6. és 5 reflexivitása) √ 7. XA ⊇X (F) 2. X Ennek belátásához - a Teljességi tétel bizonyításához hasonlóan - definiálunk egy r relációt: Xutolsó utolsó 11 11 + X . . 1 11 1 00 . . 1 0 r első sora

csupa 1-es második sora csak X+(F)-ben 1-es, másutt csupa 0. a.) r-ben F igaz UV∈F • ha U¬⊆Xutolsó, akkor az állítás igaz. √ • ha U⊆Xutolsó, akkor V⊆Xutolsó, mert ellenkező esetben V elemeivel növelhető Xutolsó lenne. √ b.) legyen A∈X+(F) tetszőleges Be kell látni, hogy A∈Xutolsó. A teljességet és X+(F) definícióját felhasználva: F|=XA. Tehát • r-ben is igaz az XA függés • X-en két sor egyezik ⇒ A-n is egyezik ⇒ A∈Xutolsó. √ 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. • X kulcs ⇔ X+(F)=R, de (XA)+(F)≠R az X

egyetlen A elemére sem (ez a minimalizálási feltétel). Az eddig elmondottak alapján a szuperkulcs- és kulcs-tulajdonság hatékonyan tesztelhető a vázolt algoritmussal.1 2. Részletesen a függőleges felbontásokról Def.: Függőleges felbontás2 Adott az (R,F) séma. 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: 1 Kérdés: AB+(F), azaz most X=AB. k Ennek egy függőleges felbontása: ρ = (R1,.,Rk), ahol az Ri ∈ R vetületekre: ∪Ri = R Megj.: a fent vázolt algoritmus implementálható a bemenet, azaz (R,F) hosszában lineáris lépésszámmal. Példa: adott az R(A,B,C,D,E) ötoszlopos reláció és az F={ABC, BD, CDE} függéshalmaz. Lezárások, fedések, vetített függések 2 Név Termék Ár a ZH anyaga idáig tart. Ez a témakör persze még folytatódik :) Jele ρ, azaz ró, ha nem látszana tisztán zöldmező zöldmező liszt cukor 70 80 19. tétel Lezárások, fedések, vetített függések ρ=(R1,R2) R1=(Név,Termék) R2=(Név,Ár) R=(Név,Termék,Á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ő • vagy F |= R1 ∩ R2 R1 R2 ∈ F+, • vagy F |= R1 ∩ R2 R2 R1 ∈ F+. Biz.: ⇐ Tfh. pl F |= R1 ∩ R2 R1 R2 igaz t ∈ r1 r2 ⇒ t ∈ r Ár 70 80 Név zöldmező

zöldmező zöldmező zöldmező Termék liszt liszt cukor cukor Á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) 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. / k R1 R2 ^ ^ =r ΠRi(mρ(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. 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). // i=1 Lezárások, fedések, vetített függések r2 de mρ(r) ⊃≠ r 3. mρ(mρ(r)) = 19.

tétel k ri = mρ(r). / 2. i=1 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. R1 R2 ^ ^ 11.11 11 00.00 11 . . 11 0 11 1 =r . 0 . 1 v R1 ∩ 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) Cím, NévTermékÁr) F = (Név 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 k 19. tétel Lezárások, fedések, vetített függések 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 Y∈F+, ahol van olyan i, hogy XY ⊆ Ri} egy vetített függés. Πρ(F) = {X Def.: Az (R,F) séma ρ felbontása megőrzi F-et, ha Πρ(F)+ ⊆ (F)+ Megj.: Mivel Πρ(F) ⊆ F+, ezért Πρ(F)+ ⊆ F+ mindig igaz Def.: Függéshalmaz fedése A G függéshalmaz az F függéshalmaz fedése, ha ugyanazt axiomatizálják, azaz G+=F+. (Ez egy szimmetrikus viszony.) Def.: Függéshalmaz minimális fedése A G függéshalmaz az F függéshalmaz minimális fedése, ha 1. G+=F+, azaz G egy fedés; 2. a G-beli függések jobboldalai egyeleműek (a felbontási és únió tételek miatt az XY függést az XAi-kkel helyettesíthetjük,

∪Ai =Y); 3. G-ből nem hagyható el függés, azaz ha XA∈G, akkor XA ∉ (G{XA})+, vagyis a többi függésből XA nem állítható elő. 4. a G-beli függések baloldalai minimálisak, nem csökkenthetők: ha XA∈G és Y⊂X valódi részhalmaz, akkor YA ∉G minden Y-ra. Tétel: Tetszőleges F-hez van G minimális fedés. Sőt, ilyen G minimális fedés hatékonyan kapható. Biz.: konstruktív F-ből indulunk ki, majd fokozatosan biztosítjuk a definíció pontjait. Kezdetben: G=F. 1. A módosított G egyenértékű a korábbival 2. XY ∈G, Y=A1,A2,,Ak helyett XA1, ahol i =1,.,k (a felbontási és únió szabály értelmében) 3. Veszünk egy XA ∈G függést H X A (G{X A})+ kk X A t ld bj k 19. tétel Lezárások, fedések, vetített függések ellenkező esetben megtartjuk. Praktikusan ez a teszt a következőképp oldható meg: • A ∈X+(G{XA}) esetén lehet a függést eldobni, és • A ∉X+(G{XA}) esetén pedig meg kell tartani. Elég tehát a lezárás helyett az

attribútum-halmaz lezárására tesztelni. 4. Ha XA ∈G és Y⊂≠X, akkor YA∉G Megj.: ha YA∈G és Y⊂X, akkor XA ∈G teljesül a reflexivitás miatt Z: átmenet az X és az Y között Y Z X Nézzük meg azon Y ⊆ X halmazokat, melyekre |XY|=1. Teszt: A ∈Y+(G) teljesül-e? • igen: ekkor XA helyett Y A-val folytatjuk az algoritmust; • nem: ekkor vesszük a következő Y-t. Ha X esetén minden Y-ra "nem" a válasz a fenti tesztkérdésre, akkor marad az XA függés. Példa: G minimális fedés keresésére az előbbi algoritmussal Adott az R(A,B,C) reláció és az F = {ABC, AB, BA} függéshalmaz. Keressük F minimális fedését, G-t. Az algoritmus lépései: 2. rendben van 3. szintén rendben van: nincs elhagyható függés Pl. ABC nem elhagyható, mert AB+({AB,BA}) = AB és C∉AB ./ 4. AB, BA ABC nem minimális baloldalú A+(F) = ABC, és C ∈ ABC, ezért ABC helyett vehetjük az AC-t. Tehát G={AB, BA, AC} Megj.: mivel A és B szerepe szimmetrikus,

ezért G = {AB, BA, BC}is minimális fedés. Ennek következménye az, hogy a minimális fedés nem egyértelmű. 20. tétel Normálformák (3NF, BCNF), normalizálás Normálformák (3NF, BCNF), normalizálás 1. Boyce-Codd normálforma (BCNF) Def.: BCNF Az (R,F) relációs séma BCNF, ha minden nem triviális XA∈F+ függés esetén X szuperkulcs, ahol A egy attribútum, A∉X (vagyis A egy, az X attribútum-halmazon kívüli attribútum). Megjegyzések: • a BCNF-ben nincsenek a szuperkulcson kívülről induló függések; a normálforma a kötelezően meglévő minimális mennyiségű függéssel rendelkezik; • BCNF-nek számít a jó, értelmes, redundancia-mentes reláció; • a legutóbbi példában bemutatott NévCím függés felrúgja a BCNF feltételét, és pont ez okoz anomáliákat. A TERMELŐ reláció tehát nem BCNF, mert Név nem szuperkulcs; • egy kétoszlopos reláció mindig BCNF. Ha ez a két oszlop A és B, akkor két nem triviális függés

lehetséges: 1. AB ⇒ A szuperkulcs 2. BA ⇒ B szuperkulcs Így a reláció mindenképpen BCNF: Főtétel.: A BCNF és a hűséges felbontás kapcsolatáról Tetszőleges (R,F) sémának ∃ρ hűséges felbontása BCNF relációkra. Megj.: tfh (R1,,Rk) egy hűséges felbontása R-nek és (S1,.,Sm) egy hűséges felbontása R1-nek Ekkor (S1,.,Sm,R2,,Rk) egy hűséges felbontása R-nek Ennek oka az, hogy a természetes illesztés művelete a sorrendre kvázi érzéketlen. A természetes illesztést először az Si-kre (R1), majd az Ri-kre kell elvégezni. Biz.: konstruktív ./ 1. Ha R BCNF, akkor az állítás egyből igaz 2. Ha R nem BCNF, akkor van nem triviális XA függés, ahol X nem szuperkulcs ρ = (R1=XA, R2=RA) egy felbontás; R helyett ezzel megyünk tovább. 3. Ha R1,R2 nem BCNF, akkor az előbbi módon folytassuk a felbontásukat Ezt az eljárást rekurzívan alkalmazva hűséges felbontáshoz jutunk. A módszer sikerre vezet, mert: a.) (XA,RA) valódi felbontás, mivel

• RA nem egyezik meg az R relációval, mert annál kisebb és • XA sem egyezik meg az R relációval, különben X szuperkulcs lenne. 20. tétel Normálformák (3NF, BCNF), normalizálás b.) a felbontás hűséges A főtétel megjegyzése miatt elég azt belátni, hogy az (R1=XA, R2=RA) hűséges felbontása R-nek. A hűségesség tételének alkalmazásával: • R1 ∩ R2 = X és • R1 R2 = A. A nem triviális ("bajkeverő") X A függés segít (ahol X nem szuperkulcs), mert XA ∈ F+, és az F |= R1 ∩ R2 R1 R2 által teljesül a hűségesség tételének feltétele, azaz a felbontás valóban hűséges. .// Példák.: BCNF-re 1. Vegyük kedvenc TERMELŐ(Név,Cím,Termék,Ár) relációnkat! F = (NévTermékCímÁr,NévCím) Ennek a Név Cím függés egy rossz függése: ez sérti a BCNF tulajdonságot, mert a Név nem kulcs, és a függés nem triviális. A fent vázolt algoritmus szerint adódik egy BCNF alakú kétoszlopos ρ: ρ = (NévCím,

NévTermékÁr), és ennek a felbontásnak mindkét tagja BCNF, tehát már egyetlen lépésben célt értünk. A felbontás hűségét az előbbi tétel garantálja. 2. Egyetemi oktatás példája R(Tanár,Tárgy,Terem,Diák,Jegy,Idő) F={TárgyTanár, IdőTanárTerem, IdőDiákTerem, IdőTeremTárgy, TárgyDiákJegy} reláció egy viszonylag realisztikus függés-halmaz A lezárási algoritmussal egyetlen kulcs adódik: DiákIdő 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.) Az X A függés szereposztása: TanárDiák Jegy (folyt.köv) 20. tétel Normálformák (3NF, BCNF), normalizálás R TanárTárgyTeremDiákIdő ez nem BCNF, fel kell bontani! a TárgyTanár rossz függés ez már BCNF, nem bomlik tovább TanárTárgy kulcs: Tárgy TárgyTeremDiákIdő ez már BCNF, nem bomlik tovább TárgyIdőTerem nem eleme F-nek, de F+nak igen; rossz! TárgyTeremIdő

kulcs: TárgyIdő, TeremIdő ez már BCNF, nem bomlik tovább Normálformák (3NF, BCNF), normalizálás 2. Harmadik normálforma (3NF) ez nem BCNF, fel kell bontani! TanárDiákJegy kulcs: TanárDiák 20. tétel Példa: Bevezetés a 3NF-hez Az amerikai irányítószámok az F függés-halmaznak megfelelően épülnek fel: R(Város,Utca,Irányítószám) F ={VárosUtcaIrányítószám, IrányítószámVáros} Ez az (R,F) séma nem BCNF, pl. az IrányítószámVáros függés sérti a BCNF-et Egy BCNF felbontás lehet a következő: ρ = (IrányítószámVáros, IrányítószámUtca). Gond: hogyan ellenőrizzük a VárosUtcaIrányítószám függést új sor beszúrásakor? Ez a függés "elvész" a daraboláskor, így azt csak a természetes illesztéssel való helyreállítás után ellenőrizhetjük. A természetes illesztés viszont egy roppant költséges művelet. TárgyDiákIdő kulcs: DiákIdő ez már BCNF, nem bomlik tovább Megjegyzések: • A felbontás

eredményei a levelekben található komponensek. • A felbontás hűséges, mert mindvégig a két részre bontás technikáját alkalmaztuk. • A felbontásban segít, ha mindig a megfelelő rossz függéseket választjuk. Állítás: Nem BCNF formájú relációkra Tfh. adott egy (R,F) séma, ami nem BCNF Ekkor van olyan X Y ∈ F függés és A∈ ∈Y attribútum, hogy az X A ∈ F+ függés megsérti a BCNF-et. Azaz: ha egy reláció nem BCNF, akkor ezt könnyen is be lehet látni. Biz.:(R,F) nem BCNF ⇒ van olyan UB ∈ F+ nem triviális függés, ahol U nem szuperkulcs Ezért B ∈ U+(F). Ez a lezárási algoritmus természetéből adódik: van olyan XY ∈ F függés úgy, hogy X⊆U és Y¬⊆U. Legyen A egy tetszőleges eleme YU-nak, vagyis A∈YU. Ekkor megállapíthatjuk, hogy: • egyrészt az XA nem triviális függés (A∉X, mert A∉U), • másrészt XA ∈ F+ (a felbontási szabály szerint). X nem szuperkulcs, nem határoz meg minden más attribútumot. Ez

abból látszik, hogy U nem szuperkulcs, és mivel X⊆U, így X sem lehet az. ./ Következmény: Ha F-ben minden függés baloldala szuperkulcs, akkor (R,F) BCNF alakú. Def.: Vetített függések Legyen ρ = (R1,.,Rk) az (R,F) séma egy függőleges felbontása Y∈F+, ahol van olyan i, hogy XY ⊆ Ri} egy vetített függés. Πρ(F) = {X Def.: Az (R,F) séma ρ felbontása megőrzi F-et, ha Πρ(F)+ ⊆ (F)+ Megj.: Mivel Πρ(F) ⊆ F+, ezért Πρ(F)+ ⊆ F+ mindig igaz Megjegyzés: az bevezető példához Az R(Város,Utca,Irányítószám) relációnak F-et megőrző módón nincs valódi felbontása. (A vetítés halmaza csak az IrányítószámVáros függés következményeiből áll) Ez arra példa, hogy egy (R,F)-et mikor nem lehet hűségesen, az F-et megőrző módon BCNF-ekre bontani. És ha már ez nem lehetséges, akkor szükség lenne egy BCNF-nél valamivel gyengébb tulajdonságokkal rendelkező normálformára, ami F-et megőrizné. Ezért találták ki a 3NFet

Def.: Prím attribútum Az (R,F) séma egy A attribútuma prím, ha a sémának van olyan X kulcsa, melynek A eleme, azaz A∈ ∈X. Def.: 3NF Az (R,F) séma harmadik normálformájú - röviden 3NF -, ha minden XA ∈ F+ nem triviális függésnél X vagy szuperkulcs vagy A prím attribútum. Észrevételek: 1. Ha (R,F) BCNF, akkor egyben 3NF is (nem érdekes, hogy A milyen attribútum) 2. Van 3NF alakú (R,F) séma, ami nem BCNF (Pl a bevezető példa, ahol a Város prím attribútum.) 20. tétel Normálformák (3NF, BCNF), normalizálás Tehát a két NF viszonya: BCNF 3NF A 3NF a tágabb, engedékenyebb NF. Def.: X+(Πρ(F)) számításának algoritmusa • Z:=X • amíg Z változik, DO k: a felbontás elemeinek száma, ρ = (R1,.,Rk) FOR i=1 TO k DO Z:=Z∪ ∪((Z∩ ∩Ri)+(F)∩ ∩Ri). Az algoritmus helyességét nem bizonyítjuk, de az nyilvánvalóan igaz, hogy: • Zutolsó ⊆ Πρ(F)+ (ez triviális), illetve • Zutolsó ⊇ Πρ(F)+ (ezt nem bizonyítjuk).

Példa: az előbbi algoritmusra R(A,B,C,D) egy négyoszlopos reláció. ρ = (AB,BC,CD) ennek egy felbontása. F = (AB, BC, CD, DA) azaz minden mindent meghatároz, tehát ez lényegében egy egyoszlopos mesterséges reláció - nem gyakorlati példa. Nyilván DA ∈ F+, mert DA ∈ F is teljesül. Ellenőrizhető a vetületeken is, mint DC, CB, BA következménye. Kérdés: A∈D+(Πρ(F)) teljesül-e? Ki tud-e jönni A a függések révén? 20. tétel Normálformák (3NF, BCNF), normalizálás 2. a G-beli függések jobboldalai egyeleműek (a felbontási és únió tételek miatt az XY függést az XAi-kkel helyettesíthetjük, ∪Ai =Y); 3. G-ből nem hagyható el függés, azaz ha XA∈G, akkor XA ∉ (G{XA})+, vagyis a többi függésből XA nem állítható elő. 4. a G-beli függések baloldalai minimálisak, nem csökkenthetők: ha XA∈G és Y⊂X valódi részhalmaz, akkor YA ∉G minden Y-ra. Tétel: Tetszőleges F-hez van G minimális fedés. Sőt, ilyen G minimális

fedés hatékonyan kapható. Biz.: konstruktív F-ből indulunk ki, majd fokozatosan biztosítjuk a definíció pontjait. Kezdetben: G=F. 1. A módosított G egyenértékű a korábbival 2. XY ∈G, Y=A1,A2,,Ak helyett XA1, ahol i =1,.,k (a felbontási és únió szabály értelmében) 3. Veszünk egy XA ∈G függést Ha XA ∈ (G{XA})+, akkor XA-t eldobjuk, ellenkező esetben megtartjuk. Praktikusan ez a teszt a következőképp oldható meg: • A ∈X+(G{XA}) esetén lehet a függést eldobni, és • A ∉X+(G{XA}) esetén pedig meg kell tartani. Elég tehát a lezárás helyett az attribútum-halmaz lezárására tesztelni. 4. Ha XA ∈G és Y⊂≠X, akkor YA∉G Megj.: ha YA∈G és Y⊂X, akkor XA ∈G teljesül a reflexivitás miatt Z: átmenet az X és az Y között Az algoritmus: Z0 = D 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; Y Z X Nézzük meg azon Y ⊆ X halmazokat, melyekre |XY|=1. Teszt: A ∈Y+(G) teljesül-e? • igen: ekkor XA helyett Y A-val folytatjuk az algoritmust; • nem: ekkor vesszük a következő Y-t. Ha X esetén minden Y-ra "nem" a válasz a fenti tesztkérdésre, akkor marad az XA függés. Példa: G minimális fedés keresésére az előbbi algoritmussal Adott az R(A,B,C) reláció és az F = {ABC, AB, BA} függéshalmaz. Keressük F minimális fedését, G-t. A l it lé é i 20. tétel Normálformák (3NF, BCNF), normalizálás 2. rendben van 3. szintén rendben van: nincs elhagyható függés Pl. ABC nem elhagyható, mert AB+({AB,BA}) = AB és C∉AB ./ 4. AB, BA ABC nem minimális baloldalú A+(F) = ABC, és C ∈ ABC, ezért ABC

helyett vehetjük az AC-t. Tehát G={AB, BA, AC} Megj.: mivel A és B szerepe szimmetrikus, ezért G = {AB, BA, BC}is minimális fedés. Ennek következménye az, hogy a minimális fedés nem egyértelmű. 20. tétel Normálformák (3NF, BCNF), normalizálás Legyen H = {A∈R; t1[X] = t2[X]}attribútumhalmaz. H ⊇ X, de H≠R, mert t1≠ t2. A H ⊇ X tulajdonságból eredően H szuperkulcsa (R,F)-nek és (R,G)-nek. HR∈G+ (és H+(G) = R). Ezért van olyan UB ∈G függés, amire U ⊆ H, B ∉H. UB = XiAi alkalmas i-re. t1, t2 ∈ mρ(r), és ezért van olyan t1, t2 ∈ r, hogy: t1[UB] = t1[UB] és t2[UB] = t2[UB]. Először: t1[U] = t2[U] t1[U] = t1[U] = t2[U] = t2[U]. def. Főtétel: A 3NF és a hűséges felbontás kapcsolatáról Egy tetszőleges (R,F) sémának van hűséges, F-et megőrző felbontása 3NF relációkra. Biz.: konstruktív Legyen G az F minimális fedése. Tfh. G = {X1A1,,XkAk}alakú Ekkor legyen ρ = (X1A1,.,XkAk,X) egy k+1 komponensű felbontás, ahol X az

(R,F) séma egy kulcsa. 1. ρ megőrzi G-t (és így F-et is) Be kell látni, hogy a vetület-függések összessége kiadja az egészet: Πρ(G)+=G+. Πρ(G)⊇G, pl. XiAi ∈G látható az Ri = XiAi darabban 2. A kapott függőleges darabok 3NF-ek X kulcs ⇒ nincs benne semmilyen függés ./ Tfh. XiAi nem 3NF, és ennek YB ∈G+ egy rossz függése a.) B=Ai Ekkor Y valódi része Xi-nek (ellenkező esetben nem lenne rossz függés), mert Xi szuperkulcsa Ai-nek. YAi ∈G+ ellentmondana G minimális fedés voltának (a 4. feltétel miatt) b.) B≠Ai, azaz B ∈Xi B nem lehet prím attribútum, mert akkor az YB nem lenne rossz függés. • Tehát Xi nem kulcsa XiAi -nek, mert akkor B prím attribútum volna; • de Xi szuperkulcs, vagyis van benne egy valódi rész (pl. U), ami kulcsa XiAi -nek Ezért UAi ∈G+, ami ismét ellentmond G minimális fedésének, azaz a definíció 4. pontjának. 3. ρ hűséges felbontás Be kell látni, hogy s = mρ(r) = r minden r-re. Ha ez nem igaz,

akkor van olyan r, hogy s = mρ(r) ⊃≠ r. Πx(s) = Πx(r) s ⊃ r csak úgy lehet, ha van s-nek egy t1 és t2 sora úgy, hogy t1[X] = t2[X] és t1≠ t2. U⊆H t1, t2 ∈ r és egyeznek U-n, s ekkor UB∈G miatt B-n is egyeznek. Ez azonban lehetetlen, mert: t2[B] = t2[B] = t1[B] = t1[B]. És ez ellentmond B ∉ H-nak def. előző def. √ Ezzel állításunkat igazoltuk. 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: BCNF 3NF 1NF . 21. tétel Többértékű függések, 4NF 21. tétel Többértékű függések, 4NF 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ő. 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ó:1 Név Kiss Kiss Kiss Kiss Nagy . Projekt A B A B B . Def.: Triviális függések • Ha Y⊆X, akkor X > Y. t1, t2-höz t3 = t1 és t4= t2 jó. • Ha X∪Y=R, akkor X > Y. t1, t2-höz t3 = t1 és t4= t2 szintén jó. (RXY = 0) • Ha XY=R, akkor X > Y. 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. Munkatárs Lalagé Lalagé Aniela

Aniela Aniela . Ez a reláció BCNF alakú, mégis tartalmaz redundáns elemeket és anomáliák forrását hasonlóakat, mint amilyenek a hagyományos függéseknél tapasztalhatók. Természetes felfogás szerint a fenti feladatot két táblával oldanánk meg: Név Kiss Kiss Nagy Projekt A B B Név Kiss Kiss Nagy Def.: Többértékű függés Adott X és Y, két attribútum-halmaz. X többértékűen meghatározza Y-t (r-ben), ha t1,t2 ∈ r és t1[X] = t2[X] esetén van t3,t4 ∈ r úgy, hogy: • t1[XY] = t3[XY], t2[XY] = t4[XY] és • t1[RXY] = t4[RXY], t2[RXY] = t3[RXY]. Jelölés: X Ábrázolva: X > Y Y RXY t1 t2 t3 t4 1 ezeket az érdekes neveket nem én találtam ki! (B J ) Munkatárs Aniela Lalagé Aniela Megállapítások a többértékű függésekkel kapcsolatban • Az (R,F) sémában F hagyományos és többértékű függések halmaza. • Definiálható a |= (logikai következmény) és a | (szintaktikai következmény) fogalma. Ezekre a már

megismert 8 alapszabály - A1, A2, A3 és 5 másik - vonatkozik Pl.: {XY}|= X > Y vagy {XY}| X > Y {X > Y}| X > (RXY) t1, t2-höz t4t3 lesz jó: X Y RXY t1 t2 t3 t4 • Igaz a teljességi tétel (belátni kicsit körülményes, de nem nehéz): |= ~ |. • Itt is értelmezhető F+, de sajnos X+(F) nem. • Itt is lehet beszélni felbontásról, hűségességről általános (R,F)-re. • Nehezebben algoritmizálható, mint a BCNF. (Kérdés, hogy megéri-e a fáradtságot?) Def.: Negyedik normálforma, 4NF Az (R,F) séma 4NF, ha tetszőleges nem triviális X > Y ∈ F+ esetén X szuperkulcs (a régi értelemben). Következmények: 1. Ha (R,F) 4NF, akkor BCNF is 2. Kétoszlopos reláció biztosan 4NF (azaz nincs benne nem triviális > ) 21. tétel Többértékű függések, 4NF 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. ρ pontosan akkor hűséges, ha R1∩R2 > R2R1

∈F+. Megj.: Mivel R1∩R2 > R1R2 ∈F+ is igaz, ezért nem kell a "vagy" ág A bizonyítás hasonló a már ismertetetthez, de most mellőzzük. Főtétel: A 4NF és a hűséges felbontás kapcsolatáról Tetszőleges (R,F) sémának van hűséges felbontása 4NF darabokra. Biz.: algoritmust adunk konstruktív bizonyításként Ahogy a BCNF-nél, itt is elég a nem 4NF relációknak valódi felbontást találni. 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 -ra nincs únió és felbontási szabály! R2 = R(XY). (Megjegyzés: > Valamint ha Y=A∈X, akkor R2=XA.) R1 valódi, mert XY≠R. R2 is valódi, mert Y≠⊂X. R1∩R2 = XY∩(R(XY)) R1R2 = RXY X Y R X > RXY -ből a komplementálás miatt következik, hogy X > R1∩R2 > R2 R1. Ezzel állításunkat igazoltuk √ Y esetén: Példa: 4NF-re és hűséges felbontásra R(Név,Projekt,Munkatárs) F = {Név > Projekt, Név >

Munkatárs}. Ez (még) nem 4 NF séma; a Név nem szuperkulcs. A felbontás a Név > Projekt rossz függés alapján lehetséges: ρ = (R1=NévProjekt, R2=NévMunkatárs), ami már 4NF-eket tartalmaz. 22. tétel A tranzakciókezelés alapfogalmai A tranzakciókezelés alapfogalmai: zárak, pattok, sorosíthatóság, egyszerű tranzakció modell 1. Alapfogalmak 22. tétel A tranzakciókezelés alapfogalmai Pl.: T1: LOCK A --- .dolgozik A-val itt tart zárat A-n UNLOCK A --- 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. 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.: 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. 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; • abortálja T-t. 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 T2: READ A A++ A++ WRITE A WRITE 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, 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 T2: LOCK B 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. 22. tétel A tranzakciókezelés alapfogalmai 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. 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. 22. tétel A tranzakciókezelés alapfogalmai T1: LOCK A, UNLOCK A T2: LOCK A, UNLOCK A 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 Ez egy olyan gráf, melynek pontjai az aktív T-k. TiTj éle a gráfnak az adott ütemezésre vonatkozóan, ha van olyan A adategység, hogy: Ti: LOCK A Ti: UNLOCK A Tj: LOCK A Tétel: Sorosítható ütemezésre Az S ütemezés sorosítható ⇔ az ütemezés precedencia gráfja DAG. Biz.: • Ha a G gráf egy DAG, akkor a csúcsoknak van egy Ti1,.,Tik topologikus rendezése Az ennek megfelelő soros ütemezés Ti1, Ti2, majd Tik összes utasítását végzi el. Ez ekvivalens S-sel. • Ha G-ben van irányított kör, akkor az itt érintett T-k közül egyik sem lehet első a soros ekvivalensben, tehát nincs soros ekvivalens. Megj.:A sorosíthatóság biztosításáról 1. A pattkezeléshez hasonlóan járunk el, de a sok abort rontaná a tranzakciós teljesítményt 2. Kétfázisú protokoll: a zárkérések megelőznek minden zárelengedést Vagyis T addig nem enged el zárat, amíg további zárat

kérni szándékozik. A T munkája így fest: . zárkérések, z(T), feldolgozás, zár elengedések, Def.: T zárpontja Az első olyan időpillanat, amikor T már minden zárát megkapta. Jele: z(T) Állítás: A kétfázisú protokollt követő T-kből álló S ütemezés sorosítható. Biz.: indirekte tfh a G precedencia gráfban van irányított kör Tn 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 A-val valami egyedi történik: olvassák vagy írják. Ebből következően vannak bizonyos konzisztencia-szabályok . 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ó. 23. tétel Az RLOCK/WLOCK-modell. Hierarchikus szerkezetek zárolása 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. 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. 23. tétel Az RLOCK/WLOCK-modell. Hierarchikus szerkezetek zárolása 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 vannak, akkor az ütemezés sorosítható. tranzakciók Biz.: analóg az egyszerű tranzakció modell hasonló tételével Def.: Zár kompatibilitási mátrix 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ármó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:

Def.: Tranzakció szemantikája Két ütemezés ekvivalens, ha: a.) ugyanazokat az értékeket olvassák RLOCK-nál; b.) ugyanazokat az értékeket rendelik minden adategységhez Def.: Precedencia vagy sorosítási gráf az RLOCK / WLOCK modellben A gráfban T1T2 (T1≠ T2) él, ha: 1. T1: RLOCK A T1: UNLOCK A nincs A T2: WLOCK A T2 feltétlenül T1után kell, hogy következzen, mert T1-nek T2-től független A értéket kell olvasnia. 2. T1: WLOCK A T1: UNLOCK A nincs A T2: WLOCK A T2-nek azért kell T1után következnie, mert a szekvencia végén T2-től függő A értéknek kell maradnia A-ban. 3. T1: WLOCK A T1: UNLOCK A nincs WLOCK A T2: RLOCK A T2-nek olyan A értéket kell olvasnia, amit T1 állított elő, így T2-nek T1 után kell következnie. A gráfban T1T2 (T1≠ T2) nem él, ha: T1: RLOCK A . T1: UNLOCK A T2: RLOCK A Ez okozza valójában a hatékonyságnövekedést, mert nem kell élt felvenni T1 és T2 közé. zárkérés RLOCK WLOCK meglévő zár az RLOCK

Igen Nem adategységen WLOCK Nem Nem Egy (i,j) mátrixelem "Igen", ha egy, az adatelemen lévő adott típusú zár mellett az új zárkérés is elfogadható, és "Nem" akkor, ha az új zárkérés nem teljesíthető. Pl.2: Tfh INCR A az A értékét olvasás nélkül növeli eggyel: RLOCK WLOCK INCR RLOCK Igen Nem Nem WLOCK Nem Nem Nem INCR Nem Nem Igen Ha ismerjük az alkalmazott zárak kompatibilitási mátrixát, akkor ennek segítségével könnyen megrajzolhatjuk a sorosítási gráfot is: fel kell venni a T1T2 élt, ha T1 valamely A adategységet i módban zárolt, majd elengedett és utána először T2 zárolja j módban, és a zár kompatibilitási mátrixban aij="Nem". 2. Zárak hierarchikus szerkezetekben 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 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. 23. tétel Az RLOCK/WLOCK-modell. Hierarchikus szerkezetek zárolása 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) 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 23. tétel Az RLOCK/WLOCK-modell. Hierarchikus szerkezetek zárolása • 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 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ó. 24. tétel Időbélyeges módszerek egy processzoros környezetben

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).) 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} 24. tétel Időbélyeges módszerek egy processzoros környezetben Ha még nem olvasták/írták az adatot, akkor egy kezdőértéket állítunk be:t-∞-t, de 0-t is használhatunk. Az ütemező azt nézi, hogy a t(Ti1)<.<t(Tik) soros sorrendhez képest van-e

ellentmondásos tranzakció. Annál a tranzakciónál abortál, ahol először észleli a növő kezdőidő szerinti sorrend megsértését. Ha egy T tranzakció egy A adategységhez fordul, akkor 4 konfliktushelyzet adódhat: 1. t(T) < w(A) és T olvasni akarja A-t Abort T a következménye annak, hogy egy később indult tranzakció már írta A-t, tehát nem olvashatjuk. (A t(T) ≥ w(A) természetesen mindig lekezelhető, és r(A):=t(T).) 2. t(T) < r(A) és T írni akarja A-t Abort T a következménye annak, hogy egy később indult tranzakció már olvasta A-t, tehát nem írhatjuk. (A t(T) ≥ r(A) természetesen mindig lekezelhető, és w(A):=t(T).) A következő két konfliktushelyzet már nem okoz Abortot: 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 24. tétel Időbélyeges módszerek egy processzoros környezetben 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. 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 A-ra. 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) 24. tétel Időbélyeges módszerek egy processzoros környezetben Def.: Verziókezelés Szoros rokonságot mutat az időbélyeg-kezeléssel, de attól függetlenül is létezik. Számos alkalmazásnál fontos a régi változatok megőrzése (pl. kórházak betegnyilvántartása). Az adatbázisok "történelme" sok mindenre felhasználható; pl kereskedelmi adatbázisoknál a szakemberek adatbányászattal szereznek információt a fogyasztói szokásokról. De lehet, hogy maga az alkalmazás követeli meg a verziók tárolását. Más ok az, hogy a régi változatok tárolásával sokszor (időben) hatékonyabb megoldások kaphatók. Ez

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

állított be) Ez a baj nem orvosolható, mert a T tranzakció T-től vagy korábbi tranzakciótól olvasott, pedig T-től vagy későbbitől kellett volna olvasnia. A helyzet ellentmondásossága abort-hoz vezet A módszer előnye, hogy az abort-helyzetek ritkulnak és nagyobb a tranzakciós teljesítmény. Hátránya: • sok helyet igényel (bár a tárak ára csökkenő tendenciát mutat manapság); • bonyolult az algoritmika (beleértve a szükségtelen verziók menedzselését); • bonyolult helyreállítás szükséges (szigorú protokoll kell). A tranzakciók újraindításának ("összeakadás" esetén) módszere az, hogy alkalmas véletlen - várakozási idő után indítjuk újra a tranzakciókat. (Pl: Ethernet-protokoll, vagy az éhező filozófusok problémája.) 25. tétel naplózás Sikertelen tranzakciók, rendszerhibák kezelése, Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 25. tétel naplózás Sikertelen tranzakciók,

rendszerhibák kezelése, 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 Példa az előzőekre: (az idő lefelé telik) 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: 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. T1 LOCK A READ A A:=A+100 WRITE A LOCK B UNLOCK A READ B T2 LOCK A READ A A:=A*A 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.: 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 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). 25. tétel naplózás Sikertelen tranzakciók, rendszerhibák kezelése, 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. Biz.: az ütemezés sorosítható, mert kétfázisú; továbbá lavinamentes, mert nincs lehetőség piszkos adat olvasására. 25. tétel naplózás Sikertelen tranzakciók, rendszerhibák kezelése, 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. 3. A helyreállítás problémája rendszerhibák esetén 25. tétel naplózás Sikertelen tranzakciók, rendszerhibák kezelése, 25. tétel naplózás Sikertelen tranzakciók, rendszerhibák kezelése, 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 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. A napló szerkezete, bejegyzései: 1. T kezdte meg működését Formálisan: (<T azonosító>, begin) 2. T írja A-t Formálisan: (<T azonosító>, A adategység, új érték, régi érték) Ha A túl nagy, akkor helyette akcióleírás szerepel a naplóban (hogyan kell az adategység új értékét előállítani). 3. (Bizonyos esetekben) T olvassa A-t Formálisan: (<T azonosító>, olvasott A értéke) 4. T eléri kész pontját

Formálisan: (<T azonosító>, commit) 5. T abortál Formálisan: (<T azonosító>, abort) A napló ilyen bejegyzések időrendi sorozata. Def.: 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. Def.: Az újra (redo) protokoll Olyan tranzakciókezelést valósít meg, amely rendszerhiba (és tranzakcióhiba) után szükségtelenné teszi az undo műveletet, csak redo kell. A protokoll a szigorú kétfázisú protokoll kiegészítése, finomítása; két része a redo naplózás és a redo helyreállítás. A redo naplózás lépései: 1. (T, begin) a

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

vizsgálata visszafelé: feljegyezzük azon tranzakciókat, amelyekre találunk (T, commit) bejegyzést a naplóban 3. addig megyünk visszafelé a naplóban, amíg ameddig nem találunk egy konzisztens állapotot 4. a 2 pontnak megfelelő tranzakciókra vonatkozó bejegyzések segítségével az DB-ben található értékeket felülírjuk az újakkal. 26. tétel Elosztott tranzakciók. Zárképzési technikák 26. tétel Elosztott tranzakciók. Zárképzési technikák Elosztott tranzakciók. Zárképzési technikák A N1 1. Alapfogalmak Def.: Elosztott DB Az elosztott adatbázis (DB) csomópontok (node, site) összessége, amelyekben egy-egy számítógép üzemel saját CPU-val és háttértárral. A csomópontok egymással össze vannak kötve adatcserére alkalmas módon. Az elosztott DB egy több helyen (gépen) lévő egységes felszínű DB Modellje egy gráf, amelyben a csúcsok a helyeket (processzorokat és táraikat) jelentik, az élek pedig az

összeköttetéseket (linkeket). Egy ilyen gráfot kijelölhet egy helyi (LAN) vagy egy nagyobb kiterjedésű hálózat (WAN). Fontos tényező a hálózat megbízhatósága, mert a megbízható működés fenntartása elemien fontos. Ennek módszerei: 1. adatok multiplikált tárolása különböző fizikai helyeken; 2. a linkek hibái ellen többszörös elérési utak biztosítása a hálózatban; 3. nagy megbízhatóságú komponensek alkalmazása Def.: Globális és lokális adategység Az adategység • funkcionális oldalról az az elem, amit írni és olvasni akarunk; • ill. amire zár és időbélyeg kerül Egy kifelé egyetlen egységnek tűnő adategység (globális adategység) több helyi tárolt részt (lokális adategységet) foglal magába. Példák: 1. ugyanazon adat több helyen (a megbízhatóság és sebesség miatt multiplikálva) 2. összetett egység gyakran bomlik fel különböző helyeken tárolt kisebb részekre Például egy biztosító ügyfél

adatbázisa fiókonként van tárolva (ez a vízszintes darabolás). 3. az előbbi két eset kombinációja Például az ügyfél-adatok fiókonként tárolódnak, de a területi központban is megtalálhatóak, hogy az összesítéseket könnyebben el lehessen végezni az adatokon. Beszélhetünk tehát globális (logikai) adategységekről, ami azt mutatja meg, hogy az adategység "kifelé", a felhasználó számára hogyan látszik. Ezzel szemben áll a lokális (fizikai) adategység fogalma, ami a modellező gráf csúcspontjaiban ténylegesen tárolt adategységet jelenti. Ebben a környezetben ugyanazt akarjuk, mint "egy processzoros" környezetben1. Célunk tranzakciók végrehajtása a logikai adategységeken. Gond: egy művelet a logikai adategységen esetleg több lokális egységet érint. (Pl Rezeda Kázmér számlája módosulását több helyen kell vezetni, követni.) Vagyis a globális tranzakció lokálisakra bomlik fel. Példa az elosztott

tranzakciókezelés problémáira A számlájáról B számlására 50 egységet utalnak: B N2 -50 -50 2 csúcson tárolják N3 +50 N1 N2 Egy művelet itt 5 csúcsot érint, vagyis 5 lokális művelet összehangolását és atomiságát kell biztosítani. +50 +50 3 csúcson tárolják 2. Elosztott zárképzés Célunk zárak képzése logikai adategységeken (hogy a globális tranzakciók sorosíthatóságát biztosítani tudjuk), melyben eszközeink lokális zárak lesznek protokollokkal kiegészítve. A módszerek elemzése elosztott rendszerben máshogy alakul, ugyanis a szokásos dolgokon (patt, abort, stb.) kívül fontos az üzenetek száma is Kétfajta üzenetet különböztetünk meg: • adatüzenet: általában hosszabb és drágább üzenet, mely az adatok eljuttatását van hivatott biztosítani egyik helyről a másikra; • kontroll üzenet: rövidebb és olcsóbb üzenet, mely a protokollok lezajlásával kapcsolatos. Def.: A WALL (write locks all) protokoll A

zárak és szemantikájuk a lokális példányokon pontosan megegyezik a R/W modellnél megismerttel. A globális adategységeken ezután zárakat az alábbiak szerint értelmezzük (A egy lokális adategység): 1. RLOCK A érvényes, ha RLOCK Ai érvényes A-nak legalább egy (lokális) példányán; 2. WLOCK A érvényes, ha WLOCK Ai érvényes A-nak összes (lokális) példányán Hatására a szokásos zárkompatibilitási mátrix az alábbi lesz: RLOCK WLOCK RLOCK Igen Nem WLOCK Nem Nem (Azaz megegyezik a lokális adategységekre értelmezett mátrixszal.) Üzenetek száma: (Tfh. A n helyen tárolódik) WLOCK: 2n kontroll üzenet = (n kérés + n válasz); és n adatüzenet; RLOCK: 1 kontroll üzenet és 1 adatüzenet (pozitív válasz esetén). Def.: Többségi zárolás 1. WLOCK A (globálisan) érvényes, ha WLOCK van az A példányai többségén 2. RLOCK A (globálisan) érvényes, ha RLOCK van az A példányai többségén ód él i i állí á i i á i iiá j 26.

tétel Elosztott tranzakciók. Zárképzési technikák Üzenetek száma: (Tfh. A n helyen tárolódik) WLOCK: n + 1 kontroll üzenet = ~(n+1)/2 kérés + ~(n+1)/2 válasz. és n adatüzenet; RLOCK: n + 1 kontroll üzenet = ~(n+1)/2 kérés + ~(n+1)/2 válasz. és 1 adatüzenet Összehasonlítva a WALL és a többségi módszert: • az adatüzenetek szempontjából azonosak; • kb. egyező számú írás/olvasás esetén kb ugyanannyi kontroll üzenetünk van; • ha több az írás, akkor a többségi a jobb; • ha az olvasás a több, akkor a WALL módszer a jobb (mert ebben olcsó az olvasás); • patt szempontjából a WALL a veszélyesebb, mert ez okoz inkább pattot és ebből fakadóan abortot. A többséginél valaki "jó eséllyel nyer" a patt-veszélyes tranzakciók közül Def.: Az n-ből k protokoll módszere (ahol k egy fix természetes szám) Ez a módszer az előző kettő általánosítása. A csomópontok száma n, továbbá (n+1)/2 ≤ k ≤ n.

1. WLOCK A érvényes, ha WLOCK Ai érvényes k db lokális példányon; 2. RLOCK A érvényes, ha RLOCK Ai érvényes (n+1-k) db lokális példányon • A módszer k = n esetén megfelel a WALL protokollnak; • k = (n+1)/2 esetén pedig a többségi protokollnak. Tehát k alkalmas megválasztásával a protokoll "hangolható". Def.: Elsődleges példányok módszere Az A logikai adategység gazdája egy előre lerögzített XA csúcs. (Pl az ügyfél gazdája az a fiók, amelynek az ügyfél kliense.) XA kezeli A-t a zárak szempontjából Konstans számú (24) kontroll üzenetre lesz szükség a kérő és XA között. Pontosabban: 1. WLOCK A-hoz kell egy kérés (kontroll) üzenet XA-ba, erre jön egy válasz, majd - jó esetben - írandó A-nak valamennyi másolata; 2. RLOCK A-hoz kell egy kontroll üzenet XA-ba, erre jön egy válasz, majd - jó esetben kiolvasható A-nak valamely másolata Tehát sokkal hatékonyabb, mint az előbbiekben megismertek, hiszen a

kontroll üzenetek száma konstans, nem n-nel arányos. Viszont sebezhetőbb, mert egy adategység egyáltalán nem elérhető, akárhány másolata is van, ha az XA csomópont kiesik. Def.: Centrális csúcs módszer Ez az előbbi speciális esete. X=XA ugyanaz, A-tól függetlenül, vagyis egyvalaki kezeli a kéréseket. Ennek következtében centralizált adatforgalom indul X felé. A módszer szervezett, de igen sérülékeny technika 26. tétel Elosztott tranzakciók. Zárképzési technikák Def.: Garasos módszer (elsődleges példányok tokennel) A rendszerben olvasó (OG) és író (IG) garasok képződnek. A megfelelő garas birtokában lehet cselekedni, azaz a garas az adategység elérését szabályozza. A következő zárkompatibilitást biztosító konvenciók vannak (azaz az A garasaira vonatkozó szabályok): 1. egyszerre legfeljebb egy db IGA lehet (tehát 0 is elképzelhető); 2. ha nincsen IGA, akkor tetszőleges számú OGA létezhet Az írás ezen szabályoknak

megfelelően a következőképp alakul: Tfh. az T az N csúcsban IGA-t akar Ha nála van az IGA író garas, akkor természetesen nem csinál semmit. I. Ekkor IGA kérő üzenetet küld a többi csúcsnak II. A kérdésére ("írhatok?") adott válasz függ az üzenetet vevő M csúcs viszonyától a kéréshez: a.) M-ben nincs IGA, ill OGA (vagy van, de lemond róla N javára); b.) M-ben van IGA, ill OGA és az kell is neki M a fenti két hozzáállás valamelyikét üzeni meg N-nek. III. Ha minden csomópont a)-t üzent, akkor N-nek IGA-ja (OGA-ja) lesz Ekkor üzen a többieknek, hogy az IGA-t ill. OGA-t semmisítsék meg Ha csak egy csomópont is b.)-t üzent, akkor N-ben nincs IGA N a kérését mindenkitől visszavonja. Az olvasás egészen hasonló, de különbséget jelent, hogy II.-ben M csak akkor mond b)-t, ha IGA-ja van (és kell neki); III.-ban siker esetén csak az IGA-t kell megsemmisíteni Üzenetek költsége: 0-3m, ahol m a csúcsok száma. A módszer jól

alkalmazkodik a hozzáférési igények térbeli mozgásához (pl.: banki tranzakciók lebonyolíthatók egy new york-i irodából vagy a Bahama-szigetekről is.) Átlagos esetben gyakran lesz 0 üzenet. 27. tétel Elosztott "Kész"-protokoll, blokkolás Elosztott "Kész"-protokoll, blokkolás 1. Elosztott tranzakciók problémái Def.: Elosztott sorosíthatóság Tranzakciók egy ütemezése egy elosztott adatbázison sorosítható, ha hatása a logikai adategységeken ugyanaz, mintha a tranzakciók valamely soros ütemezésben futottak volna le, azaz mindegyik logikai tranzakcióhoz tartozó fizikai tranzakció is befejeződik, mielőtt a soros ekvivalensben rákövetkező logikai tranzakció elkezdődik. Nem elosztott környezetben a kétfázisú zárolás elégséges feltétele volt a sorosíthatóságnak. Elosztott környezetben ez nincs így. Def.: Elosztott kétfázisú zárolás A globális sorosíthatósághoz nyilván elégséges feltétel, hogy ha a

globális tranzakciók globálisan kétfázisúak, azaz egy T egyetlen résztranzakciója sem engedhet el egyetlen zárat sem, ameddig bármelyik résztranzakció még kérhet új zárat. A megvalósítás azonban gondokba ütközik Példa: elosztott kétfázisú zárolásra Adott két tranzakció: T1 és T2, valamint két csúcs: x1 és x2. 27. tétel Elosztott "Kész"-protokoll, blokkolás elérése, sőt, akár egybe is eshetnek. Ha valamely protokoll tehát biztosítani tudja a közös kész pont képzését, akkor ez közös zárpontnak is megfelelő. A közös kész pont megvalósítása különböző hibalehetőségeket is figyelembe véve egy elosztott megegyezési feladatra vezet, amely igen költséges művelet. 2. Elosztott "Kész"-protokoll Def.: Elosztott kész pont képzése (a kétfázisú kész protokoll, 2PC) Adott egy T logikai tranzakció, számos Ti lokális tranzakcióval az Ni csomópontokban. Az a csomópont, ahol a tranzakciót

kezdeményezték, legyen a főnök, a többit nevezzük résztvevőnek. Minden résztvevő szavaz egy-egy, a főnöknek küldött üzenet formájában: • készre szavaz akkor, ha a résztranzakció elérte a kész pontját; • abortra szavaz akkor, ha bármely ok miatt a résztranzakció abortálni kényszerült. A főnök ezután két dolgot tehet: • ha minden résztvevőtől "készre szavazok" üzenetet kapott, akkor "commit" üzenetet küld valamennyi résztvevőnek. Ebből azok megtudják, hogy a tranzakció elérte kész pontját; • ha bárhonnan is "abortra szavazok" üzenetet kap, akkor a tranzakciónak is abortálnia kell, ezért abort üzenetet küld valamennyi résztvevőnek, akik ennek hatására abortálják a résztranzakciókat. Résztranzakciók: x1-re T11 T1-re: T21 T2-re: w=írás, u=elengedés, az idő lefelé telik: T11 wA uA T21 T12 wA uA wB uB T22 wB uB x2-re T12 T22 Mind a négy rész külön kétfázisú, de az egész

együtt mégsem sorosítható. • A miatt T1 előbb van, mint T2, (T1T2); • B miatt fordítva: (T2T1) Tehát hurok van a sorosítási gráfban! A megoldás ötlete: T részeinek legyen közös zárpontja, ami előtt lezajlik az összes zárkérés és ami után az összes feloldás megtörténik. (A résztranzakciók üzenetváltásokkal informálják egymást, hogy elérték a zárpontjukat, több zárra nincs szükségük.) Így már igaz lesz a kétfázisú tranzakciók sorosítási tétele. Def.: Szigorú kétfázisú zárolás A lavinák problémája az elosztott környezetben is megmaradt. Elkerülése itt is lehetséges, ha biztosítani tudjuk, hogy egyetlen résztranzakció se írjon az adatbázisba mindaddig, amíg minden résztranzakció el nem érte a kész pontját. A lavinák ellen tehát közös kész pontot kell létrehozni, amihez az kell, hogy minden résztranzakció valamennyi számítását befejezze, valamennyi zárját megkapja. Ha ez minden résztranzakcióra

teljesül akkor a tranzakció folytatható egyébként pedig Mindez állapotátmenet ábrákon : "készre szavazok" "commit" jött a küldése commit - főnöktől kezdőállapot commit képes "abortra szavazok" küldése "abort" jött a főnöktől abort Egy résztvevő állapotai mindenki "készre" szavazott commit kezdőállapot kell "commitot" küld commit valaki abortra szavazott abort kell abortot küld abort A főnök állapotai Megjegyzések: • a főnök is résztvevő egyben, ő is küld magának üzeneteket, csak éppen ezek nem költséges 27. tétel Elosztott "Kész"-protokoll, blokkolás • ha nincs főnök csak résztvevők, akkor mindenki mindenkinek kell, hogy küldjön üzenetet. Ilyenkor az üzenetek száma n2-tel lesz arányos. • hálózati hibák esetén a protokoll nem használható. Ha ugyanis Ti zárat tart fenn valamely adategységen és commit-képes állapotban van, akkor

itt is marad, ha nem jön üzenet a főnöktől (pl. hálózati hiba miatt), mert: – commit állapotba nem léphet, mert jöhet "abort" üzenet; – abort állapotba sem léphet, mert jöhet "commit" üzenet és – a zárait sem engedheti el, mert sérülhet a globális kétfázisúság. A jelenség neve blokkolás, és kiküszöbölése a hálózati hibák esetén is működőképes protokollok alapproblémája. Elosztott kész pont kétfázisú képzése Az előző protokoll továbbfejlesztése, amikor is a résztvevők a commit-abort eldöntése után két fázisban szavaznak a logikai tranzakció commitjáról ill. abortjáról Ennek eredményeképpen bizonyos hibák esetén elkerülhető a blokkolás, de a lehetősége továbbra is fennmarad. Ez a leggyakoribb algoritmus az elosztott megegyezés megvalósítására. Jelentősebb változások: – a résztranzakciók mérik azt az időt, hogy mióta várják a választ a szavazatukra. Ha túl sok idő telik

el, akkor hálózati hiba valószínű, így egy olyan állapotba lépnek be, aminek a deklarált célja a probléma feloldása. – a főnök üzenetküldéssel szólítja fel a résztvevőket a szavazás megkezdésére. Egy résztvevő állapotai Ábrázolva: "készre szavazok" "kezdj szavazni" "commit" jött a küldése érkezik commit - főnöktől kezdőállapot döntés commit képes timeout "abortra szavazok" küldése timeout "abort" jött a főnöktől abort helyreállítás "segítsetek" küldése blokkolt kezdőállapot mindenki "készre"commit várakozás szavazott kell timeout vagy valaki abortra szavazott "commitot" küld abort kell abortot küld abort A főnök állapotai commit 27. tétel Elosztott "Kész"-protokoll, blokkolás A helyreállítás folyamata: Ha a résztvevő belép a "helyreállítás" állapotba, akkor "segítsetek" üzenetet

küld valamennyi résztvevőnek (amihez ismernie kell őket). Erre válaszul jöhet: • commit üzenet, mert ha a résztvevő már commit állapotban van, akkor ezt az üzenetet kell küldenie, vagy • abort üzenet, abort állapotban lévő résztvevőtől vagy olyantól, aki még kezdő állapotban van. Ha a résztvevő commit-képes állapotban van, akkor nem tud hasznos üzenetet küldeni, így nem is küld semmit. A "blokkolt" állapotban lévő tranzakció ezután annak megfelelően jár el, amilyen üzenetet kapott. Ez a döntése helyes, mert • nem kaphat commit és abort választ is a "segítsetek" üzenetére; • nem kaphat abortot, ha a főnök commitot küldött; • nem kaphat commitot, ha a főnök abortot küldött. Ha semmilyen üzenet nem jön a segítségkérésre (mert pl. a többi résztvevőtől el van vágva vagy a többiek commit-képes állapotban vannak), akkor a blokkolás bekövetkezik. A főnök a várakozás állapotából

timeout-tal az abort állapotába kerülhet, ha valamely résztvevő hosszú idő után sem válaszol. Ekkor joggal feltételezhető, hogy a résztvevő nem elérhető vagy meghibásodott. A résztvevő, ha hosszú idő után sem kap "kezdj szavazni" üzenetet, akkor abort állapotba megy át, mert azt tételezi fel, hogy a főnök elérhetetlenné vált vagy meghibásodott. Ebben az állapotban már elengedheti a zárjait, ha pedig mégis megjön a "kezdj szavazni" üzenetet, akkor egyszerűen abortra szavaz. Megj.: egy résztranzakció kész vagy abortált állapotában is jöhetnek kérdések, ha más résztranzakció segítséget kér. Ilyenkor egy napló alapján van lehetőség korrekt választ adni 28. tétel Relációs lekérdezések kiértékelése Relációs lekérdezések kiértékelése; általános optimalizálási elvek, algebrai optimalizálás 1. Relációs lekérdezésekről általában Relációs lekérdezéseket általában nagyon sokféle

módon lehet kiértékelni. Az általános optimalizálási elvek alapja az, hogy igyekezzünk ezen kiértékelési módok közül minél jobb módszert választani: alakítsuk át a kapott relációs SQL kérdést úgy, hogy az hatékonyan számítható legyen! Készítsünk jó végrehajtási tervet! Két fő megközelítés létezik: • a fizikai és • az algebrai optimalizálás. 28. tétel Relációs lekérdezések kiértékelése Kiinduló lépésként a szóban forgó (magas szintű) kérdést átírjuk relációs algebrai kifejezéssé. A relációs algebra kifejezései egyszerű és erős átalakításokat tesznek lehetővé, és az ekvivalens átalakítások során kialakul a végrehajtási terv. Példa: egy SQL kérdés lefordított formája: ΠA(σB=C ∧ D=99(AB × CD)). Itt a D=99 feltételt rögtön a CD relációra is elvégezhetjük, így kisebb lesz a szorzat. Sőt: ΠA (σB=C (AB × σ D=99(CD))). A szorzás helyett az illesztést is végezhetünk, mivel a σ

előírt feltétele egy egyenlőség: σ D=99(CD)). ΠA (AB B=C 2. A fizikai optimalizálás A fizikai optimalizálás ötlete az, hogy megpróbáljuk figyelembe venni a tényleges adatszerkezetek sajátosságait. A fizikai szervezés ismeretében pedig megbecsüljük az egyes végrehajtási módszerek időigényét, és közülük a legígéretesebbet hajtjuk végre. Példa: legyen AB és CD két, egyaránt kétoszlopos reláció. Feladat: számoljuk ki a két reláció direkt szorzatát! Ez - mint tudjuk - egy időigényes művelet. • AB rekordjait jelöljük nA-val, blokkonként bA darab van belőlük; • CD rekordjait pedig jelöljük nC-vel, ezekből blokkonként bC darab van. (A lemezelérés a blokkok darabszámával jellemezhető.) Legyen a memóriában m blokknyi hely a műveletre! Vegyünk egy blokkot AB-ből, helyezzük el azt a memóriában, és vegyük hozzá a CD blokkjait! A művelet költsége: nA nC n n ⋅ + A = A b A bC (m − 1) b A b A   nC 1 + 

 bC (m − 1)  CD olvasások + AB olvasása egy blokk AB-ből (m-1) blokk CD-ből nC n A < , akkor érdemesebb a CD-ből venni egyesével az elemeket (blokkokat), majd bC b A ehhez betölteni (m-1) számú blokkot AB-ből. Ha Fontos még figyelembe venni az indexek (index állományok) jelenlétét is (a természetes illesztés és a vetítés műveleténél). Az is elképzelhető, hogy sok művelet helyett érdemes egy ideiglenes indexet / rendezést készíteni az adatállományhoz, mert így az érdemi munka nagyon lerövidül. Csomósodás figyelembe vétele: vajon az adott (keresett) értékű mezővel rendelkező rekordok egy csomóban helyezkednek el, vagy szétszórva? Megbecsülhetjük még a közbülső eredmények méreteit is: érdemes azt a megoldást választani, amelyben folyamatosan csökken a részeredmények mérete. Pl az A B C művelet asszociatív, ezért a relációk méretének ismeretében kiválasztható a jó megoldás. (Illesztéseknél fontos

még annak vizsgálata is, hogy egy R-beli A értékhez mikor (milyen gyakran) lesz S-beli A érték). 3. Az algebrai optimalizálás Def.: Ekvivalens relációs algebrai kifejezések Az E1 és E2 relációs algebrai kifejezések ekvivalensek (E1 ≡ E2), ha a bennük lévő alaprelációk minden konkrét értékére „lényegében” - a sorok vagy oszlopok sorrendjétől eltekintve - ugyanazt adják. A fentieknek megfelelően az optimalizálás során az eredeti E1 kifejezés helyett egy gyorsabb E2 ekvivalenst keresünk. Tétel: Néhány fontosabb relációs ekvivalencia: • asszociatív szabályok: (E1× E2) × E3 ≡ E1× (E2 × E3) (E 1 E2) E3 ≡ E1 (E2 E3 ) • kommutatív szabályok: E1× E2 ≡ E2 × E1 E1 E2 ≡ E2 E1 • vetítések összevonása: ΠA1.Ak (ΠB1Bm (E)) ≡ ΠA1Ak (E) (ekkor kell, hogy {Ai}⊆{ Bj }) • szelekciók összevonása: σF1 (σF2 (E)) ≡ σF1 ∧ F2 (E). • szelekció és vetítés felcserélései: ha F-ben csak A1.Ak attribútumok

szerepelnek, akkor: ΠA1.Ak (σF (E)) ≡ σF (ΠA1Ak (E)) • szelekció és direkt szorzás felcserélései: ha F-ben minden attribútum E1-beli, akkor: σF (E1 × E2)) ≡ σF (E1) × E2. • szelekció és únió felcserélései: ha F-ben minden attribútum E1-beli, akkor: σF (E1 ∪ E2)) ≡ σF (E1) ∪ σF(E2). Az algebrai optimalizálás végeredménye egy átalakított kifejezésfa, ami ún. csoportokra van bontva. A csoport egy több műveletből álló részfeladat, amit egy menetben érdemes elvégezni A csoport jellegzetes alakjai: σ, Π, Πσ * σ, Π, Πσ σ, Π, Πσ Itt egyargumentumú műveleteket és a * ∈ {∪,,×} kétargumentumú műveletek egyikét vontuk össze