Informatika | Tanulmányok, esszék » Az információ feldolgozás alapvető módszerei

Figyelem! Akiknek ezt elküldtem, azoknak szól, hogy ez csak egy vázlat, feltételezi a Kotsis által írt, Az információfeldolgozás alapja című doksi ismeretét, az anyag megértésére pedig nem elég. Ez csak egy vázlat az egész anyag rendszerezésére és gyors átnézésére, mivel ez a diák alapján nem volt lehetséges. Az információ feldolgozás alapvető módszerei: • Folyamatszemléletű • Adatbázis-szemléletű • Szakértői rendszerek, tudásbázisok • Döntéstámogató rendszerek Folyamatszemléletű: Célorientált: cél meghatározása célhoz vezető folyamat folyamathoz szükséges adatállomány Előny: - Kis tárkapacitás kell ← csak a hasznos adatok - Gyors feldolgozás ← feladathoz optimális adatszerkezet Hátrány: - Minden célhoz új folyamatok és állományok redundancia, rossz tárkihasználás, inkonziszetncia - Csak az eredeti kérdésre ad választ, újabbra nem Optimális szerkezet: Lehetséges szempontok az optimális

szerkezet kialakításakor: - tárlóhely foglalás (pl. tömörített) - feldolgozási idő · létrehozás · keresés · változtatás - felhasználási szempontok (pl. könnyű kezelés) Keresések: Általában kiemelt szerepe van a keresésnek, sokat használjuk, erre kell optimalizálni. Keresés időigényét befolyásolja: struktúra, algoritmus (lépésszám * lépés időigénye), betöltési idő, összehasonlítási idő, stb. Keresések fizikaiban szekvenciálisban: - Lineáris: · sorban megvizsgáljuk mindegyik rekordo · átlagosan a rekordok felét vizsgáljuk, lépésszám N/2 · ha nincs az állományban a rekord, akkor mindet megvizsgáljuk - Bináris, logaritmikus: · minden lépésben hosszra felezzük az állományt · Lépésszám: log2N · Előnye: gyors ← nem valódi osztás - Peterson-féle: · minden lépésben az előfordulás valószínűségére felezzük az állományt · Lépésszám ½ log2N · Hátrány: lassú ← valódi osztás kell, egyenletes

kulcseloszlás kell Keresések csaknem fizikai szekvenciálisban: - Kupacos: a rekordokat kupacokra osztjuk, ezek első elemeit hasonlítjuk össze először, majd a megfelelő kupacban keresünk Állománystruktúrák: Szekvenciális: Logikailag minden rekordnak egy megelőzője és egy rákövetkezője van - Fizikai szekvenciális: rekordok logikai és fizikai sorrendje megegyezik · Előny: keresés lépésszáma kicsi · Hátrány: bonyolult beszúrás, rendszeres fizikai rendezés - Logikai szekvenciális: rekordok logikai és fizikai sorrendje nem egyezik meg · Mutatók adják a sorrendet (egy-, kétirányú, gyűrűs) · Előny: nem kell a rekordokat mozgatni, több mutatórendszer alkalmazható egy állományra · Hátrány: fizikainál hatékony keresések kiesnek (bináris, Peterson), mozgófejes tárolásnál sok pozícionálás - Csaknem fizikai szekvenciális: · létrehozáskor fizikai szekvenciálisan helyezzük el (mágneslemez) · feldolgozáskor logikai

szekvenciális (pl. beszúrás a végére – túlcsordulási terület) - Gyakoriság szerint rendezett: · a sorrendet a keresés gyakorisága határozza meg · főleg logika szekv-ben, de lehet fizikaiban is · a logikai szekv. önrendező algoritmust használ Hierarchikus: egy megelőző, több rákövetkező - Belső mutatós módszerek: · left-list: visszavezetés szekvenciálisra ê fa adott módon való bejárására szabály ê adatvesztéssel jár · több mutató: rekordba annyi mutató, ahány gyermeke van ê hátrány: tág határok között változó számú gyerekek vagy változó hosszú rekordok, vagy rossz tárkihasználás · segédrekordok / kapcsolórekordok: csak a kapcsolatokat tárolják ê elérhető: minden rekordban csak két mutató legyen (következő adatra, következő tárolóra) · gyűrűs: fába függőleges és vízszintes gyűrűk ê szintén egy-egy rekordba csak két mutató - Külső mutatós módszerek: · táblázatok: táblázatban

