Information Technology | Databases » Adatbázisok vizsgatételek

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

módjai 1. tétel 3. A DBMS vázlatos modellje sémaműveletek lekérdezések adatműveletek "lekérdezés" processzor tranzakciókezelő tárkezelő DB adatok metaadatok A DBMS-hez az alábbi műveletekkel fordulhatunk: 1. Sémaműveletek: a DB logikai vázának kialakítását, módosítását jelentik (a DDL igénybevételével). 2. Lekérdezések: kérdéseket fogalmazunk meg a DB tartalmával kapcsolatban Ennek kétféle (bár nem teljesen független) változata: 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 2 Az adatbázis fogalma, fontosabb összetevői, felhasználási módjai 1. tétel A blokk egy ütemben írható/olvasható terület, mérete leggyakrabban 212-214

byte (ez egy rendszerfüggő paraméter). A tárkezelő puffer-blokkjai elkülönülésének oka a fizikai adatfüggetlenség elve: ha igényeinkben változások állnak be, akkor a továbbiakban is használható legyen az adatbázis, vagyis logikai vázát ne kelljen átszervezni. Célunk tehát az, hogy a fizikai kérdéseket a többitől nagyrészt függetlenül tudjuk kezelni. 2. "Lekérdezés" processzor (lekérdezés feldolgozó): magas szintű (pl szelektor) kérdések átalakítását végzi egyszerű utasítások sorozatára. A "MIT"-et bontja le kisebb elemekre, amelyek válaszolnak már a "HOGYAN"-ra is. Ebben a lebontásban fontos az optimalizálás, a lehetséges végrehajtások közül az "intelligens" feldolgozó választ: végrehajtási tervet készít. A standard formában megfogalmazott kérdéseket lehetőséghez mérten átalakítja, majd a már végrehajtható utasításokkal a tárkezelő felé fordul. Példa: ÜGYFÉL

tábla NÉV CÍM EGYENLEG SELECT név FROM ügyfél WHERE egyenleg < 0 AND nemzetiség = DOGON 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, 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 3 1. tétel Az adatbázis fogalma, fontosabb összetevői, felhasználási módjai 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. 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. 4 1. tétel Az adatbázis fogalma, fontosabb összetevői, felhasználási módjai 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. 5 2. tétel Az adatbázisok fejlődési trendjei Az adatbázisok fejlődési trendjei 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 m odell: kiszorulóban van, ami részint fogalmi gyengeségének következménye. • Hálós m odell: 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. 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: 1 2. tétel SELECT termék FROM termelő WHERE

mennyiség > 100 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ér dé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). 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. 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 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 f oglalá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. Pl.: C = Ügyfél Minden ügyfél egyben személy is. 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.) t rigger: 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), 3 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 m ining), 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. 4 Az ODL-modellező nyelv 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 valóság egy darabja a.) adatmodell leírás adatmodellező eszköz pl. ODL, E/K b.) DB séma DDL A folyamat tehát felfogható úgy, hogy egy "a valóság egy darabjáról" - pl. egy cég nyilvántartásáról szeretnénk adatmodellt és arról később egy DB sémát, azaz konkrét adatbázist készíteni. A

DB séma már egy tényleges értelmezhető kód A fázisok közötti átmenetek a következők: a.) adatmodellező eszközöket használva (pl ODL, E/K) készítjük el az adatmodell leírását b.) DDL segítségével alakítható ki a DB séma A folyamat legfontosabb része az a.)-ban zajló tevékenység; b) ebből már nagyrészt automatikusan adódik. Az adatmodellező eszköz többé-kevésbé formális jelölésrendszert biztosít adatok, kapcsolataik és a rajtuk végzett műveletek kifejezésére. Az adatmodellezés egyes eszközeinek kapcsolata és eredménye: ODL obj. DB a valóság egy darabja relációk E/K 2. Az ODL (Object Definition Language) módszertan Az ODL elemei: 1 relációs DB Az ODL-modellező nyelv 3. tétel – 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 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 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 2 Az ODL-modellező nyelv 3. tétel • egy objektum képe ennek megfelelően: OID + {"Az erőszak vége", 1998, 122, színes} 2. színészes példa interface Színész { attribute string név; attribute struct Cím { string város string utca} lakcím} típus rekordkonstruktor attribútumnév mező típusa mező neve

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 Az ODL-modellező nyelv 3. tétel 2. színészes példa (kapcsolat a Színész oldaláról) relationship Set < Film > szerepel benne; reverse Film: szereplők; 3. konkrét adatokkal a kapcsolatok így néznek ki: Film 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. Pl.: C = Film köztük a "szereplők", "szerepel benne" kapcsolatok N:N típusúak 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). Pl.: C = Film köztük a "gyártó" kapcsolat N:1 típusú 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. Pl.: C = Stúdió köztük az "elnök" kapcsolat 1:1 típusú, feltéve, hogy egy stúdiónak 4 Az ODL-modellező nyelv 3. tétel 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. 5 Az ODL-modellező nyelv 3. tétel 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. L ist <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, . , T n 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 > 6 Az ODL-modellező nyelv 3. tétel 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: 7 Az ODL-modellező nyelv 3. tétel 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ó. 8 Az ODL-modellező nyelv 3. tétel • A kulcs általános alakja: interface < osztálynév > (key(s) K1, K2, . , Kn ) {-}; A Ki kulcsleírás alakja: < attribútumnév >; vagy (attr1, . , attrn) Példák 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 9 Az ODL-modellező nyelv 3. tétel 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. 10 4. tétel Az egyed-kapcsolat modell 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 valóság egy darabja a.) adatmodell leírás adatmodellező eszköz pl. ODL, E/K b.) DB séma DDL A folyamat tehát felfogható úgy, hogy egy "a valóság egy darabjáról" - pl. egy cég nyilvántartásáról szeretnénk adatmodellt és arról későnn egy DB sémát, azaz konkrét adatbázist készíteni. A DB séma már egy tényleges értelmezhető kód A fázisok közötti átmenetek a következők: a.) adatmodellező eszközöket használva (pl ODL, E/K) készítkjük el az adatmodell leírását b.) DDL segítségével alakítható ki a DB séma A folyamat legfontosabb része az a.)-ban zajló tevékenység; b) ebből már nagyrészt automatikusan adódik. Az adatmodellező eszköz többé-kevésbé formális jelölésrendszert biztosít adatok, kapcsolataik és a rajtuk végzett műveletek kifejezésére. Az adatmodellezés egyes eszközeinek kapcsolata és eredménye: ODL obj. DB a

valóság egy darabja relációk E/K 2. Az Egyed/Kapcsolat (E/K) modell Nevezik még Tárgy/Kapcsolat, vagy Entitás-relációs modellnek is. 1 relációs DB 4. tétel 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 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 l ehet r ekordtí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 A1 Ak . A2 . . Példa: az ODL-nél megismert Film az E/K modellben cím év Film hossz szalagFajta 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.) 2 4. tétel Az egyed-kapcsolat modell Rajzban a kapcsolat nevét rombuszba foglaljuk: E1 R Em E2 . . . E3 Példák 1. a Film-Színész kapcsolat: cím év Film hossz név Szereplők lakcím Színész szalagFajta Megj.: az ODL-ben a lakcím rekordként volt definiálva Itt ez nem megy!

2. Nemzetközi munkamegosztás Cég Ország Termel Termék Egy cég termékeit több országban is termelheti / értékesítheti. Ez egy m=3 komponensű kapcsolat. 3. a filmes példa továbbfejlesztése gázsi Film Szerződés Stúdió 3 Színész 4. tétel Az egyed-kapcsolat modell A filmet egy adott stúdió forgatja; erre a produkcióra szerződik a színész. Ha a "gázsi" attribútumot szerepeltetni akarjuk az ábrán, akkor az csak a Szerződés nevű kapcsolathoz köthető, mert: – egy filmhez több színész és így gázsi tartozik; – egy stúdió több filmet forgat; – egy színész több filmben játszik. Tapasztalat: kapcsolatnak is lehet attribútuma. (Bár ez új egyedhalmaz felvételével kiváltható.) Kapcsolatok típusa az E-K modellben A kapcsolatok típusa megegyezik az ODL-ben ismertetett típusokkal, csak a jelöléstechnika más - a függvény-jellegre nyíl utal. 1:1 kapcsolat E1 R E2 N:1 kapcsolat E1 R E2 Pl.: Személy

Stúdióvezetó kapcsolat ("elnök") mindkét végén nyíl Pl.: Gyermek -Anya kapcsolat ("anyja") csak egy nyíl N:N kapcsolat E1 R E2 nincs nyíl Az N:1 (több-egy) kapcsolat értelmes lehet kettőnél több komponensű kapcsolatnál is. (Lásd: filmes példa - nyíl a Stúdió felé.) Általánosan: az R(E1,.,Ek) több-egy kapcsolatban a nyíl Ej felé mutat, ha tetszőlegesen választott e∈E (i≠j) egyedkollekcióhoz legfeljebb egy olyan ej van, amivel (e1,.,ej,,en) ∈ R Azaz a maradék - nyíl által nem mutatott - komponenseket (egyedeket) egyféleképp egészíthetjük ki úgy, hogy egy relációt kapjunk. 4 4. tétel Az egyed-kapcsolat modell Sokágú kapcsolat átalakítása kétágú (több-egy) kapcsolattá Menete: E1 R E2 E1 => . . E1-k . R E2 E2-k . Ek-k . . E2 R - melyet kapcsoló halmaznak szokás nevezni - elképzelhető úgy, mint egy k mutatót tartalmazó egyedhalmazt. R-nek gyakran nincs attribútuma (ekkor

gyenge egyedhalmazról beszélünk). Példa: a Szerződés kapcsolat átalakítása N:1 típusúvá (számunkra ez jobb) Színész Sz Film Szerződés F gázsi S Stúdió 5 4. tétel Az egyed-kapcsolat modell Öröklődés, alosztályok az E/K modellben Tfh. az E1 egyedhalmaz szűkítése az E2-nek Ezt jelölhetjük ezekkel: is-a vagy az egy is-a vagy az egy angol magyar Az alárendelt egyedhalmaz örökli felmenői attribútumait. Egy "objektum" nem feltétlen egy "osztályyhoz" tartozik. Példa: Film, Rajzilm, Krimifilm cím év Színész szalagFajta hossz Film Hangok is-a is-a Rajzfilm Krimifilm bizonyíték Itt nincs szükség külön Krimirajzfilm egyedhalmazra. Pl ha a "Macskafogó" a krimirajzfilm, akkor lesz egy neki megfelelő Rajzfilm és egy Krimifilm egyed is, melyek ugyanoda, ugyanarra a filmre fognak mutatni, azaz közös apjuk lesz. Megszorítások az E/K modellben 1. Kulcsok • a rajzból indulunk ki,

ezért fontos, hogy az egyszerű legyen - ami a séma egyszerűségét is mutatja. • a rajzon csak egyetlen kulcsot jelölünk: ez az ún. elsődleges kulcs (primary key) • a nem elsődleges (azaz másodlagos) kulcsokat a modell külön leírásban tünteti fel. 6 4. tétel Az egyed-kapcsolat modell Pl. a Filmet a címe és a gyártási éve azonosítja, tehát itt a (cím,év) pár az elsődleges kulcs (amit aláhúzással jelölünk). Film cím év hossz 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. 3. Hivatkozási épség A "pontosan egy" kapcsolatot lekerekített nyílhegy jelöli. Példák: 1. Egy filmnek kötelezően van egy (pontosan egy) gyártó stúdiója Film Stúdió Gyártó

