MISKOLCI EGYETEM GÉPÉSZMÉRNÖKI ÉS INFORMATIKAI KAR
DIPLOMAMUNKA
Fogalom alapú állománykezelés
Piller Imre Mérnök informatikus MSc
Konzulens: Dr. Fegyverneki Sándor egyetemi docens Alkalmazott Matematikai Tanszék
Miskolc, 2013
Miskolci Egyetem Gépészmérnöki és Informatikai Kar Alkalmazott Matematikai Tanszék
Szám:
Diplomamunka Feladat Piller Imre (BV62RU) mérnök informatikus jelölt részére. A diplomamunka tárgyköre: állománykezelés A szakdolgozat címe: Fogalom alapú állománykezelés A feladat részletezése: A feladat egy kizárólagosan címkézési módszerre épülő állománykezelő alkalmazás elkészítése. Szükséges ismertetni a címkézés matematikai modelljét, bemutatva az újfajta keresési és módosítási műveleteket. Összehasonlításokat készíteni a hagyományos rendszerek hasonló funkcióival. A megközelítés újszerűsége miatt felhasználói tesztekkel is alá kell támasztani a rendszer használhatóságát.
Témavezető: Dr. Fegyverneki Sándor, egyetemi docens A feladat kiadásának ideje:
................................. szakfelelős
Eredetiségi Nyilatkozat
Alulírott Piller Imre; Neptun-kód: BV62RU a Miskolci Egyetem Gépészmérnöki és Informatikai Karának végzős mérnök informatikus szakos hallgatója ezennel büntetőjogi és fegyelmi felelősségem tudatában nyilatkozom és aláírásommal igazolom, hogy Fogalom alapú állománykezelés című diplomamunkám saját, önálló munkám; az abban hivatkozott szakirodalom felhasználása a forráskezelés szabályai szerint történt. Tudomásul veszem, hogy szakdolgozat esetén plágiumnak számít: • szószerinti idézet közlése idézőjel és hivatkozás megjelölése nélkül; • tartalmi idézet hivatkozás megjelölése nélkül; • más publikált gondolatainak saját gondolatként való feltüntetése. Alulírott kijelentem, hogy a plágium fogalmát megismertem, és tudomásul veszem, hogy plágium esetén szakdolgozatom visszautasításra kerül.
Miskolc, . . . . . . . . . . . .év . . . . . . . . . . . .hó . . . . . . . . . . . .nap
................................. Hallgató
1. szükséges (módosítás külön lapon) A szakdolgozat feladat módosítása nem szükséges ......................
...........................
dátum
témavezető(k)
2. A feladat kidolgozását ellenőriztem: témavezető (dátum, aláírás):
konzulens (dátum, aláírás):
..............
.............
..............
.............
..............
.............
3. A szakdolgozat beadható: ......................
...........................
dátum
témavezető(k)
4. A szakdolgozat . . . . . . . . . . . . . . . . . . . szövegoldalt . . . . . . . . . . . . . . . . . . . program protokollt (listát, felhasználói leírást) . . . . . . . . . . . . . . . . . . . elektronikus adathordozót (részletezve) ................... . . . . . . . . . . . . . . . . . . . egyéb mellékletet (részletezve) ................... tartalmaz. ......................
...........................
dátum
témavezető(k)
5. bocsátható A szakdolgozat bírálatra nem bocsátható A bíráló neve: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......................
...........................
dátum
szakfelelős
6. A szakdolgozat osztályzata a témavezető javaslata:
................
a bíráló javaslata:
................
a szakdolgozat végleges eredménye: . . . . . . . . . . . . . . . . Miskolc, . . . . . . . . . . . . . . . . . . . . . . . .
................................. a Záróvizsga Bizottság Elnöke
Tartalomjegyzék 1. Bevezetés
1
2. A címkézés 2.1. Alkalmazási területek . . . . . . . . . . . . . . . . . . . 2.1.1. Fájlrendszerek . . . . . . . . . . . . . . . . . . . 2.1.2. Szemantikus deszktop és indexelő szolgáltatások 2.1.3. Címkéző alkalmazások . . . . . . . . . . . . . . 2.1.4. Katalogizálók és referencia nyilvántartók . . . . 2.1.5. Levelező rendszerek . . . . . . . . . . . . . . . . 2.1.6. Tartalomkezelő- és megosztó rendszerek . . . . 2.1.7. Kollaborációs eszközök . . . . . . . . . . . . . . 2.1.8. Szemantikus web és ontológiák . . . . . . . . . 2.2. A megoldás újszerűsége . . . . . . . . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
3 4 4 4 6 6 6 7 7 9 9
3. Fogalom orientált keresési módszer 3.1. A könyvtárstruktúra . . . . . . . . 3.2. Fogalmi hierarchiák . . . . . . . . . 3.3. Fastruktúra átalakítása kontextusra 3.4. Objektumok keresése . . . . . . . . 3.5. A kontextus bővítése . . . . . . . . 3.6. Keresés a bővített kontextusban . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
11 11 11 12 14 16 17
. . . . . . . . .
19 19 20 21 22 22 23 24 25 29
5. Parancssoros kezelőfelület 5.1. A parancsok felépítése és használata . . . . . . . . . . . . . . . . . . . 5.2. Kapcsolat a befogadó fájlrendszerrel . . . . . . . . . . . . . . . . . . . 5.3. A parancsok értelmezése és végrehajtása . . . . . . . . . . . . . . . . .
31 31 35 36
4. A kontextus kezelési módjai 4.1. A kontextushoz tartozó adatok . 4.2. Megvalósítás relációs adatbázissal 4.3. MongoDB használata . . . . . . . 4.4. Saját tárolási struktúra . . . . . . 4.4.1. Egyedi azonosítók . . . . . 4.4.2. Kifejezések és elemek . . . 4.4.3. Gyűjtemények . . . . . . . 4.4.4. Keresés név alapján . . . . 4.4.5. Adatbázisobjektum . . . .
5
. . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
6. Grafikus felhasználói felület 6.1. A felhasználói felület elemei . . 6.2. A címkék típusai . . . . . . . . 6.3. Példa az egypaneles kialakításra 6.4. A kétpaneles változat előnyei . . 6.5. További funkciók . . . . . . . . 6.6. Implementációs lehetőségek . . 6.7. Felhasználói tesztek . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
38 38 39 40 40 41 41 42
7. Fogalom alapú fájlrendszer 7.1. Felhasználókezelés . . . . . . . . . . . . 7.2. Háttértárak kezelése . . . . . . . . . . 7.3. Programok felépítése . . . . . . . . . . 7.4. Programok telepítése és konfigurációja 7.5. Folyamatok kezelése . . . . . . . . . . 7.6. Verziókezelés támogatása . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
44 44 45 46 47 48 48
. . . . . . .
. . . . . . .
. . . . . . .
8. Összegzés
50
Irodalomjegyzék
52
Adathordozó használati útmutató
54
1. fejezet
Bevezetés Az elektronikusan tárolt információk mennyisége jelentős mértékben növekszik, és a tendencia azt mutatja, hogy a növekedés a későbbiekben még erőteljesebb lesz. Ez az informatika különböző részterületeire általánosan jellemző. Folyamatosan jelentkezik az igény az új módszerek kifejlesztésére, hogy az adatok továbbítása, feldolgozása, tárolása és a szükséges információk visszanyerése még hatékonyabb lehessen. A hardver, az infrastruktúra és az alkalmazott adatmodellek is igyekeznek megfelelni az újonnan felmerülő elvárásoknak. A felhasználói szokások is komoly változásokon mentek keresztül. Ez főként annak tudható be, hogy az internet a hétköznapok szerves részévé vált. A felhő alapú technológiák megjelenésével a felhasználók elektronikusan tárolt adatainak kezelési módja is szükségszerűen változott. Ennek vannak előnyei és hátrányai is természetesen, de az vitathatatlan hogy a következő években ez a szemlélet lesz uralkodó. A rohamos fejlődés mellett az adatok szervezési módja tulajdonképpen változatlan maradt. Már a mai értelemben vett informatika előtt jelen volt az a hierarchikus rendszerezési elv, amire a modern rendszerek is épülnek. E szerint a rendszerezendő objektumok valamilyen kategorizálás alapján fastruktúrába szervezhetők. Ebben az azonos szinten lévő alkategóriáknak nem lehet közös objektuma, ilyen értelemben tehát szigorú hierarchiáról van szó. (A későbbiekben a hierarchikus kifejezés az ilyen, ténylegesen fastruktúrának megfeleltethető kialakításra vonatkozik.) Nyilvánvalóan ez az elv közel áll az emberi gondolkodásmódhoz, mivel mind a hétköznapi gyakorlatban, mind pedig a tudományterületeken gyakran megjelenik. Van viszont néhány olyan vonatkozása, amely egy általánosabb szervezési mód használatát teheti szükségessé, ahol az lehetséges. A dolgozat az állománykezelés kapcsán jelentkező problémákra ad egy megoldást. A hierarchia egyik fő problémája, hogy a kategóriákba sorolás nem feltétlenül egyértelmű. Azokban az esetekben, amikor több lehetséges kategória van, akkor el kell dönteni, hogy ténylegesen melyikbe is tartozzon az adott objektum. A kategóriák között sincs szükségszerűen alá-fölé rendeltség. Ekkor azt ismét valamilyen további szempont alapján kell meghatározni. Ezek a problémák az állományok kezelésénél számos helyen megjelenhetnek, mint például az elektronikus könyvek, zeneszámok, képek vagy dokumentumok rendszerezésénél. Szépirodalmi könyvek esetében a kategorizálás történhet például korszak, szerző és műfaj szerint is, de más sorrend is elképzelhető. A hierarchikus kialakítás ilyen esetben tehát még akkor sem lesz egyértelmű, ha a kategóriák egyébként jól ismertek. Az említett kötöttségek a keresésnél szintén megjelennek. Amikor több lehetséges kategória is van, akkor nyilvánvalóan az sem lesz egyértelmű, hogy a hierarchiában melyik következő szintre lépjünk tovább. A sorrendi kötöttség szintén nehezíti a keresést, mivel hiába tudjuk, hogy milyen speciális kategóriáról is van szó, mégis először végig 1
kell haladni a megelőző szinteken. Az új állomány nyilvántartási módszerek szükségességét többek között az is jelzi, hogy az interneten való keresés a felhasználó szemszögéből gyakran gyorsabb, mint a helyi fájlrendszerben. Ez az erőforrások kihasználása szempontjából jelent elsődlegesen gondot, mivel az adott fájl újboli letöltése szükséges és felesleges redundanciához vezet. A dolgozat elsődlegesen az említett problémákra keres megoldást a fájlkezelő rendszerek kapcsán. A címkézés egy hatékony módszernek bizonyult erre az eddig vizsgálatok alapján. A „Címkézett dokumentum-nyilvántartás felhasználóbarát kezelése és alkalmazása” című TDK dolgozatomban már adtam egy áttekintő jellegű, az egyes részterületekre általánosságban kitérő leírást a címkézés megvalósításának és alkalmazásának lehetőségeiről. Jelen dolgozat az abban elért eredményekre támaszkodik ugyan, de a megértéséhez nem feltételezi annak ismeretét, attól függetlenül használható. A dolgozat első részében azt részletezem, hogy ebben az esetben pontosan mit is jelent a címkézés. Alkalmazáspéldákon végigkövethető, hogy melyek a hasonlóságok és a lényeges eltérések más rendszerek címkézési megoldásaihoz képest. Ezt a címkézés matematikai modelljének leírása követi. A fogalmak tisztázásának köszönhetően egy egységes megközelítés és formalizmus áll rendelkezésre. A fájlok adatainak kezelési módjához a dolgozat először sorra veszi a rendelkezésre álló kész komponenseket, majd bemutat egy saját adattárolási és keresési megvalósítást is. Ahhoz, hogy valóban állománykezelésről beszélhessünk állománykezelő alkalmazás is szükséges. Ennek a felhasználói felülete parancssoros vagy grafikus szokott lenni. Mind a két típushoz készült egy-egy alkalmazás. Ezek segítségével felmérhető, hogy milyen szemléletmódbeli váltásra van szükség az ilyen típusú rendszerek kezeléséhez. A dolgozat végén különféle tesztek szerepelnek, illetve egy kitekintés hogy operációs rendszerek fájlrendszereként hogyan lehetne használni az új címkézésre épülő megközelítést. A kutató munka a Miskolci Egyetem stratégiai kutatási területén működő Innovációs Gépészeti Tervezés és Technológiák Kiválósági Központ keretében valósult meg.
2
2. fejezet
A címkézés Címke (tag) alatt alkalmazástól függően különböző dolgokat érthetünk. Hasonló fogalom a felirat (label), és a kulcsszó (keyword), amely bizonyos helyeken a címkézés szinonímájaként szerepel. Címkézni általánosságban csak annyit jelent, hogy bizonyos objektumokat rájuk jellemző címkékkel látunk el. A címke tulajdonképpen egy kifejezés, amely többletinformációval szolgál. Feliratozásnak főként azt a műveletet szokták nevezni, amikor egy, az ember számára nehezen értelmezhető és megjegyezhető formához (például azonosítószámhoz) rendelnek egyértelműen egy könnyebben kezelhető nevet. A kulcsszavas keresés tipikusan abban különbözik a címkézéstől, hogy ott a kulcsszavak már magában a tartalomban is fellelhetők. A módszerek és elnevezések nem válnak élesen külön, emiatt először azt fontos tisztázni, hogy a címkézés itt pontosan mit is jelent. A címke itt tetszőleges szöveges kifejezés lehet. Nem feltétlenül csak egy szó. A hosszára és formátumára ilyen értelemben nincs megkötés. Egy állományhoz tetszőlegesen sok címke és egy címkéhez is tetszőlegesen sok állomány tartozhat. Ez jelentheti akár azt is, hogy lesznek állományok címke nélkül, vagy címkék állomány nélkül. Az állomány tartalma és az állományhoz tartozó címkék között nem feltétlenül kell, hogy legyen bármilyen jelentésbeli kapcsolat. A rendszerezést nyilván segíti ha van, de nem szükségszerű. A címkézést szinte kivétel nélkül csak kiegészítő funkcióként szokták használni. Itt most ez a módszer a rendszerezés alapjául szolgál. Nem arról van szó tehát, hogy egy másik, önmagában is használható struktúra felett még egy absztrakciós réteget képvisel, hanem mint független, önálló réteg jelenik meg. A fájlkezelés sok absztrakciós rétegből áll. Ahhoz, hogy érezhető legyen az előbbiekben vázolt különbség, érdemes megnézni a fájlok adatainak tárolásához és eléréséhez szükséges fő rétegeket. • A fizikális réteg tárolja a fájlok adatait ténylegesen. Ez végső soron hardver eszköz kell, hogy legyen. • Egy közbülső réteg eredményezi, hogy az adatokhoz hozzá lehessen férni, és a kezelési egység a fájl lehessen. • A fájlok rendszerezett eléréséhez egy réteg struktúrába szervezi a fájlokat. Az utolsó réteg az esetek többségében egy jegyzékstruktúrát szolgáltat, amely már elég absztrakt, hogy az emberek számára is értelmezhető és kezelhető legyen. A címkézés tehát most egy alternatív harmadik réteg, nem pedig egy, az előzőekre épülő negyedik. (A későbbi adattárolási megvalósítás kissé ellentmond ennek a felépítésnek. Ez amiatt van, mert a harmadik réteget csak a másodikra építkezve nagyon nehéz, és felesleges is implementálni addig, amíg nem készültek el legalább az alapvető operációs rendszeri 3
2.1. Alkalmazási területek
szolgáltatások és felhasználói alkalmazások hozzá. A különbség természetesen ettől még jelentős, mivel a fájlok hierarchiában való tárolási módja a címkézéssel nincs közvetlen kapcsolatban.) A címke a rendszerben hasonló feladatot lát el, mint a hierarchikus struktúrákban a jegyzék. Emiatt az automatikus címkézésre már elvi szinten sem lehet szükség. Az elképzelhető persze, hogy mint segédfunkció a későbbiekben megjelenjen, de akkor is csak olyan formában, hogy a rendszer javaslatokat tesz erre vonatkozóan. A jegyzékstruktúrában a navigáció egy szinte kézzel fogható, szemléletes dolog. A címkézésre épülő rendszer esetében inkább keresésről van szó. Elvi szinten lehet itt is navigációról beszélni, viszont a címkék kötetlen megadási sorrendje a kulcsszavas keresők esetében megszokotthoz keresési módhoz hasonlít jobban.
2.1.
Alkalmazási területek
A címkézés vagy ahhoz hasonló módszer az informatikában számos területen megjelenik. Nehéz annak az eldöntése, hogy pontosan mit tekinthetünk még annak, illetve hogy melyek azok a fő alkalmazástípusok, ahol találkozhatunk ilyen megoldásokkal. A következő alpontokban példák szerepelnek ezekre a típusokra. Mivel a címkézés feladata a dokumentumok felhasználó szemszögéből egyszerűbb keresése, ezért a címkézés mellett az asztali környezetek kereső funkcióit is érdemes sorra venni. 2.1.1.
Fájlrendszerek
A fájlrendszerek szintjén is voltak már kísérletek a címkézés megvalósítására. Az egyik jelentős ezek közül a Microsoft cég által 2003 környékén fejlesztett Windows Future Storage 1 , vagy röviden WinFS. Ez egy NTFS fájlrendszerre és relációs adatbázisra épülő egységes adattároló és kezelő alrendszernek készült. A tervek szerint a Windows Longhorn majd a Windows Vista operációs rendszerhez készült, de a kiadása meghiúsult. Az elkészült komponenseket többek között a Microsoft SQL Server-be integrálták. A címkék ebben a rendszerben a többi metaadattal együtt kerültek tárolásra, hogy majd azok alapján gyorsabban lehessen keresni. Ez a kezdeményezés abból a szempontból is érdekes, hogy a hagyományos mappa mellett megjelent a virtuális mappa koncepciója is, ami a későbbi Windows kiadásokban is megmaradt. Egy jóval kisebb volumneű fejlesztés a Tagsistant.2 Ez egy kifejezetten címkézésre készített alkalmazás. A jegyzékek nevét használja mint címkéket. Mivel felhasználói térben futó fájlrendszerként implementálták, ezért nem kell hozzá külön speciális fájlkezelő rendszer. A címkék alapján történő szűrési feltételek magában az útvonalban adhatók meg. Az AND és az OR jegyzékek is szintén az egyszerűbb kezelhetőséget szolgálják, mivel így a logikai műveletek megadása is természetesen adódik. A Tagsistant Manager programmal a címkék közötti tartalmazási kapcsolatok is beállíthatók. A címkézéshez szükséges metaadatok fájlrendszerbe integrálására vannak létező megoldások, mint például a TagFS [SS06]. A hasonló fájlrendszeri megvalósítások általában kísérleti stádiumban vannak, és csak szűk körben terjedtek el. 2.1.2.
Szemantikus deszktop és indexelő szolgáltatások
A WinFS fejlesztésével közel egyidőben az Apple is komoly lépéseket tett a hatékonyabb asztali környezetekben való keresés érdekében, méghozzá a SpotLight 3 nevű indexelő 1 [WinFS]
http://blogs.msdn.com/b/winfs http://www.tagsistant.net 3 [SpotLight] http://www.apple.com/osx/what-is 2 [Tagsistant]
4
2.1. Alkalmazási területek
szolgáltatás formájában. Technikailag nem egy akkora lépésről volt szó, mint a WinFS esetében, mivel az alapvető tárolási mechanizmusban nem történt változás. Az operációs rendszer indításakor egy Metadata Server indult (mds daemon vagy mdworker néven). A változások folyamatos követése jelentősen nem lassítja a rendszer működését, az indexeknek köszönhetően viszont a keresés eredménye tulajdonképpen azonnal rendelkezésre áll. A címkézésre is ad lehetőséget a kommentek formájában (2.1. ábra).
2.1. ábra. Címkék hozzáadása a Mac OS X SpotLight nevű keresőrendszerének felületén.
Egy átfogó asztali integrációt megcélzó projekt a NEPOMUK 4 (Networked Environment for Personalized, Ontology-based Management of Unified Knowledge). A projekt főként Európai Uniós támogatással valósult meg. A KDE (K Desktop Environment) asztali környezethez készült. A célja nem csupán, hogy egy kereső szolgáltatás legyen, hanem az alkalmazások integritását is igyekszik segíteni. Az adatok konzisztens és kompatibilis tárolására törekszik, hogy majd azokat szemantika alapján rendszerezni tudja. A GNOME (GNU Network Object Model Environment) asztali környezet esetében a Tracker 5 nevű alkalmazás lát el indexelő és kereső funkciókat. Ebben a címkék olyan egy szóból álló feliratok, amelyeket bármelyik fájlhoz hozzárendelhetünk a kategorizálás érdekében. A program címkéket automatikusan is hozzá tud rendelni a fájlokhoz, melyek a felhasználó által megadottal egyenértékűek. 4 [Nepomuk] 5 [Tracker]
http://nepomuk.kde.org https://live.gnome.org/Tracker
5
2.1. Alkalmazási területek
2.1.3.
Címkéző alkalmazások
A szemantikus asztali környezetek rendelkeznek saját fájlkezelő alkalmazásokkal, melyekkel a fájlokon lévő címkéket szerkeszteni lehet. Vannak nem az asztali környezet részeként fejlesztett, hasonló funkcionalitással rendelkező alkalmazások is. Az egyik ilyen alkalmazás például az Elyse.6 Jegyzékek helyett az alkalmazás címke csomópontokat (tag nodes) használ. A csomópontok hierarchiába is szervezhetők. Mindegyik tulajdonképpen egy keresést valósít meg. Egy fájl több csoportba is tartozhat, tehát az egyes kategóriák között lehetnek átfedések. A drag-and-drop módszernek köszönhetően egyszerű a címkézés, és akár több fájlon egyidejűleg is elvégezhető. Támogatja továbbá a jegyzékstruktúra konverzióját és jelzi az ismétlődő példányokat is. A tag2find 7 egy Windows operációs rendszerhez készült címkéző alkalmazás. Ez rendelkezik egy TagBox nevű keresőmezővel, amely a tálcához integrálható. Ebbe elegendő a címkézendő fájlokat belemozgatni, de a kontextus menüből is elérhető a funkció. További hasznos jellemzői, hogy képes figyelni az újonnan megjelenő fájlokat, illetve az új címkék hozzáadására javaslatokat is tesz. A böngészőjében (Tag Browser) van egy címke felhő (Tag Cloud) melyben a gyakoriságuknak megfelelő méretben szerepelnek a címkék. A TaggedFrog 8 egy szintén nagyon jól használható alkalmazás. Szintén lehet dragand-drop módon fájlokat hozzáadni, és a címkék kiválasztásához is azokat egy címke felhőben jeleníti meg. A Windows kontextus menüjébe is integrálható. A címkékkel való keresésen túl még egyéb szűrési feltételek is megadhatók benne. Az alkalmazás felhasználói felülete a 2.2. ábrán látható. 2.1.4.
Katalogizálók és referencia nyilvántartók
A Referencer 9 egy GNOME alkalmazás, mely dokumentumok és hivatkozások rendszerezésére szolgál. Nem egy általános fájlkezelő, viszont funkcionalitásában és felépítésében ez is nagyon hasonló a tervezett rendszerhez. Elsődlegesen tudományos anyagok kezelésére készült, így a dokumentumokat is alapvetően tudományos cikkekként kezeli. A hivatkozásokhoz szükséges képes automatikusan kinyerni a PDF fájlokból, és abból BibTeX fájl is generálható vele. DOI vagy arXiv alapján is tud keresni az Interneten. A 2.3. ábrán látható egy kép az alkalmazás felhasználói felületéről. Ennek bal oldali sávjában lehet a keresésben szereplő címkéket kijelölni, akár többet is egyszerre. Ami a címkék kezelésénél nehézséget jelent, hogy csak egy görgethető lista áll rendelkezésre azok keresésére vagy szerkesztésére. 2.1.5.
Levelező rendszerek
A levelező rendszerekben is egyre gyakoribb, hogy a jegyzékekbe való csoportosítás mellett a címkézés lehetősége is adott. A Gmail esetében már az is egy címke, hogy a levél beérkezett vagy elküldött. A további címkék hozzáadása kézenfekvő. A levelet megnyitva a tárgyat követően sorban szerepelnek a levélhez rendelt címkék. Újat hozzáadni pedig egy címke ikonra kattintva lehet. Az olyan elterjedt levelezőkliensek, mint például a Thunderbird vagy az Outlook is képesek kezelni a kategóriákat. A módszer elnevezésében vannak különbségek, viszont a felhasználó szempontjából a végeredmény ugyanaz. 6 [Elyse]
http://silkwoodsoftware.com/ http://www.tag2find.com 8 [TaggedFrog] http://lunarfrog.com/taggedfrog 9 [Referencer] https://launchpad.net/referencer 7 [Tag2find]
6
2.1. Alkalmazási területek
2.2. ábra. Példa képek keresésére TaggedFrog segítségével.
2.1.6.
Tartalomkezelő- és megosztó rendszerek
A tartalomkezelő rendszerek esetében a címkézés alapfunkciónak számít. Bizonyos weboldalak, mint például a Delicious 10 kifejezetten erre épülnek. A linkekhez címkéket rendelnek, hogy ezek alapján kategorizálni és keresni is lehessen. A Flickr,11 mint az egyik legnagyobb fényképmegosztó oldal népszerűségét többek között a címkézésnek köszönheti. Ez volt az egyik első weboldal, amelynél a címkék ábrázolására címke felhőt használtak. A jelentős tartalomkezelő rendszerek (mint például a Drupal,12 Wordpress,13 Joomla 14 ) mindegyikében van már lehetőség a címkék kezelésére. Ha az összetett lekérdezéseket nem is támogatják, de annyit biztosan, hogy az adott címkével ellátott tartalmakat listázzák, legyen szó például blogbejegyzésekről, képekről vagy videókról. 2.1.7.
Kollaborációs eszközök
A kollaborációs célokra készült alkalmazások nem sokban különböznek az eddigiektől. Ami miatt mégis külön pontba kerültek, hogy a tabbles 15 nevű alkalmazás egy szép példája a használatának ilyen területen. Ebben az esetben is a jegyzékek és a címkézés előnyeinek ötvözése áll a megoldás hátterében. A tabble, amiről az alkalmazás a nevét 10 https://delicious.com 11 http://www.flickr.com 12 http://drupal.org/project/tagging 13 http://en.support.wordpress.com/posts/tags/ 14 http://extensions.joomla.org/extensions/search-a-indexing/tags-a-clouds 15 [Tabbles]
http://tabbles.net
7
2.1. Alkalmazási területek
2.3. ábra. A Referencer nevű katalogizáló alkalmazás felhasználói felülete.
kapta egy különleges tároló, ami egyaránt használható dokumentumok, mappák illetve könyvjelzők rendszerezésére is. A feltevés az, hogy mappákkal a rendszerezés kényelmesebb, míg a keresésnél inkább címkéket érdemes használni. A címkék helyett tehát itt tabble-nek nevezett virtuális mappák vannak, melyeket kerek ikonok szimbolizálnak. Címkével ellátni egy fájlt úgy lehet, mint ha azt a tabble-be bemásolnánk. Egy fájl több tabble-be is tartozhat. A kereséshez ezek után nem szükséges ismerni a fájl tényleges helyét, elegendő csak a rá jellemző tulajdonságokat felsorolni. A 2.4. ábrán látható egy példa a keresésre, amiben a keresett fájlról tudjuk, hogy az a „Business cards” és „Maurizio” tabble-ökben van benne, a kiterjesztése pdf, és nincs benne az „Old” tabble-ben.
2.4. ábra. A tabbles esetében megvalósított keresési módszerre egy példa.
Fontos megemlíteni a tabbles weboldalát. Az ilyen típusú rendszerezési módok még ha bizonyítottan jól használhatók, akkor is igényelnek némi tanulást a felhasználó részéről. A weboldal részletesen bemutatja, hogy milyen problémát és hogyan old meg ez a rendszer. Egyszerű példákon keresztül képekkel és videókkal illusztrálva segíti a megértést.
8
2.2. A megoldás újszerűsége
2.1.8.
Szemantikus web és ontológiák
A szemantikus web egy olyan kezdeményezés, amely az Interneten elérhető tartalmakat jelentésüknek, felhasználási területüknek megfelelően igyekszik rendszerezni. Ehhez elsősorban metainformációkat használ, melyeket az eredeti elképzelés szerint a gépek automatikusan állítanak elő. Az ilyen szintű automatizáltság még nem jellemző, viszont a metaadatok egységes megjelenítési formájaként az RDF (Resource Description Framework) használata már általánosnak mondható. (Erre vonatkozóan már a szemantikus web kialakulásakor született javaslat [BL98].) A metaadatok egy másik meghatározó forrása a felhasználói közösség. A különböző weboldalak segítséget nyújtanak az ilyen adatok felviteléhez. A címkézés ennek az egyik elterjedt módja, ahogy az már a tartalomkezelő oldalak kapcsán is felmerült. Ami a szemantikus web esetében a többletet jelenti, hogy vannak törekvések, melyek az addig szeparáltan működő, de hasonló módszerekre épülő szolgáltatásokat integrálni próbálják. A közösségi címkézés az eddig felvázolt címkézési módszernél összetettebb. Az egyszerűbb esetben elegendő az objektumok és címkéik viszonyát vizsgálni. Ezt a közösségi címkézés még kiegészíti azzal, hogy az adott címke milyen forrásból származik, és mennyire megbízható. A címkék jelentése (Moat Of A Tag) sem feltétlenül egyértelmű, így még azt is társítani kell valamilyen módon [PP08]. Új fogalomként megjelent a folkszonómia (folksonomy = folk + taxonomy). Ez egy olyan osztályozási rendszer, amely a felhasználók által megadott fogalmakra építkezik. Alapjául a címke ontológiák szolgálhatnak. Az egyik nehézség ennek kapcsán is az egységes formátum hiánya, melyre megoldást a közösségi címkézés modellje adhat [KB08].
2.2.
A megoldás újszerűsége
Az előző pontokban számos címkézést használó alkalmazási területről szó eset. Érdemes röviden összefoglalni, hogy a dolgozatban szereplő megközelítés miben jelent újszerűséget ezekhez képest. Az alkalmazások egy része gyakorlati indíttatású, amelynél csak egy hasznos segédfunkció hozzáadásáról van szó. Ezek nem igényelnek komolyabb elméleti megalapozást. A tapasztalatokhoz, felhasználói visszejelzésekhez igazodik a fejlesztés menete. Ide sorolható például a Tagsistant, tag2find vagy a Referencer. A másik megközelítés a fogalmak elemzéséből, ontológiai vizsgálatokból indul ki. Ezek bizonyíthatóan jó, de általában komplex struktúrákat eredményeznek. Tudományos szempontból ezek a mérvadóak, viszont az így készült alkalmazások a gyakorlatban komolyabb felkészültséget igényelnek a felhasználótól. A dolgozatban bemutatott megoldás a kettő között egy kompromisszumos megoldást ad. Egyszerű, szemléletes matematikai fogalmakra építkezik úgy, hogy közben a gyakorlati szempontok, és a felhasználói elvárások is érvényesülnek. A címkék és a jegyzékek között gyakran vonnak párhuzamot. A tabbles nevű alkalmazás például a kettő funkcionalitásából kapott speciális tárolóról kapta a nevét. Útvonal jellegű kifejezéseket alakít ki, viszont ezek használatára csak példákat hoz fel, nem célja a műveletek formális definiálása. A Tagsistant szintén a jegyzékstruktúra és a címkézés előnyeit ötvözi. Az útvonalak maguk a lekérdezések, a grafikus megvalósítás így már másodlagos, mivel adódik a parancssori kezelési módból. Ez tetszőleges fájlkezelő alkalmazás használatát teszi ugyan lehetővé, viszont azt is jelenti, hogy többletet sem ad a funkcionalitáshoz. 9
2.2. A megoldás újszerűsége
Az új, fogalom alapú megközelítés a parancssori és a grafikus kezelési módot egymásra építi. Minden grafikus műveletnek megfeleltethető egy parancs, viszont sajátos kezelőfelületet igényel, amely a fogalom alapú állománykezelést segíti. Más fájlrendszerekkel fájlokat cserélni a felvázolt rendszer az importálási és exportálási funkciói segítségével tud. Hasonló megoldást az említett alkalmazások közül az Elyse is támogat. Ami ezt egyedivé teszi, hogy a grafikus felület hierarchikus kezelési módot is biztosít. A megoldás tehát sok hasonlóságot mutat a felsorolt rendszerekkel és módszerekkel. Azok bizonyos jellemzőit át is veszi, egy egységes, letisztított keretbe helyezi el. A célterületre készített alkalmazások kiváltása nem cél. A módszer az állományok kezelésére szorítkozik, viszont ad egy olyan formalizmust, amely bármilyen címkézéssel, kategorizálással megoldható problémára illeszthető.
10
3. fejezet
Fogalom orientált keresési módszer 3.1.
A könyvtárstruktúra
A könyvtárstruktúra és a rajta elvégezhető műveletek közismerteknek tekinthetők. A rövid leírására azért van mégis szükség, hogy a későbbiekben összehasonlítható legyen a címkéket használó, fogalmakra épülő megközelítéssel. A hagyományos értelemben vett könyvtárstruktúrának mindig megfeleltethető egy olyan fagráf, melyben a jegyzékeket és a fájlokat egy-egy csomópont jelöli. Fájlok csak a fagráf leveleiben lehetnek. Minden csomópontnak kell hogy legyen neve, amely nem feltétlenül egyedi. Az állományok egyértelmű azonosításához a fa gyökeréből induló és az állományban végződő teljes útvonal megadása szükséges, és elégséges. Ez tehát a jegyzéknevek rendezett listája, melynek végén a fájl neve is szerepel (abszolút útvonal). A fájlok útvonalának célszerűen olyannak kell lennie, hogy valamilyen szinten utaljon a fájl szerepére, tartalmára. Emiatt tekinthetjük a fájlokat általánosan objektumoknak, az útvonalban szereplő jegyzékneveket pedig az objektumok attribútumainak. Egy objektumhoz tehát egy rendezett attribútumlista tartozik, melynek elején tipikusan általánosabb fogalmakra utaló nevek állnak, míg a végére kerülnek a speciális jellemzők. Ez természetesen nem szükségszerű, viszont hierarchikus felépítés ennek a kialakításnak kedvez. A gráfnak mindig van egy kitüntetett csúcspontja amely a hierarchiában elfoglalt helyet jelöli (aktuális jegyzék). A keresés során az élek mentén haladva választhatunk új csomópontot, egészen addig, amíg a keresett állományokat meg nem találjuk. A relatív útvonalakat ilyen lépések sorozatának tekinthetjük, ahol haladhatunk a gyökér felé is. Az abszolút útvonalak esetében a gyökeret tekintjük kiindulópontnak. A jegyzéknevek rendezett listája tehát keresési kifejezésként kezelhető, az eredmény pedig az aktuális jegyzék tartalma lesz. A könyvtárstruktúra műveletei szintén nagyon szemléletesek. A fájlok létrehozása, a másolás, az áthelyezés és a törlés is közvetlenül adódik a kialakításból.
3.2.
Fogalmi hierarchiák
Az új rendszer modelljének leírásához érdemes először a fogalmak formális leírásával foglalkozó tudományág (formal concept analysis [GW05]) jelöléseit és alapfogalmait röviden összefoglalni. Jelöljön G egy tetszőleges objektumhalmazt, az M pedig egy attribútumhalmazt. (Az objektumok jelen esetben az állományok, az attribútumok pedig a címkék.) A két halmaz közötti kapcsolatok leírásához tekintsük a I ⊆ G × M bináris relációt (incidence relation). Az ezekből kapott (G, M, I) hármast formális kontextusnak nevezzük. 11
3.3. Fastruktúra átalakítása kontextusra
Tekintsünk egy A ⊆ G halmazt a kontextusban. Ehhez tartozik egy A0 = {m ∈ M |(g, m) ∈ I, ∀g ∈ A} attribútum halmaz. Analóg módon a B ⊆ M részhalmazhoz szintén tartozik egy B 0 = {g ∈ G|(g, m) ∈ I, ∀m ∈ B} halmaz. Ezen A → A0 illetve B → B 0 leképzéseket derivációnak nevezzük. Az olyan (A, B) párt, amelyre fennáll az A0 = B és B 0 = A összefüggés, fogalmaknak nevezzük. A párhoz tartozó objektum halmazt attribútum-extenziónak (extent), az attribútum halmazt pedig objektum-intenziónak (intent) nevezzük [KA08]. Tekintsük az (A1 , B1 ) és (A2 , B2 ) fogalmakat. Amennyiben A1 ⊆ A2 teljesül, akkor az első fogalom a második részfogalma. A második tehát egy általánosabb fogalom. Ez a tartalmazási kapcsolat egy részbenrendezést ad meg, mégpedig (A1 , B1 ) ≤ (A2 , B2 )
⇐⇒
A1 ⊆ A2
⇐⇒
B2 ⊆ B1 .
A kontextushoz tartozó összes fogalom az előbbi részbenrendezéssel adja a fogalomhálót (concept lattice), ami egy teljes háló, vagyis minden részhalmazának van szuprémuma és infimuma. A kontextushoz tartozó összes fogalom többek között az In-Close algoritmussal állítható elő [AS09]. A fogalomhálókat alkalmaznak többek között a csoporttechnológiában is [RS98]. Az állománykezelés egy új területet jelent, és új problémákat vet fel, elsősorban a nagyobb méretű kontextus hatékony kezelése miatt.
3.3.
Fastruktúra átalakítása kontextusra
Minden fastruktúrához hozzárendelhető olyan kontextus, amely megőrzi a struktúrában lévő hierarchiát. Az ilyen kontextusok fogalomhálóját Hasse-diagram formájában ábrázolva ismét láthatóvá válik a szigorú hierarchia. A kontextus már kiegészíthető olyan többletinformációkkal is, amelyeket a fastruktúra nem tud leírni. A következőkben ezeknek a fő lépéseknek a részletezése szerepel egy példán keresztül szemléltetve azokat. A fastruktúra leképzésének több módja is lehet. Gyakorlati szempontból azt az esetet érdemes vizsgálni, melyben a jegyzékek neveinek feleltetjük meg a kontextusban az attribútumokat. Problémát jelent, hogy a jegyzéknevek nem feltétlenül egyediek, amelyen úgy lehet egyszerűen segíteni, hogy különböző attribútumokat rendelünk a különböző helyeken, de azonos névvel szereplő jegyzékekhez. Például a 3.1 ábrán dolgozatokhoz és programokhoz tartozó állományoknak az elhelyezése szerepel két lehetséges fastruktúrában. Az első esetben a csoportosítás a szerint történik, hogy dolgozatról vagy programról van-e szó, majd ezen belül év szerint szerepelnek az aljegyzékek. A második változatban fordítva, az év szerinti bontás adja a magasabb szintet. A két elrendezés jelentősen nem különbözik. A jegyzékstruktúra esetében dönteni kell, hogy melyiket szempont szerinti csoportosítási módot tekintjük általánosabbnak. Az első változatban a 2010 és 2011 nevek ismétlődnek, így azokhoz például a 2010_dolg, 2010_prog illetve a 2011_dolg, 2011_prog rendelhetők a szülőjegyzéküknek megfelelően. A fájlok nevei különbözőek, tehát azok leképzése közvetlenül adódik.
12
3.3. Fastruktúra átalakítása kontextusra
3.1. ábra. Példa dolgozatok és programok állományainak elhelyezésére kétféle struktúrában.
A kontextus tehát a G = {ábra1.png, ábra2.png, dolgozat1.tex, dolgozat1.pdf, képlet.jpg, dolgozat2.doc, prog2.png, dolgozat3.tex, dolgozat3.pdf, prog1.c, prog1.exe, utils.h, prog2.c, prog2.exe} objektumhalmazból, az M = {dolgozatok, dolgozat1, dolgozat2, dolgozat3, programok, program1, program2, 2010_dolg, 2010_prog, 2011_dolg, 2011_prog} attribútumhalmazból, illetve a 3.2 táblázattal megadott I bináris relációból áll. Ez a leképzés tetszőleges faszerkezetre elkészíthető, és belőle az eredeti struktúra mindig visszanyerhető. A példában a 2010 és 2011 jegyzéknevek attribútumként is használhatók, ekkor a visszaalakítás már nem lehetséges, viszont ez a megoldás jobban tükrözi a jelentést. Attribútumokként az a sorrendi kötöttség szünne meg, ami a példaként felhozott kétféle struktúra különbségét is jelenti. 13
ábra2.png
×
×
×
dolgozat1.tex
×
×
×
dolgozat1.pdf
×
×
×
képlet.jpg
×
×
×
dolgozat2.doc
×
×
×
prog2.png
×
×
×
dolgozat3.tex
×
×
×
dolgozat3.pdf
×
×
×
2011_prog
2011_dolg
2010_prog
2010_dolg ×
program2
×
program1
×
dolgozat3
dolgozat1
ábra1.png
dolgozat2
dolgozatok
programok
3.4. Objektumok keresése
prog1.c
×
×
×
prog1.exe
×
×
×
utils.h
×
×
×
prog2.c
×
×
×
prog2.exe
×
×
×
3.2. ábra. Az első fastruktúrához tartozó bináris reláció.
A prog2.png fájl neve jelzi, hogy a dolgozat3 és a program2 között valamilyen kapcsolat van. Az I relációt a (prog2.png, programok) és (prog2.png, program2) párokkal bővítve ez is megadható. A kontextusban ezen kívül további csoportosítási módok is bevezethetők például a kép, dokumentum, latex és exe attribútumokkal. Az említett módosítások után kapott reláció a 3.3 ábrán szerepel.
3.4.
Objektumok keresése
A kontextus esetében alkalmazott keresési mód tulajdonképpen a fagráfban való keresés általánosítása. A fagráf helyett itt egy hálóban lehet navigálni. A gyökeret a (G, ∅) fogalom szimbolizálja. A hálóban lefelé és felfelé is lehet haladni. A jelentős különbség a fagráfhoz képest, hogy itt egy csomópontnak több szülője is lehet. A 3.4 ábrán látható a példában szereplő módosított kontextus fogalmainak hálója. Az ábra a csomópontok megadásánál azt az egyszerűsített jelölésmódot használja, melynél csak az újonnan megjelenő objektumok és attribútumok kerülnek feltüntetésre. A gyökércsomópont a (G, ∅) lesz. A kiinduló állapot tehát a kontextus összes objektumát tartalmazza. Ehhez a dolgozatok, programok, 2010, illetve 2011 címkék valamelyikét adhatjuk hozzá, hogy egy alsóbb szintre léphessünk. A programok címkét választva a program1, program2 és az exe lehetőségek adódnak. Az exe-re továbblépve tulajdonképpen véget is ért a keresés, mivel bármely további címke hozzáadása már üres objektumhalmazhoz vezetne. Az eredményben itt a prog1.exe és prog2.exe állományok fognak szerepelni. Az ehhez vezető útvonal a programok/exe formában, a kijelölt fogalom pedig a ({programok, exe}, {prog1.exe, prog2.exe}) párral adható meg. A navigáció ugyan természetes módon adódik, viszont a kezelési mód a gyakorlatban több problémát is felvet. 14
×
dolgozat1.tex
×
×
×
dolgozat1.pdf
×
×
×
képlet.jpg
×
×
×
dolgozat2.doc
×
×
×
prog2.png
×
×
dolgozat3.tex
×
×
×
dolgozat3.pdf
×
×
×
×
×
exe
×
latex
×
dokumentum
×
kép
ábra2.png
2011
×
2010 ×
program2
×
program1
×
dolgozat3
dolgozat1
ábra1.png
dolgozat2
dolgozatok
programok
3.4. Objektumok keresése
× ×
×
prog1.c
×
×
×
prog1.exe
×
×
×
utils.h
×
×
×
prog2.c
×
×
×
prog2.exe
×
×
×
× × × × × ×
×
3.3. ábra. A bővített kontextushoz tartozó bináris reláció.
• A szintenkénti keresés a hierarchiához nagyon hasonló. Az általános fogalmaktól elindulva fokozatosan juthatunk el a speciálisakhoz. A gond ezzel a megoldással éppen az, hogy így az általánosabb attribútumokat mindig fel kell sorolni, még ha azok egyébként a speciálisakból következnének. Ezzel a hierarchiában lévő sorrendi kötöttség továbbra is megmaradna. • Mivel fogalmakról van szó, ezért a hálóban előfordulhatnak név nélküli csomópontok. Ebben az esetben az alsóbb szinteken megjelenő új címkékre is tovább lehet lépni. Például a dolgozatok címke után a dolgozat1, dolgozat2, dolgozat3, kép, dokumentum és latex címke is következhet. • Előfordulhat olyan csomópont amelyen több új attribútum jelenik meg. Ez akkor fordulhat elő, ha a kettő már ekvivalensnek tekinthető, ezért bármelyik hozzáadása a többi hozzávételét is jelenti. • A megoldás feltételezi, hogy rendelkezésre áll az egész koncepcióháló, amelynek a felépítése és a tárolása nagyon költséges. Fájlrendszer esetében ezért ez nem ajánlott. Ezen okok miatt a fogalomhálóban a keresést inkább lekérdezések sorozatával tanácsos megközelíteni. Ehhez keresési kifejezések szükségesek. A könyvtárszerkezet esetében az útvonal látja el ezt a feladatot. A kontextus esetében ez legyen egy attribútumhalmaz, amelyet jelöljön a Q ⊆ M (query). A keresés eredménye egy R ⊆ G (result) objektumhalmaz, amelyet az R = Q0 derivációval kaphatunk meg. Kezdetben legyen Q = ∅, így R = G. A Q halmazt bővítve az R halmaz számossága vagy csökken vagy nem változik. Minden lekérdezéshez tartozik egy (R, Q00 ) = (Q0 , Q00 ) fogalom. Teljesül, hogy Q ⊆ 00 Q , vagyis a Q00 \ Q halmazbeli attribútumok hozzáadásával nem fog csökkenni az R 15
3.5. A kontextus bővítése
programok
2010
dolgozatok
2011
program1
dokumentum latex
program2
kép
exe
dolgozat1
utils.h, prog2.c dolgozat2
dolgozat3
prog1.c
prog2.exe
dolgozat1.tex
prog1.exe
dolgozat1.pdf ábra1.png, ábra2.png
prog2.png dolgozat3.pdf
dolgozat2.doc
dolgozat3.tex
képlet.jpg
3.4. ábra. A példaként megadott módosított kontextus fogalmainak Hasse-diagramja. A tömör jelölésmód csak a csomópontban megjelenő új attribútumot vagy objektumot jelöli.
számossága, azok az attribútumok már egyébként is a fogalomhoz tartoznak. Ennek megfelelően a keresés szempontjából az M \ Q00 halmazból érdemes attribútumokat választani. Ezzel fokozatosan lehet szűkíteni a fogalmat anélkül, hogy az utolsó lépést leszámítva üres eredményhalmazt kapnánk. A későbbiekben majd szükség lesz arra is, hogy az eredmény üres legyen, mivel így vihetünk fel az adott helyre új objektumokat, és alakíthatunk ki új fogalmakat.
3.5.
A kontextus bővítése
A Q halmazban lévő attribútumokat tekinthetjük szűrési feltételeknek is. A deriváció műveletét részletesebben kiírva az R = {g ∈ G|(g, m1 ) ∈ I ∧ (g, m2 ) ∈ I ∧ . . . ∧ (g, mk ) ∈ I} alakot kapjuk, melyben mi ∈ Q és k = |Q|. Ebben a formában már szembetűnő, hogy a keresés az eddigiek alapján csak a konjunkciós műveletet használja. A teljesség kedvéért a negáció és a diszjunkció műveletének keresésben való alkalmazási lehetőségeit is meg kell vizsgálni. Előfordulhat, hogy a szűrést úgy szeretnénk megfogalmazni, hogy az adott attribútum ne szerepeljen az eredményben lévő objektumokon. Ehhez be kell vezetni az 16
3.6. Keresés a bővített kontextusban
m1 g1 g2
×
m2
m3
m1
×
×
×
×
m3 ×
×
g3 g4
m2
×
×
×
×
×
3.5. ábra. Példa kontextus komplementerrel bővítve. ({g1 , g2 , g3 , g4 }, ∅)
({g1 , g2 , g4 }, {m2 })
({g1 }, {m2 , m3 })
({g1 , g2 , g3 , g4 }, ∅)
({g1 , g3 , g4 }, {m1 })
({g2 }, {m1 , m2 })
({g2 , g3 , g4 }, {m3 })
({g3 , g4 }, {m1 , m3 })
(∅, {m1 , m2 , m3 })
({g3 }, {m1 , m2 , m3 })
3.6. ábra. A kontextushoz és a komplementer kontextushoz tartozó fogalomháló.
attribútum ellentettjének fogalmát. A kontextust bővíteni kell oly módon, hogy az attribútumok halmazához hozzáveszünk új attribútumokat. Minden ilyen új attribútumra teljesülnie kell, hogy azon objektumokkal van relációban, amellyel a neki megfelelő eredeti attribútum nincs. Egy m ∈ M attribútumnak megfelelő ilyen attribútumot nevezzük ellentett attribútumnak, jelölése pedig m. Az ellentett attribútum egy új, a fogalomhálók körében nem használt fogalom. Hasonló összefüggések leírására a komplementer kontextust szokás használni, amely (G, M, I) kontextus esetén a (G, M, G × M \ I) kontextus. A kibővített kontextus egyszerűsíti a jelöléseket és egyszerűbb tárgyalásmódot eredményez. Jelölje M a bővített attribútumhalmazt, a bővített incidencia relációt pedig I. A kereséseket az így kapott (G, M, I) kontextusban végezhetjük el. A bővítésnek köszönhetően tetszőleges Q ⊆ M halmaz az R eredményhalmazzal fogalmat fog alkotni.
3.6.
Keresés a bővített kontextusban
Tekintsük a G = {g1 , g2 , g3 , g4 } objektumhalmaz és a hozzá tartozó M = {m1 , m2 , m3 } attribútumhalmazt. A 3.5. ábra táblázatának első három oszlopában táblázatos formában megadott I bináris relációval ez egy (G, M, I) kontextust alkot. Az attribútumhalmazt az m1 , m2 és m3 ellentett attribútumokkal bővítve kapjuk a (G, M, I) relációt. Az eredeti és a komplementer kontextushoz tartozó fogalomhálók Hasse-diagramja a 3.6. ábrán látható, a kibővítetté pedig a 3.7. ábrán. A keresés menetének végigkövetéséhez jelölje Qi ⊆ Q a keresés megadásához szolgáló halmazt, és Ri ⊆ R pedig az ezekhez tartozó eredményhalmazokat. A Ci párok az i-edik lépéshez tartozó koncepciókat jelölik.
17
3.6. Keresés a bővített kontextusban
({g1 , g2 , g3 , g4 }, ∅)
({g1 , g2 , g4 }, {m2 })
({g1 , g3 , g4 }, {m1 })
({g2 , g3 , g4 }, {m3 })
({g1 , g4 }, {m2 , m1 })
({g2 , g4 }, {m2 , m3 })
({g3 , g4 }, {m1 , m3 })
({g1 }, {m2 , m3 , m1 })
({g2 }, {m1 , m2 , m3 })
({g4 }, {m2 , m1 , m3 })
({g3 }, {m1 , m2 , m3 })
(∅, {m1 , m2 , m3 , m1 , m2 , m3 }) 3.7. ábra. A kibővített relációhoz tartozó koncepcióháló.
Kiindulási pontként tekintsük a Q0 = ∅ halmazt. Az ehhez tartozó eredményhalmaz az R0 = Q00 = G. A G deriválásával visszakapjuk az üres halmazt, tehát C0 = ({g1 , g2 , g3 , g4 }, ∅). Első lépésben keressük azon objektumokat, melyek az m2 attribútummal rendelkeznek. Ez azt jelenti, hogy Q1 = {m2 }, vagyis R1 = {g1 , g2 , g4 }, amelyből C1 = ({g1 , g2 , g4 }, {m2 }). Második lépésben zárjuk ki az eredményből azon objektumokat, melyek rendelkeznek az m3 tulajdonsággal. Ez a Q2 = {m2 , m3 }, R2 = {g2 , g4 } halmazokat és a C2 = ({g2 , g4 }, {m2 , m3 }) fogalmat eredményezi. Tegyük fel, hogy tovább szeretnénk szűkíteni az eredményhalmazt az m1 attribútum szerint. Ekkor Q3 = {m1 , m2 , m3 } adja a keresést, R3 = {g2 } halmaz lesz az eredmény, az aktuális fogalom pedig a C3 = ({g2 }, {m1 , m2 , m3 }). A keresésben már mind a három attribútumot felhasználtuk, így további szűkítés nem lehetséges úgy, hogy ne üres eredményhalmazt kapjunk. Jól látható, hogy a C1 , C2 , C3 , C4 koncepciók egy útvonalat jelölnek ki a fogalomhálóban. A kontextus bővítésének köszönhetően a fogalomhálóban a keresés hasonló a fában való kereséssel. A keresésben elvileg diszjunktív művelet is lehet. Az ezekkel kapott R eredményhalmazok mindig felírhatók R = R1 ∪ R2 alakban. A művelet használata azért nem javasolt, mert így a fogalom nem lenne egyértelmű, és az a lehetőség veszne el, hogy az eredményhez közvetlenül hozzá lehessen adni objektumokat.
18
4. fejezet
A kontextus kezelési módjai 4.1.
A kontextushoz tartozó adatok
A dokumentumokhoz, címkékhez és kapcsolataikhoz tartozó adatok kezelési módjának helyes megválasztása kiemelt fontosságú feladat. Alapvetően a kontextus tárolása, módosítása és a keresési műveletei határozzák meg a rendszer fő jellemzőit, mint például a futási időt és a tárigényt. A matematikai felírás alapján a kontextushoz egy objektumhalmaz (G), egy attribútumhalmaz (M ), és az ezeken értelmezett bináris reláció (I) tartozik. A megvalósításhoz ez még ebben a formában túlságosan általános, ezért meg kell határozni egy konkrétabb reprezentációt. Az objektumok és az attribútumok egyértelmű azonosításához kulcsértékekre van szükség. A címkék esetében ez lehetne a címke neve is, mivel az biztosan egyedi. Ennek használata a későbbiekben több problémát is okozhat, mivel a nevek elméletileg tetszőleges hosszúságúak lehetnek. Adható egy ésszerű felső korlát, amellyel már rögzített hosszúságúként viszont ez rossz tárkihasználtságot eredményez. A címkkeneveknek módosíthatóaknak kell lenniük. A kulcs értékének megváltoztatása nem tartozik a javasolt művelet közé, mivel sok hivatkozás esetén a végrehajtása költséges, továbbá bizonyos rendszerek nem is teszik lehetővé a szöveg típusú kulcsok használatát, így tehát célszerű egy, a névtől független numerikus azonosítót használni. A címkékhez tartoznia kell még egy, a típusuk leírására szolgáló szöveges adatmezőnek is. Ennek előnyeire a későbbi fejezetek adnak majd magyarázatot. A rendszer objektumai jelen esetben a fájlok. Szerencsés módon a címkék adatainak tárolásához felvázolt séma a fájlokra is alkalmazható. A név értelemszerűen a fájlnév. Erre nem szabad egyediségre vonatkozó feltételt szabni, tehát a külön kulcsérték mindenképpen szükséges. (A két kezelendő halmaz diszjunkt, ezért elegendő csak halmazon belül megkövetelni a kulcsok egyediségét.) Az állományok neve nem feltétlenül utal a fájl típusára a jelenlegi rendszerekben sem. A típus fájlnévtől való elkülönítése egyfajta rugalmasságot jelent, az állományok kezelési módjának meghatározását pedig egyszerűsíti. A fájlok és címkék közötti kapcsolatok tárolásához azok kulcsait kell egymáshoz rendelni. Ennek a megvalósítása adatmodelltől függően jelentősen különbözhet. A (G, M, I) bővített kontextuson értelmezett keresési műveletek hatékony megvalósítására kell törekedni. A következő pontokban három irányvonalról lesz szó. Az első a hagyományos relációs adatmodellre épül. Ezt egy dokumentumorientált módszer követi. A készen elérhető adatbázisok után a saját adattárolási struktúrát mutatom be.
19
4.2. Megvalósítás relációs adatbázissal
4.2.
Megvalósítás relációs adatbázissal
A címke nevének megadásával történő címkézés esetén három relációs adatmodellbeli megvalósítási mód terjedt el.1 Az első a címkék neveit egy külön oszlopban tárolja el. Ennek előnye, hogy csak egy táblára van hozzá szükség, és a lekérdezések is egyszerűek lesznek. A címkék nevei között ugyanúgy lehet keresni, mint bármilyen más szöveges mező esetében. Hátránya, hogy a címkék együttes hosszúságára a mező típusa adhat egy felső korlátot, illetve sok címke esetében a keresés hatékonyságával gondok lehetnek. Ennél egy rugalmasabb megoldás, ha a címkék egy külön táblába kerülnek, és onnan hivatkoznak a címkézendő elemekre. Ez már közelebb áll a normalizált megoldáshoz, és a címkék száma sem annyira kötött. A fájlok és címkék között több-több kapcsolat van. Ehhez a kézenfekvő megoldást egy kapcsolótábla beiktatása jelenti a fájlok és a címkék adatait tároló táblák közé (4.1. ábra).
4.1. ábra. Három táblából álló séma a címkézés relációs modellbeli megvalósításához.
Az adott címkékkel ellátott fájlok nevének lekérdezése ebben a szerkezetben a következő SQL lekérdezés formájában nézhet ki.
SELECT f . name FROM f i l e s f , f i l e _ t o _ t a g f t , t a g s t WHERE f . i d = f t . f i l e _ i d AND f t . tag_id = t . i d AND ( t . name IN ( ’ tag_1 ’ , ’ . . . ’ , ’ tag_N ’ ) ) GROUP BY f . i d HAVING COUNT( f . i d ) = N
Ebben az N a lekérdezésben szereplő címkék számát jelöli. A szerkezet szimmetrikus, tehát fájlok alapján is lekérdezhetjük a hozzájuk tartozó címkék neveit például a következő módon.
SELECT t . name FROM f i l e s f , f i l e _ t o _ t a g f t , t a g s t WHERE f . i d = f t . f i l e _ i d AND f t . tag_id = t . i d AND ( f . name IN ( ’ f i l e _ 1 ’ , ’ . . . ’ , ’ file_M ’ ) ) GROUP BY t . i d HAVING COUNT( t . i d ) = M
Az M itt az állományok száma. Az ilyen irányú lekérdezés kevésbé elterjedt. Akkor alkalmazható, ha olyan objektumaink vannak, amelyeket ki lehet jelölni, és a hozzájuk rendelt címkéket szeretnénk megkapni. Olyan lekérdezésre is szükség van, amelyikben megadhatjuk azon címkék neveit, melyeket nem szeretnénk, hogy az eredményként kapott fájlokon szerepeljenek. Ez az előzőek mintájára egy alszelekttel fogalmazható meg. 1 http://tagging.pui.ch/post/37027745720/tags-database-schemas
20
4.3. MongoDB használata
SELECT f . name FROM f i l e s f , f i l e _ t o _ t a g f t , t a g s t WHERE f . i d = f t . f i l e _ i d AND f t . tag_id = t . i d AND ( t . name IN ( ’ tag_1 ’ , ’ . . . ’ , ’ tag_N ’ ) ) AND ( f . i d NOT IN ( SELECT f . i d FROM f i l e s f , f i l e _ t o _ t a g f t , t a g s t WHERE f . i d = f t . f i l e _ i d AND f t . tag_id = t . i d AND t . name IN ( ’ minus_tag_1 ’ , ’ . . . ’ , ’ minus_tag_M ’ ) )) GROUP BY f . i d HAVING COUNT( f . i d ) = N
Ezek a lekérdezések röviden leírhatók és egyszerűek ugyan, de a join és halmazműveletek miatt nem hatékonyak.
4.3.
MongoDB használata
A MongoDB egy nyílt forráskódú dokumentum orientált adatbázis [KC10]. A dokumentumok ebben JSON objektumok, melyek kollekciókba szerveződnek. A fájlok és a címkék dokumentumként kezelhetők. Érdemes őket külön kollekcióban kezelni, bár a dokumentumok rugalmas szerkezete miatt ez akár egyben megoldható lenne. A következőkben egy lehetséges implementáció bemutatására kerül sor. Egy fájl adatainak tárolása a következőképpen történhet.
{ " _id " : O b j e c t I d ( " 50741 bb6e0656aba01000832 " ) , " name " : " Minta . pdf " , " type " : " a p p l i c a t i o n /x−pdf " , " references " : [ " 50741 bd3e0656ab901000802 " , " 50741 bdbe0656a1103000811 " ] }
Az első értékpár a dokumentum egyedi azonosítóját tartalmazza. A name a fájl nevének megadására szolgál, a type-ban pedig itt egy MIME kifejezés van, ami alapján a fájl megnyitásához a program kiválasztható. A references az adott fájlhoz rendelt címkék azonosítóinak listáját tartalmazza. A címkék megadási módja tulajdonképpen megegyezik ezzel, csak a tárolt értékek jelentése lesz más. Címkék alapján keresni az adatbázisban például az alábbi parancs kiadásával lehet.
db . f i l e s . f i n d ( { " r e f e r e n c e s " : { " $all " : [ " 50741 bd3e0656ab901000802 " , " 50741 bdbe0656a1103000810 " ] } } )
21
4.4. Saját tárolási struktúra
Ezzel egy olyan dokumentumot keresünk a files kollekcióban, melyre teljesül, hogy a lekérdezésben megadott references listát részeként tartalmazza. Az a lekérdezés, melyben már a mellőzendő címkék is megadásra kerülnek az $and logikai művelettel adható meg, például a következő formában.
db . f i l e s . f i n d ( { " r e f e r e n c e s " : { " $and " : [ { " references " : { " $all " : [ " 50741 bd3e0656ab901000802 " , " 50741 bdbe0656a1103000810 " ] }} , { " r e f e r e n c e s " : { " $nin " : [ " 50741 bdbe0656a1103000811 " ] }} ] } } )
Ebben a kialakításban az állomány és a címke egyenrangúnak tekinthető. A lekérdezések ezért mindkét irányba minimális módosításokkal működni fognak, viszont az adatok felvitelénél és a törlésénél ügyelni kell a hivatkozások beállítására. Elképzelhető olyan megoldás, melyben csak a fájlokhoz tartoznak címkék azonosítóiból álló listák.
4.4.
Saját tárolási struktúra
4.4.1.
Egyedi azonosítók
A kulcsértékek formátumának meghatározása a rendszer felépítésére és skálázhatóságára komoly hatással van. Az állományok és a címkék számát nem lehet előre tudni, ezért olyan megoldásokban érdemes gondolkozni, amely használható lesz akkor is, ha a rendszerben tárolt adatok mennyisége nagyságrendekkel növekedne. A választott megoldás változó hosszúságú kulcsértékeket használ. Az alapegysége a bájt, aminek az első bitje jelzi, hogy folytatódik-e még a kulcs. A kulcs általános felépítése látható a 4.2 ábrán. 1
...
1
0
4.2. ábra. A változó hosszúságú kulcs szerkezete. A bájtok elején lévő bitek kötöttek a láncolás miatt, a többi bit szolgál a kulcs értékének tárolására.
A kulcs egy 128-as számrendszerben felírt számhoz hasonló. Ami lényeges különbség, hogy itt a nulla értéket nem lehet lehagyni a számjegy elejéről. Például a 0x00, 0x8000, 0x808000 (hexadecimális alakban felírt) értékek különböző kulcsértékeknek számítanak. A láncoláshoz használt bit nem jelent nagy plusz költséget. Nagyságrendileg például a maximum 4 hosszúságú kulcsokból 270549120 van, ami egy átlagos asztali környezetben már elegendő lehet az állományok azonosításához. A 0x00 értéket több ok miatt is érdemes speciális jelentéssel felruházni. Az egyik például, hogy így az értékeket közvetlenül egymás után lehet tárolni úgy, hogy a lista végét ez az érték jelzi. A kulcsok kezeléséhez szükséges alapműveleteket egy külön Id nevű osztály látja el. Az osztály felépítése a 4.3. ábrán látható. A size metódus a kulcs hosszát adja vissza. A copy metódus egy másolatot készít a paraméterében megadott kulcsról. A listSize a kulcsértékeket tartalmazó tömbök méretét számítja ki. A kulcsok nagyság szerint sorba rendezhetők. Ennek egyszerűbbé tételére a compare metódus két kulcsértéket össze tud hasonlítani, és −1, 0 vagy 1 értékkel tér vissza, annak megfelelően, hogy az első kulcs kisebb, egyenlő vagy nagyobb mint a második. 22
4.4. Saját tárolási struktúra
4.3. ábra. Az Id osztály metódusai.
A kulcsérték inkrementálásához az increment metódust célszerű használni. Ez egy új kulcsértéket ad vissza, mely a paraméterben szereplőt követi a rendezés szerint. (Az értéket közvetlenül növelni azért nem lehet, mert előfordulhat, hogy a növelést követően a kulcs hossza is változik.) A read és a toString metódusokkal a szöveges konverziók végezhetők el. A kulcs szöveges formátuma a keret elhagyásával kapott 7 bites egységes tizes számrendszerbeli alakjából áll ’/’ jelekkel összekapcsolva, például 0/32/11. 4.4.2.
Kifejezések és elemek
Az állományok és címkék adatait egységesen kifejezésekként, Expression objektumokként kezeli a program. Ennek azonosítója (id), neve (name) és típusa (type) van. A mezők értékének jelentése változhat attól függően, hogy fájlról vagy címkéről van-e szó. A két típus közötti elkülönítés érdekében az Expression-ből származik a File és a Tag osztály (4.4 ábra). Ennek elsősorban a függvények paraméterezésénél lesz jelentősége.
4.4. ábra. Az Expression, és a belőle származtatott osztályok főbb részei.
Az adatok tárolása szempontjából a két típus egységesen kezelhető. Erre az Element származtatott osztály szolgál. Ez a references tömbjében megadott kulcsértékekkel hivatkozni tud a más elemekre. Hivatkozásokat hozzáadni és eltávolítani az addReference illetve a removeReference metódusokkal lehet. A hivatkozásokat a tömbben növekvő sorrendben tárolja, amelynek majd a keresésnél lesz fontos szerepe. Az adatait fájlba menteni a save metódussal, fálból olvasni pedig a load metódussal lehet.
23
4.4. Saját tárolási struktúra
4.4.3.
Gyűjtemények
Az elemek gyűjteményekbe rendezéséhez a Collection osztály használható (4.5. ábra). Ez ténylegesen nem tárolja azokat, csak egy hozzáférési réteget biztosít. Egyik fő feladata, hogy nyilvántartja a szabad kulcsértékeket. Ehhez egy vermet készít, amelybe új szabad azonosítót berakni a pushFreeId, kivenni pedig a popFreeId metódussal lehet. Egy új elem létrehozásakor a getFreeId metódusa adja a következő szabad azonosítót. Törléskor a releaseId-t szükséges meghívni az azonosító felszabadításához.
4.5. ábra. A Collection osztály felépítése.
A másik fontos feladat az azonosítók útvonalakra való leképzése a getPath metódussal. Az elemek a fájlrendszerben külön fájlként jelennek meg. A gyűjtemény egy speciális jegyzékstruktúra, amelynek a gyökerét a rootDirectory adattag tárolja. Az azonosító utolsó bájtjának 10-es számrendszerbeli alakja adja a fájl nevét. A megelőző bájtokból (ha vannak) a fájlhoz vezető útvonal képezhető. Az első bitek csak a láncolás miatt fontosak, azt elhagyva, a fájlnévhez hasonlóan lehet előállítani a jegyzékneveket. A 4.6 ábrán a jegyzékstruktúra felépítésének a vázlata látható. rootDirectory
0.ext
1.ext
0.ext
...
1.ext
0.ext
127.ext
...
1.ext
0
1
127.ext
...
0
127.ext
0
...
127
1
...
127
1
...
127
4.6. ábra. Az elemek tárolásához használt jegyzékstruktúra vázlata.
A fájlok kiterjesztése kollekciónként kötött. A struktúra gyökerét és a kiterjesztést a konstruktorban lehet megadni. A provideDirectory metódus a jegyzékek kezelését egyszerűsíti, ellenőrzi a jegyzék meglétét, és automatikusan létrehozza amennyiben az hiányozna. 24
4.4. Saját tárolási struktúra
A szabad azonosítók nyilvántartásához a törölt elemek helyén egy olyan elem van, amelyik hivatkozik a következő szabad azonosítóra. Ez olyan fájlt jelent a tárolás szempontjából, amelynek a kiterjesztés helyett csak egy ’_’ utótagja van, és csak egy azonosító értéket tárol. Olvasásukhoz és írásukhoz készült a readId és writeId metódus. A lista első eleme a 0x00 kulcsértékhez tartozó elem. A freeIdListPath adattag tárolja ennek az elérési útvonalát. Adott kulcsértékhez tartozó szabad csomópont elérési útvonalát a getFreeNodePath metódus adja meg. 4.4.4.
Keresés név alapján
A címkéket a felhasználók szövegesen is megadhatják. Biztosítani kell egy hatékony adatszerkezetet, amely a nevekhez hozzá tudja rendelni az elemek azonosítóit. Ehhez alapvetően egy asszociatív tömb szükséges, ami lehet például prefix fa vagy önszervező kiegyensúlyozott fa is. A prefix fa (trie) egy olyan fastruktúra, amely a benne tárolt szavak közös prefixeit csak egy helyen tárolja. A közös prefixet követően vannak benne elágazások, méghozzá annyi irányba, amennyi lehetséges folytatás van. A tárolt értékek a fa leveleihez rendeltek. A fában a szöveges kifejezéshez tartozó értéket megkeresni úgy lehet, hogy a gyökérből kiindulva minden lépésben a következő karakternek megfelelő irányba kell továbbhaladni. Nem kötelező, de számos előnnyel jár, ha a fa rendezett, vagyis ha a gyerekelemek egy rendezési relációnak megfelelően követik egymást. A 4.7. ábrán egy olyan prefix fa látható, mely az eper, erdei, erdő, est, jeges, jegyzet, jel, jelentés, kép, könyv, kör és körút szavakat tárolja. A pont termináló karakterre azért van szükség, hogy az olyan szavakat is el lehessen helyezni a struktúrában, amely egy másik szó prefixe. A példában ilyen többek között a jel és a jelentés szó.
e
j
p
r
s
e
d
t
r
e
ő
.
i
.
.
.
k
e
ö
é
g
l .
p
n
r
.
y
.
e
y
s
z
n
v
.
e
t
.
t
é
.
s
e
. 4.7. ábra. Példa egy 12 kifejezést tartalmazó prefix fára.
A prefix fa konkrét megvalósításának több, egymástól jelentősen eltérő módja van. A karakterkészlet véges számú karakterből áll, ami egyben azt is megadja, hogy egy 25
4.4. Saját tárolási struktúra
csomópontnak maximum mennyi gyerekeleme lehet. A legegyszerűbb megoldás minden csomópontban egy tömböt tárol, amelynek az indexeléséhez a karaktereket használja. A tömbben a gyerekelemek mutatói lesznek. A keresés így nagyon gyors lesz, és az algoritmusok is egyszerűen leírhatók, viszont a tárigény szempontjából nem szerencsés a megoldás. Ha a fában aránylag kevés elágazás van, akkor a tömb feleslegesen foglalja a területet. A fát azonos típusú elemek láncolt listáiból is fel lehet építeni. Minden listaelemnek rendelkeznie kell egy gyerek és egy jobbtestvér mutatóval, illetve tárolnia kell az adott karakter értékét. A szülő és a bal oldali testvér mutatóinak tárolása egyszerűsít az algoritmusokon ugyan, viszont a tárigényt közel duplázza. Sajnos már a két pointeres változatnál is problémák merülnek fel. A tárolandó karakter általában 1 bájton elfér. Egy 64 bites rendszer tekintve egy mutató 8 bájtot foglal, amivel tehát egy csomópont mérete 17 bájt lenne. Tovább rontja a helyzetet, hogy ez a hardver oldaláról nem egy kényelmes kezelési egység, így a fordító a méretet 4 vagy 8 többszörösére egészíti ki, ami miatt a csomópont mérete 24 bájt is lehet. A csomópontokban dinamikus tömböket használva a tárigény csökkenthető. Ez a műveleti idők növekedését vonja maga után, mivel a beszúrásnál és a törlésnél is újra kell allokálni a tömböket és az elemeik nagy részét is másolni kell. A gyerekmutatók keresésnél a lineáris keresés szintjén rontja a hatékonyságot. Az alkalmazásba az előbbi, dinamikus tömböket használó prefix fa került. A Trie osztály szöveges értékekhez tetszőleges (void* típusú) mutatókat rendel. Az osztálydiagramja a 4.8. ábrán látható.
4.8. ábra. A Trie, és a belőle származtatott IdTrie osztályok.
A TrieNode struktúrában két, azonosan size elemszámú tömbre mutató pointer van. A values a csomópontban választható további karaktereket tárolja, a children pedig ennek megfelelően a gyerekelemek mutatóit. A prefixfa gyökerének címe a Trie osztály root adattagjában van. Elemeket a fába beszúrni az insert, belőle törölni pedig a remove metódusokkal lehet. Az ősosztály tetszőleges típus kezelésére képes. Az elemeket item néven kezeli, azokat a fában megkeresni a find metódussal lehet. Az osztály implementációjában iteratív algoritmusok szerepelnek. Mivel a szülőmutatókat a fa nem tárolja, ezért ahol szükség lenne rá (például mélységi keresésnél) ott 26
4.4. Saját tárolási struktúra
egy vermet épít neki átmenetileg. A verem tetejére a parentStack mutat. Új csomópontot, mint szülőt beletenni a pushParent-tel lehet, a verem tetejéről levenni pedig a popParent-tel. Annak, hogy a fa kulcsokat tárol a fájlba mentésnél (save), illetve a fájlból olvasásnál (load) lesz jelentősége. A IdTrie az adatokat szöveges formában menti le. A fájlformátum úgy épül fel, hogy egy sorban van a kifejezés, és mögötte szóközzel elválasztva a kulcsérték. A kulcs értéke a gyűjteménynél bemutatott útvonal formájában jelenik meg. Az állomány egyes sorai tehát például a következőképpen nézhetnek ki.
j e g e s 1/78/107 j e g y z e t 7/62/65 j e l 9/10/125
A kifejezésben természetesen szóközök is lehetnek, mivel a végét az egész sorban lévő utolsó szóköz határozza meg. A szöveges formátum nem hatékony, viszont néhány százezer név és kulcsérték párnál még elfogadható időn belül elvégezhető a mentés és a betöltés. A helyes működés és a műveleti idők tesztelésére készült a test/unit_test.cpp állományban definiált TrieTest osztály (4.9. ábra).
4.9. ábra. A prefixfa tesztelésére szolgáló osztály.
A teszteléshez nagy mennyiségű szöveges kifejezésre volt szükség, amelyik címke neveként előfordulhat. Ilyeneket találhatunk például szótárfájlokban, vagy valamilyen kifejezésgyűjteményben. A teszteléshez a gyűjtemény választásánál szempontként szerepelt, hogy • ékezetes betűket, speciális karaktereket is tartalmazzon. Ezekkel gyakran probléma szokott lenni, így már a tesztelés kezdeti szakaszában jobb felkészülni ezekre. • A kifejezések változatos hosszúságúak legyenek. A hosszú címkenevek a rendszerezés szempontjából később biztosan nem lesznek szerencsések, viszont a Trie osztály tetszőleges hosszúságú szöveges értékekhez készült. • Tartalmazzon ismétlődő kifejezéseket is. Erre azért érdemes külön figyelmet fordítani, mert a szógyűjteményekre ez nem jellemző, viszont az algoritmusokat az ismétlődésekre is fel kell készíteni. A választott gyűjtemény (tag_samples.txt) 174525 magyar nyelvű, de nem feltétlenül értelmes kifejezést tartalmaz. A gyűjteményben 116746 különböző kifejezés van. A TrieTest osztály a load metódusában a samples vektorba tölti fel az egyes sorokban lévő kifejezéseket. Az insertTest a vektor elemein végighalad, és mindegyiket megpróbálja beszúrni a fába. A következő lépésben mindegyiket ellenőrzi, hogy valóban 27
4.4. Saját tárolási struktúra
benne vannak-e a fában. A removeTest sorban törli a fából az elemeket, és minden törlésnél vizsgálja, hogy az valóban eltávolításra került-e. A saveAndLoadTest a fájlba mentésre és a betöltésre vonatkozik. Ez a fát feltölti elemekkel, és elmenti a test.trie fájlba, majd innen visszaolvasás után ellenőrzi, hogy mindegyiket meg tudja-e találni. A kifejezésekhez tartozó kulcsok a 0/0/1-gyel kezdődnek, és sorban egyesével növekednek. A metódusok akkor térnek vissza igaz értékkel, ha sikeres volt a teszt. Az asszociatív tömb egy másik, szintén gyakori megvalósítási módja a piros-fekete fa. A C++ szabványos sablonok között a map is ezt a struktúrát használja. A szükséges műveletekkel a map is rendelkezik, így össze lehet hasonlítani, hogy a két struktúra közül melyiket, és milyen okok miatt lenne célszerű használni. A tesztosztály rbTreeTimes és trieTimes metódusa a beszúrás és keresés sebességét méri. A tesztek mérik a beszúrás és a keresés idejét is. Ezek eredményei grafikus formában a 4.10 és a 4.11. ábrán láthatóak. A mérési pontok 10000 beszúrásonként, illetve keresésenként következtek egymás után, az időegység pedig másodperc volt. A teszt is igazolta, hogy mindkét művelet konstans idejű mindkét adatstruktúra esetében. A prefix fa eredményei rosszabbak ugyan, viszont lényegesen nem marad el a piros-fekete fa mögött. A grafikonok görbéin vannak nagyobb törések. Ezeket a memóriafoglalás időigénye, illetve a szavak hosszával arányos műveleti idők okozzák.
4.10. ábra. A prefix és piros-fekete fába való beszúrás időigénye (10000 elemenként, másodpercben megadva).
A prefix fák alkalmazásának a későbbiekre nézve vannak további előnyei is. Ilyen például, hogy csak egy prefix alapján is lehet keresni benne. Ezzel megoldható a kifejezések automatikus kiegészítése. A fa csomópontjaihoz gyakoriságokat vagy valószínűségeket is rendelhetünk. Ennek segítségével az adott prefixel kezdődő szavakat a szerint lehet rendezni, hogy melyik a leginkább várható. A hatékonyság javításához számos lehetőség adott. A beszúrás gyorsításához előre le lehet foglalni nagyobb méretű tömböket a csomópontokban. Ez a gyökérnél jelentheti akár az összes lehetséges karakternek megfelelő méretet (256 elemet), míg a levelek felé közeledve egyre kevesebbet. A kereséshez a csomópontban lévő lineáris keresést ki lehet cserélni binárisra is, mivel rendezett a fa. Az adatszerkezet nagy memóriaigényét csökkenteni a hosszú, elágazás nélküli szakaszok összevonásával lehet. Ez egy bevett gyakorlat. Az ilyen struktúrát kompakt prefix fának (compact prefix tree), radix fának (radix trie) vagy patricia trienek (Practical Algorithm to Retrieve Information Coded 28
4.4. Saját tárolási struktúra
4.11. ábra. A prefix és piros-fekete fában való keresés időigénye (10000 keresésenként, másodpercben megadva).
in Alphanumeric) nevezzük [DM68]. 4.4.5.
Adatbázisobjektum
Az eddig bemutatott osztályok az adatok tárolásának és visszakeresésének részfeladatait külön oldották meg. A Database osztály ezeket összehangolja, és egy felületet biztosít a kezelésükhöz (4.12. ábra). Az adatbázis három gyűjteményt kezel. A fileCollection az állományok adatait, a tagCollection a címkék adatait a storageCollection pedig magukat az állományokat tárolja. A címkék neveinek tárolására és keresésére szolgál a tagNames trie. Az adatbázis objektummal az adatokat cserélni File és Tag típusú objektumok formájában lehet. A lekérdezések során ezeket Element típusokra képzi le, de ez az objektum használata során nem látszik. Új fájlt beszúrni a insertFile, aktualizálni az updateFile, törölni pedig a removeFile metódusokkal lehet. A címkék esetében ugyanilyen feladatokat lát el az insertTag, updateTag és a removeTag metódus. A fájlok és a címkék közötti kapcsolatok hozzáadásához az insertRelation metódust használjuk. Ennek kétféle paraméterezése is van a szimmetria miatt. Bizonyos esetekben érdemes a társítást vagy a fájl, vagy a címke szempontjából megközelíteni. A kapcsolat törlésére megegyező paraméterezéssel a removeRelation-t lehet használni. Egy címkét név alapján lekérdezni az adatbázisból a findTagByName metódussal lehet. Ez az adatbázis objektum prefix fájában keresi meg a nevet, majd ebből készít egy új Tag objektumot. Egyidejűleg több címke is lekérdezhető a findTagsByPrefix metódussal. Ez első paraméterként a keresett címkék prefixét várja, ami lehet üres is. A limit paraméterrel a visszaadott címkék maximális száma határozható meg. Az állományok címkék alapján történő keresésére a findFiles metódus szolgál. Ennek paramétere a címkék és az ellentett címkék listája. Az eredmény File objektumok listája lesz. A keresés a következő nagyobb lépésekből áll. • A kereséshez használt két címkelistából Element típusokat tároló lista készül. Az átadott Tag objektumoknak érvényes azonosítókkal kell rendelkezniük. • A lekérdezést a query metódus valósítja meg. Ez már az azonosítók listáit várja, illetve azt a kollekciót (domain), amelyikben keresnie kell. 29
4.4. Saját tárolási struktúra
4.12. ábra. Az adatbázis osztály adattagjai és metódusai.
• A megadott azonosítók alapján beolvassa az Element objektumokat a kollekcióból. Kiválaszt egy hivatkozási tömböt (célszerűen a legrövidebbet), és abból készít egy láncolt listát. A többi hivatkozási tömbbel az intersect és a subtract metódusokkal szűri az elemeket a listából. Az intersect azokat az elemeket törli a listából, melyek nem szerepelnek a szűrési feltételként megadott tömbben, a subtract pedig éppen azokat amelyek egyeznek. • A query egy azonosító listával tér vissza. Ehhez még az adatbázis visszakeresi az elemeket, azokból kifejezéseket készít, és az így kapott eredménylistával tér vissza. A lekérdezési mód feltételezi, hogy a lekérdezésben mindig szerepel egy nem ellentett címke. A későbbiekben majd látható lesz, hogy ez egyáltalán nem jelent gondot, mivel legalább egy, vagy a felhasználóra vagy az adattárolóra vonatkozó címke mindig érvényben van a keresésben. Az adatbázis objektum a fájlok behozatalát és kimentését is biztosítja az importFile és exportFile metódusokkal. A fájlok megnyitásához a createLink metódussal link készíthető a paraméterben megadott helyre. Az adatbázis objektum tehát már képes ellátni a kontextus kezelésével járó feladatokat. A megvalósítás erősen kötődik a UNIX rendszerekhez az elemeknek és a címkék neveinek a tárolási és a linkek kezelési módja miatt.
30
5. fejezet
Parancssoros kezelőfelület A fájlok kezelésének egyik első, és a mai napig használatban lévő eszköze a parancssor. Ez a felhasználótól az utasításokat szöveges formában várja, azt értelmezi, majd szintén szöveges formában válaszol. Tipikusan a kiadott parancs a parancs nevéből és a paraméterezéséből áll. A következőkben szereplő parancsok is ezt a formát követik. Fájlkezelés kapcsán a fájlok neveinek listázására, a másolási, mozgatási és törlési műveletekre kell külön kitérni. Ezek bemutatása a feldolgozási folyamat szintjeinek megfelelően következik.
5.1.
A parancsok felépítése és használata
A parancssornak a parancs szintaktikáját és szemantikáját is ellenőrzi. Az ellenőrzéshez azt először tokenekre bontja. A tokenek adatainak tárolására egy struktúra jellegű Token osztály szolgál (5.1. ábra).
5.1. ábra. A struktúra jellegű token osztály adattagjai.
A tokenhez tartozó szöveges értéket a value mező tárolja. A TokenType mező értéke ID, PLAIN, PLUS, MINUS, NEGATED vagy BRACKET lehet. A tokeneket szóköz, vagy egyéb nem használt karakter választja el ott, ahol az elválasztás nem egyértelmű. A nem definiált karaktereket az értelmező egyszerűen kihagyja, azokra hibát nem jelez. Az ID a szöveges formában megadott kulcsérték. Ennek a szintaxis diagramja az 5.2. ábrán látható. A Number ebben egy [0; 127] intervallumon értelmezett egész számot jelöl.
5.2. ábra. A kulcs (Id) szöveges leírási módjának, és a kifejezés (Expression) szintaxis diagramja.
A PLAIN típusba a hagyományos, idézőjelek között megadott karakterlánc tartozik. A parancsokban fájlokat vagy címkéket kell egyértelműen azonosítani. A felhasználó 31
5.1. A parancsok felépítése és használata
szemszögéből a névvel való azonosítás az egyszerűbb. Erre a címkék esetében mindig van lehetőség, mivel azoknak egyedieknek kell lenniük, viszont a fájlokra ez nem feltétlenül érvényes. A keresési módszerből adódik, hogy ha megkövetelnénk a név egyediségét a fogalmakban, akkor az egész rendszerben nem lehetne két azonos nevű fájl sem. Ez nyilvánvalóan nem megfelelő megoldás, ezért az olyan esetekben, ahol a fájl azonosítása nem egyértelmű az egyedi azonosítóját kell használni. (Azonosító mindig szerepelhet a név helyett.) A későbbi szintaxis leírást egyszerűsítésének érdekében itt is bevezethetjük a kifejezést (Expression), amely az Id vagy Plain valamelyikét jelöli. A PLUS, MINUS és NEGATED olyan kifejezések, melyeket ’+’, ’-’ vagy ’!’ karakter előz meg (5.3. ábra).
5.3. ábra. A Plus, Minus és Negated tokenek szintaxis diagramja.
A BRACKET a ’[’ vagy ’]’ karakterek valamelyikét jelöli. Az eddigi elemek segítségével már az abszolút- és relatív útvonalak is definiálhatók (5.4. ábra). A címkékkel kapcsolatos műveletekhez a tag parancs használható. Ezt paraméter nélkül kiadva a kontextushoz tartozó címkék neveinek listáját kapjuk meg. A paraméterben abszolút vagy relatív útvonalat megadva az adott fogalomhoz lehet eljutni (5.5). Ezek a parancsok a jegyzékstruktúrában a cd (change directory) parancsnak felelnek meg.
5.4. ábra. Az abszolút- (AbsolutePath) és relatív útvonal (RelativePath) szintaxisa.
5.5. ábra. Címkék listázásának, és a fogalom váltásának parancsai abszolút- és relatív útvonallal.
Parancssorok esetében segíti a tájékozódást, ha az aktuális pozíció is feltüntetésre kerül. A prompt ezért az abszolút útvonalat is tartalmazza, amit egy kettőspont követ. Az eddig bevezetett parancssori elemek bemutatására a következő példát mutatjuk. [ ] : tag [ " kö r " , [ " kö r " , [ " kö r " , [ " k ép " ,
[ " kö r " , " k ép " ] " k ép " ] : ta g +" e r d e i " " k ép " , " e r d e i " ] : t ag ! " e r d e i " " k ép " , ! " e r d e i " ] : t a g −"kö r " −" e r d e i " ! " t é l " !" té l "]:
32
5.1. A parancsok felépítése és használata
Az első parancs egy abszolút útvonalat állít be, az utána következő három pedig relatívakat. Minden címke csak egyszer szerepelhet az útvonalban. A felkiáltójellel kezdődő megadás vagy egy új ellentett címkét ad hozzá az addigi útvonalhoz, vagy a már benne szereplőt negálja. Amennyiben az már negálva van, akkor az újabb negálásra nem fordul meg. Tulajdonképpen úgy kell tekinteni, mint ha felülírásra kerülne. A szemléletesebb példák érdekében érdemes itt megadni a fogalomhoz tartozó fájlok listázásának módját. Ez egyszerűen az ls vagy list paranccsal végezhető el.
[ " k ép " , ! " t é l " ] : l s 1/34 1/36 1/37
ő s z . png t a v a s z . png nyá r . png
Az első oszlopban az egyedi azonosítók vannak, a másodikban pedig a fájlok nevei. A címkenevek listázási formátuma nagyon hasonló.
[ " k ép " , ! " t é l " ] : t a g 120 11 14 0/80 0/81 0/82 0/83
erdei k ép kö r nyá r ő sz tavasz té l
A relatív útvonalban is szerepelhet azonosító, például a következő módon.
[ " k ép " , ! " t é l " ] : t a g +0/80 [ " k ép " , ! " t é l " , " nyá r " ] : l s 1/37
nyá r . png
A fájlok közös címkéinek lekérdezéséhez a fájlneveket a tag után kell megadni (5.6. ábra). A listában az aktuális fogalomhoz tartozó fájlokra lehet hivatkozni névvel, ha azok egyediek. Amennyiben a fogalom több azonos néven szereplő állományt tartalmazna, akkor az azonosítót kell használni.
5.6. ábra. A felsorolt állományokhoz tartozó közös címkék lekérdezése.
A fájlok közös címkéinek lekérdezésére példa az alábbi parancs.
[ " k ép " , ! " t é l " ] : t a g " t a v a s z . png " " nyá r . png " 11
k ép
33
5.1. A parancsok felépítése és használata
A fájlok mozgatásához használt parancsok tulajdonképpen már következnek az eddigiekből. A fogalom váltásához használt parancsokat kell kiegészíteni a fájlok listájával (5.7. ábra).
5.7. ábra. A megadott fájlok mozgatása abszolút- vagy relatív útvonallal.
A mozgatás itt mindössze átcímkézést jelent. Például a nyár.png fájlt a fénykép címkével alkotott szűkebb fogalomba áthelyezni az alábbi módon lehet.
[ " k ép " , " nyá r " ] : l s 1/37
nyá r . png
[ " k ép " , " nyá r " ] : t ag " nyá r . png " +" f é nyk ép " [ " k ép " , " nyá r " ] : t ag " nyá r . png " 11 0/80 1/46
k ép nyá r f é nyk ép
A szintaxis megengedi, hogy negált címkék is legyenek az útvonalakban áthelyezéskor. Ez itt furcsának tünhet, mivel negált címkét a fájlhoz hozzárendelni nem lehet. Erre egyrészt az egységesség miatt szükség van, másrészt pedig ha az adott áthelyezendő fájl rendelkezik egy olyan címkével amelyik negálva benne van a célként megadott fogalomban, akkor azt a címkét el kell távolítani a fájlról az áthelyezés során. Ennek a bemutatására a következő példa szolgál.
[ " k ép " , " nyá r " ] : t ag " nyá r . png " ! " t é l " ! " f é nyk ép " [ " k ép " , " nyá r " ] : t ag " nyá r . png " 11 0/80
k ép nyá r
A relatív útvonallal megadott áthelyezés csak módosítja az érintett címkéket, míg az abszolút útvonal esetében a címkelista cseréjéről van szó, például
[ " k ép " , " nyá r " ] : t ag " nyá r . png " [ " f o n t o s " , " t á j k ép " ] [ " k ép " , " nyá r " ] : t ag " nyá r . png " 58 0/165
fontos t á j k ép
34
5.2. Kapcsolat a befogadó fájlrendszerrel
A tag parancs szintaktikája viszonylag összetett, mivel az összes címkelistával kapcsolatos lekérdező és módosító műveletet ezzel lehet megvalósítani. A másolás és törlés már jóval egyszerűbb. Fájlokat másolni a cp vagy a copy paranccsal lehet. A paraméterezése megegyezik az áthelyezésével. A működésük annyiban tér el, hogy a másolást követően mindkét helyen meg lesz egy példányban az állomány, és függetlenül kezelhetőek a továbbiakban. Duplikátumok útvonal megadása nélkül készíthetők vele. Ez a sablonok használatánál lehet például hasznos, mint ahogy az alábbi rövid példa is mutatja.
[ " s a b l o n " , " LaTeX " ] : l s 0/76 0/90
j e g y z e t . tex prez . tex
[ " s a b l o n " , " LaTeX " ] : cp " p r e z . t e x " [ " s a b l o n " , " LaTeX " ] : l s 0/76 0/90 1/51
j e g y z e t . tex prez . tex prez . tex
[ " s a b l o n " , " LaTeX " ] : t ag 1/51 [ " e l őadá s " , " e l s ő vá l t o z a t " ]
A törléshez az rm vagy a remove parancsot lehet használni. Ezzel az aktuális fogalomhoz tartozó fájlokat lehet törölni a fájlok neveinek vagy azonosítóinak megadásával. Az összes fájl törléséhez a fájllista helyett paraméterként a ’*’ karaktert is meg lehet adni. Az átnevezés ebben a kialakításban nem oldható meg úgy, mint a jegyzékek esetében az mv utasítással. Ehhez itt külön be kell vezetni egy rename parancsot, ami első paraméterként az átnevezendő fájl elérését, másodikként pedig az új nevet várja. Ez a következőképpen nézhet ki.
[ " s a b l o n " , " LaTeX " ] : rename " p r e z . t e x " " p r e z e n t á c i ó . t e x "
Átnevezésre a címkék esetében is szükség lehet. Ez a rename tag utasítással végezhető el, például
[ " s a b l o n " , " LaTeX " ] : rename ta g " LaTeX " " l a t e x " [ " sablon " , " latex " ] :
5.2.
Kapcsolat a befogadó fájlrendszerrel
A címkézést használó rendszernek valamilyen módon fájlokat kell tudni cserélnie a hagyományos rendszerekkel. A fájlok importálásához az import parancs használható. Ennek első paramétere az útvonal, a második a fájl neve a harmadik pedig a típusa. Az így létrejött fájl az aktuális fogalomba kerül. Az import parancs használatát a következő példa mutatja be. [ " s a b l o n " , " l a t e x " ] : import " / Docs /sym . t e x " " sym . t e x " " t e x " 35
5.3. A parancsok értelmezése és végrehajtása
[ " sablon " , " latex " ] : l s 0/76 0/90 1/83
j e g y z e t . tex prezent á c i ó . tex sym . t e x
A fájlok kimentése hasonlóképpen történik az export paranccsal. Az exportálásához a kontextusban a fájl elérhetőségét és az új útvonalat kell megadni, például
[ " s a b l o n " , " l a t e x " ] : e x p o r t " j e g y z e t . t e x " " / Docs / j e g y z e t . t e x "
Az importálás és az exportálás is másolással jár. Amennyiben az adott fájl megnyitására lenne szükség egy link készítése hatékonyabb megoldás. Ehhez a link parancsot kell kiadni, aminek a paraméterezése teljesen megegyezik az exportáláséval. Az előbbi példa linkeléssel a következőképpen néz ki.
[ " s a b l o n " , " l a t e x " ] : l i n k " j e g y z e t . t e x " " / Docs / j e g y z e t . t e x "
Ez egy hard linket készít a megadott helyre, ami csak akkor hozható létre, ha azonos fájlrendszerben van, mint maga a címkézéses adatbázis.
5.3.
A parancsok értelmezése és végrehajtása
A szövegként érkező parancsok értelmezéséért a Command osztály a felelős (5.8. ábra).
5.8. ábra. A parancsok értelmezéséért felelős osztály felépítése.
A parse metódusában kell megadni a feldolgozandó parancsot. A feldolgozás sikerességét a visszatérési érték jelzi. Igaz értékkel tér vissza, ha rendben végre tudta hajtani. A parancs neve a commandName attribútumba kerül. A beolvasott fájlnevek a files, míg az útvonalhoz tartozó elemek a path listába kerülnek. Az absolute logikai érték jelzi, hogy a beolvasott parancsban abszolút vagy relatív útvonal szerepelt-e. Az aktuális fogalom nyilvántartásával és műveleteivel kapcsolatos adminisztrációt a Scope osztály végzi (5.9. ábra). Az aktuális lekérdezést QueryItem-ek listájában tárolja. Ebben benne vannak a címkék, illetve az isNegated logikai érték jelzi, hogy ellentett címkéről van-e szó. Ez az osztály tartja a kapcsolatot magával az adatbázissal a database adattagon keresztül. Itt már megjelenik az aktuális felhasználó jelzésére szolgáló címke is. Ezt a setUser metódussal lehet beállítani. A fájlok importálása, exportálása és linkelése az importFile, exportFile és linkFile metódusokkal hajtható végre. Az abszolút és relatív útvonal beállításához az absolutePath és relativePath metódusokat kell használni. Az aktuális fogalomra 36
5.3. A parancsok értelmezése és végrehajtása
5.9. ábra. Az aktuális fogalmat kezelő osztály.
jellemző abszolút útvonalat a getPath adja, a fogalomhoz tartozó fájlok listája pedig a getFiles metódussal kérdezhető le. A címkék neveihez a getTaglist illetve getCommonTags-t lehet használni. A többi metódus is tulajdonképpen közvetlenül megfeleltethető a már bemutatott műveleteknek. A parancssori felületet a Shell nevű osztály hozza létre (5.10. ábra).
5.10. ábra. A parancssort kezelő osztály vázlatos felépítése.
A parancssort elindítani a run metódusával lehet. Ezt követően az objektum csak minimális előfeldolgozás végez az interpret metódusában. A feladata mindössze a beolvasott parancs továbbítása a scope objektumnak. Ez olyan kivételes esetekben nem szükséges, mint például az exit parancsnál, amellyel ki lehet lépni a parancssorból.
37
6. fejezet
Grafikus felhasználói felület Az állományok kezeléséhez a felhasználók manapság már grafikus felületeket használnak. Alkalmazásonként ugyan vannak különbségek közöttük, de ennek ellenére a fő jellegzetességeik, és típusaik jól elkülöníthetőek. A legnépszerűbb az a változat, amelyik a fájlokat és jegyzékeket ikonokkal reprezentálja. Opcióként megjelenik a listás vagy fa struktúrájú megjelenítés is. Egy külön csoportot képeznek a kétpaneles (ortodox) fájlkezelők. Ennek jeles képviselői a Norton, a Volkov, a Midnight és a Total Commander. Az első három ugyan még karakteres felületet használ, viszont a fájlműveleteket bennük már kijelöléssel és közvetlen grafikus visszacsatolással lehet végrehajtani.
6.1.
A felhasználói felület elemei
A grafikus fájlkezelő felület megtervezésénél az eddig más rendszerekben már bevált módszerek és az újszerű, fogalmakra épülő elvi modell ötvözése volt a cél. Ennek eredménye az a 6.1. ábrán látható.
a
e
b
d
c
6.1. ábra. A fogalom alapú grafikus állománykezelő rendszer vázlatos felépítése a. az aktuális fogalom címkelistája b. új címke felviteléhez beviteli mező, c. címke javaslati lista, d. az eredményben szereplő állományok, e. ikon az állomány reprezentálására.
A bal-felső részben (a) a kereséshez használt címkék listája szerepel. Ez tulajdonképpen a parancssornál bemutatott prompt-nak feleltethető meg, vagy a jegyzékstruktúra esetében felső sávon elhelyezett útvonalnak. Ez alatt (b) van az új címkék megadásához a beviteli mező. Ez az új címkék felvitelénél fokozatosan lejjebb kerül. A bal oldali sáv alsó részén (c) azon címkék listáját jeleníti meg a program, amelyre a következő 38
6.3. Példa az egypaneles kialakításra
lépésben szükség lehet. Az ebben szereplő címkék meghatározásához több stratégiát egyidejűleg kell figyelembe venni. Ezek például a következők lehetnek. • Vélhetően arra a címkére lesz nagyobb szükség, amelyik több állományon szerepel. • A nemrégiben használt címkékre nagyobb valószínűséggel lesz szükség, mint a régebbiekre. • A fogalomhálóban a fogalmak közötti reláció szerinti rákövetkező fogalmakban megjelenő új címkék specializálják az aktuális fogalmat, ezért azokat érdemes előre venni. • A címke nevének gépelése közben a lehetséges címkék száma jelentősen csökkenthető akár a prefix akár a jellemző karakterkapcsolatok alapján. Ezek mellett a felhasználónak is célszerű lehetőséget biztosítani a lista összeállítási módjának befolyásolására. Ilyen lehet például, hogy bizonyos címkéket könyvjelzőszerűen rögzíthessen, vagy a ritkábban használt, de egyébként gyakori címkéket el tudja rejteni. A címkék listájának előállításában a kontextus vizsgálata is sokat segít. Ennek egyik módja a címkék hálóba szervezése lehet [KL07]. A felület nagyobbik részére (d) kerülnek a fogalomhoz tartozó állományok. Ezek megjeleníthetők a szokásos módon ikonokkal (e).
6.2.
A címkék típusai
A grafikus megjelenítés a parancssori megvalósításban bemutatott funkciók kényelmesebb, természetesebb elérési módját teszi lehetővé. A címkék típusait és használati módjukat, ezért itt pontosítani kell. Egy címke azon túl, hogy a címke nevének megjelenítésére szolgál, két fő részből áll, melynek feladata típusonként változhat (6.2. ábra). g
f
6.2. ábra. A címke sematikus rajza f . gomb a ritkábban használt funkciókhoz, g. a címke neve, és gomb a gyakrabban használt funkciókhoz.
A címke alapvető típusa az, amely az aktuális fogalom részét képezi. Ez lehet akár ellentett attribútumhoz tartozó is. A két gomb feladata itt nem válik külön. Bármelyik részére kattintva a címkét ki lehet venni a kereséshez használt címkék közül. Ezek alatt van az a címke, amely új címke felvitelére szolgál. A címke nevének begépelését követően vagy az enter billentyűt kell megnyomni vagy pedig a címkén látható plusz jelre kell kattintatni, hogy a megadott név az aktuális abszolút útvonalba belekerülhessen. A javaslatcímkékre kattintva a teljes név begépelése nélkül is kiválaszthatók a címkék. Ennek a bal szélére kattintva a negált címke kerül be a keresési kifejezésbe. Az eredményben szereplő ikonokat kijelölve a bal oldali sávon a címkék működése is változik. Az útvonal kiegészül az aktuálisan kijelölt fájlok abszolút útvonalban nem szereplő címkéivel. Az útvonalban szereplő címkék bal széle ekkor a címkék fájlokról való törlésére használható, a jobb oldali fele pedig úgy veszi ki a címkét a keresésből, hogy a fájlok kijelölése még érvényben maradjon. A címke hozzáadása ekkor már a kijelölt állományokra vonatkozik, a javaslatlistából választva is a címke már az állományra kerül. Ez azt is jelenti, hogy negált címkét nem lehet ekkor már megadni. Ennek a kezelési módnak megvan a szerencsés tulajdonsága, hogy a kijelölésben lévő fájlokat együtt lehet mozgatni a fogalmak között akár több lépésen keresztül is. 39
6.5. További funkciók
6.3.
Példa az egypaneles kialakításra
A 6.3. ábrán egy példa látható a felhasználói felületre. Itt az útvonalban a project, python és converter címkék vannak megadva. A keresés eredménye itt 10 fájl. Ezek mindegyikén biztosan szerepel az előbbi három címke.
6.3. ábra. Példa az egypaneles felhasználói felületre.
Az állományokon lévő, útvonalhoz nem tartozó címkéket kijelöléssel nézhetjük meg. A converter.py nevű fájlt kijelölve a 6.4. ábrán látható eredményt kapjuk. Az állományon öt címke van. A címkék és a kijelölés színe is utal arra, hogy mely címkék tartoznak a kereséshez, és melyek a fájlhoz. A beviteli mező és a javaslatok színe is változik. Ez szintén nem csak az egységes szinezet miatt van, hanem mert ez is jelzi a megváltozott működést.
6.4.
A kétpaneles változat előnyei
A másolási és áthelyezési műveletek szempontjából előnyös, ha egyszerre látható a forrás és a cél. Jegyzékek, jelen esetben pedig fogalmak összehasonlításakor is kedvező. A 6.5. ábrán egymás mellett látható két fogalom a hozzá tartozó címkékkel és állományokkal. A bal oldalon egy Python projekthez tartozó állományok vannak, a jobb oldalon pedig Python szkriptek. Láthatóan a converter.py és a test.py nem tartozik a szkriptek közé, mivel csak a python címke van hozzájuk rendelve. A keresési egyszerű módjának köszönhetően be lehet „másolni” az állományokat oda, ahol legközelebb keresni fogjuk. A jegyzékstruktúra böngészésére is alkalmassá tehető a bal oldali sáv. Az analógiának megfelelően a címkék helyén az aktuális jegyzékhez vezető útvonalon lévő jegyzékneveknek kell szerepelni, a javaslati listában pedig az aljegyzékeknek. Két panel esetén az importálás és az exportálás is lényegesen egyszerűbb ebben a formában. 40
6.7. Felhasználói tesztek
6.4. ábra. A kijelölés hatására a címkék funkciója megváltozik.
6.5.
További funkciók
A grafikus felület számos további funkcióval bővíthető. A fogalmak maguk halmazpárok, így az eddigiekben az eredményhalmaz rendezettségével nem kellett külön foglalkozni. A fájlokhoz érdemes még további adatokat hozzárendelni, mint például a létrehozási, elérési és módosítási dátumok, a fájlméret, vagy a használati gyakoriság. Bizonyos esetekben ezek segítségével hatékonyabban lehet keresni. Könyvjelzők alkalmazhatók akár címke akár fogalmak szintjén is. A címkék alapján történő keresés egyik előnye éppen az, hogy a fájlokhoz vezető útvonal lerövödíthető, ha tudjuk, hogy mit keresünk. Megfelelően karbantartott könyvjelzőkkel ez még tovább javítható. Integrált asztali környezet esetében egy lomtárba kerülnek az állományok mielőtt véglegesen törölnénk azokat. Mivel a törlési műveletre itt is szükség van, ezért a lomtárról is érdemes gondoskodni. Ez megoldható az asztali környezetbe való integrációval. Címkézés esetén célszerűbb egy lomtár címkét alkalmazni. A fájlokat törléskor ezzel a címkével kell ellátni, így a lomtárban lévő fájlok egyben lekérdezhetők és törölhetők. Az általános lekérdezésekben, amelyek nem kifejezetten a lomtárra vonatkoznak a lomtár címke ellentettjének kell szerepelnie.
6.6.
Implementációs lehetőségek
A fájlkezelő alkalmazás grafikus implementációjához először a megfelelő, felhasználói felületek készítéséhez alkalmas függvénykönyvtár (widget toolkit) kiválasztása szükség. Célszerű platformfüggetlen megoldásokban gondolkodni, így például a Qt, a GTK, a wxWidget vagy az FLTK jöhetnek számításba.
41
6.7. Felhasználói tesztek
6.5. ábra. Példa a kétpaneles felhasználói felületre.
6.7.
Felhasználói tesztek
Egyelőre csak ad-hoc jellegű felhasználói tesztekre került sor. Ezek a grafikus felhasználói felület tesztelésére koncentráltak. A fő kérdés az volt, hogy mennyire érthető a felület felépítése és működése egy átlagos felhasználó számára. Készült egy egyszerűbb webalkalmazás prototípus, melyről egy kép a 6.6. ábrán látható. A kontextus tárolását PHP szkriptek és MongoDB segítségével oldja meg [SF12]. Egy panelt és egy fájl kijelölését támogatja a jelenlegi változat.
6.6. ábra. Az alkalmazás prototípusának felhasználói felülete.
A visszajelzések alapján a felhasználói felület újszerűsége és az alkalmazott matematikai modell együtt azt sejteti, hogy a használati mód elsajátítása komoly erőfeszítéseket igényel. A fogalomhálónak és a műveleteinek megértése feltételez némi matematikai jártasságot, viszont az állományok kezeléséhez ezek ismerete nem szükséges. 42
6.7. Felhasználói tesztek
Számítástechnikával intenzíven foglalkozó felhasználók esetében pozitív visszajelzés volt, hogy találkoztak már a kategorizálási és visszakeresési problémák valamelyikével. A megoldási móddal kapcsolatban ekkor inkább a későbbi integrációval és rendszerek közötti átjárhatósággal kapcsolatos kérdések merültek fel. A későbbi felhasználói tesztekhez alapkövetelmény, hogy legyen egy kézikönyv, amely példákon keresztül részletesen elmagyarázza a rendszer használati módját. Ezt követően feladatokat kell összeállítani ahhoz, hogy az állományok új típusú szervezési módját a hagyományossal össze lehessen mérni. Ebben szerepelnie kell a gyakran használt fájlműveleteknek. Fontos tényező a műveletek elvégzésére fordított idő, illetve a felhasználói interakció igénye is. Mindkettőt a hatékonyság érdekében minimalizálni kell. A tesztek eredményeinek és a felhasználói visszajelzéseknek megfelelően a felületet szükség esetén változtatni kell. Például opcionális elemek hozzáadásával a módszer az egyéni fehasználói igényeknek megfelelően testreszabható lesz.
43
7. fejezet
Fogalom alapú fájlrendszer A fogalom alapú állománykezelés eddig egy szeparált, implementáció tekintetében a jegyzékstruktúrára épülő megoldást jelentett. Ez a fejezetben az új megközelítés alkalmazhatóságát mutatja be az operációs rendszerek és a szoftverfejlesztés területén.
7.1.
Felhasználókezelés
A többfelhasználós rendszerekben a jogosultságok kezelése, a felhasználók adatainak védelme már a fájlrendszer szintjén megjelenik. A jegyzékek jogosultságainak beállításával a struktúra jól elkülöníthető részekre bontható, a csoportok létrehozásával pedig a kategorizálási probléma megoldott. Érdemes azt megvizsgálni, hogy a dolgozatban bemutatott modell mennyiben alkalmas hasonló feladatok ellátására, és mely esetekben jelenthet könnyebbséget vagy nehézséget az alkalmazása. A címkézés a felhasználók csoportokba rendezését eredendően támogatja. Ez a fastruktúrára is igaz, ha a felhasználói fiókok kezelésére gondolunk. A címkézés többet jelent annyiban, hogy külön csoportok létrehozása nélkül, explicit módon szabályozni lehet a hozzáférést az állományokhoz. A fájl tulajdonosának jelzéséhez speciális (user típusú) címkékre van szükség. Ez a user1 nevű felhasználó esetében a parancssorban a következőképpen jelenik meg.
[@" u s e r 1 " ] : t a g −@" u s e r 1 " NOTE: You cannot remove u s e r t ag ! [@" u s e r 1 " ] :
Ez egy olyan címke, amelyet az aktuális felhasználó nem tud eltávolítani. Rendszergazdai jogkörben ilyen kötöttség nincs. Más felhasználói címkék hozzáadásával a fájlok megosztása is lehetséges, például a következő parancs formájában.
[@" u s e r 1 " ] : s h a r e " t u t o r i a l . pdf " +@" u s e r 2 " [@" u s e r 1 " ] : t a g " t u t o r i a l . pdf " 1/74 0/8 0/9 3/11
pdf @user1 @user2 tutorial
44
7.2. Háttértárak kezelése
A tutorial.pdf fájl így már a user2 nevű felhasználó számára is elérhetővé válik. A jogosultságok szabályozása mellett a felhasználók egyedi beállításainak kezelésével is foglalkozni kell. UNIX rendszerekben erre a feladatra a home jegyzékben azokat a fájlokat és jegyzékeket használják első sorban, amelyek neve ponttal kezdődik. Ezek az állományok konfigurációjához szükségesek. Az állomány így az érintett alkalmazáshoz is tartozik, ezért megosztott fájlként kezelhető. Az alkalmazást elindítva a felhasználó alapján egyértelműek lesznek a konfigurációs állományok. A rejtett fájl helyett itt célszerűbb azt konfigurációsként feltüntetni, mivel az a használati módjára is utal. Rejtett fájlokra szükség lehet még a felhasználókhoz tartozó, de általuk nem hozzáférhető esetekben is, mint például a felhasználói kvóta beállításai. Ezek szintén konfigurációsak, a felhasználóhoz is tartoznak, viszont azokhoz nem szabad hozzáférést biztosítani. Ez úgy oldható meg, hogy az állományhoz a rendszer vagy rendszergazda felhasználói címkéjét rendeljük, példál az alábbi módon.
[@" system " , " quota " ] : l s 41/20 41/21
quota . c o n f quota . c o n f
[@" system " , " quota " ] : t ag +@" u s e r 1 " [@" system " , " quota " , @" u s e r 1 " ] : l s 41/20
quota . c o n f
Ez a megoldás a rendszergazda számára a felhasználó és a konfiguráció típusa alapján is rendszerezhetővé teszi az állományokat.
7.2.
Háttértárak kezelése
A háttértár jelzéséhez szintén egy speciális címke használható, ami azt jelzi, hogy az adott fájl melyik meghajtóhoz tartozik. A drive1 nevű tetszőleges típusú meghajtón lévő fájlok listázásához az alábbi parancsokat kell megadni.
[@" u s e r 1 " ] : t a g +%"d r i v e 1 " [@" u s e r 1 " , %" d r i v e 1 " ] : l s
A másolási és az áthelyezési művelet ezen címke módosításaként értelmezhető. Egy másolási műveletet mutat be a következő parancs.
[@" u s e r 1 " ] : t a g " backup . dat " +%"d r i v e 1 "
A fájlrendszerben az összes elérhető állományt egy kontextusban kezeli. A promptban ezért nem jelenik meg külön, mivel mindegyik beletartozik. Amennyiben csak az egyik háttértárral szeretnénk foglalkozni az is hozzáadható a keresési kifejezéshez a szokásos módon.
[@" u s e r 1 " ] : t a g +%"d r i v e 1 " [@" u s e r 1 " , %" d r i v e 1 " ] :
45
7.3. Programok felépítése
A különböző forrásokból származó állományokat és címkéiket egy kontextusnak kell tekinteni, amely problémákat vet fel. A részkontextusokat egy kontextusba átszervezni nem célszerű. Rugalmasabb megoldást biztosít, ha mindegyikben elvégezzük ugyanazt a lekérdezést, majd a végén az eredményeiket összesítjük. A háttértárat jelölő címkével mindegyik állománynak rendelkeznie kell. A törlés ennek ismeretében úgy is megfogalmazható, hogy mindegyik ilyen címkét eltávolítjuk az állományról, például a következő módon.
[@" u s e r 1 " ] : t a g " backup . dat " 5/13 5/70 48
backup dat %d r i v e 1
[@" u s e r 1 " ] : t a g " backup . dat " −%"d r i v e 1 "
Egy állományon több fizikális hely megadására szolgáló címke lehet. Ezzel a biztonsági másolatok kezelése megoldható, mivel így a rendszer a fájl tartalmát szinkronizálni fogja.
7.3.
Programok felépítése
A programok lefordítása, linkelése, telepítése és konfigurációja kötődik a jegyzékstruktúrához. A make program esetében egy érdekes kérdés, hogy a fordítás során keletkező ideiglenes állományok hová is kerüljenek. Az egyik megoldás az, hogy a fordítás során létrejött fájlok a forrásfájlok mellé kerülnek. A másik megközelítés a jegyzékstruktúráról készít egy másolatot, és abba helyezi el őket. A fogalom alapú megközelítésben ez problémaként nem jelenik meg, mivel csak egy újabb csoportosítási mód hozzáadását igényli. Példaként tekintsünk egy egyszerű C++ programot, amelyhez a main.cpp, App.h, App.cpp, Gui.h és Gui.cpp forrásállományok tartoznak. A program összeállítási módját a Makefile írja le. A fordítás során .o kiterjesztésű fájlok keletkeznek, melyekből a linker egy app nevű futtatható állományt állít össze. A fordítás lépései és a fájlok az alábbiak szerint alakulnak. [@" u s e r 1 " , " app " ] : l s 7/63 7/62 7/65 7/64 7/60 7/61
App . cpp App . h Gui . cpp Gui . h main . cpp Makefile
[@" u s e r 1 " , " app " ] : make [@" u s e r 1 " , " app " ] : l s 45/6 7/63 7/62 45/3
app App . cpp App . h App . o 46
7.4. Programok telepítése és konfigurációja
7/65 7/64 45/4 7/60 45/5 7/61
Gui . cpp Gui . h Gui . o main . cpp main . o Makefile
[@" u s e r 1 " , " app " ] : t a g +" o b j e c t " [@" u s e r 1 " , " app " , " o b j e c t " ] : l s 45/3 45/4 45/5
App . o Gui . o main . o
[@" u s e r 1 " , " app " , " o b j e c t " ] : t a g ! " o b j e c t " [@" u s e r 1 " , " app " , ! " o b j e c t " ] : l s 45/6 7/63 7/62 7/65 7/64 7/60 7/61
app App . cpp App . h Gui . cpp Gui . h main . cpp Makefile
A fordítás során keletkezett fájlok tehát jól elkülöníthetőek a forrásfájloktól és a futtatható állománytól. Tartozik hozzájuk egy külön fogalom, így a törlésük is egyszerűen elvégezhető.
7.4.
Programok telepítése és konfigurációja
A csomagkezelő programok a csomagokhoz tartozó fájlokat a fájlrendszerben valamilyen szempont szerint kategorizálják [RR04]. Az elterjedt megoldás, hogy a fájlok típusát veszik alapul, és ennek megfelelően kerülnek például a bináris fájlok a /bin jegyzékbe, a függvénykönyvtárak pedig a /lib-be. A típus mellett más szempontokat is érvényesíteni kellett a fájlrendszer kialakításakor, így megjelent benne például az /sbin, usr/bin, usr/sbin és usr/lib. Ezek a fastruktúra kategorizálási problémájára utalnak, mivel például bin jegyzékek mindegyike futtatható binárisokat tartalmaz, így egy csoportként lenne célszerű őket kezelni. A fogalom alapú megközelítés ezt a problémát is megoldja. A futtatható állományokhoz a executable címkét rendelhetjük. A hagyományos PATH környezeti változóra sincs szükség, mivel tekinthetjük úgy, hogy a parancssorból, tetszőleges helyről elérhető futtatható állományoknak a [@"system", "executable"] útvonallal megadott fogalomhoz kell tartoznia. A programokhoz tartozó állományok egy egységként is kezelhetőek lesznek ezzel a megoldással. A forrásfájlok, dokumentációk, konfigurációs állományok alkalmazásonként és típusonként is csoportosíthatók. Az Apache webszerverhez tartozó összes fájl például a [@"system", "program", "apache"] útvonalon lesz. Ezen belül például a • [@"system", "program", "apache", "src"]: forrásfájlok, 47
7.6. Verziókezelés támogatása
• [@"system", "program", "apache", "man"]: kézikönyvek, • [@"system", "program", "apache", "executable"]: futtatható állományok, • [@"system", "program", "apache", "conf"]: konfigurációs fájlok, • [@"system", "program", "apache", "log"]: naplófájlok, különböző csoportok lesznek. Az összes telepített program konfigurációjához elegendő a [@"system", "program", "conf"] útvonalat használni. A csomagkezelés és konfiguráció így jelentősen egyszerűbbé válik.
7.5.
Folyamatok kezelése
A folyamatok nyilvántartása a rendszerek egy részében fájlrendszeri szinten is megjelennek. A Linux rendszerekben használt /proc fájlrendszer ennek egy elterjedt példája. Az adatok ebben elsődlegesen szöveges fájlokon keresztül állnak rendelkezésre. Az ezekben szereplő értékek értelmezése bizonyos esetekben nehézkes lehet, így külön programcsomagok készültek hozzá, amelyek ebben segítenek. A rendszerben futó folyamatok adatait az azonosítójuknak (PID - Process Identifier) megfelelő nevű jegyzékben helyezi el az operációs rendszer, például /proc/2897. A jegyzékeken belül közel azonos szerkezet figyelhető meg. Az összes folyamat egy adott jellemzőjének lekérdezéséhez így a fastruktúrát be kell járni, és a szükséges adatokat ki kell olvasni az adott állományokból. A címkék segítségével az adatok lekérdezési módja egyszerűsodik. A folyamatok adatai elhelyezhetők a [@"system", "process"] fogalomba. Ezen belül a folyamatok adatai például a [@"system", "process", "2897"] útvonalon lehetnek. A futó processzek lekérdezéséhez elegendő a [@"system", "process", "running"] fogalmat vizsgálni, az azonosítók lekérdezéséhez pedig a [@"system", "process", "running", "pid"] fogalom állományait. A kialakított fogalmaknak köszönhetően az eddigiekhez hasonló lekérdezések is megfogalmazhatók, amelyek viszont már nem igényelnek speciális alkalmazásokat. Természetesen a megjelenítéshez és módosításhoz ezekre is szükség van, viszont már épülhetnek a fájlrendszer nyújtotta lekérdezés jellegű szolgáltatásokra.
7.6.
Verziókezelés támogatása
A verziókezelés a címkézés esetén érdekes problémákat vet fel. Egyrészt a fa struktúrába szervezett forráskódok verziókezelését a címkék segítségével viszonylag egyszerűen meg lehet oldani. Ehhez külön címkéket kell bevezetni, amely a verzióra utal, és így az eddigiekhez hasonló lekérdezések formájában rendelkezésre állnak az adott verzióhoz tartozó fájlok. Például az app nevű alkalmazás esetében a legutolsó változat állományai a [@"user1", "app", &"latest"] abszolút útvonalon érhetőek el. A korábbi, például a 10-es változat a [@"user1", "app", &"10"] fogalomhoz tartozik. Minden változathoz nem szükséges a teljes fastruktúrát tárolni. A lekérdezési módot úgy kell kialakítani, hogy az adott verziónál nem újabb fájlok közül a legújabb tartozzon a fogalomhoz. A programokhoz tartozó fájlok fogalmak szerint is csoportosíthatóak. Ekkor már nem a fastruktúra, hanem a fogalom verziókezeléséről kell gondoskodni amely a címkék verzióinak nyilvántartását igényli. A probléma tulajdonképpen ugyanaz, mint a jegyzékstruktúra esetében, vagyis hogy az eredeti struktúrát egy idődimenzióval kell 48
7.6. Verziókezelés támogatása
kiegészíteni. A jelölésmódban ez nem jelent változást, a kontextus kezelése viszont bonyolultabb lesz. A példákban szereplő app nevű alkalmazás első három verziója az alábbiak szerint alakul.
[@" u s e r 1 " , " app " , & " 1 " ] : l s 7/60 7/61
main . cpp Makefile
[@" u s e r 1 " , " app " , & " 1 " ] : t ag −&"1" +&"2" [@" u s e r 1 " , " app " , & " 2 " ] : l s 7/63 7/62 7/60 7/61
App . cpp App . h main . cpp Makefile
[@" u s e r 1 " , " app " , & " 2 " ] : t ag −&"2" +&"3" [@" u s e r 1 " , " app " , & " 3 " ] : l s 7/63 7/62 7/65 7/64 7/60 7/61
App . cpp App . h Gui . cpp Gui . h main . cpp Makefile
Az állományok tartalma nyilvánvalóan az adott verziónak megfelelő lesz. A verziókezelés a jegyzékstruktúra esetében körültekintést igényel, ami a fogalom alapú rendszernél fokozottan szükséges. A bemutatott példa csak azt szemlélteti, hogy a fogalom alapú állománykezelési módszer verziókezelési feladatok ellátására is alkalmas.
49
8. fejezet
Összegzés A fogalom alapú állománykezelés egy olyan új megközelítés, amely az emberi gondolkodásmódhoz közel álló fogalomalkotásra építkezik, nem pedig a hagyományos könyvtárszerkezetet használja. Az állományoknak az elhelyezkedését a hozzárendelt jellemzők (attribútumok, címkék) határozzák meg. A dolgozat első része a jelenleg elérhető, címkézést használó alkalmazási területeket mutatja be. A kész alkalmazások viszonyítási alapot nyújtanak. Segítségükkel hivatkozni lehet a létező funkciókra, illetve az új megoldások szerepét is jobban kiemelhetők. A címkézésre nincs egyezményes definíció, így először tisztáztam a jelentését a dolgozat szemszögéből, illetve részleteztem az analógiát a hagyományos, hierarchikus rendszerekhez képest. A formális fogalomelemzés eszközei biztos alapot adtak az új rendszer modelljének matematikai leírásához. Ebben a formális kontextus maga a fájlrendszer, amelynek objektumai a fájlok, attribútumai pedig a címkék. A fájlrendszerben a keresési kifejezést az attribútumhalmaz egy Q részhalmaza jelentette, az eredményként kapott fájlokat pedig az R objektumhalmaz. Ez a formális fogalomelemzésben használt derivációs művelet segítségével egyszerűen elvégezhető. Saját új definícióként szerepel az ellentett attribútum fogalma, amely a kontextus kibővítéséhez szükséges. Ezzel a lekérdezések megadása egyszerűsödött, és a jegyzékekből építkező fastruktúra így megfeleltethetővé vált a címkékre épülő fogalomhálóval. További fontos eredmény, hogy a lekérdezési móddal együtt a fájlrendszerekre jellemző útvonal kifejezés is új értelmet kapott. A matematikai leírások mellett szerepel egy példa, amely szemlélteti a fastruktúra és a fogalomháló közötti konverziós lehetőségeket, illetve a fogalom alapú lekérdezési módot is bemutatja. A kontextus adatainak kezelési módjára számos lehetőség van. Először a relációs adatmodell használatának egy lehetséges módjáról esik szó, majd egy elterjedt dokumentumorientált adatbázisbeli megvalósítás következik. Mindkét változatnak vannak előnyei, viszont a keresési művelet join és halmazműveletet használ, amelyek nem kimondottan hatékonyak ilyen esetben. A gyorsabb lekérdezések és hatékonyabb tárolási mód érdekében egy saját adattárolási struktúra készült. Ez változó hosszúságú kulcsértékekkel azonosítja a fájlokat és a címkéket. A perzisztens tároláshoz az állományok gyűjteményekbe szervezhetők, amely nyilvántartja a szabad kulcsértékeket, illetve az elérési útvonalakat is megadja a kulcsok értékének megfelelően. A név alapján történő keresés egy gyakori feladat, mivel a felhasználó a címkéket a nevével adja meg, amihez hozzá kell rendelni annak azonosítóját. Az ehhez használt asszociatív tömb implementációjához a prefix fa (trie) adatszerkezet bizonyult megfelelőnek. Egy másik lehetőség még a piros-fekete fa, amellyel összehasonlítottam a műveleti idők szempontjából. Ez alapján a prefix fa nem marad el sem a beszúrás, sem pedig a keresés gyorsaságában. 50
A prefix fa választását az indokolta, hogy prefix alapján is lehet benne keresni, illetve további optimalizációra is lehetőségeket ad. A fájlok és címkék adataihoz a hozzáférést egy adatbázisobjektum biztosítja. Ez elrejti a gyűjteményeket és a nevek kereséséhez használt adatszerkezeteket. Egyszerű interfészt használ, amely már az állományok importálására és exportálására is lehetőséget ad. A fájlrendszer kezeléséhez készült egy parancssori alkalmazás. Ennek egyedi szintaktikáját definiálja az 5. fejezet. Az abszolút- és relatív útvonal megadási módjából kiindulva az összes elterjedt fájlművelet példákon keresztül szemléltetve is szerepel az interfész leírásában. A fejezet vége a parancssoros alkalmazás felépítését és működését részletezi. A felhasználók többsége a fájlműveletek végrehajtásához grafikus felületet használ. Az új rendszer ehhez egy speciális felületet biztosít, amely igazodik a matematikai modellhez, illetve a fájlkezelők megszokott megjelenítési módjához is. A műveletei megfeleltethetőek a parancssori műveletekkel, viszont az átlagos felhasználó szempontjából kényelmesebb és gyorsabb keresést tesz lehetővé. A fájlrendszerekkel kapcsolatos fejezet egy kitekintést nyújt a fogalom alapú állománykezelés későbbi felhasználási lehetőségeiről. Az operációs rendszerek és az alkalmazásfejlesztés néhány jelentős területét emeli ki, amelyben a címkék használatával egységesebb kialakítás és egyszerűbb kezelési mód érhető el. A fogalom alapú állománykezelés elterjedéséhez a felhasználók gondolkodásmódjának is változnia kell. A bemutatott rendszer egy absztrakt, de mégis közvetlen állományszervezést tesz lehetővé. Segítségével az állományokat fogalmakba csoportosíthatjuk és a kulcsszavas keresőknél megszokott módon találhatjuk meg őket a fájlrendszerben. A keresési módszer kialakításából adódóan az állományokat tetszőleges sok fogalomba helyezhetjük el, célszerűen azokba, amelyekben egyébként is keresnénk.
51
Irodalomjegyzék [AS09] Andrews, S.: In-Close, a fast algorithm for computing formal concepts, International Conference on Conceptual Structures (ICCS), Moscow, 2009. [KC10] Kristina Chodorow, Michael Dirolf: MongoDB: The Definitive Guide, O’Reilly Media, 2012. [GW05] Bernhard Ganter, Gerd Stumme, Rudolf Wille: Formal Concept Analysis, Foundations and Applications, Springer, 2005. [KB08] Hak-Lae Kim, John G. Breslin, Sung-Kwon Yang, Hong-Gee Kim: Social Semantic Cloud of Tag: Semantic Model for Social Tagging Springer-Verlag Berlin Heidelberg, 2008. [KL07] Kovács László: Generating Decision Tree from Lattice for Classification, Proceeding of ICAI07, Eger, 2007, 377-385. [KA08] Körei Attila: Fogalomhálók alkalmazása osztályfelbontási problémákra, PhD értekezés, Miskolci Egyetem, 2008. [DM68] Donald R. Morrison: PATRICIA - Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM, Volume 15 Issue 4, Oct. 1968. [PP08] Alexandre Passant, Philippe Laublet: Meaning Of A Tag: A Collaborative Approach to Bridge the Gap Between Tagging and Linked Data Université Paris-Sorbonne, 2008. [RS98] Radeleczki, S.: A fogalomhálók egy műszaki alkalmazása, International Conference on Computer Science, "MicroCAD’98", Section Applied Mathematics, University of Miskolc, March 12., 1998. pp. 1-7. [RR04] Rusty Russel, Daniel Quinlan, Christopher Yeoh: Filesystem Hierarchy Standard, Filesystem Hierarchy Standard Group, 2004. [SF12] Steve Francia: MongoDB and PHP, O’Reilly Media, 2012. [SS06] Simon Schenk, Olaf Görlitz, Steffen Staab: TagFS: Bringing Semantic Metadata to the Filesystem, Institute for Computer Science, University of Koblenz, 2006.
52
Internetes hivatkozások [BL98] Tim Berners-Lee: Semantic Web Road map, http://www.w3.org/DesignIssues/Semantic.html Internet, 2013. [Elyse] Silkwood Software: Elyse, freedom from folders, http://silkwoodsoftware.com Internet, 2013. [Nepomuk] Networked Environment for Personalized, Ontology-based Management of Unified Knowledge, http://nepomuk.kde.org Internet, 2013. [Referencer] Referencer, GNOME Document Organiser https://launchpad.net/referencer Internet, 2013. [SpotLight] Apple: OS X. It’s what a Mac a Mac http://www.apple.com/osx/what-is Internet, 2013. [Tabbles] Yellow Blue Soft: Tabbles, folders evolved, http://tabbles.net Internet, 2013. [Tag2find] Tag2find, Tag everything on your desktop, http://www.tag2find.com Internet, 2013. [TaggedFrog] LunarFrog Software: TaggedFrog, http://lunarfrog.com/taggedfrog Internet, 2013. [Tagsistant] Tagsistant, All your files, quickly and easily. http://www.tagsistant.net Internet, 2013. [Tracker] https://live.gnome.org/Tracker GNOME (Meta) Tracker Internet, 2013. [WinFS] WinFS Team Blog http://blogs.msdn.com/b/winfs Internet, 2013.
53
Adathordozó használati útmutató A mellékelt CD-lemezen megtalálható a dolgozatnak és a bemutatott programoknak a forráskódja is a programok és a dolgozat jegyzékben. A programok fordításához hagyományosan a forráskódhoz Makefile-ok tartoznak. Ez a GNU Make programmal használható. Az adott program lefordításához a make parancsot kell kiadni a forrásfájlokat tartalmazó jegyzékben. A fájlok és jegyzékek kezelési módja függ az operációs rendszertől. A jelenlegi változat GNU/Linux operációs rendszerhez készült. Az adatbázis függvénykönyvtárként fordul, aminek az eredménye egy database.a fájl lesz. A shell jegyzékben lévő parancssori alkalmazáshoz ezt statikusan linkelni kell. Az programok/database/test jegyzékben vannak a prefixfa tesztelésére szolgáló segédprogramok. Itt található a kifejezésgyűjtemény a tag_samples.txt fájlban.
54