KÜLÖNÖSEN NAGY ADATTÖMEGEK KEZELÉSÉNEK EGYES KÉRDÉSEIRİL DOKTORI ÉRTEKEZÉS TÉZISEI

EÖTVÖS LORÁND TUDOMÁNYEGYETEM INFORMATIKAI KAR INFORMATIKA DOKTORI ISKOLA INFORMÁCIÓS RENDSZEREK DOKTORI PROGRAM

KÜLÖNÖSEN NAGY ADATTÖMEGEK KEZELÉSÉNEK EGYES KÉRDÉSEIRİL DOKTORI ÉRTEKEZÉS TÉZISEI Készítette:

BUZA ANTAL okleveles matematikus A DOKTORI ISKOLA VEZETİJE: DR. DEMETROVICS JÁNOS AKADÉMIKUS A DOKTORI PROGRAM VEZETİJE: DR. BENCZÚR ANDRÁS A MATEMATIKAI TUDOMÁNYOK DOKTORA

TÉMAVEZETİ: DR. BENCZÚR ANDRÁS A MATEMATIKAI TUDOMÁNYOK DOKTORA INFORMÁCIÓS RENDSZEREK TANSZÉK VEZETİJE

Budapest, 2006.

12

1

[15] Buza A, Buza K.: „Graph-based Clustering Using Evolutionary Techniques” (kiadásra benyújtva)

[16] Buza A., Buza K.: „The Bounds of Distributed Data-intensive Computing Systems”, Pollack Periodica, Pécs. (kiadás alatt)

2

11

[6] A. Buza: “"Helping" software tools - our defenselessness”, SISY 2003, 1st SerbianHungarian Joint Symposium on the Intelligent Systems, 2003, Subotica, Serbia & Montenegro, 87-92.

Bevezetı A mőszaki fejlıdés létrehozta azokat az adatgyőjtı, adattovábbító eszközöket, ame-

[7] A. Buza: “The bounds of useful-information discover”, IS-2003: 5th International

lyek alkalmazása lehetıvé teszi azt, hogy viszonylag rövid idı alatt rendkívül nagy

Conference on Interactive Systems: The problem of human-computer interaction,

adattömegek keletkezzenek és jelenjenek meg egy-egy feldolgozó helyen. Nagy adat-

Ulyanovsk, Russia, 2003, 24-28.

tömegeket állítanak elı az adatrögzítı készülékek, az automatikus adatgyőjtı rendszerek (szenzorok), de ilyennek tekinthetık például a levelezı rendszerek által egy-egy

[8] A. Buza: “The abilities and some possible extensions of the Continuous Query Lan-

címzetthez közvetített levéltömegek is. A nagy tömegő adat tárolása is gondot jelenthet,

guage”, ICAI’04 6 International Conference on Applied Informatics, 2004, Eger,

a feldolgozás még inkább, különösen, ha a feldolgozáskor idıkorlátokat is figyelembe

Hungary, Vol.II. 39-46.

kell vennünk. Idıkritikus például egy vihar, vagy más természeti katasztrófa közeledté-

th

nek, egy éppen történı bőncselekménynek, vagy egy kialakulóban lévı forgalmi dugó[9] A. Buza: “How the database update must affect the responses being produced by the active continuous queries”, IEEE 2th International Conference on Computational Cybernetics, 2004, Wien, Austria, 401-404.

nak a felismerése, és még sok, egymástól eltérı alkalmazási terület számos más feladata. Az adatgyőjtı és adattovábbító eszközök teljesítménye szakadatlanul nı, áruk csökken, így alkalmazásuk egyre általánosabbá válik, mindez igen erıteljes igényt indukál a

[10] A. Buza: “Parallel processing of continuous data streams”, IEEE 9th International

győjtött óriási adattömegek hatékony, és az alkalmazási területek idıkorlátait is figye-

Conference on Intelligent Engineering Systems, 2005, Piraeus, Greece, CD-ROM,

lembe vevı adatrögzítési és feldolgozó módszerek, és ezeket alkalmazó rendszerek