2. Minden stúdiónak pontosan egy elnöke van, azaz nem létezhet stúdió elnök nélkül Egy elnök legfeljebb egy stúdióhoz tartozhat. Stúdió Vezeti Elnök Része Flotta 3. A kapcsolat fokának korlátozása Pl.: Hajóraj <= 3 (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. 7 4. tétel Az egyed-kapcsolat modell Egy több komponensű kapcsolat átalakításakor a kapcsoló rekordot így jelöljük: Ennek az azonosításban résztvevő kapcsolatait pedig így: Követelmények: • ha az F egyedhalmaz hozzájárul az E gyenge egyedhalmaz kulcsához, akkor azt az megfelelő R (N:1) kapcsolattal együtt így kell ábrázolni (F is lehet gyenge egyedhalmaz): E F R • az E azonosítására

szolgáló F-beli attribútumok elemei F kulcsának is. Példa: szervezeti egységek részegységekből - csoportokból - épülnek fel. A csoportokat számukkal írjuk le (ez egyetlen attribútumuk): szám Csoport név Része cím Stúdió A Csoport gyenge egyedhalmazt jelöl: ennyi attribútummal (szám) önmagában nem azonosítható, csak a "Része" kapcsolatot követve a Stúdió alapján. Ha a Csoportba bekerülne a stúdiónév (azonosító!) is, akkor további redundanciaprobléma is felmerülhetne (inkonzisztens nevek: a névváltozást nem minden előfordulásában követjük). 3. Adatmodellezési alapelvek 1. Valósághű modellezés • a fontos adatelemek és • a fontos kapcsolatok is legyenek benne a modellben! 2. A redundancia elkerülése 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; 8 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. 9 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! 1 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. 2 5. tétel sémákká Egyed-kapcsolat sémák átalakítása relációs, hálós és hierarchikus E/K sznév Hálós szcím Szállító SZ Á Szállító Ár TERÁR Ár egys ár Termék TERREND Rendelés termék SZEMREND Személy Rendelés szám menny Megrendelő név 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 E vD 3 vB C D E vE vA 5. tétel sémákká

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 2. Hierarchia -> hálós séma C B A B A C vA D D vA vC Az eredmény több fa lett. A módszer elvileg jó, de nem ad túl értelmes megoldást. (Hármas lépcsőben nemigen kérdezünk.) 4 Az alapvető fizikai tárolási szerkezetek összehasonlítása 6. tétel Az alapvető fizikai tárolási szerkezetek összehasonlítása 1. Alapfogalmak A fizikai szervezés célja, hogy egy rekordokból álló állomány kezelése megoldható legyen a következő műveletekkel: beszúrás, törlés, keresésé, módosítás. Ez a külső táras

(diszkek, dobok) adatkezelés kérdésköre. A fizikai szervezés elemei: • blokk ( lap): fix méretű adatterület, tipikusan k . 512 byte (ált k=1,,10) méretű (ez egy rendszerenként változó paraméter). A blokk számunkra egyetlen I/O művelettel elérhető tárterületet jelent. Egy blokk több rekordot tartalmazhat A blokkok elérése történhet abszolút vagy relatív cím alapján. A külső táras módszerek hatékonyságát a blokk(lap)elérések számában mérjük Tipikus blokkfelépítés: menedzsment információk maradék fej rek1 . rekn • mutató (pointer): bejegyzés, ami egy blokk / rekord címét tartalmazza blokk / rekord • • kötött r ekord / bl okk: 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 . – változó hosszúságú: kétféle alkalmazási módjuk:  fix mezőszerkezet változó hosszúságú mezőkkel: például regények text adatbázisában egy egész könyv szövege szerepelhet egy mezőben. szerző cím szöveg fix fix változó 1 A rekordban szerepelhetnek azért fix hosszúságú mezők is, ha ezek hosszára található valamilyen ésszerű felső korlát. 6. tétel Az alapvető fizikai tárolási szerkezetek összehasonlítása 2 Az alapvető fizikai tárolási szerkezetek összehasonlítása 6. tétel Ez a struktúra kizárólag fix hosszúságú mezőkkel így írható le: szerző cím fix fix . • szöveg mutató fix szöveg . Itt a szöveg-mutató mező egy kevéssé struktúrált másodlagos s zö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: Cím Év . Film Szereplő1 . 2. Mutató módszer: egyetlen mutató mezőt kell lefoglalni, amely egy, az ismétlődő elemeket tartalmazó listára fog mutatni. A mutató tehát kimutat az eredeti állományból. Például: Cím É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: 3 Az alapvető fizikai tárolási szerkezetek összehasonlítása 6. tétel Cím Év . Film Szereplő1 . SzereplőC Szereplő-lista • állomány: blokkokon elhelyezkedő információtárolási szerkezet. Az állomány blokkjai elérés-folytonosan 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 r ekord b eilleszté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. 4 6. tétel Az alapvető fizikai tárolási szerkezetek összehasonlítása 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. 5 7. tétel

Hashelés és ritka indexes szervezési módszerek Hashelés és ritka indexes szervezési módszerek 1. Adatbázisok alapvető fizikai szervezési elvei Ezek a következők: 1. Kupac (heap) (erről az előző rételben már volt szó) 2. Hash 3. Indexelt szervezés 2. Hash-szervezés Elsősorban a vödrös (bucket) hash-elés és változatai használatosak. Az alapmódszerben adott: • B db vödör (egy vödör egy kis - kevés lapból álló - lap-láncot jelent); • egy vödörkatalógus (0-tól (B-1)-ig indexelt tömb) • és a h: {kulcsok} -> [0,B-1] hash-függvény, mely legyen gyorsan számítható és ne okozzon túl sok ütközést (ütközés: két kulcshoz h ugyanazt a tömb-cellát rendeli) Ábrázolva: 0 . vödör . . . i. . . . 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 1 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 0 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. 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 0 0 1 0 1 1 vödör3 1. Ha ez az elválasztás nem lehetséges a következő (jelen esetben a harmadik) bitnél, akkor egy bittel tovább kell nézni a h(K) értékeket. A legrosszabb esetben ez a megkülönböztetés sosem ejthető meg (de ennek nagyon kicsi a valószínűsége). vödör1 00. vödör21 010. vödör22 011. Van értelme a testvér-vödrök összevonásának is. Ha törlünk egy vödörből, akkor megnézzük a testvérét: ha együtt jobban ki vannak töltve, akkor érdemes összevonni őket. Természetesen a dinamikus hash-elés az alapmódszernél nehézkesebb és

költségesebb. Ez részint attól is függ, hogy mi kerülhet be a belső memóriába (esetleg az egész szerkezet vagy csak a gyökérhez közeli csúcsok, stb.) A költséget ezért nehéz pontosan megbecsülni 2 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 d a lokális m élység. Pl d=3=d => a katalógus elemeit címző háromjegyű cím mindhárom bitjére szükség van a vödörben; benne minden rekord 000-val kezdődik. Ha d=2, akkor az azt jelenti, hogy itt elég 2 bit a rekord eléréséhez, elhelyezéséhez. A szervezés során mindvégig igaz, hogy d<= d. Tehát a globális mélység a használható, a lokális mélység

pedig a használt bitek számát jelenti. Túlcsordulás esetén a vödör lapjait két vödörben próbáljuk elhelyezni. • d nő (azaz új, nagyobb táblát készítünk), ha a d lokális mélységű vödör túlcsordult; • d csökken (azaz új, kisebb táblát készítünk), ha minden d < d. 3. Indexelt szervezés A módszer kihasználja a kulcsok rendezettségét és alapvető műveletek megvalósítására szolgál. Adott a tényleges, tárolni kívánt "fő" állomány ("nagy" rekordokkal). Felette helyezkedik el az index ál lomá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. Az index rekord felépítése: Kulcs Mutató igazi rekordkulcs általában egy lapra mutat (ez lehet az index

[bonyolultabb] vagy a főállomány [egyszerűbb] egy lapja) 3 7. tétel Hashelés és ritka indexes szervezési módszerek Az indexelés fajtái: a.) Egyszintes ritka indexelés (ISAM) • az index rekordok kulcs szerint rendezve vannak az index állományban elhelyezve; • mutatójuk a fő állományba mutat. Kapcsolat a mutató és a mutatott rekord között: K index rekord m K rek1 K rek2 a fő á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 k eresé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. A stratégia következménye, hogy a lapok legalább félig telítve lesznek a főállományban. 4 7. tétel Hashelés és ritka indexes szervezési módszerek 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). 5 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 Itt nincs szükség

vágásra és összevonásra; a fő állomány rekordja nem mozdul és az index sem változik. B . . A ritka index szabad és kötött változata között a költség szempontjából drámai különbség van. További módszerek: (a köv. tétel anyaga) c.) Többszintes indexelés d.) Sűrű indexelés 6 B-fák és sűrű indexek 8. tétel 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 ál lomá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. Az index rekord felépítése: Kulcs Mutató igazi rekordkulcs általában egy lapra mutat (ez lehet az index [bonyolultabb] vagy a főállomány [egyszerűbb] egy lapja) Az indexelés fajtái: a.) Egyszintes ritka indexelés (ISAM) b.) Egyszintes ritka indexelés - statikus változat (ezekről már az előző tételben esett szó) c.) Többszintes indexelés Ötlet: az index állomány fölé tegyünk egy (vagy több) újabb index állományt! Index állomány A felső index állomány ritka indexe az alatta lévőnek. Index állomány Fő állomány Ha az index állomány túl nagy lett (vagyis a fő állomány hatalmas), akkor a szerkezet 1fölé teendő egy újabb index állomány. B-fák és sűrű indexek 8. tétel A dinamikus többszintű indexek B-fákkal valósíthatók meg. Az index állomány szintek ún. index fát alkotnak: Index fa Fő

állomány gyökér szint i. index szint utolsó index szint Tulajdonságok: • minden lap legalább félig telítve van (ez alól csak az egész kicsi szerkezetek jelentenek kivételt); • a gyökér-levél utak egyforma hosszúak (ez egy kiegyensúlyozottsági tényező); • a keresés logaritmikus; a logaritmus alapszáma attól függ, hogy hány index rekord fér egy lapra (tehát nem az elágazások száma befolyásolja); • a módszer teljesen dinamikus - elkerüljük ezáltal, hogy egy nagy állomány közepébe ugorjunk. Ezt a szervezési módot az egyes SW-cégek többnyire szabványosítják - ilyen például az IBM VSAM szabványa, amelyben B-fákat használnak. d.) Sűrű indexelés A fő állomány minden rekordjához tartozik index bejegyzés. index állomány Fontos, hogy itt nem tételezünk fel semmiféle rendezettséget a fő állomány rekordjaival kapcsolatban! rek1 rek2 rekn . fő állomány A sűrű indexelés célja, hogy a kötött fő állományt

felszabadítsuk: ritka index A sűrű indexre építünk valamilyen elérési utat, például egy ritka indexet. sűrű index szabad rekordok Fő állomány kötött rekordok 2 B-fák és sűrű indexek 8. tétel A sűrű indexelés tehát önmagában nem egy új elérési technika, hanem csak egy segédeszköz a fő állomány felszabadítására. Ez "szabadság" a módszer fő előnye, hiszen a sűrű index állomány rekordjait úgy mozgathatjuk, ahogy csak akarjuk. Ha fontos számunkra a fő állomány rekordjainak különböző kulcsok szerinti gyors elérése, akkor a fenti sűrű indexes szervezés egyenesen el sem kerülhető, nem csak praktikus szempontok miatt van rá szükség. 3 B-fák és sűrű indexek 8. tétel 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 ku lcs-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ú 4 B-fák és sűrű indexek 8. tétel Ha pl. egy kérdésben m4 és m9 ismert (ezek lehetnek: szemszín és hobby), akkor h4(m4) és h9(m9) jelentősen leszűkíti a keresést, a szóbajövő rekordok körét. A szervezési mód tehát a keresés idejét nagy mértékben lecsökkentheti, de a kulcs-alapú kereséssel szemben (vagy mintha minden kombinált kérdéshez saját index állományt készítenénk) gyorsaságban még így is messze alulmarad. 5 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban Tárolási struktúrák és sémakezelés hálós adatbázisokban 1. Bevezetés A hálós adatmodell a CODASYL DB TG (Comittee On Data Systems Languages - Data Base Task Group) bizottság munkájának eredménye. A CODASYL bizottság a 70-es

években dolgozta ki a hálós adatkezelés alapelveit és foglalta össze a DBTG-ajánlásban. Az ANSI az ajánlást a 80-as években standarddé tette. A DBTG-ajánlás részei: • hálós DDL • DML és extra kiegészítések (például egy, a jó hatékonyságú DB-k létrehozásában fontos szerepet játszó hasznos adatszerkezet.) Egy - elvi és gyakorlati szempontból is nagy jelentőségű - klasszikus hálós adatbázis-kezelő rendszer az IDMS nevet viseli. 2. A hálós adatmodell elemei I. Adattípusok • (logikai) r ekord 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 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. kapcs név E rekordtípus 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 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban 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. E/K sznév Hálós szcím Szállító SZ Á Szállító Ár TERÁR Ár egys ár Termék TERREND Rendelés termék SZEMREND Rendelés szám

Személy menny Megrendelő 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 Az elhelyezési információk fajtái: 2 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban – 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 I S. 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ó Rezeda Kázmér Termék rend1 Ár ár-rekord: érdemi rész rend2 . rendn sz mut t mut átlalában annyi mező van itt, ahány kapcsolatban gyermek az illető A gyűrű séma szinten tervezhető. 2. Dolgozó-Projekt modell (lásd: 2 melléklet) átalakítva: 3 9. tétel Dolgozó Tárolási struktúrák és sémakezelés hálós adatbázisokban Dolgozik

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

CURRENT (<set-név>): a születő rekord a kapcsolat "kurrens", aktuális gyűrűjébe kerül. Megtartási kényszer (RETENTION) Azt mutatja meg, hogy egy gyermek mennyire vehető ki a kapcsolatból. Lehetőségek: • FIXED: a gyermek nem vehető ki a kapcsolatból, azaz a gyűrűből. A gyermek e gyűrűt csak törléssel hagyhatja el. Pl: esetleg TERÁR • OPTIONAL: nincs korlátozás, pl. ilyen a SZEMREND • MANDATORY: egyfajta átvihetőséget jelent, amikor a gyermek típusú rekord átvihető másik gyűrűbe, de egyúttal nem létezhet gyűrű nélkül. 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. LOCATION MODE IS VIA TERÁR SET. 01 ÁR REAL. 01 TNÉV VIRTUAL 4 9. tétel Tárolási struktúrák és sémakezelés hálós adatbázisokban 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. (DBTG) SET SZEMREND. ORDER IS LAST. OWNER IS SZEMÉLY. MEMBER IS RENDELÉS. SET SELECTION IS MANUAL. RETENTION IS OPTIONAL. III. Hálós DML: köv tétel 5 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 1. Bevezetés A hálós adatmodell a CODASYL DB TG (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 (a ktualitás) m utató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 I S 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). 1 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 Tehát a rekord sablon a rekord kitöltésére szolgáló közbülső hely; a rekord ezen közbülső helyen keresztül kapcsolódik a DB-hez és a külvilághoz. Hivatkozás mezőre: Pl. SZEMÉLYFIZ vagy FIZ IN SZEMÉLY (egy más dialektus szerint). DML utasítások: a gyűrűkben való mászkálás bennük erősen támogatott. • GET • GET <rekordnév> • GET <rekordnév> <mezők> • GET <mezők> Ezek lényegében ugyanazt jelentik, ennek megfelelően a rekord, amire vonatkoznak, minden ugyanaz, csak az eredmény megjelenítése lesz más. A programkurrens alapján egyértelmű, hogy melyik rekordról van szó. A GET parancs-változatok jelentése: a CRU által mutatott rekord a saját sablonjába másolódik. A paraméterek csak hibaellenőrzésre szolgálhatnak • Az érdemi utasítások a kurrencia