rekordokhoz bejegyzések adják a következőt / előzőt ê probléma: itt is a változó mennyiségű gyerek · bináris mátrixok: ábrázolja, hogy van-e kapcsolat a rekordok között ê hierarchikus állományoknál elég a mátrix felét tárolni (értsd: felfele mindig csak egy szülő van, csak lefele van több gyerek) Hálós: több megelőző, több rákövetkező – megpróbáljuk a hierarchikusra visszavezetni - Belső mutatós módszerek: · Nem jó: left-list, segédrekord, gyűrű ê Visszavezetés hierarchikusra: elemek többszöri tárolása helyett virtuális elemek használata (nem tartalmaznak adatot, csak mutatót az adat helyére) · Több mutatós eljárás: alkalmazható itt is, de nem használhatjuk ki a szintek létezését, mert itt nincsenek - Külső mutatós: · Táblázatok: ugyanúgy · Bináris mátrixok: ugyanúgy, de nem elég a fél mátrix tárolása Nem konszekutív = asszociatív struktúrák: nem rákövetkezés, hanem más logika szerint

Indexelt szervezés: - Sűrű indexelés: minden rekordhoz tartozik egy index (kulcs – cím) · Egy állományhoz több index · Előny: Könnyű új rekordot hozzáfűzni, gyors keresés · Hátrány: nagy indexállomány, amit karban kell tartani · Indexállomány szerkezete: ê Bináris fa: elméletben jó ¯ ha kiegyensúlyozott, akkor gyors a keresés ¯ kiegyensúlyozottság fenntartása időigényes ê B+ fa (Bayer fa): gyakorlatban ezt használják (pl. Oracle) ¯ az adatokra mutató pointerek mind a leveleken vannak ¯ gyors keresés, lognN lépés ¯ Könnyű karbantartás - Ritka indexelés: nem minden rekordhoz, csak jelzőpontokhoz tartozik bejegyzés · rendezés szükséges · ált. többszintű indexek, egymásba építhetőek · előny: gyors keresés, könnyű beszúrás · hátrány: csak egy szempont alapján szervezhető (a rendezés elve a nem indexelteknél) - Index-szekvenciális szervezés: · Ritka indexelés egyik formája, mágneslemezre tervezték ·

Index szintek: ê Fő index ê Cilinder index ê Sáv index · Lemez felosztása: ê Index terület ê Adatterület ê Túlcsordulási terület · adatok fizikai szekvenciálisan + indexek hozzájuk + új adatok logikai szekvenciálisan (mutatókkal) a túlcsordulásira · időnként újra kell rendezni és a logikaiból fizikait csinálni Direkt szervezés: a rekordok kulcsai és címei között egy leképezés hozza létre a kapcsolatot. - Leképezések: cél, hogy legyen egy-egy értelmű · Közvetlen leképezés: pl. kulcs = személyi szám sok üres hely ê eleget tesz a fentinek ê nagyon rossz tárkihasználás – használhatatlan · Hashing: engedünk a fenti igényből, lehet leképezés azonos helyre, de kevés ê Különböző kulcshoz ugyanaz a cím szinonim ê Jobb tárkihasználás ê Módszerek pl: csonkítás, maradék módszer - Szinonimok kezelése: · Külső láncolás: ê külön területen tároljuk a szinonimokat ê mutatólánc köti össze őket ê