3p.

megalkotására. Az igény már erıteljesen jelentkezik, az alkalmazható módszerek, eljárások keresése a jelen és a közeli jövı feladata.

[11] Buza A.: „Az információtechnológia harmadik korszaka”, ME-DFK közlemények

A nagy adattömegek kezelésének feladata máskor is megjelenik. A keletkezés módjától függetlenül a számítógép-hálózat segítségével összekapcsolt számítógépeken (pél-

XIX, 1998, Dunaújváros, 23-41.

dául az Interneten) hozzáférhetı roppant nagy (és dinamikusan növekvı) adathalmaz [12] Buza A.: “The different effects of the database update during the long execution of

hasznos feldolgozásának az igénye már megfogalmazódott, az igény kielégítésének

continuous queries”, Conference of PhD Students in Computer Science, 2004,

módszerei és eszközei eléggé szegényesek, tág teret adnak az újabb elgondolások kidol-

Szeged, 33.

gozására. A keletkezett nagy adathalmaz korábban még fel nem ismert értékes összefüggése-

[13] Buza A.: „Adatfolyamok párhuzamos feldolgozása”, Informatika a Felsıoktatásban Konferencia, 2005, Debrecen, CD-ROM, 6p.

ket, „tudást” is tartalmazhat, ennek kinyerését általánosan az adatbányászat feladatának tekintik. Az adatbányászat messze nem lezárt. A dolgozatban bemutatok egy új adatbányászati eljárást és annak implementációját is.

[14] Buza A., Buza K.: „Egy új klaszterezı algoritmus”, Neumann János Számítógéptudományi Társaság Konferenciája, 2006, Gyır. CD-ROM 10p.

10

3

elosztott feldolgozás, mind az adatfolyam feldolgozás elosztott modellje, és hatékony

A dolgozat célkitőzései A dolgozat célkitőzése a mai és a közeli jövıbeni nagy adattömegeket produkáló

eljárásai tovább fejleszthetık, de ugyanígy a klaszterezési algoritmus c és h függvé-

rendszerek áttekintése, az adattömegek kezelésének már látható problémái összefoglalá-

nyei jó megválasztásának módszerei, valamint a nagy adathalmazok használatának kér-

sa, és fıként a problémák kezelésére vonatkozó néhány lehetséges megoldás, módszer

dései, illetve az adatfolyam feldolgozó nyelvek is további kutatások tárgyát képezhetik.

kidolgozása és elemzése.

Az alkalmazott módszerek A dolgozatban más-más típusú problémákkal foglalkoztam. Ezek vizsgálatakor az adott témakör feldolgozásánál megszokott módszereket alkalmaztam. Az adatigényes elosztott feldolgozás vizsgálatakor a helyzet és a lehetıségek felmérését követıen a válaszidıt leginkább befolyásoló fıbb paraméterek vizsgálatával foglalkoztam, majd az optimálishoz közeli megoldások kereséséhez numerikus kísérleteket

Az értekezésben feldolgozott témakörökhöz kapcsolódó publikációk listája

végeztem. A CQL nyelvi bıvítés szükségességének indoklását követıen a szintaktikus és szemantikus definíciók megadása után az így bıvített nyelv kifejezı erejének és kiértékelhetıségének megváltozását vizsgáltam, különös figyelemmel a megvalósítás és a hasz-

[1] A. Buza: “Extension of CQL over dynamic databases”, Journal of Universal Computer Science, September, 2006. (Megjelenés alatt.)

nálhatóság gyakorlati szempontjaira, azaz a korlátos memóriában való kiértékelhetıség és a mőködési idı megváltozásának várható mértékére. Az új klaszterezı algoritmus megalkotásakor és elemzésekor bonyolultságát elméleti úton vizsgáltam, megvalósíthatóságáról és hatékonyságáról tényleges implementá-

[2] A. Benczúr, A. Buza: “Modeling of response time of distributed data intensive computing systems”, 4th MATHMOD, 4th IMCAS Symposium on Mathematical Modeling, 2003, Wien, Austria, 1331-1338.