mutatókat kezelik. Erre szolgálnak a FIND utasítások: 1. FIND <rekordtípus> BY DBKEY X - itt X egy változó Pl.: X = CURRENT OF TERMÉK FIND TERMÉK BY DBKEY X. 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 O WNER O F CURRE NT <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 2 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. 3 11. tétel Sémakezelés és tárolási struktúrák hierarchikus adatbázisokban Sémakezelés és tárolási struktúrák hierarchikus adatbázisokban 1. Bevezetés Szemben a hálós modellel ez az adatmodell úgymond "szervesen" alakult ki, nem egy bizottság munkájának eredménye. Például a hierarchikus adatmodellt használja az IMS (IBM), illetve a SYSTEM 2000 (egyetemi fejlesztés). Alapötlete az, hogy próbáljuk meg a világ - esetleg vélt - hierarchiái mentén megszervezni a DB-t. Ilyen hierarchiát

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

hierarchikus megoldására: Film Szerepel 1 Színész 11. tétel 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 Érdemes a gyökeret VRT-nek (virtuális rekordtípusnak) választani. Színész VRT (virtuális rekordtípus) Színész Film VRT (virtuális rekordtípus) Általánosan: E1 e1,e2,. E2 f1,f2,. e2 e1 f1 f2 f2 f4 A rekordok szintjén megjelennek a fák. rekordtípusok 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. Á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 2 A A D B C B E 11. tétel C D Sémakezelés és tárolási struktúrák hierarchikus adatbázisokban vD vB E vE vA Az átíráskor minden rekordtípust és nyilat ábrázolunk. Kijelöljük az első gyökeret - ez általában egy nagy be-fokszámú rekordtípus. (Itt: A) Az átalakítással gyakran nem kapunk "szép" fát, sokszor nem is lehet a feladatot egyetlen fával megoldani. Ezért célszerű vagy szükséges is lehet több gyökeret választani 2. Hierarchia -> hálós séma B A B A C vA C D D vA vC Az eredmény több fa lett. A módszer elvileg jó, de nem ad túl értelmes megoldást. (Hármas lépcsőben nemigen kérdezünk.) 3. A hierarchikus DDL A hierarchikus DDL-ben irányított fákat írunk le: TREE <fanév> <rekordtípusok leírása> <rekordtípusok leírása> ::= <rekordnév> <információ>

<információ> ::= 1. Mezők: név, szint, típus, hossz 2. Hely a fában: • ROOT (gyökér) • PARENT <rekordnév> (szülő) 3. Virtualitás • virtuális: igen / nem • hol az eredetije VIRTUAL <rekordnév> IN <fanév> Példa: (3. melléklet) Fiók Ügynök Ügyfél a gyökér TREE BIZTOSÍTÓ RECORD FIÓK ROOT. 01 FNÉV. 01 FCÍM. RECORD ÜGYNÖK PARENT=FIÓK. 01 NÉV. 01 KÖTÉS. (* az ügynök által eladott biztosítások éves díjtételeinek összege *) RECORD ÜGYFÉL PARENT=ÜGYNÖK. 01 ÜNÉV. 01 ÜCÍM 3 11. tétel Sémakezelés és tárolási struktúrák hierarchikus adatbázisokban 4. Hierarchikus DML (DL/I) köv tétel 4 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban 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 ÜNÉV. 01 ÜCÍM 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:  T • A gyökértől T-hez vezető út van. 1 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban • Csak T-re és felmenőire (melyek ezen az úton vannak) tartalmazhat feltételt. <feltétel> ::= <rekordnév>.<mezőnév> Θ érték Θ ∈ {<,≤, >,≥,≠} elemi összehasonlító műveletek A feltételek

kombinálhatók: AND, OR, NOT. Példa: (az előbb definiált sémában) Keressünk egy (a legelső) olyan ügynököt, akinek kötései 100000 felett vannak és a csornai fiókban dolgozik. GET LEFTMOST ÜGYNÖK WHERE FCÍM="Csorna" AND KÖTÉS > "100000" vagy: read C, K. GET LEFTMOST ÜGYNÖK WHERE FCÍM=C AND KÖTÉS > K • GET NEXT Egy lépést jobbra lép a fában, ha tud. 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 N EXT-tel gyalogolunk végig a többi ügyfélen. Az utolsó WHERE sor 2 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban szükséges, mert elhagyása esetén esetleg más ügynök ügyfeleit is kilistáznánk. Egyszerre egy rekordot kapunk meg, ezért ezt a DML-t nevezik "egyszerre egy" típusú nyelvnek is. Ahogyan a hálós modellben láttuk, itt is van rekordsablon, kurrencia, mezőkre való hivatkozás. A szülő átlépésének elkerülése pedig WHERE-rel lehetséges Létezik a kurrens szülő fogalma is: a GET-tel vagy GET NEXT-tel legutoljára elért felmenő típusú rekord. • GET NEXT WITHIN PARENT Jobbra lép, megtartva a kurrens szülőt. Példa:

Nehagyd Döme további kalandjai Az előző példa során megeshet, hogy több Nehagyd Döme nevű ügynök is van. Ekkor az összes ilyen ügynök klienseit kiírja a program. A következő módon megtarthatjuk az apa típusú rekordot a keresés során: GET LEFTMOST ÜGYNÖK WHERE NÉV = "Nehagyd Döme" while NOT FAIL do GET NEXT WITHIN PARENT ÜGYFÉL print ÜGYFÉL.ÜNÉV (* a rekordsablonra hivatkozunk ) end while A példában a fa preorder sorrendjének megfelelő legelső adott nevű ügynök klienseit listázzuk. 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 H OLD: 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 3 12. tétel Lekérdezés és adatkezelés hierarchikus adatbázisokban 2. Nehagyd Döme pályát változtat GET HOLD LEFTMOST ÜGYNÖK WHERE NÉV = "Nehagyd Döme" AND FCÍM = "Csorna" DELETE 4 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 rek ord. Az alapötlet az, hogy a DB rekordokat egységként kezeljük Ezáltal rekordszinten tükröződik a séma fa-szerkezete A gyökértípusra szervezünk elsődleges elérést (pl hash-elést, indexelést, stb.) Például az előbbi biztosítási sémánál a gyökér a FIÓK vödörkatalógus DB-rekord  f1 ügyn ügyn . . több lap láncolva A DB rekord több láncolt lapból áll. Fentről lefele a hash-szervezés gyors mozgást biztosít Egy DB rekord tárolása történhet: 1. Preorder fonal szerint: r,a1,a2,b1,b2,c1,c2 r a1 a2 b1 a3 b 2 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

a2 b 1 a3 • 2 mutató / rekord; • de gyorsabb a navigáció. 5 13. tétel Relációs algebra, relációs teljesség Relációs algebra, relációs teljesség 1. Bevezetés A praktikus alkalmazások szempontjából a relációs adatmodell a legfontosabb a modellek közül. Sikerének titka egyszerűsége, érthetősége, és a hozzá kapcsolódó számos művelet S bár kifejezőereje jó, hatékonysága hozzá képest alulmarad. Alapja a síkbeli, kétdimenziós táblázat, a reláció. A reláció a táblákkal analóg, mert a kapcsolatokat ezek segítségével lehet leírni. A reláció elemei a sorok, a táblázat fejlécében pedig az attribútumok szerepelnek. Példa: FILM CÍM Óz . ÉV . SZALAGFAJTA . = r rek. Def.: Reláció A reláció egy síkbeli tábla, ami pedig egy direkt szorzat egy részhalmaza, amelyben a sorok (rekordok) sorrendje lényegtelen. Felfogható úgy is, mint Attribútum -> É rték függvények halmaza, ahol az oszlopok (= attribútumok)

sorrendje irreleváns. A fenti példában: FILM ∈ CÍM × ÉV × SZALAGFAJTA × . r(CÍM)="Óz" Def.: Nézet 1. Szintén egy síkbeli táblázat: R A1 A2 . Ak R(A1,A2,.Ak) 2. ~R⊆D1×D2××Dk, ahol Di az Ai értékkészlete (A sorok sorrendje nem számít) 3. A sor egy f{A1,,Ak} ∪Di függvény (Az oszlopok sorrendje nem számít) 1 13. tétel Relációs algebra, relációs teljesség 2. A relációs adatmodell alapműveletei (EF Codd, 70) 1. halmazműveletek: • únió (Jele: ∪) Adott két reláció: R és S. R∪S az R és S sorait jelenti. A műveltnek nincs mindig értelme, ezért megfogalmazhatunk - nem kötelező érvényű követelményeket az únióval kapcsolatban: – legyen R és S oszlopszáma egyenlő! – esetleg oszlopaik típusa is feleljen meg egymásnak! Példa: R A a a b B a c c S A a a a b D a d c b R∪S A a a b a b ? a c c d b Ahogy a példában is látszik, előfordulhat, hogy az únióban hiányozni fog egy attribútumnév

(oszlopfejléc). Az ismétlődő sorok általában nem megengedettek (pl: (a,a) ) az únióban, mivel a relációs világ értékorientált, és a redundanciát igyekszik kiiktatni ott, ahol lehet. • különbség (Jele: ) Adott két reláció: R és S. RS elemei R azon sorai lesznek, amelyek nem szerepelnek S-ben. RS örökli az R oszlopszámát, attribútumait, típusait. Példa: az úniónál bemutatott R-re és S-re RS A b B c • direkt szorzat (Descartes-szorzat, jele: ×) Adott két reláció: R (k oszlopa és m sora van) és S (l oszlopa és n sora van). R×S-nek (k+l) számú oszlopa lesz, amikor a direkt szorzat-képzés során R sorait kiegészítjük az S soraival az összes lehetséges módon. Tehát R×S-nek mn számú sora lesz Formálisan: R(A1,.Ak) R×S(A1,.Ak,B1,,Bl) S(B1,.,Bl) 2 13. tétel Relációs algebra, relációs teljesség Példa: az úniónál bemutatott R-re és S-re k=l=2 k+l=4 R×S A a B a a c A a . b a . D a . b a . Az