Hátrány: rossz tárkihasználás a külön terülte miatt, az első elemet nem lehet törölni · Belső láncolás: ê Szinonimok az elsődleges terület még nem használt részeire, helyükhöz közel ê Itt is mutatók kötik össze őket ê Előny: jó tárkihasználás ê Hátrány: lehet, hogy a szinonim később használandó helyre kerül oda való adatból műszinonim lesz · Nyílt (Peterson) módszer: ê Mint a belső láncolás, de nem használunk mutatókat, elemek mindig egymás után lesznek ê Hátrány: keresés több lépést igényel · Többszörös hashing: ê Ha egy hashing algoritmus szinonimot képez, akkor másikkal próbálkozunk ê Általában 2 algoritmus,, a maradék szinonimokat az eddigi módszerekkel kezelik · Bucket (vödör, bugyor): ê Rekord csoportok kapnak címeket ê Előny: kevesebb szinonimkezelsé ê Hátrány: a bucketben is kell keresni ê Hardver szempontok indokolhatják · Szinonimkezelések összehasonlítása: ê Figyelembe kell

venni a hardvert, lépésszámot, algoritmusidőt ê RAM: ¯ TH: nagy algoritmusidő ¯ NyM: több lépés mint BL-nél. ¯ BL: másodlagos szinonimok miatt több lépés, mint KL-nél ¯ KL: leggyorsabb, de rossz tárkihasználás ê Mozgófejes. ¯ TH, KL: sok fejmozgás ¯ NyM: több lépés mint BL-nél ¯ NyM-hez nem kell CPU, így a leggyorsabb lehet Adatbázis szemléletű: Rendelkezésre álló adatok összes adat és kapcsolatuk integrált adatbázis kérdésekhez ezt használjuk. View: Felhasználó szükségei, jogai adatbázis egy részét látja. Adatreprezentáció: nézetek konceptuális modell (magas) implementációs modell (reprezentációs) fizikai modell Egyed-kapcsolat (ER) modell: egyed (entity) + tulajdonság (attribute) + egy tulajdonság a kulcs + kapcsolatok Adatbázis felügyelő feladatai: - jogok kiosztása - adatbázis tervezése sémák, alsémák - adatbázis karbantartása - kapcsolattartás a felhasználókkal DDL: adatleíró nyelv,

adatbázis felügyelő eszköze DML: adatmanipuláló nyelv, felhasználók eszköze DML nyelvek csoportjai: - Alkalmazott nyelv szerint: · Host: már megírt nyelvbe építik be az adatb. Kezelést · Self contained: önálló adatb. Kezelő rendszer - Felhasználás jellege szerint: · Procedurális: egy lépésben egy rekordon dolgozik · Deklaratív: egy lépésben egy meghatározott tulajdonságú halmazt dolgoz fel (pl. SQL) Adatfüggetlenség: - Fizikai: fizikai modell változás ne kényszerítse az implementációs modell változását - Logikai: logika struktúrában változtatás ne érintse a felhasználókat Tervezései szempontok: - Titkosság (hozzáférés) - Biztonság (géphiba) - Pontosság (ne legyen hibás adat) - Válaszidő - Kényelem - Költségek - Konkurens használat (adatok lezárása) - Patthelyzetek felismerése, kezelése - Tranzakciók visszagörgetése Alapvető ABKR modellek: Hierarchikus: Adatokat fákban tároljuk. Egy-egy szögpont a szegmens,

ebben adatok és mutatók további szegmensekre. Nézetek a számukra érzékeny szegmenseket látják. Tulajdonságai: - Igazi ABKR: több felhasználós, ugyanazt látják - Nem igazi ABKR: lekérdezés hatékonysága függ az adatstruktúrától Hálós: CODASYL bizottság által létrehozott DBTG jelentése alapján. Fogalmak: - DDL, DML - Séma, alséma - Set: kétszintű fa, tulajdonos + tagok, egy rekord egyik setben tulaj, másikban tag, leírhatóak velül a legbonyolultabb hálós kapcsolatok - Area: rekordok halmaza Lekérdezésre a COBOL nyelvet javasolták hots-nak, felváltotta a PL1. Relációs: Napjainkban ezt használják. Reláció = táblázat: oszlopai a tulajdonságok, sorai az n-esek (rekordok), oszlophoz tartozó értékek a mezők. Feltételezések a táblázatról: - Nincsenek benne azonos tartalmú sorok vagy oszlopok - Oszlopok és sorok sorrendje nem hordoz infót - Szuperkulcs: egyértelműen meghatározza a sort - Kulcs: tovább nem szűkíthető

