Modell-lekérdezések hatékony kiértékelése

OData támogatás
Konzulens:
Dr. Bergmann Gábor
Méréstechnika és Információs Rendszerek Tanszék

Napjainkban a szoftverfejlesztés terén egyre nagyobb szerepet kap a modellvezérelt tervezés. Ennek a megközelítésnek nagy előnye, hogy a modellen automatikusan különféle tesztek és ellenőrzések sokaságát hajthatjuk végre automatikusan, még a kész szoftver előállítása előtt. Ezzel a célberendezésbe vagy végfelhasználóhoz kerülő szoftver megbízhatóságát, karbantarthatóságát, továbbfejleszthetőségét növelhetjük. A modellvezérelt fejlesztési folyamatok gyakorlati megvalósítása során gyakran előkerülő probléma, hogy a modellek felett bizonyos feltételeket szeretnénk megfogalmazni, deklaratív megközelítéssel lekérdezéseket futtatnánk a választott modellen. Erre az Eclipse EMF modellező rendszerében megjelenő igényre számos eszköz jött létre, többek között az Eclipse OCL és a Méréstechnika és Információs Rendszerek tanszéken fejlesztett és az ipar által is használt Emf-IncQuery keretrendszer.

A lekérdezéseket megfogalmazhatjuk a gráf felett gráfmintákként is, melyek deklaratívan megfogalmazható lekérdezési szabályokkal specifikálják a lekérdezést. Ezeknek a modellben történő feltérképezése során számításigényes feladat az adott gráfminták illeszkedéseinek megkeresése a modellben. A mintaillesztésre többféle (különböző helyzetekben gyors és hatékony) megközelítés létezhet.

Az egyik lehetséges megközelítés az inkrementális illesztés. Alapötlete abban rejlik, hogy mikor egy mintának az összes illeszkedését kigyűjtötte az eljárás, eltárolja ezeket, hogy a későbbi lekérdezések során rendkívül gyorsan visszaadhassa azt. Ezzel jelentős gyorsulás érhető el ismételt lekérdezéskor, ellenben sok esetben nehézségeket, kihívásokat tartogathat. Egyfelől az illeszkedéshalmazok számosságuknál fogva jelentős memóriaigénnyel jelentkezhetnek. További probléma, hogy a modell módosulása miatt az illeszkedéshalmazokat frissíteni kell. Ehhez egyedi megoldás kell, valamint értesülni kell a modell változásairól. Az Emf-IncQuery keretrendszerben már létezik egy ilyen inkrementális illesztésen alapuló algoritmus, a témakörben népszerű Rete hálókon alapuló eljárás. Ennek sajátossága, hogy az illeszkedéshalmazokon kívül további információkat is eltárol a modell változása esetén bekövetkező frissítés gyorsítására. Ennek azonban következménye a megnövekedett memóriafogyasztás.

Egy másik lehetséges eljárás a tanulmányaim során általam megvizsgált Treat algoritmus. Inkrementális tulajdonságán felül alapötlete az, hogy csak a lekérdezés végeredményét, az illeszkedéshalmazokat tárolja, így kisebb a memóriaigénye, viszont a frissítés művelete lassabb, összetettebb is lehet. Emiatt viszont szükség van egy olyan betétalgoritmusra, mely gyorsan és hatékonyan segít megválaszolni a megváltozott modell felett a frissítés kérdését. Választásunk a korábbi félévek során a Viatra2, majd az EMF modellreprezentációk felett általam megvalósított, tesztelt és mért keresőalgoritmusra esett esett, az előretekintő mintaillesztésre. Az eljárás fő előnye, hogy más mélységi keresőalgoritmusokhoz képest hatékonyabban illeszt többféle helyzetben is: ha nagyobb a minta, csak egyetlen illesztésre van szükség, vagy a mintának egy része már illeszkedik. Utóbbi különösen előnyös a frissítés során.

Diplomám keretein belül megvalósítottam az előretekintő keresést az Emf-IncQuery keretrendszerben, továbbá elkészítettem a Treat alapú inkrementális illesztő logikát. A Treat eljárás aktívan használja és támaszkodik a (keresés típusú) előretekintő mintaillesztőre, a kezdeti illesztéshez és a frissítéshez is ezt az algoritmust használja. Külön kihívást jelentett, hogy a minták egymásra hivatkozása a frissítést egy nagy kihívást jelentő, érdekes feladattá teszi. Az elért eredményeimet a Méréstechnika és Információs Rendszerek tanszéken fejlesztett és alkalmazott TrainBenchmark nevű tesztkörnyezetbe is integráltam. Végül összemértem a Treat eljárás teljesítményét és memóriafogyasztását a jelenleg használt inkrementális, és kereső alapú megoldásokkal.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.