alapműveletek közül ez a legnehezebb és leglassabb. Bár polinom időben elvégezhető, mégis ez aleginkább időigényes művelet. 2. relációs műveletek : • szelekció (Jele: σF(R) 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; 2. hagyjuk el R többi oszlopát; 3. hagyjuk el az esetleges ismétlődéseket is 1 σ, azaz szigma 3 13. tétel Relációs algebra, relációs teljesség Példa: ΠA(R) A a b A relációs alapműveletek relációkat adnak eredményül, ezért ezen relációs műveletek egymással k ombinálhatók. Pl: σA<D(R×S), ez először egy Descartes-szorzást, majd egy szelekciót jelöl. 3. A relációs adatmodell további fontos műveletei • metszet (Jele: ∩) Adott két reláció: R és S. R∩S sorai azok a sorok lesznek, melyek R-nek és S-nek is sorai. Formálisan: R∩S=R(RS)=S(SR) Példa: az úniónál megismert R-re és S-re R∩S A a a B a c Az attribútumok öröklődése itt kétféle lehet. • természetes

illesztés (összekapcsolás, join) (Jele: ) Adott két reláció, R és S. Az természetes illesztés művelete bármely két halmazra értelmes operáció. R S kiszámítása attól függ, hogy melyek a közös attribútumnevek a relációkban: R(A1,.Ak,B1,,Bs) S(A1,.Ak,C1,,Cd) vagyis az Ai-k a közös attribútumnevek. – Az R×S-ből indulva vesszük azokat a sorokat, amelyekre igaz, hogy R.Ai=SAi – Az eredményt vetítjük rá R.A1,,RAk,C1,,Cd,B1,,Bs-re Tulajdonságai: – Az így kiadódó R S -nek (k+s+d) számú oszlopa lesz. – Örököl attribútumokat és típusokat is. – k=0 esetén egyszerű szorzatműveletet jelent. – Kifejezhető alapműveletekkel (a gyakorlatban igyekszünk másként megkapni az egyesítés eredményét): R S = ΠA1,.Ak,B1,,Bs,C1,,Cd(σAi=Ai(R×S)) A vetítésnél nem kell az azonos sorokat törölni. Példa: k=1, s=2,d=1, (k+s+d)=4 R A B C a a b c 4 2 3 b S c 4 R S 13. tétel Relációs algebra, relációs teljesség D a b C 2

3 x A 2 B C D a a a b b c 2 2 3 a x b • félillesztés (Jele: ) Technikai szerepe van a lekérdezési optimalizátorokban (elosztott rendszerekben). R S = ΠR(R S). • Általános (Θ) illesztés Adott két reláció: R és S. A az R, B az S reláció attribútuma. R S jelentése: σAΘ B(R×S) AΘB Ebben az esetben tehát nem egyenlőségre, hanem általános műveletre végezzük el az illesztést. Példa: R S R.C<SC A a B b R.C 2 D b S.C 3 Def.: Relációs teljesség Egy relációs lekérdező nyelvet relációsan teljesenek nevezünk, ha benne az öt alapművelet (únió, különbség, direkt szorzat, szelekció, vetítés) megvalósítható. Az SQL relációsan teljes. Egyes komoly lekérdező nyelvek ezen minimális követelményeket túl is teljesítik, azaz nem csak relációs, hanem aggregációs műveletekre is képesek. Def.: Aggregáció Az összesítő műveleteket, melyek egy relációból elemi értéket állítanak elő, aggregációknak

nevezzük. Például: AVG (átlag), MIN (minimum), MAX (maximum), CNT (számlálás), SUM (összegzés). Példa: DOLGOZÓ(SzemélyiSzám, Fizetés,.) FCNT Szemszám, AVG Fizetés(DOLGOZÓ) eredménye egy számpár lesz. Megkapjuk a dolgozók számát és az átlagos fizetést. 4. NULL értékek problematikája A NULL értékek kitöltetlen attribútum-értékeket jelentenek. Például: TERMELŐ(Név,Cím,Termék,Ár) (Rezeda Kázmér,NULL,Zab,300) σCím="Budapest"(TERMELŐ) A NULL érték jelentése azonban nem homogén. Jelentheti azt, hogy 5 13. tétel Relációs algebra, relációs teljesség – 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. Példa: R A a a S B b c B b e C d e R S

A a a B b c C d NULL Ennek a műveletnek az univerzális relációs megközelítésnél van szerepe, ahol az univerzális relációban minden attribútum szerepel. • Jobboldali külső illesztés (Jele: ) Benne fordított a szereposztás R-re és S-re nézve. • Teljes külső illesztés (Jele: ) Benne a teljes R és S megjelenik. Példa: R S A a a NULL B b c e C d NULL e • Külső únió (Jele: ∪k) Részben ∪-kompatibilis relációk egyesítését jelenti. Példa: DIÁK(Név,Témavezető,Tanszék) TANÁR(Név,Tanszék,Beosztás) DIÁK ∪k TANÁR eredménye: diák tanár Név . . 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ó. 6 13. tétel Relációs algebra, relációs teljesség 5. E/K séma - relációs séma átalakítás Az átalakításra van egy teljesen gépies út, ami azonban nem adja mindig a legjobb

megoldást. Egyed: E(A1,.,Ak) R(A1,,Ak) Reláció Az egyed egy az egyben átalakítható relációvá (k-oszlopos táblává). E A1 . R(A1,.,Ak) Ak Bonyolultabb átalakítás: E1 Em R(A1,.,As, B1,,Bl,, S1,,St) E2 R . E1 kulcsa kulcsa E2 kulcsa Em . . . . Hogyan kaphatunk jó átalakított relációs sémát? • ábrázoljunk minden információ-elemet! • a fontos igényeket kifejező műveletek legyenek hatékonyak! Például: ne kelljen túl sok helyről összeszedni egy fontos lekérdezés adatait. 7 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. . t=t(2)=(Rezeda K.,Fő u) t[1]=Rezeda K. t[2]=Fő u. Cím Fő u. . Def.: Megengedett formulák I. Alap- vagy prímformulák • R(t): igaz értéket vesz fel, ha t értéke egy R-beli sor. Itt R egy alapreláció, t pedig egy sorváltozó. • t[i]Θs[j]: igaz értéket vesz fel, ha t,s értékeinél a t[i] és s[j] értékek Θ viszonyban vannak. Itt t és s sorváltozók, és Θ ∈ {=,≠, <, >,≤,≥} • t[i]Θc, illetve • cΘ t[i], ahol c egy érték. Értékük akkor igaz, ha a t sorváltozó értéke Θ kapcsolatban van c-vel. Pl.: t[1]=Rezeda K II. Összetettebb formulák Ha ϕ, és ψ megengedett formulák, akkor ϕ∨ψ ϕ∧ψ ϕ¬ is megengedett formulák. Igazság-értékük a szokásos módon döntendő el Ha a t sorváltozó is adott, akkor a ∃tϕ is megengedett formula. III. További megengedett formula: ∀tϕ = ¬∃t(¬ϕ) Def.: Kötött és szabad változók Egy sorváltozó kötött, ha kvantor (∃ vagy ∀)

vonatkozik rá; és szabad, ha nem kötött. Pl.: i kötött: iΣf(i) x kötött: ∫f(t) 1 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. 2 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.) 2. Oszlopkalkulus Az oszlopkalkulusban az ún. oszlopváltozók egy mező értékét vehetik fel Ábrázolva: reláció A B . D sorváltozó oszlopváltozó Alapformulák • R(u1u2.uk) egy k-oszlopos alapreláció, amelyben az ui oszlopváltozók szerepelnek • uΘv,uΘc,cΘu, ahol u és v oszlopváltozók, c egy érték, és Θ elemi összehasonlító operátor. Az építkezés ezekkel az alapformulákkal és a ¬∧∨∀∃ jelekkel történik, ugyanúgy, ahogy a sorkalkulusnál. Def.: Megengedett (kifejezett) reláció az {u1,u2,.,uk; ϕ( u1,u2,,uk)}reláció, ahol a ϕ formulának csak az u1,u2,,uk lehet a szabad változója. 3 14. tétel Sor- és oszlopkalkulus Def.: Biztonságos formula Nem más, mint egy biztonságosan kifejezett r eláció. Ahogy a

sorkalkulusnál is láttuk, úgy itt is megfogalmazható a DOM(ϕ)-vel egy kvantorfeltétel. Tétel: A sorkalkulus ekvivalens 1 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. 1 az ekvivalencia jele: ↔ 4 14. tétel Sor- és oszlopkalkulus 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 s orkalkulus is kifejezhető a relációs al gebra 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. 5 Relációs lekérdező nyelvek (QBE) 15. tétel Relációs lekérdező nyelvek (QBE) 1. A relációs lekérdező nyelvekről általában Két fő csoportjuk van: a.) Algebra típusú nyelvek • A relációs algebrát valósítják meg egy az egyben. • ΠA1.Ak (R) ↔ R % A1,,Ak • Felhasználói felületként nem használatosak. • Valódi felhasználási területük: lekérdezés-feldolgozó rendszerekben történő (algebrai) optimalizálás. 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. 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: Πcím(σMunkakör=kazánkovács(Alkalmazott Személy)) Ez valójában egy "recept": – képezzük az Alkalmazott és Személy

természetes, név szerinti illesztését (Név, Cím, Munkakör az eredmény); – ebből szűrjük ki azokat a sorokat, ahol a foglalkozás éppen kazánkovács; – majd vetítünk a címre, hiszen csak erre vagyunk kíváncsiak. 1 Relációs lekérdező nyelvek (QBE) 15. tétel Gyorsítási lehetőség: a szűrést előbb is elvégezhetjük. Πcím(σMunkakör=kazánkovács(Alkalmazott) Személy) [További gyorsítás: vetítés a névre] 2. Amit a QBE-ről tudni kell A QBE (Query By Example) egy önálló IBM-fejlesztés eredményeként létrejött nyelv. Jellemzője, hogy képernyő-orientált és direkt manipulációs eszközként funkcionál. Azaz a felhasználó a saját maga által kidolgozott módszereket alkalmazhat általános esetekre. Ehhez a rendszer alapeszköze a reláció-váz (skeleton). A QBE a felszínen oszlopkalkulus-jellegű nyelv, de implicit módon sorvátozókat használ. 2.1 A QBE szintaktikus elemei • A parancsok felépítése: string . –

kiíró utasítás: P. – beszúró utasítás: I. – törlő utasítás: D. • A változók felépítése: string Példa: Adott a Személy(Név, Cím, Szsz, .) alapreláció Személy Név P. Kiss P. P.Kiss Cím Szsz . megjeleníti az összes Személyt kiírja az összes Kiss nevűt 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 2 Relációs lekérdező nyelvek (QBE) 15. tétel 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. Oszlopkalkulussal megfogalmazva az alábbi kérdések adhatók ki QBE-ben: {a1,.,ak ∃ b1,,bn: R1(c11,,c1i1)∧ ∧ Rm(cm1,,cmin)} Az Ri relációban vagy oszlopváltozó vagy konstans szerepel. A QBE további eszköze a feltétel-doboz (cond. box), amibe olyan feltételek kerülnek, amelyek a táblázatba nem írhatók be. Nincs fix szabály az ismétlődő sorokra. (Ahogy pl a vetítésnél volt) • ALL.: multihalmaz, az ismétlődés megmarad; • UN.: ismétlődés nincs Pl.: Rendelés Szám Név P.UN Termék brokkoli . P.ALL Mennyiség . P.ALL Azok nevét kapjuk meg - egyszeresen -, akik brokkolit rendeltek. Minden (Termék, Mennyiség) párt megkapunk. A "szokásos" számlaegyenleget) Ügyfél aggregációk is használhatók, például: (megkapjuk Egyenleg P.AVGALL 2.3 A QBE DDL elemei • Tábladefiníció - példán keresztül mutatjuk be: I. TERMELŐ I KEY I. TYPE I.

DOMAIN I. INVERSION I. Tnév Y CHAR NEVEK N Cím N CHAR CÍMEK N Terméknév Y CHAR TERMÉKNÉV N 3 Ár N FLOAT MENNY N az összes Relációs lekérdező nyelvek (QBE) 15. tétel – 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. 4 Relációs lekérdező nyelvek (QBE) 15. tétel 2.4 A QBE néhány DML utasítása • Beszúrás: I. kerül a sorinformációs részbe Pl: TERMELŐ I. Tnév Sasad Sasad Cím Cím Cím

Terméknév kutyabenge Ár 50 A Címet előre nem tudjuk; a feltehetőleg már meglévő információt kikerestetjük az adatbázisból. • Módosítás: U. kerül a sorinformációs részbe Pl: SZEMÉLY U. Név Szsz xyz.u Cím Akácfa u. A keresés kulcs-attribútumok szerint történik (most: személyi szám), a módosítás pedig csak a nem kulcsmezőket érinti. • Törlés: D. kerül a sorinformációs részbe Pl: SZEMÉLY D. Név Szsz xyz.u Cím Kulcs alapján azonosítja a törlendő sort. A fentiek alapján kimondhatjuk, hogy a QBE relációsan teljes nyelv. (Azaz megvalósítható benne az únió, direkt szozás, vetítés, szelekció (F-et cond. box-ban kell felírni) és különbség (törléssel kell megoldani).) 5 A QUEL lekérdező nyelv 16. tétel 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. 1 A QUEL lekérdező nyelv 16. tétel 2.1 A QUEL DDL-je: adatleíró utasítások (DDS) • Új reláció (tábla) létrehozása: CREATE <relációnév> (<mezőnév> : <típus> <hossz>);* A * mutatja azt, hogy többoszlopos relációk a szokásos módon létrehozhatók. Típusok: – I1, I4, I8: egészek 1,4,8 byte-on ábrázolva

– F4, F8: lebegőpontos számok 4 ill. 8 byte-on – Cn: n (fix) hosszúságú karaktersorozat – Varchar(n) és Text(n): legfeljebb n-hosszú string – Date: dátum típus – Money: 16 jegyű szám, az utolsó 2 jegy tizedesjegy (pénzösszegek tárolására). Tárolási szerkezetek: – ISAM, CISAM: index-szekvenciális (ritka index) [C: compact, azaz kompaktabb, tömörebb, és ezért lassabb változat] – HASH, CHASH – BTREE, CBTREE – HEAP: ez az alapértelmezett szerkezet. • Új indexehozása: INDEX ON <relációnév> IS <indexnév> (<mezőnév>); Példa: Adott az ALKALMAZOTT (NÉV, SZSZ, RÉSZLEGNÉV, FIZETÉS) reláció MODIFY ALKALMAZOTT TO BTREE UNIQUE ON SZSZ; [elsődleges elérés] INDEX ON ALKALMAZOTT IS NÉV IND (NÉV); MODIFY NÉV IND TO CBTREE ON NÉV; [másodlagos elérés] Az első MODIFY parancs az ALKALMAZOTT állományt B-fa szervezésűvé alakítja. A keresési kulcs az SZSZ személyi szám lesz (ami ráadásul egyedi is). A második

MODIFY az állomány másodlagos elérését definiálja (CBTREE szerint). • Reláció ill. index törlése: DROP <tábla- ill. indexnév>; 2.2 A QUEL kereső-kérdések rendszere (Queries) A kereső-kérdések tipikusan három részből tevődnek össze: a.) (biztonságos) sorváltozó-specifikáció (ez felel meg az SQL-ben a FROM-nak) RANGE OF <sorváltozónév> IS <alaprelációnév>; . RANGE OF. [Ilyen sorból több is van b.) előtt] Pl.: RANGE OF E IS ALKALMAZOTT; [az előző példából] E az alkalmazottakon fut végig. Hivatkozások: ENÉV, ESZSZ, E:RÉSZLEGNÉV 2 A QUEL lekérdező nyelv 16. tétel b.) kérdés-test (ez felel meg az SQL-ben a SELECT-nek) Meg kell adni RETRIEVE-vel, hogy mi jelenjen meg az eredményben. Pl.: RETRIEVE (EALL); [E összes komponense megjelenik] RETRIEVE (E.NÉV, ERÉSZLEGNÉV); [csak a név és a részleg neve] RETRIEVE UNIQUE (E.FIZETÉS); [kiszűrjük a többször előforduló adatokat] Időleges relációk is

