google.com, pub-5333805121326903, DIRECT, f08c47fec0942fa0

2013. január 21., hétfő

Az állományok feldolgozásának módszerei


Bevezetés
Az információ feldolgozás története korábban kezdődött, mint az elektronikus adatfeldolgozás. A múlt század végén az amerikai népszámlá­lás részére dolgozta ki Hollerith lyukkártyás rendszerét. Az ekkor megállapított kártya szabvány még az 1980-as években is haszná­latban volt, az 1970-es években pedig még mechanikus Hollerith gépekkel (rendező, stb.) is lehetett találkozni Magyarországon. Ugyanakkor az első generációs számítógépekre nem csak az elektroncsövek, hanem a kis tárolókapacitás mellett az is jellemző volt, hogy azokat csak erre specializálódott szakemberek tudták használni. Nem csoda, hogy ezeket a gépeket elsősorban kalkulátorként alkalmazták. (Erre a célra is fejlesztették őket ki.) A második generációs gépek a fordítóprog­ramok révén már szélesebb felhasználói kör számára voltak elérhetőek, s már valamivel nagyobb kapacitású háttértárolóik is lehetővé tették az első információ-feldolgozó rendszerek megjelenését. Mindez fokozottan igaz a harmadik számítógépes generációra (operációs rendszerek megjelenése). Nem véletlen, hogy azt a mesterséget, melyet eleinte számítástechnikának neveztek, ma informatikának hívják: napjainkban a számítógépek fő fel­használási területe az információ-feldolgozás. Mára az információ feldolgozása igazi iparrá vált, az információban szegény országok más iparágakban sem lehetnek sikeresek. Az információ feldolgozás alapvető módszerei Napjainkig az információ feldolgozásnak három alapvető formája ismeretes: a folyamatszemléletű információ feldolgozás, az adatbázis-szemléletű információ feldolgozás, és a szakértői rendszerek.  A folyamatszemléletű információ feldolgozás E rendszerek legfőbb jellemzője hogy azok célorientáltak, azaz ké­szítésükkor először az elérendő célt kell meghatároznunk, majd a cél isme­retében tervezzük meg az ahhoz vezető folyamatot, s a folyamat által használandó adatállományokat (file). Az állományok csak adatokat tartalmaz­nak: kapcsolatokat a folyamat írja le. A tervezés sorrendje tehát:  cél   folyamat   állományok Az ilyen módon megtervezett adatállományok nem igényelnek túl nagy tárolókapacitást, hiszen csak a valóban felhasználandó adatokat kell tárolnunk. Másrészt az adatállományok feldolgozása igen gyors lehet, hiszen azok szerkezete optimálisan illeszkedhet az adott feladathoz. (Tisztázandó persze, hogy tekinthetünk optimális illeszkedésnek.) A leírt tulajdonságok indokolják, hogy miért használták az első információ fel­dolgozó rendszerek ezt a formát, s hogy miért használják még napjainkban is kisebb volumenű, alkalmi feladatok esetén. Ugyanakkor a folyamat szemléletű információ feldolgozás minden célhoz új folyamatot és állományokat kíván, függetlenül az esetleges kö­zös adatok előfordulásától. Az így keletkező redundancia rossz tárolókihasználást eredményez - és ami még nagyobb baj - felidézi az  inkonzisztencia veszélyét, vagyis azt, hogy egy-egy több helyen előfor­duló adat egyes példányainak különbözik a tartalma. Hátránya az effajta feldolgozásnak az is, hogy csak az eredeti kérdésre ad választ, a rendszer­nek ad hoc jellegű kérdések nem tehetők fel. Optimális szerkezetű állományok A programozással foglalkozók jól tudják, hogy arra a kérdésre: mi a jó program ismérve, nem lehet egyszerűen válaszolni. El kell döntenünk, milyen szempontból akarjuk a programokat összehasonlítani. Ha az in­formáció feldolgozó rendszereket vizsgáljuk, a helyzet ugyanilyen bonyo­lult.  tárolóhely létrehozás Optimalizálási szempontok  feldolgozási idő  keresés  változtatás  felhasználói szempontok Könnyen belátható, hogy a felsorolt szempontok egyidejűleg nem elégíthetőek ki maradéktalanul, bármelyiket választjuk is ki az optimalizá­lás alapjául, az így adódó megoldás a többi szempont szerint messze lesz az optimálistól. Így pl. a tárkihasználás szempontjából ideális tömörített állományok feldolgozása nyilvánvaló többletidőt igényel, a könnyen kezelhető felhasználói felületek mind tár, mind idő tekintetében igen sokat követelnek. (Gondoljunk csak pl. a DOS-os és a WINDOWS-os progra­mok hely- és időigénybeli különbségeire!) De ellent mondanak egymásnak az időre optimalizálás "al" szem­pontjai is: nyilvánvalóan pl. a keresést jelentősen meggyorsítja, ha egy állomány strukturált (mondjuk a keresési kulcs szerint rendezett), ugyan­ekkor a rendezettség megteremtése a létrehozáskor, megtartása új rekor­dok beszúrásakor komoly időigénnyel járhat. Az elmondottak ellenére általában kijelenthetjük, hogy a modern in­formációs rendszerekben kiemelt szerepe van a keresésnek. Egyfelől a nagy hálózatok korában az időfaktor többnyire szorítóbb mint az elosztott információk helyigénye, másfelől az időre való optimalizáláson belül elmondhatjuk, hogy egy-egy változtatást (adatbeszúrás, törlés) megelőz az illető rekord keresése (van-e ilyen, s ha igeműn, hol). Ha mindehhez hoz­závesszük, hogy egy-egy állományban (melyet egyszer hozunk létre) igen sokszor kell keresnünk, nem meglepő a keresés kiemelt szerepe. A keresés időigényét két tényező szabja meg, az egyik az átlagosan szüksége lépésszám (hány keresési lépést kell végrehajtanunk átlagosan egy-egy keresés alkalmával), a másik az egyes lépések időigénye. Ha feltesszük, hogy rekordjainkat azonos gyakorisággal keressük, egy-egy keresés időigényére alábbi képletet adhatjuk:SN ( TA +  TB + TC )                                                                                                                                 A képletben TA az u.n. algoritmusidőt jelenti, azaz annak az algo­ritmusnak az átlagos végrehajtási idejét, mely kijelöli a legközelebb meg­vizsgálandó rekordot, TB az u.n. behozási idő, azaz a tárolóról való beol­vasás átlagos időigénye, végül TC az összehasonlítási (komparálási idő, mely a beolvasott rekord kulcsának megvizsgálásához szükséges. Végül SN az átlagosan szüksége lépésszám. Belátható, hogy központi tár esetén elesik a TB tag, míg az általá­nosan használt mozgófejes lemezeknél TA és TC elhanyagolható TB-hez képest. Másrészt míg TC idejét nem tudjuk befolyásolni, TA, TB és  SN értéke a választott algoritmustól függ. Azt pedig, hogy milyen keresési algoritmusok között választhatunk az állomány szervezési módja, szerke­zete határozza meg. Például ha egy adott nevű személy létező rekordját akarjuk egy rendezetlen állományból kikeresni, az u.u. lineáris keresést alkalmazhat­juk, azaz sorban meg kell vizsgálnunk a rekordokat, hogy azonosak-e az általunk keresettel. Ez esetben átlagosan a rekordok felét kell megvizsgál­nunk (azaz SN k N/2). Ha az illető rekordja nem található meg az állo­mányban, ennek megállapításához már az egész állományt végig kell ke­resnünk (vagyis S'N k N). Ha az állomány a névre rendezett, az utóbbi esetben is elég a rekordok felét megvizsgálni (S'N k N/2). Így a struktúra megváltoztatása önmagában gyorsított az eljáráson. Más kérdés, hogy az ilyen módon strukturált állományokban már sokkal hatékonyabb keresési algoritmusok használatára is van remény. A legfontosabb állomány struktúrák1.) Szekvenciális állomány struktúrák ahol logikailag a rekordok mindegyikének egy megelőzője és egy rákö­vetkezője van (az első és az utolsó elem kivételével).2.) Hierarchikus állomány struktúrák; ahol logikailag a rekordok mindegyikének egy megelőzője, de esetleg több rákövetkezője van (az első elem kivételével). 3.) Hálós állomány struktúrák; ahol logikailag a rekordok mindegyikének több megelőzője és több rákö­vetkezője lehet. 4.) Asszociatív állomány struktúrák; ahol nem a rákövetkezés ill. megelőzés adja a állomány struktúráját, más logikai szempont szerint lehet a rekordokat ill. rekordok egy csoportját kiválasztani. Szekvenciális állomány struktúrák: Fizikai szekvenciális állomány struktúrák Fizikai szekvenciális struktúráról akkor beszélhetünk, ha a rekordok logikai és fizikai sorrendje megegyezik. E zervezési forma legfontosabb előnye, hogy a természetesen itt is alkalmazható a lineáris keresés mellett annál jóval hatékonyabb keresési eljárások alkalmazását is lehetővé teszi. A.) Bináris, logaritmikus keresés E közismert keresési eljárás lényege, hogy a megvizsgálandó állo­mány ill. állományrész középső rekordjának kulcsát hasonlítjuk össze a keresett rekordéval, s így eldönthetjük, hogy  a.) megtaláltuk a keresett rekordot, b.) a keresett rekord a vizsgált állomány bal felében van, c.)  a keresett rekord a vizsgált állomány jobb felében van. A keresést ezután már csak az előzőlépésben vizsgált állomány felében kell folytatnunk (ha egyáltalán). Belátható hogy bináris keresés esetén e az átlagosan szükséges lé­pésszámra mind sikeres, mind sikertelen esetben SN = log2 N. B.) Peterson-féle keresés Az előző módszer továbbgondolásából adódik ez a módszer. A gondolatmenet lényege az, hogy az állományt az egyes lépésekben ne két hosszra egyenlő részre osszuk, hanem két olyan részre, melyekben a kere­sett rekord előfordulása egyenlően valószínű. (Pl. egy nevekre rendezett nyilvántartásban Ács Aba rekordját nyilván az állomány elején, Zöld Zol­tánét a végén célszerű keresni.) Az ilyen felezéshez nyilván ismerni kell a kulcsok eloszlását. Feltehetjük pl., hogy azok eloszlása egyenletes. Ekkor  SN =1/2 log2 N. Mindebből nem következik azonban, hogy a Peterson-féle keresés mindig hatékonyabb a binárisnál. Ennek egyik oka az, hogy kulcsaink eloszlása messze eshet az egyenletestől, s ilyenkor e módszer hatékonysága jelentő­sen romlik. A másik ok, hogy a Peterson módszer minden lépése arányosí­tást, azaz "igazi" osztást igényel. A bináris keresésnél erre nincs szükség, az itt használt felezés a rendkívül gyors léptetéssel megvalósítható. Mivel központi tárbeli használatnál, az egyes lépések időigényét az algoritmus­idő határozza meg, hiába igényel a Peterson féle keresés kevesebb lépést, ha azok jóval lassabban hajthatók végre. Bármilyen gyorsak a fizikai szekvenciális állománystruktúránál használható keresési eljárások, elhamarkodott kijelentés lenne azt állítani, hogy az ilyen állományok feldolgozása N < 4 esetén gyorsabb, mint a struktúrával nem rendelkezőké. Az állomány kezelésekor ugyanis a kere­sésre fordított időn kívül figyelembe kell venni azt is, melyet a karbantar­tásra, azaz a rendezettség megtartására kell fordítanunk. Mindezt össze­vetve azt mondhatjuk, hogy fizikai szekvenciális struktúra használata első­sorban a statikus állományoknál javasolt, azaz ott ahol egy-egy struktúrát érintő változtatásra (pl. beszúrás) sok keresés esik. Logikai szekvenciális állomány struktúrák Logikai szekvenciális struktúráról akkor beszélünk, ha a rekordok logikai és fizikai sorrendje nem egyezik meg. A logikai sorrendet ez esetben legtöbbször a rekordokban elhelye­zett mutatók (pointerek adják) meg. (Meg lehetne adni a logikai sorrendet valami külső táblázat segítségével is, ezt azonban a szakirodalom általá­ban az indexelt szervezés részeként tárgyalja: v.ö.  pont.)  A muta­tórendszerek lehetnek egy és kétirányúak, ill. gyűrűsek. Az állomány, és a sokszor ugyancsak speciális listaként kezelt üres helyek kezdetét egy u.n. indító tábla tartalmazhatja. E szervezési mód legfőbb előnye, hogy alkalmazásakor az állo­mány logikai struktúrájának megváltoztatása igen könnyű, nem igényli a rekordok mozgatását, csupán a mutatók módosítása szükséges. További jelentős előny, hogy fizikailag ugyanaz az állomány több mutatórendszer alkalmazásával többféle logikai szekvenciális rendbe is szervezhető. (E logikai szekvenciáknak nem kell minden esetben valamennyi rekordot tartalmazniok.)  A felsorolt előnyök mellett a logikai szekvenciális szervezésnek komoly hátrányos tulajdonságai is vannak. Elsősorban azt kell megemlíte­nünk, hogy e szervezési forma mellet nem állnak rendelkezésünkre olyan hatékony keresési algoritmusok mint a bináris, vagy a Peterson féle. Nem kisebb probléma, hogy mozgófejes lemez használata esetén - ha a rekor­dok véletlenszerűen helyezkednek el az állományban - a keresés során szükséges pozícionálások száma a feldolgozást nagyon lelassítja. (Egy C cilindert elfoglaló állomány esetén két rekord elérése között átlagosan C/3 cilindernyi pozícionálásra van szükség.) A fenti hátrányok kiküszöbölésére, vagy legalább csökkentésére használhatóak az u.n. "csaknem fizikai szekvenciális" struktúrák. E struktúrák lényege, hogy az állományt - mely logikai szekvenciális, így mutatókkal rendelkezik - létrehozásakor a mágneslemezen fizikailag is szekvenciálisan helyezzük el. Beszúráskor nem szükséges a fizikai szekvencialitást megtartani, az új rekordot a - miden cilinderen külön-külön fenntartott - u.n. cilinder túlcsordulási területre helyezzük, és a logi­kai rendbe a mutatók segítségével illesztjük be. Látható, hogy így elkerülhejük a sok pozícionálásból adódó idő­veszteséget. Ezen túlmenően azonban e szervezési formának az is előnye, hogy mellette alkalmazhatjuk az u.n. "kupacos" keresési módszert. A keresési módszer lényege, hogy a rekordokat (N db.) G kupacra osztjuk, majd először e kupacok első elemeit hasonlítjuk össze a keresett rekord­dal. Így vagy megtaláljuk a keresett rekordot, vagy legalább meghatároz­hatjuk, hogy melyik kupacban van. Ezután ezt a kupacot kell végigkeres­nünk. Ha az egyes kupacok kezdőelemei az elsődleges (nem a túlcsordu­lási) területen vannak, a keresés elég gyors lehet. Természetesen kulcskér­dés a kupacok méretének megválasztása. Bizonyítható, hogy ha az egyes kupacok méretét kN-re választjuk, a szükséges lépésszámra SN =kN adódik. Az eddigiekben mindig feltételeztük, hogy az egyes rekordokat azonos gyakorisággal keressük vissza (ezt a soronkövetkező bekezdés kivételével a továbbiakban is feltesszük majd). A logikai szekvenciális szervezés azonban lehtőséget ad erősen különböző keresési gyakoriságú rekordok olyan szekvenciába szervezésére, melynél a sorrendet a keresési gyakoriság csökkenő sorrendje szabja meg. Ilyen szervezés fizikai szekvenciális struktúrában is lehetséges, a logikai szekvenciális struktúra esetén azonban alkalmazhatóak az u.n. önrendező algoritmusok is, melyek a gyakoriság ismerete nélkül, ill. változó gyakoriság mellett is lehetővé teszi a gyakoriság szerinti szervezést. (A legegyszerűbb ilyen algoritmus minden rekordot annak keresése után az első helyre csatol. Ha nem is érhető így el pontos gyakoriság szerinti rendezés, azt ez az egyszerű eljá­rás is biztosítja, hogy a gyakran használt rekordok mindig az állomány elején legyenek találhatók.) A hierarchikus állomány struktúrák A hierarchikus (faszerű) struktúrák számítógépes ábrázolására egya­ránt elterjedtek mind a belső mutatós (pointeres), mind a külső mutatós (táblázatos) eljárások. A.) Belső mutatós eljárások a.) Visszavezetés szekvenciális struktúrákra. E módszereknél a fa egy megadott módon való bejárását rögzítjük. A legjellegzetesebb ilyen módszer az u.n. a left-list módszer. Sajnos az eljárás információvesztéssel jár: az eredeti fastruktúra nem állítható vissza belőle egyértelműen. b.) Több mutató használata. A rekordokban lehet annyi mutatót elhelyezni, ahány rákövetkezője (gyermeke) van az illető rekordnak. Az ábrázolás teljesen egyértelmű, hátrányos tulajdonsága viszont, hogy - mivel a rákövetkezők száma tág határok között változhat - vagy igen rossz tárolókihasználással, vagy vál­tozó hosszú rekordok használatával kell számolnunk. c.) Külön kapcsolórekordok használata. Látszólag bonyolítja a helyzetet, ha az információt hordozó rekor­dokon kívül egy újabb rekordtípust vezetünk be, mely csak a kapcsolatok leírására szolgál. Ugyanakkor ezzel a megoldással elérhető, hogy egy-egy rekordban (a kapcsolórekordokat is beleértve) legfeljebb két mutató le­gyen, sőt az is, hogy ezek egyike "oldalra", másika "lefelé" mutasson, ami a struktúrát igen áttekinthetővé teszi. d.) Gyűrűk alkalmazása. Szokásos megoldás a fában "függőleges" és "vízszintes" gyűrűket szervezni, melyekkel ugyancsak megoldható, hogy egy-egy rekord ne tartalmazzon kettőnél több pointert. B.) Külső mutatós eljárások a.) Táblázatok használata. E táblázatokban az egyes rekordokhoz tartozó bejegyzések adják meg a rákövetkezőket (esetleg a megelőzőt is). Mivel a rákövetkezők száma itt is erősen változhat, a táblázatok ábrázolásánál ugyanazokkal a problémákkal kell szembenéznünk, mint a több mutatós rendszer alkalma­zásánál. b.) Bináris mátrixok használata. Bináris mátrixokban ábrázolhatjuk, hogy egyes rekordok között van-e kapcsolat. A bináris jellegen kívül az teszi - az egyébként nagymé­retű mátrixokkal operáló - módszert használhatóvá, hogy hierarchikus állományoknál elég a mátrix felét tárolni (a másik félmátrix csak 0 eleme­ket tartalmaz).  A hálós állomány struktúrák: A.) Belső mutatós eljárások a.) Visszavezetés a hierarchikus struktúrákra. Megkisérelhetjük a hálós struktúrákat hierarchikusra visszavezetni. Ez esetben úgy kerülhetjük el az egyes elemek többszörös tárolását, hogy azok helyett - egy kivételével - u.n. virtuális elemeket alkalmazunk (azaz olyan elemeket, melyek adatokat nem, csak azok helyére való utalást tar­talmaznak. b.) Több mutatós eljárások. Ezek az eljárások ugyanúgy használhatók, mint a hierarchikus eset­ben, az előnyök és a hátrányok is ugyanazok lesznek. Itt azonban nem alkalmazhatóak azok az eljárások (külön kapcsolórekordok, gyűrűk), melyek kihasználják a szintek létezését: a "vízszintes", a "függőleges" fogalmát. B.) Külső mutatós eljárások a.) Táblázatok használata. A táblázatok alkalmazását illetően semmi lényeges különbség sincs a hálós és a hierarchikus eset között. b.) Bináris mátrixok használata. A bináris mátrixok is ugyanúgy használhatók, mint a hierarchikus állományoknál, itt azonban általában nem lesz elegendő a fél mátrix táro­lása. Asszociatív állomány struktúrák  Indexelt állomány struktúrák A.) A sűrű indexelés E szervezési formánál az adatállomány minden tételéhez tartozik az index állományban egy index bejegyzés: egy kulcs cím pár. Ilyen módon több szempont alapján több index is szervezhető, az adatállományhoz új rekordok könnyen fűzhetők (a végére), az index bejegyzés ismeretében a keresés gyors. Ugyanakkor nagyméretű index állományokban kell keresni, és azokat karban is kell tartani. Kulcskérdés tehát az index állomány szerkezetének helyes megvá­lasztása. Sok szempontból az u.n.  bináris fák (olyan fák, melyek miden elemének legfeljebb két gyermeke van) használata tűnik előnyösnek. Ha egy bináris fa kiegyensúlyozott (azaz az utolsó ill. és az utolsó előtti szint kivételével minden elemnek valóban két leszármazottja van), a keresés igen gyors benne: közelítőleg log2 N lépésre van szükség átlagosan. Ugyanakkor a kiegyensúlyozottság megtartása új elemek beszúrásánál igen időigényes. A gyakorlatban indexállományok készítésére elsősorban az u.n. B-fákat (Bayer fákat) használják. (Ilyen struktúrát alkalmaz a közismert Turbo Access, a dBASE, a Clipper,  a FoxPro, stb.) A B-fa lényege, hogy az indexállomány lapokra van osztva, egy-egy lapon (a gyökérelemet kivéve) n és 2n közé eső számú bejegyzés, és a bejegyzéseknél eggyel több pointer van. (Ez az n szám jellemző a szervezésre.) Az ilyen állomá­nyok könnyen karbantarthatóak, és a bennük való keresés elég gyors: közelítőleg logn N lépésre van szükség átlagosan. B.) A ritka indexelés E szervezési formánál nem minden rekordhoz, csak bizonyos jelző­pontokhoz tartozik bejegyzés. Természetesen az eligazodáshoz ez esetben valamilyen rendezettség szükséges. Az indexek általában több szintűek, az alsó szintű indexekben (sok bejegyzés) való eligazodást újabb ritka index segítheti. Jól példázza a ritka indexelést a szokásos telefonkönyv. Ilyen szervezés mellett igen gyors a keresés, és az állományba aránylag könnyen lehet új rekordokat beszúrni.Ugyanakkor ilyen index rendszer csak egy szempont alapján szer­vezhető. C.) Az index-szekvenciális szervezés A ritka indexelés egyik legnépszerűbb megvalósítása az index-szekvenciális szervezés. Kifejezetten mágneslemezre tervezték: így a leg­alsó (legritkább) index a sávindex. (A sávokat technikailag amúgy sem lehetséges másképpen, mint szekvenciálisan feldolgozni.) Fő index Az index szintek:Cilinder index Sáv index  Minden egyes cilindert három részre osztanak, hogy az azon levő területeket fejmozgás nélkül lehessen elérni. Index terület A lemez felosztása: Elsődleges adatterület Túlcsordulási terület Az állomány létrehozásakor a rekordok az elsődleges adatterületre kerülnek, melyet csak részben töltenek fel. A feltöltés rendje fizikai szekvenciális. Ekkor rögzítik az indexeket. Ha az elsődleges adatterület betelik, a rekordok a túlcsordulási területre kerülnek, mutatókkal ellátva, azaz logikai szekvenciális rendben. Az adatok keresése az index rendszeren keresztül történik. Természetesen az index-szekvenciális állományokat időről időre újra kell szerveznünk, azaz valamennyi rekordot az elsődleges területre kell tölteni. Ellenkező esetben a feldolgozás nagyon lelassulhat. A direkt állomány szervezés A direkt szervezésnél a rekordok kulcsai és címei között egy leké­pezés hozza létre a kapcsolatot. Természetesen kívánatos lenne, hogy ez a leképezés egy-egy értelmű legyen, vagyis, hogy a leképezés ne rendeljen azonos címeket különböző kulcsokhoz (látjuk majd, hogy ez a követel­mény nem mindig teljesíthető). A.) A leképezések A fenti követelményeknek eleget tévő leképezést közvetlen leképe­zésnek nevezzük. Erre példa egy olyan elképzelt állomány, mely a teljes magyar lakosság adatait tartalmazza, s melynél a kulcsként használt sze­mélyi szám egyben a rekord állományon belüli sorszáma. (Bináris számí­tógépben ábrázolt kulcsokat minden további nélkül tekinthetünk numeri­kus értékeknek, s az sem okozhat problémát, hogy címként az állományon belüli sorszámot tekintjük.) A közvetlen leképezések sajnos többnyire katasztrofálisan rosszul gazdálkodnak a tárterülettel, s így gyakorlatilag használhatatlanok. (Megjegyezzük, hogy tekinthetjük ilyen szervezésnek a sűrűn indexelt állományokat is, ezekre nem vonatkozik a rossz tárkihasz­nálásról szóló megjegyzés.)  A jobb tárkihasználás érdekében követelményeinkből engedni kény­szerülünk.  Az u.n. hashing algoritmusok olyan leképezések, melyek - lehetőleg nem túl sokszor - megengedik, hogy különböző kulcsokhoz ugyanaz a cím tartozzék (ezek az u.n. szinonimok). Cserébe jobb tárki­használásra számíthatunk. A tapasztalat azt mutatja, hogy 80-85%-os tár­kihasználás mellett 20%-nél nem több szinonim elfogadható érték. A leggyakoribb hashing algoritmusok: a.) a csonkítás melynél lhagyjuk a kulcs olyan jegyeit, melyek nagy valószínű­séggel csak kevés értéket vesznek fel ( pl. a már említett személyi számnál a hónapok tizes jegyei, stb.), és a maradék számot tekintjük az állományon belüli sorszámnak, b.) a maradék módszer melynél a kulcsot egy m modulussal osztjuk, s a sorszám az osztás maradéka lesz. (Célszerű modulusként prímszámot választani.) E módszer előnyös tulajdonsága, hogy az eredetileg egyenletes elosztást nem rontja el. B.) A szinonimok kezelése Hashing algoritmusok esetén külön kell gondoskodnunk a szinonimok kezeléséről. a.) A külső láncolás E módszernél egy külön területen tároljuk a szinonimokat, melyeket mutatólánc köt össze az eredeti (hashing algoritmus által adott) címmel. Mivel előre nem lehet a szinonimok számát tudni, a külön szinonimterület fenntartása akadálya a jó tárkihasználásnak. b.) A belső láncolás Itt is mutatórendszer köti össze a szinonimot eredeti címével, azon­ban azt az elsődleges terület egy üres (és lehetőleg az eredeti címhez közel eső) helyére tesszük. A tárterület kihasználása jó lesz, azonban lehetséges, hogy a szinonim által elfoglalt helyre később igényt tart annak "jogos" tulajdonosa, mely rekordból így "műszinonimot" csinálunk. Ennek keze­lése az állomány feldolgozásakor több lépést igényel. c.) A Peterson módszer (nyílt módszer) A rekordok ugyanott helyezkednek el, mint a belső láncolásnál, azonban nem használunk mutatókat. Az állomány struktúrája egyszerű, feldolgozása azonban több lépést igényel, mint ha a belső láncolást alkal­mazzuk. d.) Többszörös hashing Ha a kiszemelt hashing algoritmus szinonimra vezet, alkalmazha­tunk újabb és újabb ilyen algoritmusokat, mígcsak a probléma el nem hárul. (A gyakorlatban két hashing algoritmust használnak, az esetlegesen még maradó szinonimokat az a.)-c.) módszerek valamelyikét alkalmaz­zák.) e.) Bucket-ek (bugyrok) alkalmazása  Lehetséges az egyes címekhez nem egy, hanem több rekordnyi helyet rendelni. Így kevesebb lesz a szinonimok kezelésére fordítandó idő, ugyanakkor minden keresésnél az érintett bucket-et (pontosan átlagosan annak a felét) meg kell vizsgálni. A módszer használata akkor indokolt, ha a tároló fizikai tulajdonságai (és a rekordok rövidsége) amúgy is csak több rekord egyidejű ki- ill. bevitelét teszik lehetővé. C.) A szinonimkezelő módszerek összehasonlítása  E témakörnek komoly, és nagy matematikai apparátust megmozgató irodalma van, itt csak igen durva heurisztikus okoskodásra van módunk. Központi tárban való használat esetén, előnytelen a többszörös hashing számára a jelentős algoritmusidő (egy hashing algoritmus lefutta­tása jóval hosszabb, mint egy cím átírása, vagy egy regiszter növelése, amit a láncolás ill. a nyílt módszer igényel). A nyílt módszer több lépést igényel mint a láncolások, s algoritmusideje azokéval összemérhető. Jól­lehet a belső láncolás hajszállal több lépést igényelhet a külsőnél (a "műszinonimok" miatt), nagyobb súllyal esik latba a jó tárkihasználás. Így általában a belső láncolást tudjuk javasolni. Mozgófejes lemeznél előnytelenek a sok fejmozgást igénylő mód­szerek: ilyen a többszörös hashing és a külső láncolás. Bár a belső lánco­lás elméletileg kevesebb lépést igényel a nyílt módszernél, ha a szinonim rekord ugyanazon a sávon van, mint az eredeti helye, a gyakorlatban ez az előny nem érvényesül. Ugyanakkor, ha a szinonim az eredeti helyet köz­vetlenül követi (és ez igen gyakori eset), a nyílt módszer gyorsabb is lehet (nem kell a mutatókat feldolgozni). Végeredményben tehát ilyen esetek­ben többnyire a nyílt módszer javasolható. Az adatbázis szemléletű információfeldolgozás         Egyfelől a tárolókapacitások robbanásszerű növekedése, másfelől a felhasználói körnek a rendszertámogatások által lehetővé tett bővülése indokolta az új információ-feldolgozási forma megjelenését az 1960-as években. E szemlélet lényege, hogy a rendelkezésre álló adatokból indu­lunk ki, az összes adatot és a közöttük fennálló összes kapcsolatot egy integrált adatbázisba gyűjtjük, és valamennyi felhasználó valamennyi kérdéséhez ezt az adatbázist (vagy ennek egy részét) használhatja. A felhasználók nagy részének nincs szüksége a teljes adatbázisra, sokszor egy-egy felhasználónak nincs is joga az adatbázisban mindenhez hozzáférni. Egy-egy felhasználói nézet (view) tehát csak az adatbázis egy részét láthatja. Ezen belül is szabályozandó, hogy a látott adatokkal mit tehet (más egy adatot megnézni, vagy pl. megváltoztatni). Szükséges tehát, hogy legyen valaki, aki a felhasználókénál na­gyobb hatáskörrel rendelkezve, ezeket a jogokat kiossza és a munkát fel­ügyelje. Ez a személy, vagy csoport az adatbázis felügyelő. Az ő joga és kötelessége az adatbázist megtervezni, elkészíteni a teljes logikai struktú­rát leíró sémát, valamint az egyes nézetek által látott adatbázis-rész logikai struktúráit leíró alsémákat. Ugyancsak az adatbázis felügyelő feladata az adatbázis működtetése során a felhasználókkal való kapcsolattartás, az adatbázis logikai és fizikai struktúrájának a felhasználói igényeknek meg­felelő módosítása, valamint az adatbázis tartalmának rendszeres mentése. A séma és alséma leírások az u.n. DDL (Data Definition Language: Adatleíró Nyelv) nyelven készülnek ezt a nyelvet többnyire csak az adat­bázis felügyelet használhatja. A felhasználók a lekérdezéseket, adatváltoz­tatásokat a DML (Data manipulation Language: Adatmanipuláló Nyelv) nyelven eszközölhetik. E nyelveknek két nagy csoportja van. Egy Host Language (Beépített Nyelv) azoknak a programozóknak áll rendelkezé­sére, akik az általuk korábban jól megismert magasszintű nyelven kíván­nak dolgozni, ezt a nyelvet egészíti ki a rendszer adatbázisok kezelésére alkalmas utasításokkal, eljárásokkal. Egy Self Contained Language (Önálló Nyelv) teljesen kerek önálló rendszer, ami lehet programozási nyelv éppúgy, mint egy paraméterezéssel kezelhető felhasználói felület (erre példa a légi- stb. társaságok helyfoglalási rendszerei). A tervezéskor az adatbázis felügyelőnek figyelembe kell vennie az adott információ-feldolgozás előzményeit, és nyitva kell hagynia a ké­sőbbi változtatások lehetőségét. Ezt segíti elő a logikai és fizikai adatfüg­getlenség. A logikai adatfüggetlenség azt jelenti, hogy az adatok logikai struktúrájában történő változtatás ne érintse az ezen változtatást nem igénylő felhasználók munkáját. Hasonló követelmény a fizikai struktúrá­val kapcsolatban a fizikai adatfüggetlenség. A két követelmény együttes teljesítése esetén beszélhetünk adatfüggetlenségről. Ugyancsak ügyelni kell a tervezéskor biztonság (géphiba, természeti csapás stb. elleni védelem), a titkosság (illetéktelen hozzáférések megaka­dályozása v.ö. 6.pont), továbbá a pontosság (lehetőleg ne kerüljön az adatbázisba hibás adat) követelményeire. Mivel az adatbázisokat többnyire egyidejűleg is többen használják, gondoskodni kell a változtató tranzakciók alatt az adatok lezárásáról, az ebből adódó patthelyzetek felismeréséről, a sikeres tranzakciók véglegesí­téséről, a sikertelenek visszagörgetéséről. Végezetül nem hagyhatók figyelmen kívül a válaszidő és a költsé­gek kérdése sem. Az adatbáziskezelő rendszerek építenek az operációs rendszerek data management rutinjaira, így rendszerint a fizikai input/output lebo­nyolítását az operációs rendszerre bízzák. Az adatbázis kezelő rendszereket illetően ezidő szerint három mo­dell (approach) ismeretes: a hierarchikus, a hálós, és a relációs.   A hierarchikus modell  A legrégebbi modell, ma már nem használatos. A csoport jellegze­tes képviselője az IBM által készített IMS. Lényege, hogy az adatokat fákban tároljuk, ahol a fák egy-egy szögpontja  a szegmens (segment) adatokat és a további szegmensekre utaló mutatókat tartalmaz. A fák gyö­kérelemei hagyományos állományokba vannak szervezve. Az egyes néze­tek a számukra érzékeny szegmenseket (sensitive segment) látják. A modell a hálós struktúrájú feladatok leírására csak korlátozottan alkalmas, ilyen esetekben a lekérdezés hatékonysága erősen függ az adat­bázis struktúrájával.A hálós modell A hierarchikus modell ki nem elégítő volta miatt hamarosan szük­ségessé vált az új modell kidolgozása. Sok individuális próbálkozás után a CODASYL bizottság által létrehozott DBTG (Data Base Task Group) jelentései (1969-1971) hozták létre azt a terminológiai és metodológiai közös alapot, amin a hierarchikus rendszereket fejleszteni lehetett. Mint­egy két évtizedig ez a jelentés volt a nagy adatbáziskezelő rendszerek ter­vezésének alfája és omegája. A DBTG jelentés terminológiai javaslataiból már használtunk néhá­nyat: ilyen pl. a séma, az alséma,  DDL, DML stb. A legfontosabb meto­dológiai újítás a set fogalmának bevezetése volt. A set egy rekordokból álló kétszintű fa, melynek gyökéreleme a tulajdonos (owner), levelei a tagok (members). Természetesen egy-egy rekord lehet az egyik set-ben tulajdonos, egy másikban tag, s ugyanígy lehetséges, hogy egy rekord több set-nek is tagja legyen. A set-ek segítségével a legbonyolultabb hálós kapcsolatok is leírhatók. (Esetleg kapcsolórekordok bevezetésével.) A másik fontos új fogalom a terület (area), mely együtt kezelendő rekordok egy halmazát jelenti. A hálós adatbáziskezelő rendszerek egyik fontos reprezentánsa a Magyarországon is elterjedt IDMS (Integrated Data Management System), melyben a fentieken kívül rendelkezni lehet a set-ek tagjainak rendezésé­ről, a rekordok valamilyen hashing algoritmus szerinti elhelyezéséről, indextáblák készítéséről stb. is. E tulajdonságok a hálós adatbáziskezelő rendszereknek nem kötelező, de gyakori tartozékai. DML-ként a DBTG jelentés a COBOL nyelv host language-ként való használatát javasolta (akkoriban szinte kizárólag kötegelt (batch) feldolgozást használtak, s az elterjedt magasszintű nyelvek közül csak a COBOL volt alkalmas adatok manipulálására). A COBOL-t sok helyen hamar felváltotta a PLI, majd az interaktív feldolgozás térnyerésével a más, ezt kihasználó felhasználói felületek is.  A relációs modell A relációs modell ötlete Codd 1970-es cikkéből származik, így lé­nyegében egyidős a DBTG jelentéssel. Mégis csaknem húsz évet kellet várni arra, hogy ez a modell átvegye a vezető szerepet. Az ok: a számító­gépek kapacitásának és sebességének kellet növekednie ahhoz, hogy a relációs modellt hatékonyan implementálni lehessen. Mindenesetre napja­inkban szinte kizárólag e modell alapján készülnek adatbáziskezelő rend­szerek. A reláció ebben az értelemben tulajdonképpen egy táblázat (table) a gyakorlati szakirodalom így is említi. A táblázat oszlopai a tulajdonságok (domains), a sorai az n-esek (tuples). A hagyományos terminológiának megfelelően azonban gyakran nevezik azonban a sorokat rekordnak, az egyes oszlopokhoz tartozó értékeket mezőnek (field). A táblázattal kapcsolatos alapvető feltételezések, hogy abban ne legyenek teljesen megegyező tartalmú sorok vagy oszlopok, továbbá a sorok és az oszlopok sorrendje ne hordozzon információt. Azt a mezőt, vagy mezőkészletet, mely a sort (a sor többi elemét) egyértelműen megha­tározza, kulcsnak nevezzük.  Karbantartási anomáliák és információvesztések elkerülése végett a relációkat célszerű normalizálni. A normalizálás legfontosabb lépései az alábbi normál formákon át vezetnek.  a.) 1NF A relációt elsőrendben normalizáltnak nevezzük, ha annak mezője elemi értéket (nem relációt) tartalmaz. b.)  2NF A relációt másodrendben normalizáltnak nevezzük, ha elsőrendben normalizált, és amennyiben valamelyik mezőjének azonosításához egy összetett kulcs szükséges, nincs olyan mező, melynek azonosításához elegendő ennek egy része. c.) 3NF A relációt harmadrendben normalizáltnak nevezzük, ha másodrendben normalizált, és a nem kulcs jellemzői nem függenek egy­mástól. d.) BCNF A relációt BOYCE-CODD értelemben normalizáltnak nevezzük, ha a fentieken kívül teljesül az is, hogy egyetlen nem kulcs jellemző sem határozza meg egy összetett kulcs valamelyik összetevőjét (nincs kulcstö­rés). Bizonyítható, hogy minden reláció felbontható ilyen, normalizált relációkra, ezt  a műveletet nevezzük dekompozíciónak.  A relációk legfontosabb tulajdonsága, hogy azok exakt matematikai esz­közökkel kezelhetőek. Ilyen eszközrendszer a relációs algebra és a relá­ciós kalkulus. A relációs algebra A.) A relációs algebra alapműveletei:1.) Unió: RkS Az R és az S reláció unióján azt a relációt értjük, melyben szerepel­nek mindazon sorok, melyek akár az R, akár az S relációban szerepelnek. Az R és az S reláció (és természetesen az eredmény reláció) sorhossza meg kell egyezzék. 2.) Különbség: R-S Az R és az S reláció különbségén azt a relációt értjük, melyben csak azok a sorok szerepelnek, melyek benne vannak az R, de nincsenek benne az S relációban. 3.) Direkt szorzat: RkS A r sorhosszúságú R és a s sorhosszúságú S reláció direkt szorzatán azt a relációt értjük, melynek r+s hosszúságú soraiban minden R-beli sort minden S-beli sor előtt előfordul. 4.) Projekció: k (R) Az R reláció i1,i2,...ik osylopaira való projekción azt a relációt értjük, mely az R relációból úgy keletkezik, hogy elhagyjuk a felsoroltakon kívüli oszlopokat. 5.) Szelekció: k (R) Az R relációnak az F feltétel melletti szelekcióján azt a relációt ért­jük, mely az R relációból úgy származtatható, hogy abból csak az F felté­telnek eleget tévő sorokat hagyjuk meg.Az F feltétel az [i]k [j] (a sor i-edik és j-edik eleme között fennáll k ) és az [i] kc (a sor i-edik eleme és a c konstans között fennáll k) elemi kifejezések logikai műveletekkel (k, k,k) való összekötéséből állhat. K tetszőleges összehasonlító operátort (k, k, kk, kk, k,k) jelenthet. B.) A következmény műveletek: A soronkövetkező műveletek voltaképp nélkülözhetőek, de a gya­korlatban jól lehet őket használni. 1.) Metszet: RkS  RkS = R - (R - S) 2.) Hányados: RkS Az R és az S reláció hányadosán azt a relációt értjük, melyre igaz, hogy (Rk S)k S összes sora R-beli sor. (Feltesszük, hogy r > s, és s k 0.) A hányados valóban következmény művelet. Legyen ugyanis T = k (R), továbbá  V = k1 ((TkS)-R). Ekkor belátható, hogy RkS = T - V. 3.) Feltételes kapcsolat (k join): R * S=k (RkS) [i]k[j] [i]k[r+j] 4.) Természetes kapcsolat (natural join):  R * S Hasonló a feltételes kapcsolathoz de itt a szelekció feltétele az, hogy az azonos nevű oszlopokban azonos érték szerepeljen. Természetesen a szelekció után projekcióra is szükség lesz, az azonos tartalmú oszlopok egyikét meg kell szüntetni. C.) Példa a relációs algebra alkalmazására Tekintsük az alábbi adatbázist: legyen három relációnk. a.) Autók: jele A Mezői: rendszám, gyártmány, típus, szín, ...... b.) Emberek: jele E Mezői: szemszám, név, foglalkozás, cím, ..... c.) Kapcsolat: jele K Mezői: forgrsz, szemszám. Feladat: keressük ki a sárga opelek tulajdonosainak foglalkozását. A megoldás: R1 =kl (A) R2 =k (R1) R3 = R1 * K   rendszám=forgrsz R4 = k (R3) R5 = R3 * E R6 = kás (R5) Természetesen mindezt egy formulába is foglalhatjuk: kf(k (k (k  (A))*K)*E). rendszám=forgrsz  A relációs kalkulus A másik relációk kezelésére használatos matematikai módszer a re­lációs kalkulus. Az alábbi formájú kifejezéseket vizsgáljuk: {t | k(t)}. Ennek jelentése: azokat a t sorokat tekintjük, melyek kielégítik a k (t) formulát. A formula következő atomokból épülhet fel: a.) R(s) azt jelenti, hogy az s sor része az R relációnak, b.) u[i] k v[j] azt jelenti, hogy az u sor i-edik és a v sor j-edik eleme között fennáll a k viszony, c.) u[i] k c azt jelenti, hogy az u sor i-edik eleme és a c konstans között fennáll a k viszony. Az atomok önmagukban is formulák, de azokat a logikai műveletek jeleivel (k, k,k) összeköthetjük, ezenkívül a k (van olyan, hogy) és a k (minden olyan) és a zárójelek is használhatóak. A relációs kalkulus eszközeivel minden felírható, amit a relációs algebrával kifejezhetünk. Ez egyszerűen belátható az alapműveleteknek megfelelő kifejezések felírásával.1.) Egyesítés {t | R(t) k S(t)} 2.) Különbség {t | R(t) k kS(t)} 3.) Direkt szorzat {t|(kkku)(k v)(R(u) kS(v)k t[1]=u[1]k......k t[r]=u[r]k t[r+1]=v[1]...k t[r+s]=v[s]} 4.) Projekció{t(k) | (ku)(R(u) kt[1]=u[i1] k...k t[k]=u[ik]} 5.)Szelekció {t | R(t) kF} Ugyanakkor készíthetünk olyan kifejezéseket is, melyek a relációs algebrában nem fejezhetők ki. Pl.  {t | kR(t)}. Könnyen látható, hogy ennek a kifejezésnek nem sok értelme van. Az effajta kifejezések kizárá­sával létrehozhatjuk az u.n. biztos kifejezések körét.  Ehhez szükség van a DOM függvény bevezetésére. Egy k formulához rendelt DOM(k) azok­nak az elemeknek a készletét jelenti, melyek a k formulában közvetlen, vagy közvetett módon említésre kerülnek. Ahhoz, hogy egy kifejezés biztos legyen, az alábbi feltételeknek kell eleget tennie. 1.) Ha egy t sor kielégíti a k formulát, miden komponense tagja DOM(k)-nek. 2.) kminden  (ku)(k (u)) formájú részkifejezésére ahol u kielégíti k(u)-t, u minden komponense tagja DOM(k)-nak. A biztos kifejezések készletéről már belát­ható, hogy equivalens a relációs algebra kifejezéskészletével. Lekérdezés relációs rendszerekben Az első lekérdező rendszerek pusztán a relációs algebra vagy kalku­lus számítógépes megvalósítását tűzték ki célul. (Ilyen például az IBM által kifejlesztett ISBL.) Ez azonban nem elégíthette ki a felhasználói felü­letekkel kapcsolatos egyre magasabb igényeket. Viszonylag korai nyelv az ugyancsak IBM termék QBE (Query by Example), mely táblavázak (skeleton) részbeni kitöltése után a táblázat fennmaradó részének kitölté­sével ad választ a felhasználó kérdéseire. Ez a technika a legújabb rend­szerekben is megtalálható. A QBE változó vektorok alkalmazásával tette lehetővé az egyes relációk összekapcsolását. A.) Az SQL Manapság szabványnak tekinthető az SQL (Structured Query Language), melyet szinte minden korszerű adat-báziskezelő rendszer "ért".Az SQL - némiképp eltérően a hagyományos szokásoktól - négy nyelvet, ill. résznyelvet tartalmaz. a.) A DDL Ezen lehet táblákat, nézettáblákat (view) és indexeket létrehozni (CREATE), táblákat módosítani (ALTER), valamint táblákat, nézettáblá­kat  és indexeket megszüntetni (DROP).   b.) A DCL (Data Control Language) E nyelv feladata kettős, egyrészt ide tartozik a jogosítványok kiosz­tása és visszavonása (GRANT, REVOKE), másrészt e nyelven lehet a tranzakciókat véglegesíteni, ill. visszagörgetni (COMMIT, ROLLBACK). c.) A DML E résznyelv tartalmazza a rekordok beszúrásához (INSERT), mó­dosításához (UPDATE) és törléséhez (DELETE) szükséges utasításokat. d.) A QUERY  Ez a résznyelv egyetlen utasításból áll (SELECT), mely azonban a legösszetettebb kérdések megfogalmazására is alkalmas. B.) A negyedik generációs nyelvek (4GL) A modern adat-báziskezelő rendszerek még az SQL-beli "programozást" is meg akarják takarítani a felhasználónak. Különféle paraméterezhető form, report, menu stb. generátorok teszik ezt lehetővé.  Osztott adatbázisok kezelése A nagy hálózatok és az ezek következtében sok távoli lekérdezés a 80-as évekre erősen megnövelte  a kommunikációs költségek részarányát az adatbázis-kezelés költségein belül. Ez a tény sugallta az ötletet: próbál­juk meg az adatokat a felhasználás közelében elhelyezni. Az eredmény: egy fizikailag megosztott, de logikailag egységes adatbázis. Az osztott jelleg a felhasználó számára nem látható (transzparens), ugyanakkor több jellegzetes előnnyel és hátránnyal jár. Az előnyök: 1.) A kommunikációs költségek már említett csökkenése. 2.) Mindenki a számára ismerős adatokat gondozza. 3.) Egy-egy csomópont kiesése esetén a többi adatai továbbra is elérhe­tőek. 4.) Lehetséges a moduláris tervezés, a rugalmas konfigurálás. 4.) Hosszabb idő alatt a rendszer gépei akár ki is cserélhetők.A hátrányok:1.) A rendszer bonyolultabb és sebezhetőbb lesz, 2.) Nem könnyű minden csomópontra egyformán jó személyzetet találni, másrészt, ha találunk fenyeget a szuboptimalizáció veszélye. 3.) Mindig valamennyi gépnek működnie kell. 4.) Többféle hardvert és szoftvert kell a rendszernek kezelnie és "összehoznia". 5.) Bonyolult a jogosultságok ellenőrzése (a jogosultságokat leíró tábláza­tokat hol tároljuk: egy csomópontban, vagy mindenütt?). Külön problémát jelent, ha feladjuk a redundancia-mentesség elvét. Erre okot szolgáltathat az is, ha nem eldönthető egy-egy adatról, hogy hol használják legtöbbet, de biztonsági okokból is dönthetünk egy-egy adat többszörözése mellett. Ilyen estekben biztosítanunk kell, hogy az egyes példányok tartalma azonos legyen, azaz a rendszer konzisztens maradjon. Az első osztott rendszerek megvalósításához nagy segítséget nyújtott az u.n. backend gépek felhasználása. Az adatok elhelyezése tervezéskor az adatbázis felügyelő feladata (Mivel az osztott rendszereknél megkell különböztetnünk központi és csomóponti adatbázis felügyeletet, pontosabban a központi adatbázis felü­gyeleté). A már működő rendszerek automatikusan is képesek a felhaszná­lás gyakoriságát figyelve a kópiák számán és elhelyezkedésén változtatni. Az adatbázis felügyelő számára több elemzési módszer áll rendelke­zésre döntései meghozatalakor. a.) A forrás-nyelő elemzés Elsősorban a felhasználás gyakoriságát kell vizsgálnunk.Nem mind­egy azonban, hogy a felhasználó csomópont nyelő (azaz csak olvassa az adatot, s így a felhasználáskor elég a legközelebbi példányt megtalálnia), vagy forrás (mely az adatot létrehozza, vagy módosítja).  b.) Az ABC elemzés Az adatok kategóriákba sorolhatók "nélkülözhetetlenség" szerint. Ezekhez a kategóriákhoz különböző minimális kópiaszámot rendelhetünk. c.) Az érzékenység elemzés A különböző csomópontok költség/teljesítmény aránya más és más lehet. Nyilvánvaló, hogy a teljesítményt "kevésbé érzékeny" csomópon­toknál növelni, az "érzékenyebbeknél" csökkenteni kell. Említettük már a konzisztencia megőrzésének fontosságát. Ez a szinkronizációs protokollok feladata. E protokollok vagy biztosítják az erős konzisztenciát (vagyis azt, hogy egy-egy adat kópiái egyszerre vál­tozzanak meg), vagy a gyenge konzisztencia (amikor az adatbázis hos­szabb-rövidebb ideig inkonzisztens marad) mellett gondoskodnak arról, hogy ez ne okozhasson problémát. A konzisztencia mérőszáma a kohe­rencia, mely erős konzisztenciánál azonosan 1 értékű, gyenge konzisz­tenciánál pedig 1-hez tart. Következtetésképp a koherencia konvergenciája a konzisztencia feltétele.   A szinkronizációs protokollokat két részre oszthatjuk. A központosí­tott protokollokban az egyik (nem feltétlenül mindig ugyanaz) csomópont szerepe kitüntetett, az osztott protokolloknál ilyen nincs. A.) Központosított protokollok a.) A központi zárellenőrzés Egy állandó központ végzi el a változtatásokhoz szükséges lezáráso­kat. Működése hasonlít az osztatlan adatbázisoknál megszokotthoz. A központ sérülésére érzékeny, csak statikus adatbázisoknál használható, erősen konzisztens módszer. b.) A zseton módszer Egy, a csomópontok között körbejáró "zseton" jelöli ki az alkalmi központot, mely a változtatásokhoz szükséges lezárásokat elvégezheti. Igen kedvelt, erősen konzisztens módszer. c.) Az elsődleges példány módszer Egy adat kópiáit egy szekvenciába szervezzük, s a változtatások csak ennek mentében történhetnek. Mivel a tranzakciók nem előzhetik meg egymást, nem okoz gondot, hogy a módszer gyengén konzisztens. Előnye, hogy az ideiglenesen működésképtelen csomópontok újra mun­kába állítása egyszerű B.) Osztott protokollok Az időbélyeg módszer E módszernél a tranzakciók elindításuk időpontjából és a csomópont azonosítójából egy időbélyeget kapnak, mely meghatározza végrehajtásuk sorrendjét. A távolságból adódó félreértéseket rendszeres dummy üzenetek küldésével kerülik el. A módszer gyengén konzisztens. Szakértői rendszerek Az információkezelés legfiatalabb ága az u.n. szakértői rendszerek készítése. Felépítésük ill. elkészítésük alapvető sémája a következő. A felhasználó egy felhasználói felülettel (user interface) áll kapcso­latban, mely program a felhasználó és a rendszer közötti dialógust vezérli. A felhasználói felület a következtető rendszerhez (inference engine) kapcsolódik. Ez a rendszer "lelke" mely a tudásbázis és esetleg egyéb adatbázisok felhasználásával a válaszokat kidolgozza. Az okoskodás, következtetés (reasoning) lehet adat- vagy célvezérelt. A tudásbázis szabályok és állítások gyűjteménye, melyet a tudás­mérnök (knowledge engineer) tölt fel egy területi szakértő (domain expert) tudásának számítógépben tárolható alakra "fordításával" (a szakér­tői rendszerek - ezidő szerint legalábbis - csak egy-egy elég szűk tudo­mányterületet ölelnek fel). Fontos, hogy az eredeti és a számítógépes tudás közötti fordítási szakadék (semantic gap) a lehető legkisebb legyen. Számos szakértői rendszerek készítésére alkalmas keretrendszer (shell) áll a felhasználók rendelkezésére, melyben a felhasználói felület, a következtető rendszer és a tudásbázis struktúrája adott. Egyes rendszerek­nél azonban ezek a komponensek is többé-kevésbé változtathatók. A fej­lesztés, változtatás a rendszermérnök (system engineer) feladata. A szakértői rendszereknek nem csak biztos állításokat kell kezelniök, mind a rendszerbeli tudás, mind a felhasználó válaszai tartal­mazhatnak bizonytalanságot. Ezt a -100 és 100 közé eső bizonyossági tényezővel (CF = certainty factor) írhatjuk le. Az egyszerű állításokon és összefüggéseken kívül e rendszerek spe­ciális adatelemeket, összetett és hierarchiákban megjelenő vázakat (frame) és aktív u.n. démonokat is tartalmazhatnak.  Alapvető elvárás a szakértői rendszerekkel kapcsolatban, hogy kö­vetkeztetéseiket megmagyarázzák, s a modern rendszerek tanulni is képe­sek. Az adatok bizalmas kezelése  A modern ipar, kereskedelem, államigazgatás, stb. (azaz a társada­lom) zavartalan működéséhez azt jól kiszolgáló informatikai rendszereket igényel. Alapvető fontosságú ezen rendszerek védelme a behatolás szabo­tázs, stb. ellen. Az USA-ban már a 80-as években kimutatták, hogy egy-egy számítógépes bűncselekmény nagyságrendekkel nagyobb kárt okoz, mint egy átlagos bankrablás. A védelemnek alapvetően három formája van: a.) a.) fizikai védelem mely az adatokhoz való illetéktelen hozzáférést fizikailag próbálja megakadályozni (Zárt, őrzött számítóközpont, stb.. A modern rendszerek­ben az adatok ilyenfajta védelme a műholdas adatátvitel elterjedése óta alig lehetséges, hisz az ilyen vonalak vételének megakadályozása fizikai­lag lehetetlen.), b.) az ügyviteli védelem mely a követendő biztonságtechnikai szabályokat, kötelező viselke­dési módokat, továbbá a kötelező dokumentálás rendjét írja elő (elsősorban a felelősségkérdését szabályozza), c.) az algoritmikus védelem olyan algoritmusok összessége, mely a fentieket hatékonyan előse­gítő, kiszolgáló algoritmusokat tartalmaz. (Mi csak ezzel foglalkozunk.) Az algoritmikus védelem is tovább osztható: a rejtjelezés és az üze­nethitelesítés lehetővé teszi az adatok védetlen közegen való továbbítását, a felhasználó azonosítás a rendszert használó személyek egyértelmű azo­nosítására szolgál (ugyanez a feladata számítógépek kapcsolata esetén a partner azonosításnak), a hozzáférés védelem megakadályozza az egyéb­ként jogos felhasználót abban, hogy hatáskörét túllépje, végül a digitális kézjegy az elküldött üzenetek letagadását akadályozza meg. A rejtjelezés Régóta ismeretes, hogy a védhetetlen közegen átjuttatandó x üzene­tet valamilyen  y = E(x)  transzformációval torzítani érdemes, természetesen úgy, hogy az üzenet címzettje képes legyen az inverz  x = D(y)  transzformációra. A transzformációktól elvárjuk, hogy (legalábbis az üzenet "érvényességi idején" belül) kívülálló számára megfejthetetlenek legye­nek, a címzett ugyanakkor gyorsan és könnyen megértse azokat. Mivel nem könnyű nagyszámú megfelelő E-D párt előállítani, nem egy, hanem kétváltozós transzformációkat célszerű alkalmazni, ahol a másik változó az esetenként cserélhető kulcs. Így a transzformációk akár nyilvánosak lehetnek, csak a kulcsok titkos kezelését kell megoldani. Ha az E transzformációnál alkalmazandó Kr rejtőkulcsból ennek D transzfor­mációnál alkalmazandó Kf fejtőkulcs párja könnyen meghatározható, konvencionális kódolásról beszélhetünk, ellenkező esetben a kódolás nyilvános (rejtő) kulcsú. A.) A konvencionális kódolás                                                                A legelső konvencionális kódolási eljárás Julius Caesar nevéhez fűződik: üzenteiben a latin abc minden betűje helyett a rákövetkező harmadikat használta. Főleg katonai körökben alkalmazták a következő eljárásokat. a.) Helyettesítés A nyílt szöveg minden betűjét megadott rend szerin egy másikkal helyettesíthetjük. (Pl. az abc-hez egy abc permutációt rendelünk.) A nyelvi sajátosságok (betűk gyakorisága) alapján megfejthető. b.) Periodikus helyettesítés Az előzőhöz hasonló de több helyettesítési szabályt használunk periodikusan cserélve (pl. több abc permutációt). Ez is megfejthető: azo­nos betűkombinációkból lehet a periódus hosszára következtetni, s ezután az egyszerű helyettesítésnél leírtakhoz hasonlóan okoskodni. c.) Kulcsfolyamos rejtés A helyettesítést aperiodikussá tesszük. A helyettesítést egy szöveg vezérli, az abc hosszának megfelelő számú különböző abc permutációból álló mátrixban a rejtendő szöveg betűjének megfelelő oszlopban és a kulcsszöveg soron következő betűjének megfelelő sorban álló betű lesz a rejtett szöveg következő betűje. A agyméretű mátrix tárolását elkerülendő, választhatjuk az i-edik sort az abc i lépéses eltolásának. A betűk reprezentálhatóak az abc-n belüli sorszámaikkal. Ekkor a kódolás (és a dekódolás) leegyszerűsödik a kódo­landó (dekódolandó) és a kulcsszöveg megfelelő betűinek (mod abc hossz) való összeadására. Sajnos ez a kódolás is feltörhető (egy betűsorozatból két szöveg bontható ki!). A  ulcsfolyamos rejtéshez hasonló kódolási eljárás a számítástech­nikában is alkalmazható: ha a a kódolandó és a kulcsfolyam mod 2 össze­adása a kódolás, ugyanez lehet a dekódolás módja is. A kulcsfolyamot valamilyen véletlenszám generátor állíthatja elő, ekkor kódolási kulcsként csak ennek elindítási módját kell a partnereknek egyeztetniök. Sajnos az előbbiekben vázolt módszer nagyon érzékeny a szinkronitásra (egy bit kiesése az egész üzenetet értelmetlenné teszi). Ezért az üzeneteket többnyire blokkokba rendezik, s így küldik el. A rejtjelötvözés azt jelenti, hogy több egyszerű transzformáció egy­más utáni alkalmazásával élünk. 1949-ben Shannon javasolta a keverő transzformációk bevezetését, mely váltakozva helyettesítések (s-réteg) és permutációk (p-réteg) egymásutánjából áll. A Shannon féle elvek továbbfejlesztése alapján készítette az IBM a 60- as évek második felében a LUCIFER berendezést (128 bites blokkok, 128 bites kulcs, 6-7 emberév fejlesztési munka). Ezt követte az egyetlen LSI áramkörrel elkészíthető DES (Data Encryption Standard, 64 bites blokk, 56 bites kulcs).  Ez utóbbi 1977 óta USA szabvány. A DES-t számos támadás érte, de az idő a fejlesztőket igazolta. (Diffie, Hellman egy elméleti gépet is szerkesztett a DES-sel kódolt üzenetek feltörésére. A gép fél nap alatt feltörte volna az üzeneteket, de teljesítmény-felvétele 2 Mw lett volna, így gondolatkisérlet maradt.) B.) A nyilvános (rejtő)  kulcsú kódolás E módszerek alapja valamilyen nehezen invertálható u.n. egyirányú (trap-door) függvény. Az MIT eljárásnál ahhoz, hogy a rejtőkulcsból a fejtőkulcs meghatá­rozható legyen, egy többszáz jegyű számot kell prímtényezőkre bontania. Míg egy szám prímtényezőiből való előállítása (összeszorzása) egyszerű és gyorsan megvalósítható munka (néhány száz jegyű számokkal 1ksec alatt lehet műveleteket végezni, ugyanakkor a ma ismert leghatékonyabb eljárással egy 200 jegyű szám prímtényezőkre bontásához 3.8*109 évre van szükség.) Egy másik ismert megoldás, a Merkle-Hellman módszer az u.n. le­fedési feladaton alapszik. A kulcsgondozás  Nyilvánvaló, hogy ha a kulcsok megfelelő védelme nem biztosított, az egész kódolási rendszer értelmetlen. A kulcsok gondozása három fela­datbál áll. A.) Kulcsgenerálás Az a művelet, melynek eredményeképpen a kulcsok előállnak. Egy valódi véletlenszám generátor segítségével végrehajtható. B.) Kulcskiosztás a.) Alapkulcsok A kulcsok kiosztása történhet egy alapkulcs készleten keresztül, melyet rendszeren kívüli eszközökkel juttatnak el a résztvevőkhöz. Az alapkulcsokat, melyek gyakran nyilvános kulcsú rendszerhez tartoznak, csak a kulcsok cseréjéhez használják. b.) Merkle "rejtvény" módszere A hívó fél n db (Ki, Ii) párt küld partnerének gyengén kódolva. Ez egyet kiválaszt, feltöri, és Ii-t visszaküldi. Ezzel a kommunikáció kulcsa meghatározott. A behatolónak átlagosan a párok felét kell ahhoz feltörnie, hogy megtudja, Ii-hez melyik Ki tartozik. c.) A "hatványozós" módszer A módszer alapja, hogy az i és a j felhasználó kitalál egy-egy xi ill. xj számot. Egymásközt kicserélik az Yi = kxi (mod p),  ill. az  Yj = kxj (mod p) számokat (p prímszám, k a p elemű véges test egy primitív eleme), a kommunikáció kulcsa a  K = kj szám (vagy annak valamilyen függvénye) lehet. Ennek előállítása Yj és xi vagy Yi és xj ismeretében egy egyszerű hatványozást igényel, a behatoló­nak viszont a diszkrét logaritmusképzés a feladata. C.) Kulcstárolás Nehézségeket okozhat, ha a kulcsokat akár túl kevés, akár túl sok ember ismeri. (Az első esetben esetleg szükség esetén nem  áll rendelke­zésre a kulcs, a második esetben nagy a kiszivárgás veszélye.) Megoldást jelentenek az u.n. (n,k) küszöbrendszerek. E rendszerek lényege, hogy a kulcsot n db. (nem feltétlenül diszjunkt) részre osztva, bármelyik k kulcsrészletből a kulcs előállítható, de nincs olyan k-1 kulcs­részlet, amiből ez megtehető lenne. Ilyen küszöbrendszerek készítésére több matematikai módszer is rendelkezésünkre áll. Felhasználó és partner azonosítás, hozzáférés védelem A.) A felhasználó azonosítás a.) A jelszóvédelem Talán a legrégebbi felhasználó azonosítási mód a jelszavak haszná­lata. A módszer használhatóságát azonban csökkenti, hogy a túl hosszú és értelmetlen jelszavakat nehéz megjegyezni, ugyanakkor a rövid és értel­mes szavak gyakran egyszerű próbálkozással kitalálhatóak. Ezért a jelsza­vakat célszerű gyakran változtatni. Ez többféle alapon történhet a legbizto­sabb valami előre rögzített algoritmust használni. A jelszavakat a számító­gépes rendszer nem közvetlenül, hanem valamilyen egyirányú transzfor­máció alkalmazása után tárolja, így a tároló táblázatból sem lehet azokat megállapítani b.) fizikai azonosító használata A felhasználók azonosítására gyakran használnak valamilyen fizikai eszközt. A legelterjedtebbek a különféle azonosító kártyák. Ezek nehezen hamisíthatók, de könnyen el lehet őket lopni. Jelentősen fokozhatja a biztonságot a fizikai azonosító eszköz és a jelszó együttes használata. c.) személyi jellemzők Nem lophatók el, és nem hamisíthatók a különféle személyi jellem­zők (ujj- vagy tenyérlenyomat, recehártya erezet, stb.). E jellemzők számí­tógépes tárolása és kiértékelése még nem teljesen megoldott, a biztató eredmények azonban azt sugallják, hogy a jövő útja erre keresendő. B.) A hozzáférés védelem Nem elegendő kiszűrni a jogosulatlan behatolókat, a rendszernek azt is számon kell tartania, hogy a jogos felhasználók hatásköre mire terjed ki. A felhasználó által működtetett ügynök folyamatok hatáskörét a hozzáfé­rési mátrix szabja meg. Ennek elemeit akár ügynökökhöz, akár adatokhoz kötötten tárolhatjuk. C.) A partnerazonosítás A számítógép-számítógép kapcsolatokban is szükség lehet azonosí­tásra. E célra fenntarthat minden számítógép pár egy-egy kulcsot, ez azonban egy n elemű hálózatnál n2 kulcsot jelent. Folyhatnak az informá­ciócserék valamilyen hitelesítő központon keresztül, ez azonban a kom­munikáció költségét növeli jelentősen. Megoldást jelenthet, ha minden csomópont egy, csak a hitelesítő központ által ismert kulccsal tud e köz­ponthoz bejelentkezni, s üzenet továbbítási igényét bejelenteni. A köz­ponti jelöli ki a kommunikáció kulcsát, melyet a fenti kulccsal kódolva a hívónak visszaküld. Ugyancsak küld emellett egy csomagot, mely a hí­vandó fél kulcsával kódolva tartalmazza a kommunikáció kulcsát, s a hívó megjelölését. Ha a hívó e csomagot a hívott félhez továbbítja a párbeszéd kettejük között folytatódhat, s az azonosítás is kielégítő biztonsággal tör­tént meg. Üzenethitelesítés, digitális kézjegy Az üzenetek hitelesítéséhez két feltétele van, egyrészt ellenőrizni kell, hogy egy-egy blokkban az és csak az érkezett-e a címzetthez amit a feladó feladott, másrészt tudnunk kell azt is, hogy az egyes blokkok abban a sorrendben érkeztek e meg amilyenben feladták őket (ideértve azt is, hogy nem hiányzik-e közülük). Az első célhoz ellenőrző összegeket, a másodikhoz sorszámot célszerű a blokkban elhelyezni még a kódolás előtt. A digitális kézjegy arra szolgál, hogy segítségével a címzett megbi­zonyosodhassék egy üzenet feladójáról és bizonyíthassa, hogy  az illetőtől kapott ilyen üzenetet. Olyasmire van szükség tehát mint az aláírás, ami könnyen azonosítható, de nehezen hamisítható. A cél elérhető úgy is, hogy a kényes kommunikációt egy hitelesítő központ közbeiktatásával végezzük (mintha tanú előtt beszélnénk) ez az u.n. nem valódi digitális kézjegy. Elegánsabb megoldás a valódi digitális kézjegy. Ehhez egy nyilvá­nos kulcsú kódolási rendszer lehet felhasználni, mégpedig olyant, mely "megfordítható", azaz E(D(x)) = x (az általunk említett módszerek ilye­nek). Használjuk a kódolási módszert fordítva, azaz úgy, hogy a titkos fejtő kulccsal rejtünk (és nyilván a nyílt rejtő kulccsal fejtünk). Ekkor a címzett, ha a nyílt kulccsal fejthető üzenetet kap, biztos lehet abban, hogy azt csak a titkos kulcsot ismerő feladó küldhette. Ugyanakkor - mivel a címzett nem ismeri a titkos kulcsot - ha rendelkezik az üzenetnek a nyílt kulccsal megfejthető kódolt változatával, nyilvánvaló, hogy azt ő nem készíthette, azaz az üzenet a feladótól származik.

0 megjegyzés:

Megjegyzés küldése