szuperkulcs Anomáliák: - Módosítási: azonos adatok több helyen szerepelnek, többet kell módosítani - Beírási: hiányos adatok miatt nem, lehet bevinni - Törlési: sor törlésével később szükséges infó is elvész Anomáliák kiküszöbölése: normálforma - 1NF: reláció mezői elemi értékek - 2NF: 1NF és egyik mezőérték meghatározásához összetett kulcs kell, akkor másikhoz is ez kell - 3NF: 2NF és nem kulcs jellemzői függetlenek egymástól - BCNF: 3NF és egyetlen nem kulcs sem része egy összetett kulcsnak (nincs kulcstörés) - 4NF: csak akkor áll fenn A1A2AN B1B2BN, ha A1A2AN szuperkulcs Relációs algebra: Relációs kalkulus: SQL: - DDL: · nézettáblák és indexek létrehozása · módosítása · megsznütetése - DCL: · Jogosítványok kiosztása · Tranzakciók kezelése (véglegesítés, visszagörgetés) - DML: · Rekord beszúrása · Módosítása · törlése - Querry: · lekérdezés · Select utasítás - 4GL generátorok:

programozás megspórolása, paraméterezett form/report/menu generátorok Továbbfejlesztett modellek: EER (Extended Entity Relational): - Subclass – superclass: közös tulajdonságok leírása - Superclass tulajdonságai öröklődnek - Felosztás lehet diszjunkt vagy átfedő (egymást átfedi, vagy nem) - Felosztás lehet teljes vagy részleges (lefedi az összes lehetőséget vagy nem) - Specializáció: egy csoportra jellemző tulajdonságok keresése - Generalizáció: közös tulajdonságok keresése - Kategória: olyan subclass, melynek több superclassa van Nested Relational Model: - Nem 1NF - Rekordok egymásba építhetőek Structural Data Model: - Relációs modell továbbfejlesztése - Két típus: · Relations · Connections /lehetne részletezni/ Objektum-orientált adatbázisok: - OOP alapján jön létre - Objektumosztájok perzisztensek - Objektumosztájok osztottak - Objektumoknak saját azonosítója van - Lehetnek bonyolult objektumok is - Egységbezárás,

öröklés, polimorfizmus - OQL: · SQL-re hasonlít · Lényeg az objektum, reláció másodlagos - SQL3: · Lényeg a reláció, az objektum másodlagos - Új lehetőségek: · Felhasználói adattípusok, eljárások · Nagy objektumok kezelése · Konstruktorok · Táblák közötti öröklés /lehetne bővíteni + O2 kifejtés kellhetne/ Deduktív adatbázisok - Logikai programozással dolgozik - Tényeket és szabályokat ír le Adatbázis kezelő architektúrák: Három fő rész: - Data Processing (fizikai adatkezelés) - Business Logic (adatvédelem) - User Interface Architektúrák: - Kliens-szerver · Szerver: AB, DP, BL · Kliens: BL, UI - Többrétegű · Szerver: AB , DP · Középső réteg: BL · Kliens: UI Osztott adatbázisok: - Cél: adatok elhelyezése a felhasználás közelében, a kommunikációs költségek csökkentésére - Eredmény: fizikaliga megosztott, logikailag egységes adtbázis - Előnyök: · Kommunikációs költségek csökkenése · Mindenki

a neki ismerős adatokat gondozza · Egy csomópont kiesésénél a többi adatai elérhetőek maradnak · Moduláris tervezés, rugalmas konfigurálás · Rendszer gépei ki is cserélhetőek - Hátrányok: · Bonyolultabb, sebezhetőbb rendszer · Minden csomópontra jó személyzet kell ↔ szuboptimalizáció veszélye · Mindig valamennyi gépnek működnie kell · Többféle hardvert és szoftvert kell a rendszernek kezelnie · Bonyolult a jogosultságok ellenőrzése. - Konzisztencia: probléma, ha feladjuk a redundancia-mentességet és több helyen tároljuk az adatokat (biztonsági okból vagy mert több helyen használják), biztosítani kell a konziszetnciát - Elemzések: · Forrás-nyelő elemzés: használat gyakorisága, módja (olvas vagy ír többet) · ABC elemzés: adatok fontosság szerinti besorolás, ezekhez másolat darabszám rendelése · Érzékenység elemzés: csomópontok terhelése költség / teljesítmény arány alapján - Konzisztencia: /itt kellene,