kialakíthatók a RETRIEVE INTO kulcsszóval. Pl.: RANGE OF E IS SZEMÉLY; RETRIEVE INTO PASAS (PNÉV=E.NÉV, ) WHERE ENEM=hím; Itt az E.NÉV kifejezés ad értéket a PNÉV attribútumnak Aggregációk Ezek már a korábban megismert AVG, CNT, SUM, MIN, MAX. A különbség csak annyi, hogy a feltételvizsgálat aggregáción belülre tehető, sőt: csoportosításra is alkalmas. Pl.: RETRIEVE MAX(EFIZETÉS); RETRIEVE MAX(E.FIZETÉS WHERE ECÍM=Fő u); RETRIEVE MAX(E.FIZETÉS BY NEM); [GROUP BY] RETRIEVE MAX(E.FIZETÉS BY NEM WHERE ECÍM=Fő u); Az aggregációk egymásba ágyazhatók és szerepelhetnek a ϕ formulában is. Az eredményt maga a RETRIEVE formázza azáltal, hogy attribútumait milyen sorrendben adjuk meg. A rendezés a SORT BY <mezők> -kel lehetséges; a rendezést a kérdés-test végére kell tenni. Pl: PASAS SORT BY PNÉV A; [A: ascending, növekvő] c.) feltétel(ek) (ez felel meg az SQL-ben a WHERE-nek - itt is így használják) WHERE után a ϕ

formulában fogalmazzuk meg a feltételt. ϕ tartalmazhatja az AND (∧), OR (∨), NOT (¬) kulcsszavakat. Továbbá a ϕ-be tehető explicit kvantor is - ilyen például az ANY. Ennek szintaktikája: ANY (<kérdés-test a WHERE nélkül> <feltétel>) Eredménye: • 0, ha nincs ilyen, és • 1, ha van. 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 . 3 A QUEL lekérdező nyelv 16. tétel . DELETE E; WHERE ϕ [kiválasztjuk, hogy mit akarunk törölni] • Beillesztés: APPEND TO Szerkezete: APPEND TO SZEMÉLY(Kif1, .); – 4 Az SQL adatbáziskezelő nyelvi felület 17. tétel 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, SQLCODE 1) 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 1 2 Lásd: Adatbázisok Laboratórium jegyzet, 1998. 33 oldal: a Pro*C előfordító Forrás: Adatbázisok Laboratórium jegyzet, 1998. (19oldaltól) 1 Az SQL adatbáziskezelő

nyelvi felület 17. tétel A nyelv utasításait az alábbi csoportokba oszthatjuk: 1. adatleíró (DDS, Data Definition Statement); 2. lekérdező (Queries) 3. adatmódosító (DMS, Data Manipulation Statement); 4. adatelérést vezérlő (DCS, Data Control Statement) utasítások 2.1 Az SQL DDL-je: adatleíró utasítások (DDS) • Új reláció (tábla) létrehozása: CREATE TABLE <táblanév> (<oszlopnév> <típus> [NOT NULL] [,<oszlopnév> <típus> [NOT NULL], . ]); Ha valamely oszlop definíciója tartalmazza a NOT NULL módosítót, akkor a megfelelő mezőben mindig valamilyen legális értéknek kell szerepelnie. • Új nézetek létrehozása: CREATE VIEW <nézetnév> [(<oszlopnév> [,<oszlopnév> , . ])] AS <lekérdezés 3>; 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. 3 Lásd később (Queries) 2 Az SQL adatbáziskezelő nyelvi felület 17. tétel – 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.2 Az SQL lekérdezései A lekérdezések általános szintaxiasa a következő: SELECT <jellemzők> ezek definiálják az eredménytábla oszlopait FROM <táblák> ezek adják meg a lekérdezésben résztvevő táblák nevét [WHERE <logikai kifejezés>] ezzel válogathatunk az eredmény sorai között [GROUP BY <attribútumok>] ez rendezi egymás mellé az eredménytábla sorait [HAVING <attribútumok>] ezzel a csoportosítás révén keletkező eredménysorokra kiválasztási feltételt írunk elő [ORDER BY <attribútumok>] ez határozza meg a megjelenő sorok sorrendjét Tulajdonságok: • A lekérdezésekben felhasznált Θ operátor többféle lehet; például különböző halmazoperátorok is alkalmazhatók (EXISTS, IN, NOT IN, CONTAINS [ez utóbbi másodrendű operátor,

nagyon erős!]). • A lekérdezésekben használhatók aggregációk is, más néven oszlopfüggvények és eredményeik. Ilyenek: AVG, COUNT, SUM, MIN, MAX A "szokásos" programozási nyelveken ezen oszlopfüggvények eredményét ciklussal kaphatjuk meg. • A lekérdezésekben NULL értékek is felhasználhatók. Pl: WHERE Cim IS NULL • A SELECT-ek egymásba ágyazhatók. A beágyazott lekérdezés vagy egyetlen, vagy több értéket állít elő. Több érték egy halmazt jelent, tehát a halmazműveleteket használhatjuk • Algebra-műveletek: UNION(∪), INTERSECT(∩), MINUS (/). 2.3 Az SQL DML-je: adatmódosító utasítások (DMS) • Adatok bevitele INSERT INTO <táblanév> [(<oszlopnév> [,<oszlopnév>, . ])] VALUES (<kif1>[, <kif2>, .]); Tulajdonságok: – Ha nem adjuk meg az oszlopok nevét, akkor a tábla deklarálásánál megadott sorrendben minden mezőnek értéket kell adni. – Ha viszont megadtuk az egyes oszlopok

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

módosít, egyébként csak a logikai kifejezés által kiválasztott sorokat töröljük. 2.4 Az SQL adatelérést vezérlő utasításai (DCS) • Jogosultságok definiálása GRANT [DBA | CONNECT | RESOURCES] TO <felhasználó> [, <felhasználó>, .] IDENTIFIED BY <jelszó> [, <jelszó>, .]; Ezzel a paranccsal az egyes felhasználóknak az adatbázishozvaló hozzáférési jogát szabályozzuk. A DBA jogosultság az adatbázis adminisztrátorokat definiálja, akiknek korlátlan joguk van az összes adatbázis objektum felett, nem csak létrehozhatják, módosíthatják, illetve törölhetik őket, de befolyásolhatják az objektumok tárolásával, hozzáférésével kapcsolatos paramétereket is. A RESOURCES jogosultsággal rendelkező felhasználók létrehozhatnak, módosíthatnak, illetve törölhetnek új objektumokat. A CONNECT jogosultság csak az adatbáziskezelőbe való belépésre jogosít. GRANT <jogosultság> [,<jogosultság>, .] ON

<tábla- vagy nézetnév> TO <felhasználó> [WITH GRANT OPTION]; a megkapott jogosultság tobábbadható Ezzel a paranccsal az egyes objektumokhoz (táblákhoz, nézetekhez) való hozzáférést szabályozzuk. A <jogosultság> az objektumon végezhető műveleteket adja meg • Tranzakciókezelés A tranzakció az adatbázis módosításának olyan sorozata, amelyet vagy teljes egészében kell végrehajtani, vagy egyáltalán nem. Az adatbáziskezelők biztosítják, hogy mindig vissza lehessen térni az utolsó teljes egészében végrehajtott tranzakció utáni állapothoz. Egy folyamatban lévő tranzakciót vagy a COMMIT utasítással zárhatunk le, amely a korábbi COMMIT óta végrehajtott összes módosítást véglegesíti, vagy a ROLLBACK utasítással törölhetjük hatásukat, visszatérve a megelőző COMMIT kiadásakor érvényes állapotba. 4 Az SQL adatbáziskezelő nyelvi felület 17. tétel • 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. 5 18. tétel Funkcionális függések 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 1 18. tétel Funkcionális függések b.) Név, TermékNév, Cím,Termék, Ár = R (azaz az egész rekordot meghatározza) 2

18. tétel Funkcionális függések 2. Adott az R(A,B,C) reláció táblája A a a B b c C c c = r rek. r-ben az • ABC függés "üresen" teljesül, az • AC függés nem "üresen" igaz, és a • CB függés nem teljesül. Bennünket a lényegi f üggések érdekelnek, amelyek általános érvényűek és részei modellünknek. 3. Adott a SZEMÉLY reláció: . Szsz Nem 1. 1. ffi ffi Szemszí n kék kék NemSzemszín: ez nem igazi függés, ezzel szemben a SzszNem már igazi függést jelez. Ez már számunkra is fontos! Általánosan: adott az (R,F) pár, ahol R egy reláció és F függések egy halmaza. Csak olyan R-hez illeszkedő r relációkkal foglalkozunk, melyekben F függései teljesülnek. Ezek a függések azért ilyen kiemelten fontosak számunkra, mert anomáliákat okozhatnak. Pl.: a TERMELŐ relációban adott NévCím és Név, TermékR függések mellett előfordulhat, hogy ha valaki nem termel terméket, akkor nem lesz felvéve a

címe sem. Def.: Függőleges felbontás Az anomáliák elkerülése érdekében használható a függőleges felbontás technikája. Ekkor nem magát R-et, hanem függőleges vetületeit tároljuk. Előbbi példánkban: R1: ΠNév,Cím(R) R2: ΠNév,Termék,Ár(R) Ezzel a felbontással az anomáliák is eltünnek. Ennek az előnynek azonban az az ára, hogy R helyreállítása, az R=R1 R2 természetes illesztés költséges művelet. Felmerül a kérdés, hogy mért nem használható egy másik függőleges felbontás, például a következő: (Név,Cím,Ár) és (Név, Termék) Ez rossz, mert elvész a Termék és Ár közötti kapcsolat! A révén az összes ár szerepelni fog az összes termék mellett adott nevű termelő esetén. Azaz: RR R" 3 18. tétel Funkcionális függések Látható tehát, hogy miben áll a természetes illesztés "mágikus" szerepe: az eredeti reláció visszaállítása vagy vele történik, vagy sehogy. Az elkövetkezendőkben ezt

tételként is meg fogjuk fogalmazni. 3. A funkcionális függés elméleti háttere Def.: Logikai következmény Adott az (R,F) pár. Az XY függés logikai k övetkezménye F-nek, ha XY érvényes minden olyan Rsémájú r relációban, ahol az F is érvényes. Jele: F |= XY Ha a logikai következmény fogalma mellé megalkotjuk a levezethetőség fogalmát is (|), akkor kezünkben lesz az a "kalkulus", ami a normailizáláshoz kell. Ugyanis, ha tökéletesen formalizáljuk a levezetést, akkor elérjük a kitűzött |= ≈ | célt. • | ⇒ |= irány: az igazság-tétel mondja majd ki; • |= ⇒| irány: a (Gödel-féle) teljességi tétel mondja ki. Def.: Armstrong-axiómák (R,F)-re A1. Reflexív szabály Y⊆X⊆R ⇒ XY A2. Kiegészítési szabály Ha XY és Z⊆R ⇒ XZ YZ A3. Tranzitivitási szabály Ha XY és YZ ⇒ XZ Def.: Levezethetőség F-ből az UV levezethető, ha az UV függés megkapható F-ből az A1-A3 alkalmazásával. Jele: F | UV

Tétel: Igazság-tétel F | XY esetén F |= XY is teljesül. Biz.: ha r-ben igaz A1-A3 "baloldala", akkor a "jobboldala" is igaz lesz A1: X Y r: ( ( )) t1 sor ( ( )) t2 sor Nagy X halmazon megegyeznek ⇒ kis Y-on is! A2: X Z Y ( )( )( ) t1 sor ( )( )( ) t2 sor Ha az X és Z halmazai megegyeznek ⇒ az Y-ok is! r: A3: X Z Y ( )( )( ) t1 sor ( )( )( ) t2 sor Ha az X-ek megegyeznek ⇒ az Y-ok is ⇒ a Z-k is! r: 4 18. tétel Funkcionális függések Ezzel állításunkat igazoltuk. 5 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, UtcaIrsz,

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:{XY, XZ}| XYZ. 2. Felbontási szabály Az előbbi szabály komplementere. Formálisan:{XY}| XZ, ahol Z⊆Y. 3. Áltranzitív szabály Formálisan:{XY, WYZ}| WXZ. Biz.: az Armstrong-axiómákkal történik 1. Únió-szabály Mi alapján? 1. XZ ∈F 2. YXYZ A2 (Y a kiegészítő halmaz) 3. XY ∈F 4. XYX A2 (X a kiegészítő halmaz) 5. XYZ A3 (4. és 2 tranzitivitása) 2. Felbontási szabály 1. XY 2. YZ 3. XZ Mi alapján? ∈F A1 A3 (1. és 2 tranzitivitása) 3. Áltranzitív szabály 1. WYZ 2. XY 3. XWYW Mi alapján? ∈F ∈F A2 (W a kiegészítő halmaz) 6 18. tétel Funkcionális függések 4. XWZ A3 (3. és 1

tranzitivitása) 7 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: F+:={XY; F | XY}, azaz F+ az F összes szintaktikus következménye. Ha modellünk része F, akkor F+ is az; ez utóbbi ad teljes képet a függések rendszeréről. Ugyanekkor F+ mérete túlságosan nagy, és ezért a gyakorlati alkalmazásokban nemigen alkalmazható. Példa: Adott az R(A1,.,An,B1,,Bn) reláció és az F={AiBj} függéshalmaz, ahol i,j=1,.,n 2 Azaz n db. függésünk van, és F+ kb 22n elemből áll, ami nagyon sok és nehezen számolható. F+ tartalmazza az összes olyan XY függést, ahol: • 0≠X⊆{A1,.,An} • 0≠Y⊆{B1,.,Bn} Szerencse, hogy van egy hatékonyan számítható függés-fogalom, ami képesség tekintetében nem marad el a függéshalmaz