ciójával és számos kísérlettel gyızıdtem meg. [3] A. Buza, P.B.Kis: “The third Period of Information technology”, FUSST’99 The Sixth Fenno-Ugric Symposium on Software Technology, 1999, Tallinn, Estonia,

1. tézis Megállapíthatók az adatigényes elosztott feldolgozás jellemzı paraméterei és ezek összefüggései. A feltárt összefüggések felhasználásával, valamint a gyakorlatban elıforduló további paraméterek figyelembevételével, elméleti számításokkal és modellezés segítségével megállapíthatók a legjobb feladat-megoldási idı, a legolcsóbb feladatmeg-

269-275. [4] A. Buza: “The limits of data-set queries”, 2001, Magyarország, ICAI’01 5th International Conference on Applied Informatics, 2001, Eger, Hungary , 23-29.

oldás és más célfüggvényekkel jellemezhetı feladat felbontási és szétosztási paraméterek és módszerek. Alkalmazásukkal optimális, vagy ahhoz közeli feladat-szétosztást ér-

[5] A. Benczúr, A. Buza: “The effect of non-execution and part task result integration in distributed data-intensive computing systems”, SPLST'2003, Symposium on Pro-

hetünk el. Az algoritmusok párhuzamosíthatóságának és a párhuzamos mőködésnek a kérdése-

gramming Language and Software Tools, 2003, Kuopio, Finland, 2-13.

it már régóta alaposan tanulmányozzák, számos eredmény és ezeket összefoglaló mővek

4

9

nési formája az adatfolyamokban való megjelenés, ennek feldolgozásával a 2. fejezet-

születtek. Ezekben a meggondolásokban általában nem foglalkoznak az adatmennyiség

ben foglalkoztam; egyrészt a CQL egy – megítélésem szerint – hasznos bıvítésével,

kérdésével. Ugyanakkor számos gyakorlati alkalmazásban nemcsak az algoritmus pro-

másrészt az adatfolyam-feldolgozás elosztott modelljével. Nagy adathalmazokban eddig

cesszorigénye lehet nagy, hanem a felhasznált adattömeg is. Olyannyira, hogy a fel-

fel nem ismert értékes összefüggések keresése az adatbányászat feladata, a 3. fejezetben

használt adattömeg esetleg el sem fér az egy gépen rendelkezésre álló adathordo-

egy új adatbányászati algoritmust mutatok be. A nagy adattömegek kezelésének prob-

zó(ko)n, tehát mindenképpen szétosztott tárolást kell alkalmazni. Nemcsak az adattö-

lémái minıségileg különböznek az adatkezeléssel kapcsolatos korábbi számítógépi fel-

meg nagysága miatt, hanem más meggondolások, okok miatt is egyre inkább megjelen-

adatoktól, ezeket az új feladatokat foglalom össze a 4. fejezetben.

nek olyan alkalmazási rendszerek, amelyek adatai is elosztottan (szétszórtan) kerülnek tárolásra. A dolgozat 1. fejezetében az adatigényes elosztott feldolgozással foglalkoztam, az eredmény a fenti tézisben foglalható össze. A témával foglalkozó publikációim:

Az eredmények hasznosítása

[2], [5], [16].

Az 1. fejezet eredményei az adatigényes elosztott feldolgozási rendszerek tervezésében és az elosztási algoritmusok tervezésében hasznosíthatók. Az eredmények és a modellezés segítségével megkereshetı az optimálishoz közeli feladatszétosztási stratégia, és a felhasználandó gépek (rendszerek) száma. A CQL R-A-O bıvítésével a CQL nyelv gyakorlati használhatósági köre bıvül, alkalmassá válik olyan típusú kérdések feltevésére is, melyek a hétköznapi használat során gyakran felmerülnek, de az eredeti CQL megválaszolásukra nem (vagy csak részben) volt képes. (2.1 fejezet).