hogy Kotsis szerint mi a koherencia és konzisztencia, de ő úgysem mondja meg soha/ · Erős: a koherencia 1, adatok egyszerre változnak meg · Gyenge: a koherencia 1-hez tart, adatbázis rövidebb ideig inkonzisztens · Koherencia: konzisztencia mérőszáma, rendszer összefüggősége · Konzisztencia: több azonos adat egyidejű hitelessége (azonossága) - Szinkronizációs protokollok: · Központosított: ê Központi zárellenőrzés: központ végzi a változtatásokat, lezárásokat ê Zseton módszer: csomópontok között körbejáró zseton dönt ê Elsődleges példány módszer: adat kópiái szekvenciában, sorban végigmegy rajtuk a változás · Osztott: ê Időbélyeg: minden tranzakció végrehajtása az indítás időpontjának sorrendjében Adatvédelem: - Fizikai: illetéktelen hozzáférés fizikai akadályozása - Ügyviteli: biztonságtechnikai szabályok, kötelező viselkedések, dokumentálás - Algoritmikus: fentieket hatékonyan segíti ·

felhasználó / partner azonosítás: használók egyértelmű azonosítása · hozzáférés védelem: jogos felhasználó ne lépje túl a jogkörét · rejtjelezés: védtelen közegen való továbbítás · üzenethitelesítés: védtelen közegen való továbbítás · digitális kézjegy: elküldött üzenetek letagadásának akadályozása Rejtjelezés: - Konvencionális kódolás: · Helyettesítés: minden betűt másikkal helyettesítünk szabály szerint · Periodikus helyettesítés: mint előző, de több szabályt periodikusan cserélgetve · Kulcsfolyamatos rejtés: abc permutáció táblázatban kulcs és szöveg karakterei az oszlop és sorindexek (mint IBA-n), érzékeny a szinkronhibára · Rejtjelötvözés vagy keverő transzformációk: több egyszerű módszer egymás után - Nyilvános kulcsú: egyirányú, nehezen invertálható függvényen alapszik · MIT módszer (prímfelbontás). · Merkle-Hellmann módszer (hátizsák probléma) /hát ez meg mi a

lószar?/ Kulcsgondozás: kulcsok védelme nélkül értelmetlen a kódolás - Kulcsgenerálás: véletlenszám generátorral - Kulcskiosztás: · Alapkulcsok: kulcskészlet, rendszeren kívül juttatják el a résztvevőkhöz · Merkle „rejtvény” módszere: hívó Ki, Ii párokat küld, gyengén kódolva, a másik egyet kiválaszt, feltöri, Ii-t visszaküldi ezzel a kommunikáció kulcsa meghatározott · A "hatványozós" módszer: /itt van egy sor ronda képlet/ - Kulcstárolás: ne ismerje a kulcsot se túl kevés, se túl sok ember · Kulcsokat felosztják n részre, de a kulcs k db részletből előállítható /mint IBA-n/ Felhasználó azonosítás: - jelszóvédelem - fizikai azonosító használata: pl. kártya - személyi jellemzők: pl. ujjlenyomat Partner azonosítás: Azonosítás a gép-gép kapcsolatban - Mindegyiknél egy-egy kulcs a másikhoz – n elemű hálózatnál n2 kulcs - Hitelesítő központon keresztüli kommunikáció: magas komm.