lezárásától. Ez pedig az: Def.: Attribútumhalmaz lezárása Adott az X⊆R attribútumhalmaz. Ennek lezárása X+(F), amire igaz, hogy: X+(F):={A⊆R; F | XA}; ami szoros összefüggésben áll a levezethetőséggel. Fontos különbség az előző fogalomhoz (függéshalmaz lezárása) képest, hogy míg F+ függésekből, addig X+(F) attribútumokból áll. Állítás*: F | XY ⇔ Y⊆X+(F) Biz.: ⇒ irány Tfh. F | XY és A∈Y Be kell látni, hogy: F | XA. √ Ez viszont a felbontási szabály miatt mindig igaz. ⇐ irány Be kell látni, hogy ha Y⊆X+(F), akkor F | XY. Legyen Y=A1,.,Ak attribútumok együttese Felt.: F | XAi, ahol i=1,,k Alkalmazzuk többször az únió-szabályt! XA1 XA2 } XA1 A2 XA1 A2 A3 } 1 19. tétel Lezárások, fedések, vetített függések XA3 . Végül: XA1,A2,.,Ak √ Tétel: Teljességi tétel Adott az (R,F) pár, és fel szokás tételezni azt, hogy az attribútumok legalább kétértékűek. F |= XY esetén F | XY

is teljesül. (Azaz: a logikai következményről meg lehet győződni.) Biz.: legyenek az attribútumok a {0,1} elemei A bizonyítás alapötlete, hogy (R,F)-hez "modellt" készítünk. r egy kétsoros reláció: X+(F) X biztosan eleme X+(F)-nek (lehet, hogy nem valódi). X r első sora csupa 1-es 11 . 1 11 . 1 második sora csak X+(F)-ben 1-es, 11 . 1 00 . 0 másutt csupa 0. Nem lényeges az attribútumok alaphalmaza, csak az. hogy az oszlopokban azonos vagy különböző értékek szerepelnek-e. 1. állítás: r-ben teljesülnek F függései, azaz ha VW∈F, akkor VW teljesül F-en. (Ez jelenti azt, hogy modellt készítettünk (R,F)-hez.) Biz.: Legyen VW∈F Esetszétválasztás: • ha V¬⊆X+(F), akkor az állítás igaz, hiszen nincs r-nek két sora, ami V-n egyezne. √ • ha V⊆X+(F), akkor az Állítás* ⇒ iránya miatt: 1. F | XV 2. VW ∈F miatt 3. F | XW A3 miatt (1., 2 tranzitivitása) 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 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 2 19. tétel Lezárások, fedések, vetített függések X-en két sor egyenlő ⇒ a két sor Y-on is egyenlő, azaz Y⊆ X+(F), abból "nem lóghat ki". Az Állítás* ⇐ iránya szerint pedig F | XY, ezzel állításunkat igazoltuk. √ Következmény: |= és | egyenértékű. Ezért X+(F):={A⊆R; F | = X A} is írható, amit ki is használnak automatikus sémaelemzőkben. 3 19. tétel Lezárások, fedések, vetített függések Def.: Algoritmus X+(F) számítására Bemenete: az (R,F) ár és az X⊆R attribútumhalmaz. Kimenete: az X+(F) attribútumhalmaz. A módszer iteratív: X0:=X Xi+1:= Xi ∪ {azon A attribútumok, melyekhez van olyan UV∈F

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

akkor az állítás igaz. √ • ha U⊆Xutolsó, akkor V⊆Xutolsó, mert ellenkező esetben V elemeivel növelhető Xutolsó lenne. √ b.) legyen A∈X+(F) tetszőleges 4 19. tétel Lezárások, fedések, vetített függések Be kell látni, hogy A∈Xutolsó. A teljességet és X+(F) definícióját felhasználva: F|=XA. 5 19. tétel Lezárások, fedések, vetített függések Tehát • r-ben is igaz az XA függés • X-en két sor egyezik ⇒ A-n is egyezik ⇒ A∈Xutolsó. √ Megj.: a fent vázolt algoritmus implementálható a bemenet, azaz (R,F) hosszában lineáris lépésszámmal. Példa: adott az R(A,B,C,D,E) ötoszlopos reláció és az F={ABC, BD, CDE} függéshalmaz. Kérdés: AB+(F), azaz most X=AB. Megoldás: Xö=X=AB X1=AB∪CD=ABCD X2=ABCD∪E=ABCDE=R, azaz definíció szerint R szuperkulcsa és kulcs is (R,F). Ez utóbbi (kulcs) tulajdonsághoz meg kell mutatni: valódi része nem szuperkulcs. • Ki kell számolnunk A+(F)-et, ez: A+(F)=A≠R • és

B+(F)-et is, ez pedig: B+(F)=BD≠R. Tehát a minimalitási tulajdonság valóban teljesül. Példánk tapasztalatai általánosíthatók: Tétel: Szuperkulcsra és kulcsra • X szuperkulcs ⇔ X+(F)=R. • 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ás 2 k Adott az (R,F) séma. Ennek egy függőleges felbontása: ρ = (R1,.,Rk), ahol az Ri ∈ R vetületekre: ∪Ri = R i=1 Például: R = TERMEL(Név,Cím,Termék,Ár) R1= (Név,Cím) R2= (Név,Termék,Ár) ρ = (R1,R2) egy lehetséges függőleges felbontás, ahol k=2 1 2 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 6 19. tétel Lezárások, fedések, vetített függések A továbbiakban azt az ötletet fogjuk

alkalmazni az anomáliák e lkerülése érdekében, hogy egy, az (R,F) sémához illeszkedő r reláció esetében r h elyett az ri:=ΠRi(r) relációkat, azaz r függőleges darabjait, vetületeit fogjuk tárolni. Jelölés: ri:=ΠRi(r) az r reláció függőleges vetülete r mρ(r):= ri, ahol a sorrend közömbös, mert a természetes illesztés lényegében asszociatív művelet. ~ r2) r3 = r1 ( r2 r3 ) i=1 Pl.: (r1 Példa: (elrettentő, azaz rossz felbontást bemutató példa) Adott a következő háromoszlopos reláció: r: Név zöldmező zöldmező r1:=ΠR1(r) : Termék liszt cukor Ár 70 80 Név zöldmező zöldmező mρ(r):= r1 R=(Név,Termék,Ár) ρ=(R1,R2) R1=(Név,Termék) R2=(Név,Ár) Termék liszt cukor r2:=ΠR2(r) : Név zöldmező zöldmező Név zöldmező zöldmező zöldmező zöldmező r2 de mρ(r) ⊃≠ r Termék liszt liszt cukor cukor Ár 70 80 Ár 70 80 70 80 Def.: Hűséges (veszteségmentes) felbontás Az (R,F) séma egy ρ felbontása

hűséges (veszteségmentes), ha minden illeszkedő r relációra mρ(r) = r. Állítás: adott R,F,ρ,r az előbbiek szerint. 1. r ⊆ mρ(r) 2. ΠRi(mρ(r)) = ΠRi(r) = ri 3. mρ(mρ(r)) = mρ(r) 7 19. tétel Lezárások, fedések, vetített függések Az állítás fontos következménye, hogy ha mρ(r) ⊃≠ r, akkor katasztrofális helyzet áll elő, mivel nem állítható helyre az ri vetületekből az eredeti r reláció. 2 alapján nem tudjuk megmondani, hogy mi volt az eredeti reláció: r vagy mρ(r), mivel ezek vetületei azonosak. Tehát: az r visszanyerhető az ri darabokból ⇔ mρ(r) = r. (Ezt F-től remélhetjük) Az eredeti reláció visszaállítása vagy természetes illesztéssel történhet, vagy sehogy. Biz.: 1. Legyen t∈r, az r reláció egy sora Ekkor ti = t[Ri] ∈ ri, ahol t[Ri] t-nek az Ri oszlopok alá eső része. A ti sorok túlélik az illesztés szűréseit és eredményül t-t adják: t ∈ mρ(r). / 2. Az r ⊆ mρ(r) miatt a tartalmazás

igaz a vetületekre is: ri = ΠRi(r) ⊆ ΠRi(mρ) Be kell látni, hogy ti = t[Ri] ∈ ΠRi(mρ(r)). t ∈ mρ(r), ami mρ(r) definícióját használva azt jelenti, hogy: ∃ sj ∈ r sorok úgy, hogy sj[Rj] = t[Rj], ahol j = 1,. Speciálisan j = i, és ekkor si[Ri] = t[Ri] = ti, és mert si ∈ r, ezért ti ∈ ri. / 3. mρ(mρ(r)) = k ΠRi(mρ(r)) = i=1 k 2. ri = mρ(r). / 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. ρ pontosan akkor hűséges, ha • vagy F |= R1 ∩ R2 R1 R2 ∈ F+, • vagy F |= R1 ∩ R2 R2 R1 ∈ F+. Biz.: ⇐ Tfh. pl F |= R1 ∩ R2 R1 R2 igaz t ∈ r1 r2 ⇒ t ∈ r R1 R2 ^ ^ =r s1 s2 R1 R2 ezek az r-beli sorok összeilleszthetők (besatírozott részük azonos) 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 8 19. tétel Lezárások, fedések, vetített függések ⇒ (vázlat) H a két függés egyike sem áll fenn, akkor a felbontás nem mindig hűséges. R1 R2 ^ ^ 11.11 11 00.00 11 . . 11 11 =r 0 1 . 0 . 1 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) F = (NévCím, NévTermékÁr) 1. egy jó felbontás a következő: ρ = (R1=NévCím, R2=NévTermékÁr) Ekkor R1 ∩ R2 = Név és R1 R2 = Cím. Ebben az esetben F |= R1 ∩ R2 R1 R2, sőt a levezethetőségen felül az ∈ F is teljesül. És mivel a hűséges felbontás tételének feltétele teljesül, ezért ρ egy hűséges felbontása R-nek. 2. egy rossz felbontás a következő: ρ = (R1=NévTermék, R2=NévCímÁr) Ekkor R1 ∩ R2 = Név.

Automatikus tesztelés alá vetve: Név+(F) ⊇ R1 R2 vagy ? ? Név (F) ⊇ R2 R1 ? + Alkalmazzuk a lezárási algoritmust Név+(F)-re! 0. lépés: Név 1. lépés: NévCím ¬⊇ R1 R2 = Termék és NévCím ¬⊇ R2 R1 = CímÁr. Vagyis a felbontás nem hűséges Def.: Vetített függések Legyen ρ = (R1,.,Rk) az (R,F) séma egy függőleges felbontása Πρ(F) = {XY∈F+, ahol van olyan i, hogy XY ⊆ Ri} egy vetített függés. 9 19. tétel Lezárások, fedések, vetített függések 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 h agyható e l 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 Y Z X 10 19. tétel Lezárások, fedések, vetített függések Nézzük meg azon Y ⊆ X halmazokat, melyekre |XY|=1. Teszt: A ∈Y+(G) teljesül-e? • igen: ekkor XA helyett YA-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ű. 11 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 o ka az, hogy a t ermészetes i llesztés művelete a s orrendre 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 1 20. tétel Normálformák (3NF, BCNF), normalizálás • RA nem egyezik meg az R relációval, mert annál kisebb és • XA sem egyezik meg az R relációval, különben X szuperkulcs lenne. Tehát a reláció csökkenő ⇒ előbb-utóbb megállhatunk a kétoszlopos relációknál. b.) a felbontás hűséges A főtétel megjegyzése miatt elég azt belátni, hogy az (R1=XA, R2=RA) hűséges felbontása R-nek. A hűségesség tételének alkalmazásával: • R1 ∩ R2 = X és • R1 R2 = A. A nem triviális ("bajkeverő") XA 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évCí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 B CNF 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) 2 20. tétel Normálformák (3NF, BCNF), normalizálás ez nem BCNF, fel kell bontani! R TanárTárgyTeremDiákIdő TanárDiákJegy kulcs: TanárDiák ez nem