2. tézis A CQL nyelv a 2.1.9. pontban bevezetett R-A-O kiterjesztéssel alkalmassá tehetı olyan kérdések megválaszolására, amelyekben a felhasznált adatbázisokban a kérdés hosszú mőködése alatt bekövetkezett tartalmi módosulások a felhasználó által kívánt (különbözı) hatásokkal vehetık figyelembe. Ez az R-A-O kiterjesztés a CQL kifejezı erejét növeli, a korlátos memóriában való kiértékelhetıségét és a válasz pontosságát nem befolyásolja; a válasz késleltetési idejét

Az adatfolyam feldolgozás elosztott sémájának tanulmányozása hasznosítható adat-

a triggerek használatához hasonlóan, vagy annál kevésbé növeli.

folyamok idıkritikus feldolgozási rendszerei tervezésekor. (Például meteorológiai, for-

Abból a célból, hogy az adatfolyamokra vonatkozóan kérdéseket adhassunk meg, a

galomszabályozási, folyamatszabályozási, bőnüldözési és más alkalmazásokban.) (2.2

Stanford Egyetem kutatócsoportja javasolja a CQL (Continuous Query Language) nyel-

fejezet)

vet. Ez a nyelv az adatbázisokra vonatkozó kérdések megadási lehetıségét biztosító

A 3. fejezetben bemutatott klaszterezési algoritmus hasznossága abban áll, hogy

SQL-hez igen hasonló, annak kiterjesztésének is tekinthetı. Elıfordulnak azonban

olyan klaszterezési feladatok megoldását is lehetıvé teszi, mely feladatokat a korábbi

olyan gyakorlati helyzetek, amikor egy kérdés megválaszolásához egyszerre szükség

klaszterezı eljárásokkal nem, vagy kevésbé jól lehetett megoldani. (Bár természetesen

van adatbázisokban tárolt információkra és az adatfolyamokból érkezı információkra is.

ez sem teljes körő megoldás; „mindenre” jó, univerzális klaszterezési algoritmus az álta-

A CQL kérdés hosszú mőködési idejő, ezalatt az adatbázisok tartalma is változhat. Kü-

lános vélekedés szerint nem létezik.)

lönbözı alkalmazási területeken az adatbázis tartalmi változásának a CQL válaszra másmás módon (visszamenılegesen, a módosítás pillanatától érvényesülıen, vagy más módon) kell hatnia. A dolgozat 2. fejezetének elsı felében példákkal illusztrálom a külön-

További kutatási területek

bözı elvárt hatásokat és a CQL olyan kiterjesztésére teszek javaslatot, amely alkalmassá A dolgozatban feldolgozott öt fı témának a további kutatási lehetıségeit a megfelelı fejezetekben tárgyaltam. Mindegyik téma nyitott, tovább kutatható, a most fel nem

teszi a CQL-t az adatbázis tartalmi változásainak a felhasználó által kívánt hatással való feldolgozására. A CQL javasolt bıvítését elemezve megállapítható, hogy a CQL

dolgozott, vagy leegyszerősített paraméterek hatása vizsgálható. Mind az adatintenzív

8

5

R-A-O kiterjesztése a CQL kérdések kiértékelhetıségét nem befolyásolja, a késleltetési

képpen befolyásolható, s így számos feladattípusra alkalmazható. A témával foglalkozó

idejét elfogadható mértékben növeli. A témával foglalkozó publikációim: [1], [8], [9],

publikációim: [14], [15].

[12].

5. tézis 3. tézis

Megadható a számítógépes adatkezelés korszakokra bontása és a korszakok jellem-

Az adatfolyam-feldolgozásban megjelennek a nagy feldolgozási kapacitást igénylı idıkritikus alkalmazások. A kívánt feldolgozási kapacitás egy számítógépen nem, vagy

zése. Rendszerezhetık a 3. korszak, a különösen nagy adatmennyiségek kezelésének feladatai.

csak nagyon drágán biztosítható, sokkal inkább alkalmasnak látszik sok számítógép

Az adatok kezelése igen általános, az informatikai rendszerekben tipikus kísérı fel-

együttes használata. Ennek megvalósítására megkonstruálható az adatfolyam-