Költség - Központnál vannak a hitelesítő kulcsokat, a gépek ide bejelentkeznek komm. előtt, központ kiosztja nekik a továbbiakban használandó kulcsokat Digitális kézjegy / üzenethitelesítés: - Üzenethitelesítés: · az érkezett-e a címzetthez, amit a feladó küldött ellenőrző összeg · abban a sorrendben érkezett-e, nem hiányzik-e valami sorszám - Digitális kézjegy: · Megbizonyosodás a feladóról · Bizonyítja, hogy tényleg tőle kapta · Lehetőségek: ê Nem valódi digitális kézjegy: központon keresztül ê Valódi digitális kézjegy: nyilvános kulcsú kódolással /mint IBA-n/ Hagyományos igények: OLTP (On Line Transaction Processing): /hát ez itt sem érthető, meg a wikipedián sem/ - az ábrázolt mini világ minden adatát tartalmazza - az utolsó állapotot mutatja - sok adatmódosítás - egy-egy tranzakció kevés adatot érint - viszonylag egyszerű, de ad hoc kérdésekre is tud válaszolni - a válaszidő kicsi - jellemző

több, párhuzamosan működő felhasználó Új igények: - Adatfolyamok feldolgozása: pl. érzékelők, banki forgalom folyamatos, de nem tároljuk az összes adatot, viszont feldogozzuk - Előre elkészített adatok a vezetőknek: döntéstámogató rendszer (Decision Support System) - Nem ismert összefüggések kiderítése: tudásfeltárás (Data Mining, adatbányászat) OLAP (On Line Analitical Processing): - Gyirs válasz analitikus lekérdezésekre (?) - nem feltétlenül egészen up-to-date - csak az elemzéshez szükséges adatokat tartalmazza, ezek azonban több mini világból származnak - tartalmazza a régi adatokat (trendek) - jellemzően olvas, de bonyolult elemzéseket végez - a válaszidő nem kritikus - látványos riportok, ezek könnyen elérhetőek ROLAP (Relational On Line Analitical Processing): A jól ismert és bevált relációs eszközöket használja, ezek azonban nem erre a célra készültek. MOLAP (Multidimensional On Line Analitical

Processing): - Az adatokat egy többdimenziós kockában tárolja - Könnyű megvizsgálni egy kiválasztott élnek a többitől való függését - lassan kiépíthető, hardware igényes rendszer - gyorsan ad választ a várt kérdésekre Adattárházak: - Témaorientált, integrált, időben változó, nem átmeneti adatrendszer - Elsődleges célja a stratégiai döntések támogatása - Régebbi adatokat is tartalmaz (historikus adatok) Adatpiac: - adattárház egyik fontos komponense - kiválasztott tárgyaknak osztályhoz kötött részhalmaza - alkalmazás-központú adattárház - az adattárház nem más, mint adatpiacok összessé - előnye: · minden osztály maga állapíthatja meg az általa használt adatok struktúráját · egy-egy osztály eldöntheti, a historikus adatokból menynyire van szüksége · minden osztály maga döntheti el, mikor milyen folyamatot futtat · kisebb egységek kezelése olcsóbb - lehetnek az adatpiacok átfedőek, egy adatbázisból több

is kiépíthető Tudásfeltárás: - rejtett, ismeretlen, potenciálisan hasznos tudás kinyerése az adatokból nem triviális módon - Adatbányászat: az adatok összefüggéseinek feltárása - Lépései: · Adatkiválasztás: szükséges adatok · Adattisztítás: kettőződések, hiányok, elírások · Bővítés: újabb szükséges adatok hozzávétele · Szűkítés: kihagyjuk a felesleges, vagy ki nem töltött részeket · Kódolás: ha túl részletes az adat kódok használata, kategóriákba sorolás · Adatbányászat: ê hagyományos lekérdező eszközök: pl. átlagszámítás ê statisztikai technikák: összefüggések keresése ê vizuális technikák: ábrák eloszlások időben összefüggéseket vehetünk észre ê hasonlóság, távolság, szomszédság: rekordokat dimenziós tér pontjainak tekintve, szomszéd viselkedése megjósolhat a viselkedést ê döntési fák ê társító szabályok · jelentéskészítés - Új problémák: nagyon sok adat

válogatás, keresés kell