BCNF, fel kell bontani! a TárgyTanár rossz függés ez már BCNF, nem bomlik tovább TárgyTeremDiákIdő TanárTárgy kulcs: Tárgy ez már BCNF, nem bomlik tovább TárgyTeremIdő kulcs: TárgyIdő, TeremIdő TárgyIdőTerem nem eleme F-nek, de F+-nak igen; rossz! ez már BCNF, nem bomlik tovább TárgyDiákIdő kulcs: DiákIdő ez már BCNF, nem bomlik tovább Megjegyzések: • A felbontás eredményei a levelekben található komponensek. • A felbontás hűséges, mert mindvégig a két részre bontás technikáját alkalmaztuk. • A felbontásban segít, ha mindig a megfelelő rossz függéseket választjuk. Állítás: Nem BCNF formájú relációkra Tfh. adott egy (R,F) séma, ami nem BCNF Ekkor van olyan XY ∈ F függés és A∈Y attribútum, hogy az XA ∈ 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. ./ 3 20. tétel Normálformák (3NF, BCNF), normalizálás Következmény: Ha F-ben minden függés baloldala szuperkulcs, akkor (R,F) BCNF alakú. 2. Harmadik normálforma (3NF) Példa: Bevezetés a 3NF-hez Az amerikai irányítószámok az F függés-halmaznak megfelelően épülnek fel: R(Város,Utca,Irányítószám) F ={VárosUtcaIrányítószám, IrányítószámVáros} Ez az (R,F) séma nem BCNF, pl. az IrányítószámVáros függés sérti a BCNF-et Egy BCNF felbontás lehet a következő: ρ =

(IrányítószámVáros, IrányítószámUtca). Gond: hogyan ellenőrizzük a VárosUtcaIrányítószám függést új sor beszúrásakor? Ez a függés "elvész" a daraboláskor, így azt csak a természetes illesztéssel való helyreállítás után ellenőrizhetjük. A természetes illesztés viszont egy roppant költséges művelet. Def.: Vetített függések Legyen ρ = (R1,.,Rk) az (R,F) séma egy függőleges felbontása Πρ(F) = {XY∈F+, ahol van olyan i, hogy XY ⊆ Ri} egy vetített függés. Def.: Az (R,F) séma ρ felbontása megőrzi F-et, ha Πρ(F)+ ⊆ (F)+ Megj.: Mivel Πρ(F) ⊆ F+, ezért Πρ(F)+ ⊆ F+ mindig igaz Megjegyzés: az bevezető példához Az R(Város,Utca,Irányítószám) relációnak F-et megőrző módón nincs valódi felbontása. (A vetítés halmaza csak az IrányítószámVáros függés következményeiből áll) Ez arra példa, hogy egy (R,F)-et mikor nem lehet hűségesen, az F-et megőrző módon BCNF-ekre bontani. És ha már

ez nem lehetséges, akkor szükség lenne egy BCNF-nél valamivel gyengébb tulajdonságokkal rendelkező normálformára, ami F-et megőrizné. Ezért találták ki a 3NF-et. 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. 4 20. tétel Normálformák (3NF, BCNF), normalizálás É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.) 5 20. tétel Normálformák (3NF, BCNF), normalizálás Tehát a két NF viszonya: BCNF A 3NF a tágabb, engedékenyebb NF. 3NF Def.: X+(Πρ(F)) számításának algoritmusa • Z:=X • amíg Z változik, DO FOR i=1 TO k DO k: a felbontás elemeinek száma, ρ

= (R1,.,Rk) Z:=Z∪((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? 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 6 20. tétel Normálformák (3NF, BCNF), normalizálás 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 h agyható e l 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 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 YA-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 7 20. tétel Normálformák (3NF, BCNF), normalizálás F = {ABC, AB, BA} függéshalmaz. Keressük F minimális fedését, G-t. Az

algoritmus lépései: 2. rendben van 3. szintén rendben van: nincs elhagyható függés Pl. ABC nem elhagyható, mert AB+({AB,BA}) = AB és C∉AB 4. AB, BA ./ ABC nem minimális baloldalú A+(F) = ABC, és C ∈ ABC, ezért ABC helyett vehetjük az AC-t. Tehát G={AB, BA, AC} Megj.: mivel A és B szerepe szimmetrikus, ezért G = {AB, BA, BC}is minimális fedés. Ennek következménye az, hogy a minimális fedés nem egyértelmű. Főtétel: A 3NF és a hűséges felbontás kapcsolatáról Egy tetszőleges (R,F) sémának van hűséges, F-et megőrző felbontása 3NF relációkra. Biz.: konstruktív Legyen G az F minimális fedése. Tfh. G = {X1A1,,XkAk}alakú Ekkor legyen ρ = (X1A1,.,XkAk,X) egy k+1 komponensű felbontás, ahol X az (R,F) séma egy kulcsa. 1. ρ megőrzi G-t (és így F-et is) Be kell látni, hogy a vetület-függések összessége kiadja az egészet: Πρ(G)+=G+. Πρ(G)⊇G, pl. XiAi ∈G látható az Ri = XiAi darabban 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 8 20. tétel Normálformák (3NF, BCNF), normalizálás 3. ρ hűséges felbontás Be kell látni, hogy s = mρ(r) = r minden r-re. Ha ez nem igaz, akkor van olyan r, hogy s = mρ(r) ⊃≠ r. Πx(s) = Πx(r) s ⊃ r csak úgy lehet, ha van s-nek egy t1 és t2 sora úgy, hogy t1[X] = t2[X] és t1≠ t2. Legyen H = {A∈R; t1[X] =

t2[X]}attribútumhalmaz. H ⊇ X, de H≠R, mert t1≠ t2. A H ⊇ X tulajdonságból eredően H szuperkulcsa (R,F)-nek és (R,G)-nek. HR∈G+ (és H+(G) = R). Ezért van olyan UB ∈G függés, amire U ⊆ H, B ∉H. UB = XiAi alkalmas i-re. t1, t2 ∈ mρ(r), és ezért van olyan t1, t2 ∈ r, hogy: t1[UB] = t1[UB] és t2[UB] = t2[UB]. Először: t1[U] = t2[U] t1[U] = t1[U] = t2[U] = t2[U]. def. U⊆H t1, t2 ∈ r és egyeznek U-n, s ekkor UB∈G miatt B-n is egyeznek. Ez azonban lehetetlen, mert: t2[B] = t2[B] = t1[B] = t1[B]. És ez ellentmond B ∉ H-nak def. előző def. √ Ezzel állításunkat igazoltuk. 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 . Új típusú műveletek: • ZOOM, UNNEST: P1 "kibontása" 9 Forma Dór . 20. tétel Normálformák (3NF, BCNF), normalizálás • NEST: az előbbiek fordítottja Megjegyzés: a (-z eddig tárgyalt) normálformák egymásba ágyazódása így fest: BCNF 10 3NF 1NF Többértékű függések, 4NF 21. tétel 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 . 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! (BJ) 1 Munkatárs Aniela Lalagé Aniela Többértékű függések, 4NF 21. tétel A bevezető példában ilyen többértékű függés: • Név > Projekt • Név > Munkatárs • Név > Projekt,Munkatárs Vagy egy korábbi példából: Tárgy > TeremIdő. Def.: Triviális függések • Ha Y⊆X, akkor X > Y. t1, t2-höz t3 = t1 és t4= t2 jó. • Ha X∪Y=R, akkor X > Y. t1, t2-höz t3 = t1 és t4= t2 szintén jó. (RXY = 0) • Ha XY=R, akkor X > Y. Ez egy fontos speciális eset, ami azt mutatja meg, hogy ez a többértékű függés - amit sorgenerálónak is nevezhetünk - tágabb,

mint az egyenlőség-generálónak is mondható funkcionális függés. Megállapítások a többértékű függésekkel kapcsolatban • Az (R,F) sémában F hagyományos és többértékű függések halmaza. • Definiálható a |= (logikai következmény) és a | (szintaktikai következmény) fogalma. Ezekre a már megismert 8 alapszabály - A1, A2, A3 és 5 másik - vonatkozik Pl.: {XY}|= X > Y vagy {XY}| X > Y {X > Y}| X > (RXY) t1, t2-höz t4t3 lesz jó: X Y RXY t1 t2 t3 t4 • Igaz a teljességi tétel (belátni kicsit körülményes, de nem nehéz): |= ~ |. • Itt is értelmezhető F+, de sajnos X+(F) nem. • Itt is lehet beszélni felbontásról, hűségességről általános (R,F)-re. • Nehezebben algoritmizálható, mint a BCNF. (Kérdés, hogy megéri-e a fáradtságot?) Def.: Negyedik normálforma, 4NF Az (R,F) séma 4NF, ha tetszőleges nem triviális X > Y ∈ F+ esetén X szuperkulcs (a régi értelemben). Következmények: 1. Ha (R,F)

4NF, akkor BCNF is 2. Kétoszlopos reláció biztosan 4NF (azaz nincs benne nem triviális > 2 ). Többértékű függések, 4NF 21. tétel 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 R2 = R(XY). (Megjegyzés: > -ra nincs únió és felbontási szabály! Valamint ha Y=A∈X, akkor R2=XA.) R1 valódi, mert

XY≠R. R2 is valódi, mert Y≠⊂X. R1∩R2 = XY∩(R(XY)) R1R2 = RXY X Y R X > RXY -ből a komplementálás miatt következik, hogy X > R1∩R2 > R2 R1. Ezzel állításunkat igazoltuk √ Y esetén: Példa: 4NF-re és hűséges felbontásra R(Név,Projekt,Munkatárs) F = {Név > Projekt, Név > Munkatárs}. Ez (még) nem 4 NF séma; a Név nem szuperkulcs. A felbontás a Név > Projekt rossz függés alapján lehetséges: ρ = (R1=NévProjekt, R2=NévMunkatárs), ami már 4NF-eket tartalmaz. 3 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 A többfelhasználós működés során több felhasználó egyidőben használja az adatbázist. Pl: banki tranzakciók, repülőgépes helyfoglalás, on-line katalógusok, stb. Def.: Tranzakció Ebben a környezetben alapfogalom a tranzakció (processz, folyamat), ami egy program futását jelenti. A

tranzakció atomi, azaz oszthatatlan tevékenységet jelöl Atomi, mert a tranzakciónak: • vagy teljes a hatása az adatokon, • vagy semmilyen hatással nincs rájuk. 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 k ell á 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++ Baj: A értéke csak 1-el nő! 1 WRITE A WRITE A 22. tétel A tranzakciókezelés alapfogalmai Def.: Zárak (lock) Az előbbi probléma egy megoldási lehetősége a zárak alkalmazása. • A zár adategységhez kötődő fogalom; az adategységen a zárat "valakinek" el kell helyezni. (Adategység lehet a DB egy sora, egy egész tábla vagy csupán egy mező is Méretének megválasztása érinti a tranzakciós teljesítményt és az abort-ok számát is.) • A tranzakció lépései között: – a zár képzése a LOCK A, – a zár elengedése, feloldása az UNLOCK A utasítással történik. Pl.: T1: LOCK A --- .dolgozik A-val itt tart zárat A-n UNLOCK A --- Amíg T1 zárat tart A-n, addig más T-k csak korlátozottan (esetleg egyáltalán nem) férhetnek A-hoz, várakozniuk kell a zár felszabadulásáig. Def.: Ütemező (scheduler) A DBMS-ben a

tranzakciókezelés problémáival az ütemező foglalkozik. Ez a DBMS azon része, amely az adatelérési igényeket kezeli adott jogosultságok szerint. Fő tevékenységei: • váratja / továbbengedi T-t; • zárakat ad ki / old fel; • abortálja T-t. Def.: Protokoll Szabályrendszer, melyet ha a résztvevő T-k betartanak, akkor bizonyos kedvező jelenségek érhetők, illetve bajok kerülhetők el. Def.: Patt (patthelyzet, holtpont, deadlock) T-k egy csoportjából senki sem tud továbblépni, mert mindegyik egy olyan zárra vár, amit egy másik T tart. A patt tehát a zárak tartásának egy lényeges problémája Pl.: legegyszerűbb formájában: idő T1: LOCK A 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). 2 22. tétel A tranzakciókezelés alapfogalmai Tétel: Pattok kialakulásának szükséges és elégséges feltétele Pontosan akkor nincs patt egy adott időpillanatban, ha a várakozási gráf DAG (körmentes). Biz.: • Ha a gráf DAG, akkor ∃ topologikus rendezése: Ti1,.,Tin, és ez egy lefutási sorrendet biztosít a T-k számára. (Ti1 léphet, mert nem vezet bele él) • Ha a gráf nem DAG, akkor van benne irányított kör, amelyben a T-k patthelyzetben vannak. Def.: Pattok orvoslása 1. Várakozási gráf figyelése, és szükség szerint abort Az ütemező az esetleges patt ciklusból egy vagy több tranzakciót kiiktat, ezáltal a többi T futhat tovább. 2. Rendezés (<) az adategységeken Szabály: T a zárakat a < rendezés szerint növekvő sorrendben kéri. A módszer árnyoldala, hogy interaktív rendszerekben ezt nem mindig tudják teljesíteni. 3. A T tranzakció egyszerre kéri az összes szükséges

zárat . Az adatokon végzendő munkát T csak ezután kezdi Az előbbi módszernél felmerült gondok lépnek itt is fel. 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 3 22. tétel A tranzakciókezelés alapfogalmai Célunk az elkövetkezendőkben, hogy biztosítsuk a sorosíthatóságot. Ez nehezebb feladat, mint a pattmentesítés, és függ az alkalmazott tranzakciós modelltől is. 2. Tranzakciós modellek Def.: Egyszerű tranzakció modell LOCK A és UNLOCK A alkalmazását jelenti. Ha T megkapja a "kemény" zárat A-ra, akkor a többi T≠T tranzakció semmit sem tehet A-val. Tranzakció: szabályos LOCK, UNLOCK párok sorozata, T: LOCK A,.,UNLOCK A. A LOCK és UNLOCK között található A kritikus intervalluma Feltehetjük, hogy itt Aval valami egyedi történik: olvassák vagy írják Ebből következően vannak bizonyos konzisztencia-szabályok. Pl.: idő T1: LOCK A, UNLOCK A 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, 4 22. tétel A tranzakciókezelés alapfogalmai 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 5 22. tétel A tranzakciókezelés alapfogalmai Tn . T1 T2 T3 . z(Tn) < z(T1) < z(T2) < z(T3) Az összes egyenlőtlenség együtt nem teljesülhet. További állítások: 1. A következő zárpont szerinti növő soros ütemezés S-sel ekvivalens 2. Tfh T1 nem kétfázisú Ekkor megadható egy kétfázisú T2 és a két T-nek egy olyan S ütemezése, ami nem sorosítható. Megj.:További modellekkel a köv tételekben ismerkedünk meg 6 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. Def.: Tranzakció szemantikája Két ütemezés ekvivalens, ha: a.) ugyanazokat az értékeket olvassák RLOCK-nál; b.) ugyanazokat az értékeket rendelik minden adategységhez Def.: Precedencia vagy sorosítási gráf az RLOCK / WLOCK modellben A gráfban T1T2 (T1≠ T2) él, ha: 1. T1: RLOCK A T1: UNLOCK A nincs A T2: WLOCK A T2 feltétlenül T1után kell, hogy