adat. Emiatt az adatkezeléssel régóta foglalkoznak, aminek eredményeként egyre komp-

feldolgozás elosztott modellje. A modell vizsgálatával megállapíthatók felhasználási

lexebb adatkezelési elgondolások és megoldások születtek. Az adatkezelési feladatok és

lehetıségei és korlátai.

megoldások fejlıdése korszakokba sorolható. Az elsı korszak a programozás kora,

A szenzor hálózatokkal, az adatfolyam feldolgozással kapcsolatos közlemények az

amely a minél hatékonyabb programozási nyelvek és algoritmusok kidolgozására kon-

adatfolyam feldolgozó algoritmus bonyolultságával nem foglalkoznak, márpedig az

centrált. A második korszak az adatbázisok kora, amely (leginkább a szoftverkrízis ha-

adatfolyam-feldolgozó algoritmus lehet olyan bonyolult és/vagy változatos, hogy annak

tására) az adatkezelés célszerő megoldását kereste. Az elsı és második korszak eredmé-

megvalósítására nem ésszerő célhardvert, vagy firmware-t készíteni, másrészt erıforrás-

nyei és a jelentısen megnövekedett technikai lehetıségek oda vezettek, hogy mára elı-

igénye lehet olyan nagy, amely egy számítógépen nem, vagy gazdaságosan nem, elégít-

állt az a helyzet, amelyet úgy is jellemezhetünk, hogy: „elárasztanak az adatok”. Egy

hetı ki. Ilyenkor a feladatnak jobban megfelel több számítógép használata. A dolgozat

alkalmazás, egy alkalmazó számára is hozzáférhetıvé vált óriási és állandóan növekvı

2. fejezete második részében megadom az adatfolyam-feldolgozás elosztott modelljét és

adatmennyiség az eddigi módszerekkel már feldolgozhatatlan. Egyre erıteljesebben

annak vizsgálatát. A témával foglalkozó publikációim: [10], [13].

fogalmazódnak meg minıségileg más feladatok megoldásának igényei. A dolgozat 4.

4. tézis

problémák áttekintését adom meg. A témával foglalkozó publikációim: [3], [4], [6], [7],

fejezetében az adatkezelés 3. korszaka jellemzését és az új típusú igények, feladatok,

Megadható olyan új klaszterezı algoritmus, amely kategorikus attribútumokkal is bíró adathalmazokat esetenként a korábbi klaszterezı algoritmusoknál jobban klaszterez. Az új algoritmus az adathalmazból gráfot épít, majd ebben elvágó él-, illetve

[11].

Összegzés

ponthalmazokat keres. A feladat általánosságban NP-nehéz, ezért közelítı algoritmu-

A dolgozatban egymástól bizonyos mértékig független kutatási témákat és az ezek-

sokkal is megelégedünk. A közelítı algoritmus a feladatát evolúciós technikával oldja

ben született eredményeket foglaltam össze. E témák azonban egy fı problémacsoport

meg. Megtörtént az algoritmus implementációja is. Mőködtetésének tapasztalatai ked-

köré rendezhetık, nevezetesen mindannyian a nagy adattömegek kezelésének feladatai-

vezıek.

hoz tartoznak. A hardver-szoftver technikai lehetıségek óriási adattömegek elérhetısé-

A dolgozat 3. fejezetében a tézisben összefoglalt új klaszterezı algoritmust adok meg. Az algoritmus részletes bemutatása és elemzése után a megvalósításáról és annak

gét biztosítják, az ebben rejlı lehetıségek kihasználására egyre erıteljesebben fogalmazódik meg az igény.

kedvezı tapasztalatairól is összefoglalót adok. Az algoritmus nem „egyetlen” fix mőkö-

A nagy adattömeg feldolgozása nagy processzorigényt is jelenthet, az adatigényes

déső, hanem két – paraméterként is tekinthetı – függvényének változtatásával sokféle-

elosztott feldolgozásokkal az 1. fejezet foglalkozik. Nagy adattömegek egyik megjele-

6

7