következzen, mert T1-nek T2-től független A értéket kell olvasnia. 2. T1: WLOCK A T1: UNLOCK A nincs A T2: WLOCK A T2-nek azért kell T1után következnie, mert a szekvencia végén T2-től függő A értéknek kell maradnia A-ban. 3. T1: WLOCK A T1: UNLOCK A nincs WLOCK A T2: RLOCK A T2-nek olyan A értéket kell olvasnia, amit T1 állított elő, így T2-nek T1 után kell következnie. A gráfban T1T2 (T1≠ T2) nem él, ha: T1: RLOCK A . T1: UNLOCK A T2: RLOCK A Ez okozza valójában a hatékonyságnövekedést, mert nem kell élt felvenni T1 és T2 közé. Tétel: A WLOCK / RLOCK ütemezés sorosíthatóságáról Az S ütemezés sorosítható ⇔ a G precedencia gráf DAG. Biz.: analóg az egyszerű tranzakció modell hasonló tételével 1 23. tétel Az RLOCK/WLOCK-modell. Hierarchikus szerkezetek zárolása 2 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 tranzakciók vannak, akkor az ütemezés sorosítható. Biz.: analóg az egyszerű tranzakció modell hasonló tételével Def.: Zár kompatibilitási mátrix Az RLOCK / WLOCK bevezetésével elérhető előnyök gondolata alapján további zármódok is definiálhatók. Ettől nyilván akkor várhatunk további hatékonyságnövekedést, ha az értelmezett zár-módok között minél több olyan van, amely egy adategységen egyidejűleg tartható fenn, azaz összeférhetők, kompatibilisek. A zár-módok közti összeférhetőséget a zár kompatibilitási mátrixban szokás ábrázolni. Pl.1: zárkérés RLOCK WLOCK meglévő zár az RLOCK Igen Nem adategységen WLOCK Nem Nem Egy (i,j) mátrixelem "Igen", ha egy, az adatelemen lévő adott típusú zár mellett

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

tovább növelheti. Kitüntetett jelentősége van annak az esetnek, amikor az adat egységek v alamilyen 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). 4 23. tétel Az RLOCK/WLOCK-modell. Hierarchikus szerkezetek zárolása Ez utóbbi feltételezés azonban azt is eredményezheti, hogy két tranzakció tart fenn egyidejűleg zárat ugyanazon az adategységen. A jelenség neve zárkonfliktus, amit alkalmaz szabályok

megtartásával el kell kerülni. A figyelmeztető protokoll zárműveletei: • LOCK A: zárolja A-t és valamennyi leszármazottját. Két különböző T nem tarthat fenn egyidejűleg zárat ugyanazon az adategységen. • WARN A: A-ra figyelmeztetést (warning) rak. Ekkor A-t más T nem zárolhatja • UNLOCK A: eltávolítja a zárat és figyelmeztetést A-ról. A protokoll szabályai ugyanazok, mint az egyszerű tranzakció modellben, továbbá: 1. egy T első művelete kötelezően a "LOCK gyökér" vagy "WARN gyökér" 2. LOCK A vagy WARN A akkor helyezhető el, ha A szülőjén már van WARN 3. UNLOCK A akkor lehetséges, ha az A gyerekein már nincs LOCK vagy WARN 4. kétfázisú: az első UNLOCK után már nem következhet LOCK vagy WARN Tétel: A figyelmeztető protokollos ütemezés sorosíthatóságáról 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ó. 5 Időbélyeges módszerek egy processzoros környezetben 24. tétel 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. 1 24. tétel Időbélyeges módszerek egy processzoros környezetben Megjegyzés: elképzelhető, hogy egy ütemezés sorosítható •

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

és T olvasni akarja A-t Abort T a következménye annak, hogy egy később indult tranzakció már írta A-t, tehát nem olvashatjuk. (A t(T) ≥ w(A) természetesen mindig lekezelhető, és r(A):=t(T).) 2. t(T) < r(A) és T írni akarja A-t Abort T a következménye annak, hogy egy később indult tranzakció már olvasta A-t, tehát nem írhatjuk. (A t(T) ≥ r(A) természetesen mindig lekezelhető, és w(A):=t(T).) A következő két konfliktushelyzet már nem okoz Abortot: 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. 2 24. tétel Időbélyeges módszerek egy processzoros környezetben Az ütemezés folyamata a következő: 1. T1 olvashatja A-t: r(A) = 20 lesz 2. T2 olvashatja A-t (a jövőben olvasás "történt", de ez nem zavaró): r(A) = 20 marad 3. T1 írhatja C-t: w(C) = 20 lesz 4. T2 írni akarja C-t, most a 4 típusú helyzet következett be T2 nem ír, w(C) marad, továbblépünk. 5. T2

olvashatja A-t: r(A) = 20 marad 6. T2 írni akarja A-t, de 2 miatt abortálni kell T2-t Ugyanis A-t már a jövőben olvassa valaki. A működés szorosan kapcsolódik a kezdőidőkhöz. Pl ha ugyanebben a példában r(C)=25 lenne, akkor az abort már a 3. utasításnál bekövetkezne Az időbélyeges ütemezés tehát nem tesz semmit a baj elkerülésére, de ha az bekövetkezik, akkor aborttal oldja fel a helyzetet. Megjegyzés az időbélyegek tárolásáról Gond az, hogy esetleg sok r(A) és w(A) bejegyzés van a rendszerben. Ötlet: legyen t-∞ = min{t(T), ahol T aktív}. Vagyis van egy időhorizontunk, ami "alatt" nem tároljuk az időket; vagyis elég azokat az r(A) és w(A) időket tárolni, melyek t-∞-nél nagyobbak (vagy egyenlőek vele), azaz aktívak. 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 3 24. tétel Időbélyeges módszerek egy processzoros környezetben t(T) = 100 érkezik. T: WRITE A és w(A) = 80. Ez egyelőre jogos akciónak látszik. De elképzelhető, hogy a tényleges írás előtt valaki már w(A) = 110-zel ír. Ez egy abort-helyzet lenne T-re, amit későn, csak a COMMIT után fedeznénk fel. Az ellenőrzés elvégzéséig zárat kell tartani A-n! Kétféle megoldás adódik: 1. Tfh T az A-t írja vagy olvassa Akkor végezzük az ellenőrzést, amikor T ténylegesen A-hoz fordul, vagy 2. közvetlenül a COMMIT - a befejező lépés - előtt Mindkét esetben az ellenőrzés kezdetétől az esetleges tényleges írásig

zárat kell tenni Ara. A két technika jellemzője: 1. hosszabb zárak, kevesebb abort; 2. rövidebb zárak, de több abort (ez az optimista stratégia) 3. Verziókezelés időbélyeges modellben Def.: Verziókezelés Szoros rokonságot mutat az időbélyeg-kezeléssel, de attól függetlenül is létezik. 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. 4

24. tétel Időbélyeges módszerek egy processzoros környezetben 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.) 5 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 1. Bevezetés Eddig nem foglalkoztunk azokkal a problémákkal, amelyek akkor lépnek fel, ha egy tranzakció nem fut le teljesen, valamely ok miatt idő előtt befejeződik. Ezek a lehetséges

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

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

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

adatbázist helyreállítani, ha egy tranzakció abortál (csak redo kell); 2. zárait csak az adatbázisba való írás után engedi el Ez szabály biztosítja valójában azt, hogy piszkos adatot ne lehessen olvasni, tehát elkerüljük a l avinákat, ami kifejezetten előnyös. Azaz az események pontos sorrendje: COMMIT, írás a DB-be, zárak elengedése. Mindez természetesen csak akkor igaz, ha nem kell rendszerhibákkal is számolni, amelyek az írási folyamat megzavarásával eredményezhetik, hogy piszkos adat kerül az adatbázisba. Ez ellen azonban más módszerekkel kell védekezni (lásd később: naplózás). Tétel: A szigorú kétfázisú protokoll sorosíthatóságáról 2 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 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. 3 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 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 Bevezetés 4 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás A rendszerhibák elleni védekezés általános módszere a naplózás (journal, log). A napló a mi értelmezésünk szerint az adatbázison végrehajtott változások története. Erre nagyon odafigyelünk, gondosan és rendszeresen mentjük bele a változásokat. Szerkezete, tartalma a rendszeres visszaállításokat segíti. A napló

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

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

tranzakciókat, amelyekre találunk (T, commit) bejegyzést a naplóban 3. addig megyünk visszafelé a naplóban, amíg ameddig nem találunk egy konzisztens állapotot 4. a 2 pontnak megfelelő tranzakciókra vonatkozó bejegyzések segítségével az DB-ben található értékeket felülírjuk az újakkal. 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. 5 25. tétel Sikertelen tranzakciók, rendszerhibák kezelése, naplózás 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. 6 26. tétel Elosztott tranzakciók. Zárképzési technikák Elosztott tranzakciók. Zárképzési technikák 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 ad ategysé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örnyezetben 1. Célunk tranzakciók végrehajtása a logikai adategységeken. 1 ezt egybe vagy külön kell írni? valaki elárulhatná nekem! Én inkább egyprocesszorost írnék. 1 26. tétel Elosztott tranzakciók. Zárképzési technikák 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: A N1 B N2 -50 -50 2 csúcson tárolják N3 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 +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. RL OCK 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) 2 26. tétel Elosztott tranzakciók. Zárképzési technikák 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 Ezen módszernél is igaz az állítás,

miszerint a zárkompatibilitás teljesül. Ü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ú (2.4) 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. 3 26. tétel Elosztott tranzakciók. Zárképzési technikák 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. 4 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 b iztosító k onvenció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. 5 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 s oros ü 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. Résztranzakciók: T1-re: T2-re: x1-re T11 T21 x2-re T12 T22 w=írás, u=elengedés, az idő lefelé telik: T11 wA uA T21 T12 wA uA wB uB T22 wB uB 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! 1 27. tétel Elosztott "Kész"-protokoll, blokkolás A megoldás ötlete: T részeinek legyen közös z árpontja, ami előtt lezajlik az összes zár-ké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 po ntot 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 valamennyi résztranzakciónak abortálnia kell. Tehát a közös kész pontot megelőzi a közös zárpont elérése, sőt, akár egybe is eshetnek. Ha valamely protokoll tehát biztosítani tudja a közös ké sz po nt

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 m egegyezé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. 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 2 "abort" jött a főnöktől Egy résztvevő állapotai 27. tétel Elosztott "Kész"-protokoll, blokkolás 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 üzenetek; • 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. 3 27. tétel Elosztott "Kész"-protokoll, blokkolás Egy résztvevő állapotai Ábrázolva: "kezdj szavazni" "készre szavazok" "commit" jött a érkezik küldése 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" szavazott commit várakozás kell timeout vagy valaki abortra szavazott

"commitot" küld commit abort kell abortot küld abort A főnök állapotai A helyreállítás folyamata: Ha a résztvevő belép a "helyreállítás" ál lapotba, 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" ál lapotban 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. 4 27. tétel Elosztott "Kész"-protokoll, blokkolás 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 5 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. 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), < bC b A majd 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 1 28. tétel Relációs lekérdezések kiértékelése ideiglenes indexet / rendezést készíteni az adatállományhoz, mert így az érdemi munka nagyon lerövidül. Csomósodás f igyelembe 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 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)). Sőt: Itt a D=99 feltételt rögtön a CD relációra is elvégezhetjük, így kisebb lesz a szorzat. Π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: ΠA (AB σ D=99(CD)). B=C 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: 2 28. tétel Relációs lekérdezések kiértékelése 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. * σ, Π, Πσ σ, Π, Πσ 3