HierTag: een hiërarchisch en taggebaseerd bestandssysteem. Ontwerp en implementatie

HierTag: een hiërarchisch en taggebaseerd bestandssysteem. Ontwerp en implementatie.

Auteur: Karel Marissens Promotor: Philippe Van Laethem Studierichting: Toegepaste Informatica Afstudeerrichting Netwerken Academiejaar: 2008 - 2009

HierTag: een hiërarchisch en taggebaseerd bestandssysteem. Ontwerp en implementatie.

Auteur: Karel Marissens Promotor: Philippe Van Laethem Studierichting: Toegepaste Informatica Afstudeerrichting Netwerken Academiejaar: 2008 - 2009

Synopsis De laatste jaren neemt de hoeveelheid bestanden en informatie die een computergebruiker bijhoudt steeds meer toe. Deze bestanden worden gesorteerd in een hiërarchie, een boomstructuur. Elk bestand krijgt hierbinnen een vaste plaats. Een hiërarchisch bestandssysteem zorgt voor deze opslag. Hoe meer data erbij komen, hoe moeilijker het wordt deze terug te vinden. Daarom wordt er op zoek gegaan naar andere methodes voor het organiseren van informatie. Met de opkomst van Web 2.0 is het taggen van data populairder geworden. Tags, beschrijvende kernwoorden, worden geassocieerd met data. Achteraf kunnen de data teruggevonden worden door te zoeken op basis van deze tags. Eén van de eerste websites die dit idee succesvol toepaste is Delicious (www.del.icio.us), een 'social bookmarking' website waarbij bladwijzers online kunnen bijgehouden worden. Deze worden niet gesorteerd in mappen, maar worden getagd. Door tags te combineren kan gezocht worden naar bladwijzers. Andere bekende websites die het concept van tagging gebruiken zijn Flickr (www.flickr.com), een website voor het online plaatsen van foto's, YouTube (www.youtube.com), Last.fm (www.last.fm) en Gmail (www.gmail.com). Zou dit idee uitgebreid kunnen worden naar een systeem voor het beheer van alle bestanden op een computer? Bij onderzoek bleken al een aantal taggebaseerde bestandssystemen te bestaan. Voorbeelden hiervan zijn DBFS en Tagsistant. Er bleken echter ook een aantal nadelen verbonden te zijn aan dergelijke bestandssystemen. Bestanden hebben geen vaste plaats meer maar kunnen teruggevonden worden door het combineren van tags. De gebruiker moet dus altijd zoeken naar de bestanden. Mensen hebben echter graag vaste logische structuren. Het overzicht over de bestanden vervalt bij een taggebaseerd bestandssysteem. Hierdoor ontstond het idee om een hiërarchisch en taggebaseerd bestandssysteem te combineren. Ook dit soort bestandssystemen bestond reeds. Voorbeelden hiervan zijn Stratus, XTagFS en Leap. Deze systemen werken echter naast de bestaande hiërarchie. Leap bijvoorbeeld is een applicatie waarbinnen bestanden getagd kunnen worden. De tagfunctionaliteit is echter enkel beschikbaar binnen de applicatie zelf. Deze is volledig afwezig in bijvoorbeeld dialoogvensters voor het openen en opslaan van bestanden. Het ontbrak de bestaande oplossingen dus aan een zekere mate van integratie met de hiërarchie. Dit probeert HierTag op te lossen. HierTag behoudt de hiërarchie maar voegt in elke map enkele speciale submappen toe waarmee aan bestanden tags kunnen toegekend worden of terug verwijderd worden en waarmee gezocht kan worden op basis van tags naar bestanden in de map van waaruit de zoekmap geopend wordt. Binnen deze zoekopdracht kunnen tags gecombineerd worden met de operatoren and, or en combine_with. Heel dit systeem is geïmplementeerd als een hiërarchie. Tags en operatoren worden voorgesteld als mappen. Zoeken op basis van tags komt dus overeen met het achtereenvolgens openen van mappen. Aangezien HierTag werkt via een hiërarchie werkt het samen met om het even welke bestandsbeheer-applicatie en is het ook beschikbaar in dialoogvensters voor het openen en opslaan van bestanden. HierTag is geschreven in Python en gebruikt een Xapian database voor het opslaan van de relaties tussen bestanden en tags. Voor de implementatie van het bestandssysteem zelf werd FUSE gebruikt.

2

Voorwoord Graag wil ik alle mensen bedanken die mij geholpen hebben gedurende het verloop van mijn bachelorproef. Hiertoe behoren onder andere mijn promotor dhr. Philippe Van Laethem en verscheidene leden van de FUSE en Xapian mailinglijst.

3

Inhoudsopgave Inleiding........................................................................................................................................ 6  1  Wat is een bestandssysteem? ............................................................................................... 7  2  Soorten bestandssystemen.................................................................................................... 8  2.1  Hiërarchische bestandssystemen ..................................................................................... 8  2.1.1  Nadelen .................................................................................................................... 9  2.1.2  Voorbeelden ............................................................................................................. 9  2.2  Taggebaseerde bestandssystemen.................................................................................... 9  2.2.1  Nadelen .................................................................................................................. 10  2.2.2  Voorbeelden ........................................................................................................... 11  2.3  Combinaties van hiërarchische en taggebaseerde bestandssystemen............................ 12  2.3.1  Nadelen .................................................................................................................. 13  2.3.2  Voorbeelden ........................................................................................................... 13  3  HierTag: integratie van een hiërarchisch en taggebaseerd bestandssysteem. .............. 16  3.1  Hiërarchie ...................................................................................................................... 16  3.2  Tags toevoegen .............................................................................................................. 18  3.3  Tags verwijderen ........................................................................................................... 18  3.4  Tags hernoemen............................................................................................................. 19  3.5  Zoeken op basis van tags ............................................................................................... 19  3.5.1  Resultaatbestanden weergeven............................................................................... 20  3.5.2  Tagselecties opstellen............................................................................................. 20  3.6  Up to date houden van de bestandslijst ......................................................................... 22  3.7  Eenvoudige back-ups..................................................................................................... 22  3.8  Installatie van HierTag .................................................................................................. 22  4  Technische aanpak.............................................................................................................. 24  4.1  Programmeertaal: Python .............................................................................................. 24  4.2  Bestandssysteem: FUSE ................................................................................................ 24  4.2.1  FUSE API............................................................................................................... 26  4.2.2  Python bindings...................................................................................................... 26  4.3  Database......................................................................................................................... 26  4.3.1  RDBMS.................................................................................................................. 27  4.3.2  Xapian .................................................................................................................... 32  5  Beperkingen......................................................................................................................... 36  5.1  Caching door bestandsbeheer-applicaties...................................................................... 36  5.2  Tags verdwijnen na aanpassing bestand door sommige applicaties.............................. 36  5.3  Resultaatbestanden aanpassen lukt niet met bepaalde applicaties................................. 37  6  Opgeloste problemen .......................................................................................................... 38  6.1  Een map verwijderen resulteerde in een oneindige lus ................................................. 38  6.1.1  Een nieuwe speciale map: +TRASH...................................................................... 38  6.1.2  Een verborgen .+RMDIR map ............................................................................... 39  6.1.3  De speciale mappen verbergen............................................................................... 39  6.2  De toevoeging van +SAVE in de +ADD-map .............................................................. 40  6.3  Toevoegen van tags aan HierTag via de gebruikersinterface........................................ 42  7  Toekomstmogelijkheden .................................................................................................... 43  4

7.1  Mac OS X versie............................................................................................................ 43  7.2  Eigen mapnamen voor speciale mappen ....................................................................... 43  7.3  Tagsuggesties................................................................................................................. 43  7.4  Negaties in tagselecties.................................................................................................. 43  7.5  Tags met bepaalde functionaliteit.................................................................................. 43  7.6  Totaalaantallen............................................................................................................... 43  7.7  Uitbreiding gebruikersinterface ..................................................................................... 44  Besluit ......................................................................................................................................... 45  Literatuurlijst ............................................................................................................................ 46 

5

Inleiding Het associëren van tags, beschrijvende kernwoorden, met data is de laatste jaren enorm opgekomen, vooral door de opkomst van Web 2.0. Delicious (www.del.icio.us), een website waarbij bladwijzers online kunnen bijgehouden worden, was één van de eerste die het idee succesvol toepaste. Bladwijzers werden getagd, zodat deze teruggevonden konden worden door te zoeken op basis van tags. Een ander bekend voorbeeld is Flickr (www.flickr.com). Deze website biedt gebruikers de mogelijkheid eenvoudig foto’s online te plaatsen en deze te taggen. Achteraf kunnen foto’s teruggevonden worden door te zoeken op tags. Het idee is verder doorgedrongen bij websites zoals YouTube (www.youtube.com), Last.fm (www.last.fm) en Gmail (www.gmail.com). Ook offline applicaties zoals iPhoto, voor het beheer van foto’s, beschikken nu over tagfunctionaliteit. Deze evolutie, een zoektocht naar nieuwe manieren om informatie te organiseren, heeft mij altijd al gefascineerd. Toen ik het voorstel voor het maken van een taggebaseerd bestandssysteem tussen de voorstellen voor bachelorproeven zag staan, was mijn interesse meteen gewekt. Een taggebaseerd bestandssysteem zou het idee van tagging kunnen doortrekken van specifieke datatypes (bladwijzers, muziek, foto’s) naar alle bestanden op de computer van een eindgebruiker. Alvorens een dergelijk bestandssysteem kon ontwikkeld worden was het belangrijk om eerst onderzoek te doen naar wat een bestandssysteem precies is. Dit wordt uitgelegd in het eerste hoofdstuk. Ook belangrijk was welke types bestandssystemen er reeds bestaan en wat hun vooren nadelen zijn. Hier wordt uitgebreid op ingegaan in het tweede hoofdstuk. Op basis van die kennis kon een ontwerp voor een nieuw bestandssysteem ontwikkeld worden. In het derde hoofdstuk wordt dieper ingegaan op de werking van dit nieuwe bestandssysteem, met de naam HierTag. Hoe dit technisch werd verwezenlijkt wordt uit de doeken gedaan in hoofdstuk vier. Hoofdstuk vijf handelt over de beperkingen tijdens het gebruik van HierTag die buiten HierTag zelf liggen. De problemen die tijdens de ontwikkeling werden opgelost zijn vermeld in hoofdstuk zes. In een laatste hoofdstuk wordt ten slotte ingegaan op wat de toekomst zou kunnen brengen voor HierTag.

6

1 Wat is een bestandssysteem? Een bestandssysteem voorziet een methode voor het opslaan en organiseren van computerbestanden (documenten, e-mails, foto’s, filmpjes, liedjes, ...) en de data die ze bevatten zodat deze gemakkelijk terug te vinden zijn en geopend kunnen worden. Sommige bestandssystemen gebruiken opslagmedia zoals een harde schijf of cd-rom en houden de fysieke locatie van de bestanden bij. Andere bestandssystemen geven toegang tot data op servers door zich te gedragen als clients voor een netwerk protocol (bv. NFS en SMB clients). Daarnaast zijn er ook virtuele bestandssystemen. Deze bieden een toegangsmethode voor virtuele data. Een typisch voorbeeld hiervan is procfs (“process filesystem”), waarmee procesinformatie van de kernel geraadpleegd kan worden op vele Unix-achtige computersystemen.

7

2 Soorten bestandssystemen 2.1 Hiërarchische bestandssystemen Een hiërarchisch bestandssysteem organiseert bestanden in een boomstructuur van mappen. In de root, het vertrekpunt van het bestandssysteem, kunnen verschillende mappen en bestanden aanwezig zijn. Elke map in het bestandssysteem kan op zijn beurt weer andere mappen en bestanden bevatten. Op dit moment is dit het meest gebruikte systeem. De manier van werken komt bij mensen zeer logisch over omdat het overeenkomt met de manier waarop fysieke documenten gesorteerd worden. Fysieke documenten worden typisch gegroepeerd in mapjes. Deze mapjes worden gegroepeerd in laden, die op hun beurt gegroepeerd worden in een kast. Op diezelfde manier kunnen bestanden in een hiërarchisch bestandssysteem gegroepeerd worden in mappen, kunnen mappen gegroepeerd worden in nog andere mappen, enz. Op figuur 2.1 is een eenvoudig voorbeeld te zien van een hiërarchie. In de root, aangeduid met ‘/’, zijn 2 mappen aanwezig: Foto’s en Iconen. In beide mappen zitten enkele bestanden.

Figuur 2.1: Een hiërarchie. De unieke locatie van een map of bestand binnen een bestandssysteem wordt typisch aangegeven door middel van een pad. Dit is een opeenvolging van hoe de mappenstructuur doorlopen moet worden om vanuit de root bij een bepaalde map of bestand te komen. De namen van de mappen en bestanden worden hierbij gescheiden door een ‘/’. Er kan bijvoorbeeld verwezen worden naar de map Iconen in het bovenstaande schema met het pad /Iconen. Om naar de afbeelding van het legoblokje te verwijzen wordt het pad /Iconen/Legoblok.png gebruikt. Dit wijst erop dat om bij het bestand Legoblok.png te komen een gebruiker eerst de map Iconen moet openen gevolgd door het bestand Legoblok.png. Dit

principe

kan

doorgetrokken

worden naar uitgebreidere hiërarchieën, waarbij bijvoorbeeld verwijst naar een foto van de Tower Bridge in Londen die genomen is op de eerste dag van een reis naar Londen in het jaar 2009. Om het bestand terug te vinden opent de gebruiker vanuit de root de map Foto’s. Vervolgens selecteert hij de map 2009, gevolgd door de map Londen en de map Dag1. Hierin vindt hij uiteindelijk het bestand Towerbridge.jpg terug. /Foto’s/2009/Londen/Dag1/Towerbridge.jpg

8

2.1.1 Nadelen Het principe van een hiërarchisch bestandssysteem is logisch en eenvoudig. Doordat een bestand een vaste plaats heeft in de hiërarchie is het echter niet altijd even eenvoudig om een bestand terug te vinden. Immers, het precieze pad naar het bestand moet bekend zijn. Weet de gebruiker in het voorbeeld van de Tower Bridge niet meer in welk jaar hij naar Londen geweest is, dan moet hij mogelijk verschillende mappen, die verschillende jaren voorstellen, afgaan om de foto terug te vinden. Zo kunnen ook problemen optreden wanneer een gebruiker bijvoorbeeld foto’s en filmpjes heeft van een trouwfeest. De foto’s kunnen in een submap van de map Foto’s geplaatst worden (/Foto’s/Trouwfeest) en de filmpjes in een submap van de map Filmpjes (/Filmpjes/Trouwfeest). Echter raakt daardoor het verband tussen beide verloren. Een gebruiker kan bij het zien van de foto’s van het trouwfeest niet weten dat er ook filmpjes aanwezig zijn in een andere map. Vele besturingssystemen hebben tegenwoordig een ingebouwde zoekmachine voor bestanden. OS X heeft zo bijvoorbeeld Spotlight, Linux heeft Tracker en Beagle en ook Windows Vista heeft een eigen variant. Deze indexeren alle bestanden, slaan metadata (data die gegevens beschrijven, zoals de auteur van een document, het aantal pagina’s, de taal waarin het document is opgesteld, ...) op en houden veranderingen in het bestandssysteem bij. Daardoor kan snel gezocht worden naar bestanden. Dit lost het eerste probleem op, waarbij het precieze pad van een bestand gekend moet zijn. Het tweede probleem is echter niet opgelost.

2.1.2 Voorbeelden Enkele voorbeelden van veelgebruikte hiërarchische bestandssystemen zijn NTFS (Windows), HFS+ (OS X) en EXT3 (Linux). Aan de gebruikerskant lijken deze systemen erg op elkaar. Onder de kap zijn er echter grote verschillen die niet thuishoren binnen de scope van dit verslag.

2.2 Taggebaseerde bestandssystemen Een taggebaseerd bestandssysteem maakt komaf met de boomstructuur van een hiërarchisch bestandssysteem. Bestanden hebben geen vaste plaats meer. In de plaats daarvan worden bestanden getagd. Dit wil zeggen dat beschrijvende kernwoorden, tags, met bestanden geassocieerd worden. Op figuur 2.2 zijn dezelfde bestanden te zien die gebruikt werden bij de uitleg over hiërarchische bestandssystemen. Per bestand zijn een aantal tags aangegeven die omschrijven wat de inhoud van het bestand is, wat voor type bestand het is (foto of icoon) en in welk formaat het bestand opgeslagen is (jpg, gif of png).

Figuur 2.2: Tags geassocieerd met bestanden.

9

Om bestanden terug te vinden combineert de gebruiker tags in een tagselectie. Hij kan bijvoorbeeld alle bestanden opvragen die getagd zijn als icoon, wat de 4 rechtse afbeeldingen zijn. Een diepere selectie is het opvragen van bestanden die getagd zijn als zowel icoon als basketbal. Dit levert enkel het icoon van de basketbal op. Binnen een tagselectie zijn verschillende combinatiemethoden mogelijk voor het combineren van tags door het gebruik van operatoren. De operatoren die gebruikt kunnen worden verschillen van systeem tot systeem. Enkele voorbeelden hiervan zijn: o

AND-operator:

o

OR-operator:

o

NOT-operator:

Enkel bestanden die getagd zijn met beide tags.

Bestanden die getagd zijn met één van beide tags, of allebei. Bestanden die niet getagd zijn met een bepaalde tag.

Wanneer meerdere van deze operaties gebruikt kunnen worden binnen een systeem is de vraag welke operaties voorrang krijgen op andere. Hier volgt een voorbeeld waarbij zo’n twijfel mogelijk is: icoon AND bal OR lego

Het is niet duidelijk wat hiermee bedoeld wordt. Een eerste mogelijkheid is dat de bestanden bedoeld worden die getagd zijn als bal of lego, maar ook als icoon: icoon AND ( bal OR lego )

Een andere mogelijkheid is dat de bestanden bedoeld worden die ofwel getagd zijn als icoon en bal, ofwel als lego: ( icoon AND bal ) OR lego

Welke van deze 2 mogelijkheden de juiste is hangt af van het gebruikte systeem.

2.2.1 Nadelen Doordat bestanden geen vaste plaats meer hebben moet de gebruiker altijd zoeken door middel van tags. Hoewel het mogelijk is om de bestanden terug te vinden is dit voor gebruikers niet altijd een even intuïtieve handeling. Mensen hebben graag een vaste structuur en overzicht over hun bestanden. Dit valt bij taggebaseerde bestandssystemen helemaal weg. Een ander nadeel is dat steeds gezocht wordt in alle bestanden, daar waar het bij zoekmachines voor hiërarchische bestandssystemen vaak mogelijk is de zoekopdracht te beperken tot een bepaalde map in de hiërarchie, waardoor een groot aantal niet-relevante bestanden meteen weg worden gefilterd. Bij taggebaseerde bestandssystemen hebben bestanden bovendien geen relatieve plaats meer ten opzichte van elkaar. Deze relatieve plaats is de manier waarop genavigeerd kan worden van de map waarin het ene bestand zich bevindt naar de map waarin het andere bestand zich bevindt. Een typisch voorbeeld waarbij dit gebruikt wordt is een website. In een hiërarchie staat deze bijvoorbeeld opgeslagen in de map /Website. Binnen deze map is een bestand index.html opgeslagen waar de inhoud van de homepagina instaat: /Website/index.html. Ook is er een submap Afbeeldingen met daarin het bestand foto.jpg: /Website/Afbeeldingen/foto.jpg. In het bestand index.html kan relatief verwezen worden naar de foto als volgt: Afbeeldingen/foto.jpg. Het bestand index.html staat in de map /Website, om vanuit deze map naar de foto te navigeren moet de map Afbeeldingen geopend worden en kan vervolgens de foto teruggevonden worden. Dit is omschreven door het relatieve pad. Merk op dat er geen ‘/’ voor het relatieve pad staat. Een pad dat begint met een ‘/’ duidt namelijk op een pad dat omschreven wordt vanuit de root, een zogenaamd absoluut pad, terwijl bij een relatief pad het pad beschreven wordt vanuit een andere map. 10

Stel dat het index.html bestand en foto.jpg bestand in een taggebaseerd bestandssysteem zijn opgeslagen. Beide zouden vindbaar zijn, maar foto.jpg zou niet langer in de submap Afbeeldingen staan. De relatieve verwijzing is dus niet langer correct.

2.2.2 Voorbeelden Er bestaat al een aantal taggebaseerde bestandssystemen, waarvan enkele hier worden opgesomd. Dit zijn allemaal virtuele bestandssystemen in die zin dat ze een laag vormen bovenop een hiërarchisch bestandssysteem. 2.2.2.1 DBFS DBFS staat voor Database File System. Het is een proof of concept bestandssysteem geïntegreerd in de core van KDE, één van de bekendste window managers voor Linux. Het vervangt alle dialoogvensters die te maken hebben met het openen en opslaan van bestanden. Een aparte applicatie voor bestandsbeheer (KDBFS) is ook toegevoegd. KDBFS beschikt over een ‘View’, waarin de bestanden te zien zijn die aan de selectie voldoen. Deze selectie kan gemaakt worden aan de hand van 5 filters die te zien zijn op figuur 2.3. Deze filteren op basiscategorieën (filter 1), vroeger gemaakte selecties (filter 2), tags (filter 3), datums (filter 4) en bestandsnaam (filter 5). De tagfilter is hierbij het meest relevant. Zoals op de figuur te zien is, is dit meer dan een lange lijst van tags. Tags kunnen hiërarchische relaties hebben. Op de figuur zijn de tags Final Project, SOAT en Stage bijvoorbeeld hiërarchisch binnen de tag University geplaatst. Dit betekent dat wanneer University bij een selectie gebruikt wordt, deze 3 subtags automatisch meegenomen worden in de selectie. Tijdens een filteropdracht kunnen meerdere tags geselecteerd worden. Deze worden in de filter gecombineerd als OR-operaties. Met andere woorden, alle bestanden die getagd zijn als één van de geselecteerde tags worden geselecteerd. Dit beperkt ook meteen de mogelijkheden van filtering op tags.

Figuur 2.3: KDBFS, de bestandsbeheer-applicatie van DBFS. 11

2.2.2.2 Tagsistant Tagsistant, voordien bekend als TagFS, presenteert tags als mappen in een hiërarchie. Na het laden van het bestandssysteem is een lijst te zien van alle tags in de vorm van mappen. Door een map te openen wordt een tag geselecteerd. Alle bestanden die getagd zijn met die tag zijn zichtbaar. Ook 2 speciale mappen zijn zichtbaar: AND en OR. Deze kunnen gebruikt worden om de tagselectie uit te breiden. Binnen Tagsistant zijn deze mapnamen geschreven met hoofdletters, om de leesbaarheid te bevorderen worden ze in deze tekst echter met kleine letters geschreven. Door naar de map /foto/AND/verjaardag te gaan worden alle bestanden zichtbaar die getagd zijn met zowel de tag foto als de tag verjaardag. De map /verjaardag/AND/foto geeft hetzelfde resultaat aangezien de tagselectie dezelfde tags omvat. De map /foto/OR/film daarentegen toont alle bestanden getagd als foto, film of beide. OR heeft bovendien voorrang op AND. Dat wil zeggen dat de map /foto/AND/verjaardag/OR/nieuwjaar alle bestanden toont die getagd zijn als foto en verjaardag, alsook alle bestanden die getagd zijn als nieuwjaar. Eenvoudig weergegeven betekent dit: ( foto AND verjaardag ) OR nieuwjaar

Om alle bestanden te selecteren die getagd zijn als verjaardag of nieuwjaar, maar ook foto, kan de map /foto/AND/verjaardag/OR/foto/AND/nieuwjaar geopend worden: ( foto AND verjaardag ) OR ( foto AND nieuwjaar )

Naast deze basisfunctionaliteit ondersteunt Tagsistant ook plugins, wat autotagging toelaat. Zo kunnen bijvoorbeeld tags gegenereerd worden op basis van metadata van fotobestanden. Ten slotte wordt een applicatie, Tagman, meegeleverd waarmee relaties tussen tags aangegeven kunnen worden. Een eerste voorbeeld is de tag heavymetal. Via Tagman kan aangegeven worden dat een bestand getagd als heavymetal ook automatisch getagd wordt met de tag metal, aangezien deze kortere benaming vaak met hetzelfde doel gebruikt wordt. Een tweede voorbeeld is het aangeven dat wanneer de tags broer, zus, mama of papa toegepast worden, automatisch ook de tag familie toegepast wordt. Bij het kort testen van Tagsistant werkte het toch niet zo optimaal. Het was bijvoorbeeld niet duidelijk hoe (en of) bij het opslaan van een bestand meerdere tags kunnen toegekend worden. Een bestand opslaan in /tag1/AND/tag2 resulteerde in een foutmelding. Hetzelfde gold voor /tag1/OR/tag2. Het tonen van alle beschikbare bestanden na het selecteren van een tag leek ook niet zo handig omdat bij het selecteren van de tag foto er potentieel duizenden bestanden moeten weergegeven worden. Bij een steeds groter wordende lijst van bestanden kan dit negatieve gevolgen hebben op de performantie van het systeem.

2.3 Combinaties van bestandssystemen

hiërarchische

en

taggebaseerde

Zowel hiërarchische als taggebaseerde bestandssystemen hebben een aantal nadelen die het ander niet heeft. Door beide systemen te combineren wordt hieraan verholpen. Bestanden worden in een hiërarchie opgeslagen maar zijn ook geassocieerd met tags, waarop ze gefilterd kunnen worden. Op figuur 2.4 zijn dezelfde bestanden terug te vinden als getoond werd bij de uitleg over hiërarchische en taggebaseerde bestandssystemen. Men ziet een hiërarchie waarbij bestanden in 2 grote mappen opgedeeld zijn: Foto’s en Iconen. Daarnaast is per bestand aangegeven welke tags ermee geassocieerd zijn.

12

Figuur 2.4: Zowel hiërarchie als tags.

2.3.1 Nadelen De bestaande systemen die binnen deze categorie vallen combineren hiërarchische en taggebaseerde bestandssystemen door deze naast elkaar te laten bestaan. De hiërarchie blijft behouden maar daarnaast zijn de bestanden ook bereikbaar vanuit een apart systeem waarmee tags toegekend kunnen worden en bestanden teruggevonden kunnen worden. Het grote nadeel is dat de systemen vrijwel los van elkaar functioneren. Bij het opslaan van een bestand kan bijvoorbeeld niet meteen aangegeven worden welke tags ermee geassocieerd worden, dit gebeurt achteraf. Een goede integratie van beide systemen ontbreekt.

2.3.2 Voorbeelden 2.3.2.1 Stratus Stratus presenteert tags net als Tagsistant in een hiërarchie. Ook de structuur van deze is sterk gelijkend. Tags komen zo ook overeen met mappen. Bestanden komen overeen met symbolische links naar de echte bestanden. Stratus functioneert naast de bestaande hiërarchie. Om bestanden uit de bestaande hiërarchie in Stratus zichtbaar te maken worden symbolische links aangemaakt in een speciale map, die verwijzen naar alle mappen en bestanden die opgenomen moeten worden. Stratus indexeert deze automatisch. In de root van het Stratus bestandssysteem wordt een lijst van alle tags en bestanden getoond. Door een tag te selecteren wordt een lijst van combineerbare tags getoond alsook de bestanden die ermee getagd zijn. Door één van de tags te selecteren wordt de tagselectie uitgebreid. Alle combineerbare tags alsook bestanden die getagd zijn met beide tags worden weergegeven. De map /foto toont alle tags die gecombineerd kunnen worden met de tag foto alsook alle bestanden getagd als foto. De map /foto/2009 toont alle tags die gecombineerd kunnen worden

13

met de tags foto en 2009, alsook alle bestanden die getagd zijn als zowel foto als 2009. In Tagsistant werd ditzelfde bereikt door de map /foto/AND/2009 te openen. Een nieuwe tag toevoegen in Stratus komt overeen met het aanmaken van een nieuwe map. Om een bestand te taggen kan het bestand gekopieerd worden in de map die overeenkomt met de tag. Wanneer een selectie /foto/2009 gemaakt is kan de tag 2009 van een bestand verwijderd worden door het bestand (weergegeven door een symbolische link) te verwijderen uit de map. Achter de naam van elk bestand plakt Stratus een lijst van alle tags die met het bestand geassocieerd zijn. De tags worden hierbij gescheiden door een dubbelpunt. Wanneer de bestandsnaam aangepast wordt kan deze lijst ook aangepast worden. Wordt een tag bij de lijst bijgevoegd, dan wordt het bestand als dusdanig getagd. Bestaat deze tag nog niet dan wordt de tag toegevoegd aan Stratus. Wanneer een tag uit de lijst verwijdert wordt is het bestand niet langer met die tag geassocieerd. Stratus heeft een aantal nadelen. Zo toont de root van het systeem alle bestanden, wat bij duizenden bestanden het systeem enorm kan vertragen. Ook de taglijst achter de bestandsnaam is niet zo handig. Een lijst van bestanden wordt daardoor al snel onoverzichtelijk. Het verwijderen van tags door het verwijderen van bestanden uit mappen is bovendien niet intuïtief en zorgt ervoor dat het effectief verwijderen van een bestand onhandig wordt. Hiervoor moet namelijk het originele bestand (in de hiërarchie) verwijderd worden. Het kan niet rechtstreeks vanuit Stratus. 2.3.2.2 XTagFS XTagFS is een taggebaseerd bestandssysteem voor Mac OS X. In het hiërarchische bestandssysteem gebruikt door Mac OS X (dit is typisch HFS+) is het mogelijk om voor elk bestand ‘Spotlight Comments’ in te geven. Spotlight is de ingebouwde zoekmachine binnen Mac OS X. Via deze comments kan de zoekfunctie verbeterd worden. XTagFS beschouwt de comments als tags, waarbij een spatie een onderscheid maakt tussen verschillende tags. XTagFS indexeert deze en maakt een virtueel bestandssysteem aan, weergegeven binnen een hiërarchie. De werking hiervan loopt gelijk met deze van Tagsistant en Stratus: door tags (mappen) te openen kan gezocht worden naar bestanden. /foto/2009 toont aldus alle bestanden die getagd zijn als foto en 2009. De huidige versie van XTagFS laat enkel het openen van bestanden toe vanuit het virtuele bestandssysteem. Tags toekennen en verwijderen kan enkel via de Spotlight Comments. Dit maakt het systeem vrij onhandig in gebruik omdat het hiërarchisch en taggebaseerd deel bijna volledig los staan van elkaar. 2.3.2.3 Leap en Punakea Leap kan gebruikt worden naast Finder, de standaard bestandsbeheer-applicatie van Mac OS X. Het is een programma dat de mappenhiërarchie combineert met tags en metadata. Door een combinatie van verschillende filters kunnen bestanden gezocht worden. De werking hiervan is gelijkaardig aan die van KDBFS, de bestandsbeheer-applicatie van DBFS (zie puntje 2.2.2.1). Eén van de handige punten is dat de selectie meteen beperkt kan worden tot een bepaald deel van de hiërarchie. Ook handig is dat op basis van de mappenstructuur waar het bestand zich bevindt, alsook metadata omtrent het bestand, automatisch bepaalde tags geassocieerd worden met het bestand. Om tags toe te voegen aan bestanden kan een bestand van om het even welke locatie in Finder naar een speciaal paneel aan de rand van het scherm gesleept worden waarna meteen tags ingegeven kunnen worden, die bovendien automatisch toegevoegd worden aan de ‘Spotlight Comments’. 14

Punakea is een applicatie met gelijkaardige doelstellingen als Leap. De interface is echter beperkter en bestanden moeten manueel toegevoegd en getagd worden. Het nadeel van zowel Leap als Punakea is dat het losstaande applicaties zijn naast Finder. Dit betekent dat in dialoogvensters voor het openen en opslaan van bestanden de functionaliteit van de applicaties (zoals o.a. de tags) niet gebruikt kan worden. Het toekennen van tags gebeurt dus altijd achteraf en om bestanden terug te vinden op basis van tags moet de applicatie gebruikt worden.

15

3 HierTag: integratie van een hiërarchisch en taggebaseerd bestandssysteem. Zowel hiërarchische als taggebaseerde bestandssystemen hebben een aantal nadelen. HierTag probeert hiervoor een oplossing te vinden door de 2 te combineren. Anders dan bij de systemen die dit principe reeds toepassen, zoals besproken in puntje 2.3, integreert HierTag de 2 systemen in plaats van deze naast elkaar te laten bestaan.

3.1 Hiërarchie HierTag implementeert een hiërarchie door een map uit het bestaande hiërarchisch bestandssysteem te spiegelen. Stel dat een gebruiker in zijn bestaand hiërarchisch bestandssysteem de mappen Bestanden, Gebruiker, Tags, ... heeft. Binnen de map Bestanden is een bestand Verslag.doc aanwezig alsook een submap Foto’s. In deze map Foto’s zijn 2 bestanden aanwezig: Voetbal.jpg en Basketbal.jpg. Deze structuur is weergegeven op onderstaande figuur.

Figuur 3.1 Bij de configuratie van HierTag wordt aangegeven welke map van de bestaande hiërarchie gespiegeld moet worden. In dit voorbeeld is dat de map /Bestanden. HierTag wordt geladen in een map naar keuze binnen de bestaande hiërarchie. Het lijkt aldus deel uit te maken van de bestaande hiërarchie. HierTag kan bijvoorbeeld geladen worden in de map /Tags. De structuur van het hiërarchisch bestandssysteem wordt:

Figuur 3.2 De mappen en bestanden die in de map /Bestanden staan worden gespiegeld in de map /Tags. Wanneer een bestand of map toegevoegd, aangepast of verwijderd wordt in de map /Bestanden wordt die verandering gereflecteerd in de map /Tags. Wordt een bestand of map toegevoegd, aangepast of verwijderd in de map /Tags (dus binnen HierTag), dan wordt die verandering rechtstreeks doorgevoerd in de map /Bestanden.

16

Belangrijk is dat de bestanden en mappen slechts één keer worden opgeslagen, namelijk in de map /Bestanden. De bestanden en mappen binnen HierTag zijn virtueel. HierTag baseert zich voor het weergeven van de bestanden en mappen volledig op de map /Bestanden. HierTag kan geladen worden in een map naar keuze in het bestaande hiërarchisch bestandssysteem. Wordt het geladen in de map /Gebruiker/HierTag, dan zal het deze map zijn die de inhoud van de map /Bestanden spiegelt. Dit is te zien op onderstaande figuur.

Figuur 3.3 Omdat om het even welke map gebruikt kan worden voor het laden van HierTag wordt bij de bespreking van paden binnen HierTag enkel het stuk genomen dat steeds hetzelfde is. In het bovenstaande voorbeeld zijn dit de volgende mappen en bestanden: /Foto’s /Foto’s/Voetbal.jpg /Foto’s/Basketbal.jpg /Verslag.doc

Tot dusver biedt HierTag nog geen enkel voordeel ten opzichte van het gebruik van de bestaande hiërarchie. HierTag voegt echter tagfunctionaliteit toe door in elke map binnen HierTag speciale mappen toe te voegen waarvan de naam voorafgegaan wordt door een ‘+’. Een voorbeeld:

Figuur 3.4 Hoe deze speciale mappen precies werken wordt in de volgende punten uit de doeken gedaan. Tags worden binnen HierTag voorgesteld als mappen. Wanneer in de volgende uitleg gesproken wordt over tags worden mappen bedoeld met de naam van een tag. Een tag selecteren komt overeen met het openen van de map die de tag voorstelt.

17

3.2 Tags toevoegen In elke map binnen de hiërarchie wordt een speciale map deze map is hieronder te zien.

+ADD

toegevoegd. De werking van

Figuur 3.5 Na het openen van de map +ADD is een lijst van alle tags te zien. Na het selecteren van een tag zijn 2 speciale mappen te zien: +AND en +SAVE. Deze laatste is een lege map. Door +AND te openen wordt opnieuw een lijst van alle tags weergegeven, met uitzondering van degene die reeds geselecteerd zijn. /+ADD/foto/+AND zal dus alle tags tonen behalve de tag foto. /+ADD/foto/+AND/2009/+AND zal alle tags tonen behalve de tags foto en 2009. Om één of meerdere tags toe te voegen aan een bestand wordt een bestand verplaatst naar de map +ADD, gevolgd door de toe te kennen tags. Door het bestand /Iconen/Voetbal.jpg (zie figuur 2.4) te verplaatsen naar /Iconen/+ADD/voet/+AND/nike, worden de tags voet en nike met het bestand geassocieerd. Merk hierbij op dat de +ADD-map gebruikt wordt die in de map staat waarin het bestand zich bevindt. Wanneer het bestand /Iconen/Voetbal.jpg verplaatst wordt naar /+ADD/voet,voet dan wordt de tag voet geassocieerd met het bestand Voetbal.jpg, maar wordt het bestand ook verplaatst van de map /Iconen naar de root (‘/’). Het kan natuurlijk voorvallen dat een gewenste tag nog niet bestaat. Deze kan toegevoegd worden door het aanmaken van een map binnen de +ADD-map. Op de naam van een tag liggen momenteel wel een aantal restricties. Zo mogen tags enkel bestaan uit kleine letters, nummers en liggende streepjes. Spaties, accenten en andere speciale karakters zijn niet toegelaten en worden geweigerd. HierTag maakt het ook mogelijk om bij het opslaan van een bestand meteen een aantal tags aan te geven. Hiertoe wordt eerst naar de map in de hiërarchie gegaan waarbinnen het bestand opgeslagen moet worden. Vervolgens wordt de map +ADD geopend en worden de gewenste tags geselecteerd, gescheiden door +AND-mappen. Ten slotte wordt de map +SAVE geopend. Deze is leeg en duidt het eindpunt van de tagselectie aan. Om bijvoorbeeld een icoon van een tennisbal (Tennisbal.jpg) op te slaan kan de volgende map gebruikt worden: /Iconen/+ADD/tennisbal/+AND/icoon/+AND/bal/+AND/jpg/+SAVE

Binnen de hiërarchie zal het Tennisbal.jpg bestand opgeslagen worden in /Iconen. Ook zullen meteen de tags tennisbal, icoon, bal en jpg geassocieerd worden met het bestand. Het is belangrijk het verschil op te merken tussen het toevoegen van een tag aan een bestaand bestand en aan een nieuw bestand. Bij een bestaand bestand wordt de +SAVE-map niet geselecteerd, terwijl dit bij een nieuw bestand wel gebeurt. Wanneer een bestand van buiten HierTag gekopieerd of verplaatst wordt naar HierTag, wordt dit ook beschouwd als een nieuw bestand. De +SAVE-map dient dus gebruikt te worden. De reden hierachter is een technische beperking die uitgebreider uitgelegd wordt in puntje 6.2.

3.3 Tags verwijderen Naast de +ADD-map is er ook een speciale +REMOVE-map aanwezig in elke map binnen de hiërarchie. De werking hiervan is hieronder afgebeeld en loopt grotendeels gelijk met deze van +ADD. 18

Figuur 3.6 Nadat +REMOVE geopend wordt zijn alle tags zichtbaar die toegepast zijn op bestanden in de huidige en onderliggende mappen. Om tags van een bestand te verwijderen wordt een bestand verplaatst naar de +REMOVE-map en één of meerdere tags daarbinnen gescheiden door de speciale map +AND. Door het bestand /Iconen/Voetbal.jpg te verplaatsen naar de map /Iconen/+REMOVE/voetbal/+AND/bal worden de tags voetbal en bal niet langer meer geassocieerd met het bestand Voetbal.jpg. Doordat de +REMOVE-map alle tags bevat die toegepast zijn op bestanden in de huidige en onderliggende mappen kunnen dit er meer zijn dan de tags geassocieerd met 1 bestand. Er kan dus niet rechtstreeks getoond worden welke tags geassocieerd zijn met 1 bestand in de hiërarchie. Het volledig verwijderen van een tag uit HierTag kan door om het even welke map die een tag voorstelt te verwijderen.

3.4 Tags hernoemen Door om het even welke map die een tag voorstelt binnen HierTag te hernoemen kan een tagnaam aangepast worden.

3.5 Zoeken op basis van tags Naast de mappen +ADD en +REMOVE is er nog een laatste speciale map aanwezig in elke map van de hiërarchie: +FIND. Deze bevat alle functionaliteit voor het zoeken op basis van tags. Dat deze map aanwezig is in elke map van de hiërarchie betekent ook dat wanneer er gezocht wordt op basis van tags, er enkel gezocht wordt naar bestanden in de map van waaruit +FIND geopend werd, alsook alle submappen. /Iconen/+FIND zoekt dus in alle bestanden in de map /Iconen of één van de submappen (indien die er zouden zijn). Logischerwijze komt /+FIND overeen met alle bestanden in HierTag. De map van waaruit +FIND geopend wordt, wordt in de verdere uitleg de startmap genoemd. De +FIND-map kan gebruikt worden zoals weergegeven in onderstaand schema.

Figuur 3.7 Na het openen van de map +FIND wordt een lijst weergegeven van alle beschikbare tags. Met andere woorden, alle tags toegepast op minstens 1 van de bestanden uit de startmap. Ook een speciale map +FILES is hier direct beschikbaar. 19

Na het selecteren van een tag worden 4 speciale mappen weergegeven: +AND, +OR, +COMBINE_WITH en +FILES. De eerste 3 bieden verschillende mogelijkheden om tags te combineren. Na één van deze te selecteren wordt een lijst weergegeven van combineerbare tags. Indien zo’n tag geselecteerd wordt, worden opnieuw de combinatiemogelijkheden (+AND, +OR, +COMBINE_WITH en +FILES) weergegeven. Op die wijze kan de tagselectie meer en meer uitgebreid worden.

3.5.1 Resultaatbestanden weergeven Wanneer een tagselectie volledig is kan de +FILES-map geopend worden om een lijst te zien van de bestanden die aan de selectie voldoen. Het is ook mogelijk om de +FILES-map meteen na de +FIND-map te openen. De tagselectie is dan leeg, waardoor alle bestanden uit de startmap of één van diens submappen getoond worden. Deze optie is niet beschikbaar wanneer +FIND geopend wordt vanuit de root. Daarenboven is het aangeraden deze map niet te openen wanneer het aantal bestanden in de startmap enorm groot is. Het weergeven van al deze bestanden zou aardig wat tijd kunnen kosten. Het bekijken van de resultaatbestanden vereist binnen HierTag dus een extra stap (het openen van +FILES), waar dat bij Tagsistant en Stratus niet het geval was. Dit is een bewuste keuze die de performantie verbetert, doordat gedurende het opstellen van de tagselectie geen rekenkracht verspild wordt aan het tonen van alle bestanden die aan de selectie voldoen. Aan de bestanden die te zien zijn na het openen van de +FILES-map wordt achter hun bestandsnaam, maar voor hun extensie, een uniek nummer toegevoegd. Eén van de redenen van deze toevoeging is dat meerdere bestanden met dezelfde naam kunnen voorkomen. Stel dat in het voorbeeld van figuur 2.4 de map /+FIND/voetbal/+FILES geopend wordt. Dit komt overeen met alle bestanden die getagd zijn als voetbal. Dit is zowel /Foto’s/Voetbal.jpg als /Iconen/Voetbal.jpg. Deze hebben beide dezelfde naam: Voetbal.jpg. Bestanden met eenzelfde naam kunnen niet in eenzelfde map bestaan. Door echter er een uniek nummer aan toe te voegen wordt de naam toch verschillend en kunnen ze toch beide in de +FILES-map afgebeeld worden. Als de bestanden in het voorbeeld van links naar rechts genummerd zijn van 1 tot 6 is het resultaat van /+FIND/voetbal/+FILES de bestanden Voetbal+1.jpg en Voetbal+3.jpg. In de +FILES-map is het mogelijk om bestanden te hernoemen. Wanneer het unieke nummer daarbij verwijderd wordt, wordt het automatisch terug toegevoegd. Het bestand dat in de hiërarchie overeenkomt met het resultaatbestand wordt ook van naam veranderd, weliswaar zonder het unieke nummer achteraan de naam. Naast de resultaatbestanden zijn ook de speciale mappen +ADD en +REMOVE te zien in de +FILESmap. Deze functioneren zoals uitgelegd in puntje 3.2 en 3.3. Ze kunnen gebruikt worden voor het toevoegen en verwijderen van tags van de resultaatbestanden.

3.5.2 Tagselecties opstellen De mogelijkheden voor tagselecties binnen HierTag zijn uitgebreid. Drie operatoren zijn aanwezig: +AND, +OR en +COMBINE_WITH. 3.5.2.1 De +AND-operator De +AND-operator legt op dat enkel de bestanden die getagd zijn met zowel de tag die ervoor staat als degene die erna staat voldoen aan de selectie. /+FIND/icoon/+AND/jpg/+FILES levert dus alle bestanden op die getagd zijn als zowel icoon als jpg. In het voorbeeld zijn dit de afbeeldingen van een voetbal en een volleybal.

20

3.5.2.2 De +OR-operator Deze selecteert alle bestanden die getagd zijn met de tag voor of na de +OR. /+FIND/lego/+OR/dunk/+FILES selecteert bijvoorbeeld alle bestanden die getagd zijn met lego, dunk, of beide. Dit komt overeen met de foto Basketbal.jpg en het icoon Legoblok.png. 3.5.2.3 De +COMBINE_WITH-operator combineert de gehele tagselectie die ervoor komt met de gehele tagselectie die erna komt. Een voorbeeld: +COMBINE_WITH

/+FIND/jpg/+AND/dunk/+COMBINE_WITH/icoon/+OR/lego/+FILES

Dit levert alle bestanden op die getagd zijn als jpg en dunk, gecombineerd met alle bestanden die getagd zijn als icoon of lego. 3.5.2.4 Prioriteiten van operatoren Bij de uitleg van taggebaseerde bestandssystemen werd reeds aangehaald dat bepaalde operatoren voorrang hebben op andere, en dat dit verschilt van systeem tot systeem. HierTag geeft +COMBINE_WITH voorrang op +AND, wat op zijn beurt voorrang krijgt op +OR. Dit kan best verduidelijkt worden met enkele voorbeelden: /+FIND/jpg/+AND/dunk/+OR/icoon/+FILES

Aangezien +AND voorrang heeft op +OR selecteert dit alle bestanden die getagd zijn als dunk of icoon, maar ook als jpg. Dit zijn de bestanden Basketbal.jpg uit de map Foto’s en Voetbal.jpg en Volleybal.jpg uit de map Iconen. Eenvoudig voorgesteld: jpg AND ( dunk OR icoon )

Dit blijft gelden wanneer meerdere +OR-operatoren achter elkaar gebruikt wordt, alsook wanneer een +AND-operator na een +OR-operator komt. Een voorbeeld: /+FIND/jpg/+AND/voetbal/+OR/volleybal/+OR/lego/+AND/icoon/+FILES

Het resultaat hiervan zijn alle bestanden die getagd zijn als voetbal, volleybal of lego, maar ook als jpg en icoon. Dit zijn de bestanden Voetbal.jpg en Volleybal.jpg uit de map Iconen. Eenvoudig voorgesteld: jpg AND ( voetbal OR volleybal OR lego ) AND icoon

De derde operator, +COMBINE_WITH, heeft voorrang op beide anderen. Een voorbeeld: /+FIND/foto/+AND/dunk/+COMBINE_WITH/foto/+AND/voetbal/+FILES

Dit levert een combinatie van alle bestanden die getagd zijn als foto en dunk, met alle bestanden die getagd zijn als foto en voetbal. Beide bestanden uit de map Foto’s voldoen hieraan. Deze tagselectie kan vereenvoudigd geschreven worden als: ( foto AND dunk ) COMBINE_WITH ( foto AND voetbal )

Hierbij valt op te merken dat hetzelfde resultaat bereikt kan worden met volgende tagselectie: /+FIND/foto/+AND/dunk/+OR/voetbal/+FILES

Vereenvoudigd: foto AND ( dunk OR voetbal )

Verschillende tagselecties kunnen dus hetzelfde resultaat opleveren. 21

3.5.2.5 Combineerbare tags Tijdens een tagselectie wordt na het selecteren van een operator (+AND, +OR of +COMBINE_WITH) een lijst getoond van alle combineerbare tags. Dit zijn alle tags waarmee de tagselectie uitgebreid kan worden en nog steeds resultaatbestanden opleveren. /Iconen/+FIND toont zo bijvoorbeeld de tags voetbal, icoon, bal, jpg, volleybal, basketbal, gif, lego, blok en png. Of eenvoudig gezegd, alle tags toegepast op minstens één van de bestanden in de map Iconen. Tags zoals dunk en foto die op geen van de bestanden gebruikt worden,

worden niet weergegeven aangezien deze geen resultaatbestanden zouden opleveren. /Iconen/+FIND/jpg/+AND toont de tags voetbal, icoon, bal en volleybal. Enkel de bestanden Voetbal.jpg en Volleybal.jpg binnen de map Iconen zijn geassocieerd met de tag jpg. Tags die combineerbaar zijn met de tag jpg zijn dus alle tags toegepast op deze 2 bestanden, met uitzondering van de tag jpg aangezien deze reeds in de tagselectie opgenomen is.

3.6 Up to date houden van de bestandslijst Zoals eerder vermeld spiegelt HierTag een bepaalde map uit een bestaand hiërarchisch bestandssysteem. Wanneer in deze achterliggende structuur aanpassingen worden aangebracht (bijvoorbeeld het hernoemen van bestanden), worden deze meteen gereflecteerd in de hiërarchie binnen HierTag. De database die bijhoudt welke tags geassocieerd zijn met een bestand heeft hier echter geen weet van en bevat nog steeds de oude informatie. HierTag past echter automatisch opruiming van de database toe. Dat wil zeggen, zodra een aanvraag binnenkomt voor een bestand dat niet meer bestaat in de achterliggende hiërarchie (of verplaatst is), wordt de informatie hiervan verwijderd uit de database. De eindgebruiker zal daardoor nooit onbestaande bestanden zien na het zoeken op basis van tags.

3.7 Eenvoudige back-ups Zowel de bestanden als de database die gebruikt worden door HierTag zijn elk opgeslagen in een map in de hiërarchie van een bestaand hiërarchisch bestandssysteem. Tijdens de installatie van HierTag worden deze 2 locaties geconfigureerd. Een handig gevolg hiervan is dat voor het maken van een back-up van HierTag, simpelweg deze 2 mappen dienen geback-upt te worden met back-upsoftware naar keuze. Daarnaast wordt met HierTag een applicatie meegeleverd waarmee de database met taginformatie geëxporteerd en terug geïmporteerd kan worden.

3.8 Installatie van HierTag De installatie van HierTag is vrij eenvoudig. De eerste stap is zorgen dat de nodige software geïnstalleerd is. HierTag maakt gebruik van Python (versie 2), FUSE, de FUSE Python bindings, Xapian en de Xapian Python bindings. Bij vele Linux distributies zijn deze softwarepakketten rechtstreeks en eenvoudig te installeren via het softwarepakketbeheer. De tweede stap voor de installatie van HierTag is het meegeleverde configuratiebestand invullen. Hierin zijn 3 variabelen aanwezig. De eerste variabele geeft het pad aan waar, in de bestaande hiërarchie, de originele bestanden zullen opgeslagen worden. Dit is de map die door HierTag gespiegeld zal worden. De tweede variabele geeft het pad aan waar de database zal in opgeslagen worden, ook dit is een gewone map in de bestaande hiërarchie. De laatste variabele geeft aan waar het bestandssysteem geladen (‘gemount’) zal worden. Eenmaal deze configuratie voltooid is kan het HierTag bestandssysteem geladen worden door in de terminal hiertag.pyc uit te voeren en het pad naar het configuratiebestand mee te geven als parameter. Stel dat de code van HierTag (met hiertag.pyc) in de map /home/gebruiker/hiertag

22

staat en het configuratiebestand (config.txt) ook, dan kan HierTag geladen worden met het volgende commando: python /home/gebruiker/hiertag/hiertag.pyc /home/gebruiker/hiertag/config.txt

Dit is iets ingewikkelder dan het doorlopen van een installatiewizard. Het starten door middel van een commando geeft de gebruiker echter wel de vrijheid dit aan te roepen van waar hij maar wil. Zo zou een gebruiker kunnen zorgen dat het aangeroepen wordt bij het starten van het besturingssysteem, waardoor het HierTag bestandssysteem meteen beschikbaar is.

23

4 Technische aanpak 4.1 Programmeertaal: Python Python is een high-level programmeertaal. De ontwerpfilosofie benadrukt de leesbaarheid van code. De kernsyntax en semantiek van Python zijn daarom minimalistisch, terwijl de standaard library groot en omvangrijk is. Zo gebruikt het bijvoorbeeld insprongen als block delimiters, wat ongebruikelijk is bij populaire programmeertalen. Block delimiters geven bijvoorbeeld het begin en einde van een functie aan. Bij vele populaire programmeertalen duidt een openingsaccolade het begin en een sluitaccolade het einde van een functie aan. Bij Python duidt een insprong (spaties of een tab karakter) het begin van een functie aan. Waar de insprong ongedaan gemaakt wordt eindigt de functie. Meerdere programmeerparadigma’s (zoals objectgeoriënteerd werken) worden door Python ondersteund. Daarenboven beschikt het over een volledig dynamisch type systeem (het type van variabelen wordt niet bij de initialisatie aangegeven) alsook automatisch geheugenbeheer. Interesse in de vrij aparte syntax alsook positieve ervaringen van het gebruik van Python door vrienden zorgden ervoor dat ik Python koos boven een meer vertrouwde programmeertaal zoals Java. Deze keuze heb ik mij niet beklaagd en persoonlijk verkies ik de syntax van Python nu boven deze van bijvoorbeeld Java. HierTag werd ontwikkeld in Python versie 2.5.2.

4.2 Bestandssysteem: FUSE FUSE is een afkorting voor Filesystem in Userspace. Het is een laadbare kernelmodule voor Unix-achtige besturingssystemen die het mogelijk maakt voor gewone gebruikers om een eigen bestandssystemen te ontwikkelen zonder kernelcode aan te passen. Wanneer een gebruiker in een Unix-achtig besturingssysteem een aanvraag doet naar een bestandssysteem, zoals het opvragen van de inhoud van een map, wordt deze aanvraag vanuit de user space doorgestuurd naar het VFS, het Virtual Filesystem, in de kernel. Dit is een abstractielaag bovenop het echte bestandssysteem die een interface, een ‘contract’, tussen de kernel en het echte bestandssysteem specificeert. Het schrijven van een bestandssysteem vereist het schrijven van een kernelmodule die aan dit ‘contract’ voldoet. Doordat dit ‘contract’ eenduidig is voor alle compatibele bestandssystemen kan het besturingssysteem werken met een scala aan bestandssystemen zonder hiervoor specifieke aanpassingen te moeten aanbrengen. De aanvraag voor het bekijken van de inhoud van een map wordt door het VFS dus doorgestuurd naar het echte bestandssysteem, dat een resultaat teruggeeft aan het VFS. Het besturingssysteem kan vervolgens dit resultaat gebruiken voor het weergeven van een lijst aan de gebruiker. Het nadeel van deze manier van werken is dat voor het ontwikkelen van een nieuw bestandssysteem, een kernelmodule geschreven moet worden. Dit is niet eenvoudig. FUSE brengt hier echter een oplossing voor. Het neemt de plaats in van het bestandssysteem als kernelmodule en stuurt alle binnenkomende aanvragen (vanuit het VFS) door naar de user space. Daar stelt FUSE een API beschikbaar (libfuse). Wie een eigen bestandssysteem wil ontwikkelen kan een applicatie schrijven die deze API gebruikt. Het beantwoorden van de aanvragen (system calls) van het VFS gebeurt dus niet langer op niveau van de kernel, maar op niveau van de user space. Figuur 4.1 geeft een mooi overzicht van hoe dit in zijn werk gaat. Linksboven is een commando weergegeven dat een gebruiker zou kunnen uitvoeren om de inhoud van de map /tmp/fuse te 24

tonen. Deze aanvraag wordt doorgestuurd naar het VFS (linksonder), die het doorstuurt naar de kernelmodule van het echte bestandssysteem (rechtsonder). Klassieke bestandssystemen zoals NFS en Ext3 geven een antwoord aan de vraag van het VFS. De FUSE kernelmodule stuurt de vraag echter nog verder door: terug naar de user space (via libfuse). Daar wordt geantwoord op de aanvraag door een ‘bestandssysteem’ dat de FUSE API implementeert. Dat antwoord passeert vervolgens terug langs de FUSE kernelmodule en het VFS om uiteindelijk door het besturingssysteem gebruikt te worden voor het weergeven van de lijst van bestanden en mappen.

Figuur 4.1: de werking van FUSE Dat bestandssystemen die gebruik maken van FUSE in de user space draaien heeft het grote voordeel dat alles waartoe een gewone applicatie toegang heeft gebruikt kan worden, bijvoorbeeld een databasetype naar keuze. De beste methode om te demonstreren wat voor mogelijkheden dit biedt is het opsommen van enkele bestaande bestandssystemen die FUSE gebruiken: o

GmailFS: Een bestandssysteem dat data opslaat als mails in Gmail.

o

YouTubeFS: Lokaal bladeren tussen je favoriete YouTube video’s zonder naar de YouTube website (www.youtube.com) te gaan.

o

Bluetooth File System: De bluetooth apparaten in de buurt als een mappenlijst weergeven en de mogelijkheid bieden bestanden op de apparaten te plaatsen door deze simpelweg te kopiëren naar de map die overeenkomt met het apparaat.

o

WikipediaFS: Omgaan met artikels van Wikipedia (www.wikipedia.org) alsof het echte bestanden op de harde schijf zijn.

o

FlickrFS: Uploaden en downloaden van foto’s van of naar Flickr (www.flickr.com) vanuit het bestandssysteem, alsook zoeken tussen de foto’s. Een foto kopiëren in het bestandssysteem komt bijvoorbeeld overeen met het uploaden van deze naar de website.

Honderden andere voorbeelden zijn terug te vinden op de website van FUSE (www.fuse.sourceforge.net). Ook Tagsistant en Stratus die eerder genoemd werden gebruiken FUSE. Bij het implementeren van HierTag werd gebruik gemaakt van FUSE versie 2.7.3.

25

4.2.1 FUSE API Voor het implementeren van de functionaliteit van een FUSE bestandssysteem beschikt de FUSE API over een groot aantal methodes, die overeenkomen met system calls, die geïmplementeerd kunnen worden. De werkwijze die hiervoor gebruikt wordt is het maken van een klasse die overerft van de FUSE klasse. Vervolgens kunnen de methodes van de FUSE klasse overschreven worden met een eigen implementatie. Het is niet noodzakelijk om alle methodes te overschrijven. Enkele van deze methodes zijn readdir(), getattr(), mkdir(), unlink(), rmdir(), chmod(), chown(), rename(), ... Het is belangrijk te beseffen dat één actie van een gebruiker op het bestandssysteem niet steeds vertaalt in één aangeroepen methode (system call). Meestal wordt een combinatie van een aantal methodes gebruikt, die soms nog ietwat verschillen tussen verschillende besturingssystemen. Het weergeven van de bestanden uit een bepaalde map triggert onder andere readdir() en getattr(). Readdir() geeft een lijst terug van alle bestanden, mappen, links, ... die voorkomen in de map. Vervolgens wordt voor elk van deze items getattr() aangeroepen om te achterhalen of het gaat om een bestand, een map, een link, ... alsook welke rechten erop zijn toegepast, de bestandsgrootte, de datum van aanmaak, enz. Ook de manier waarop applicaties omgaan met bestanden is niet altijd even voorspelbaar. Een eenvoudig voorbeeld hiervan is Gedit, een teksteditor. Wanneer een gebruiker met Gedit een bestand aanpast en deze aanpassingen opslaat, wordt het bestaande bestand niet gewoon overschreven. Gedit maakt eerst een tijdelijk verborgen bestand aan met een unieke naam. Dit bestand wordt de nodige rechten en eigenaar gegeven (chmod() en chown() methodes), waarna de inhoud wordt weggeschreven. Het oude bestand wordt hernoemd (rename() methode) naar een bestand met dezelfde naam, gevolgd door een tilde. Daarna wordt het tijdelijke verborgen bestand hernoemd naar de juiste bestandsnaam. Gedit zorgt er standaard (dit is aanpasbaar in de voorkeuren) dus voor dat er steeds een backup is van de vorige versie van het bestand met dezelfde naam, gevolgd door een tilde. FUSE biedt gelukkig een debugmodus aan waarmee, in combinatie met eigen output, kan achterhaald worden welke methodes achtereenvolgens worden aangeroepen. Enkele eenvoudige acties op het bestandssysteem zorgen echter al snel voor duizenden lijnen debuginformatie, waardoor het achterhalen van problemen niet eenvoudig is.

4.2.2 Python bindings Om een bestandssysteem in Python te schrijven dat gebruik maakt van FUSE zijn Python bindings voor FUSE beschikbaar. Deze komen qua werking overeen met de algemene FUSE API. Meegeleverd met de Python bindings is een voorbeeld-bestandssysteem dat een map uit het bestaande bestandssysteem spiegelt. In praktijk komt dit erop neer dat de functies van de FUSE API een implementatie hebben die de Python functie aanroept met de gelijkwaardige functionaliteit. Voor de unlink() functie is dit bijvoorbeeld os.unlink(), voor getattr() is dit os.lstat(), enz. Dit voorbeeld-bestandssysteem gaf een goed startpunt voor de ontwikkeling van HierTag.

4.3 Database Een database die de relaties tussen bestanden en tags bijhoudt is de kern van HierTag. Hoewel het soms mogelijk is om hele bestanden in een database op te slaan wordt meestal enkel het pad naar het bestand opgeslagen. Een zoekopdracht in de database levert aldus de paden op naar de bestanden die eraan voldoen, waarmee de echte bestanden opgehaald kunnen worden. Dit is de

26

methode die HierTag gebruikt aangezien, zoals eerder besproken, HierTag een bestaand hiërarchisch bestandssysteem gebruikt voor de effectieve opslag van de bestanden.

4.3.1 RDBMS Vele mensen denken bij het woord database meteen aan een RDBMS, een Relationeel Database Management Systeem. Dit soort database bestaat uit één of meerdere tabellen, die onderlinge relaties kunnen hebben. Voorbeelden van dergelijke databases zijn MySQL, PostgreSQL en Microsoft SQL Server. De data van HierTag zouden op verschillende manieren opgeslagen kunnen worden in een dergelijke database. Deze methodes worden hieronder besproken. 4.3.1.1 Eén enkele tabel

Figuur 4.2 Dit is een gedenormaliseerd model dat bestaat uit slechts één enkele tabel. Deze tabel bestaat uit de velden pad en tags (in zijn eenvoudigste vorm). In het veld tags worden alle tags geassocieerd met het bestand, aangegeven door het veld pad, achter elkaar gezet, gescheiden door bijvoorbeeld een spatie. Tagselecties Zoeken op tags kan door in de WHERE-clausule van de SQL gebruik te maken van LIKE. Onderstaand voorbeeld zoekt bijvoorbeeld de bestanden op waarmee de tag foto geassocieerd is: SELECT * FROM HierTag WHERE tags LIKE ‘%foto%’

Het gebruik van operatoren bij de tagselectie blijft ook relatief eenvoudig. Om alle bestanden te zoeken die geassocieerd zijn met de tag foto en 2009 kan de volgende query gebruikt worden: SELECT * FROM HierTag WHERE tags LIKE ‘%foto%’ AND tags LIKE ‘%2009%’

Hier zijn echter enkele problemen mee. Zo wordt er gezocht naar de tagnaam in het hele veld tags, maar er wordt niet aangegeven dat er voor en na de tag een spatie moet staan. Een bestand geassocieerd met de tag fotoboek zou aldus ook gevonden worden wanneer gezocht wordt op de tag foto. Om dit op te lossen zou gezocht moeten worden op de tag, met een spatie ervoor en erna. Bovendien zou het veld tags moeten beginnen en eindigen met een spatie. Een ander probleem is dat LIKE in dit geval niet zo performant zou zijn. Er kan bijvoorbeeld geen index gebruikt worden voor het zoeken. Dit in tegenstelling tot bijvoorbeeld filteren op pad. Stel dat alle bestanden opgevraagd dienen te worden die zich bevinden in de map /fotos/2009 of één van diens submappen. De volgende SQL query zou gebruikt kunnen worden: SELECT * FROM HierTag WHERE pad LIKE ‘/fotos/2009/%’

27

Doordat hier de inhoud van het veld pad gekend is vanaf het begin, maar niet tot op het einde, kan wel een index gebruikt worden voor performantieverbetering. Bij de tags daarentegen is de inhoud niet bekend vanaf het begin, de tag komt ‘ergens’ in het veld voor, en in dat geval kan geen index gebruikt worden. Daarnaast zijn er nog andere problemen. Doordat alle tags in één veld staan moet dit veld groot genoeg zijn. Hoe groter het veld, hoe slechter de performantie van LIKE. Fulltext search, zoals bijvoorbeeld MySQL (MyISAM engine) en PostgreSQL bieden, kan de performantie van zoeken naar tekst binnen een veld wel verbeteren. Combineerbare tags Tijdens het opstellen van tagselecties geeft HierTag steeds enkel combineerbare tags weer. Dit zijn tags welke effectief resultaatbestanden zouden opleveren. Het eenvoudigste voorbeeld van combineerbare tags is wanneer de gebruiker de map /+FIND opent. In dit geval zijn alle tags in de database combineerbare tags. Er wordt immers gezocht tussen alle bestanden in alle mappen. Bij dit datamodel is het niet zo eenvoudig om deze lijst op te stellen. Alle rijen van de tabel moeten namelijk doorlopen worden. Bovendien moeten voor elke rij de tags ‘manueel’ uit het veld tags gehaald worden. Dit is vrij omslachtig. Wordt de +FIND-map niet vanuit de root geopend maar vanuit een submap zoals /Foto’s, dan wordt enkel gezocht naar bestanden binnen die submap en elk van haar submappen. De tags die dus getoond worden bij /Foto’s/+FIND zijn enkel de tags geassocieerd met bestanden binnen deze map /Foto’s. Om deze lijst van tags te vinden worden dus alle rijen van de tabel overlopen waarbij het veld pad duidt op een bestand binnen deze map /Foto’s. Er kan gezegd worden dat enkel de relevante rijen overlopen worden. Tijdens het opstellen van de tagselectie zelf wordt de hoeveelheid relevante rijen nog meer beperkt. Neem het volgende voorbeeld: /+FIND/foto/+AND/2009/+AND

De gebruiker wil de tagselectie ‘foto AND 2009’ nog verder uitbreiden. De relevante rijen zijn hier alle rijen waarbij zowel de tag foto als de tag 2009 voorkomen in het veld tags. Dit is logisch, aangezien dit alle rijen zijn die als resultaatbestand zouden te zien zijn wanneer de gebruiker de tagselectie niet verder probeerde uit te breiden: /+FIND/foto/+AND/2009/+FILES

Tags die geassocieerd zijn met andere bestanden (en dus rijen) kunnen nooit een resultaat opleveren wanneer ze deze tagselectie uitbreiden. Immers, een bestand dat geassocieerd is met de tags foto en bbq, maar niet met de tag 2009, zal nooit het resultaat zijn van de volgende tagselectie: /+FIND/foto/+AND/2009/+AND/bbq/+FILES

Er valt op te merken dat niet steeds de hele tagselectie in rekening wordt gebracht bij het bepalen van de combineerbare tags. Stel bijvoorbeeld dat de gebruiker de volgende map heeft geopend: /+FIND/foto/+AND/2009/+OR

De gebruiker wil dus een tagselectie opstellen zoals deze: foto AND ( 2009 OR x )

De combineerbare tags zijn dus eigenlijk net dezelfde tags als wanneer de gebruiker de keuze maakte voor de tag 2009. Bij het opzoeken van de combineerbare tags zijn de relevante rijen dus 28

deze waar de tag foto in het veld tags voorkomt. De tag 2009 wordt niet gebruikt bij het bepalen van de relevante rijen. Ditzelfde principe geldt bijvoorbeeld bij de +COMBINE_WITH-operator. Deze maakt een onderscheid tussen aparte tagselecties. Bij het opzoeken van combineerbare tags is dus enkel de tagselectie die na de laatste +COMBINE_WITH-operator staat relevant. Een klein voorbeeld: /+FIND/foto/+AND/2009/+AND/bbq/+COMBINE_WITH/muziek/+AND

Doordat de +COMBINE_WITH-operator het begin van een nieuwe tagselectie aangeeft zijn de relevante rijen hier deze waarbij de tag muziek voorkomt in het veld tags. De tags foto, 2009 en bbq behoren tot een aparte tagselectie en hebben dus geen invloed op de bepaling van de relevante rijen. Tags toevoegen, hernoemen en verwijderen Tags zijn bij deze methode altijd geassocieerd met een bestand, ze bestaan niet op zichzelf. In principe zou een speciaal ‘bestand’ toegevoegd kunnen worden aan de database dat getagd wordt met alle, of alle niet gebruikte, tags. Het moet dan bovendien uit de resultaatbestanden gefilterd worden. Dit zou daarenboven problemen opleveren omdat de inhoud van het veld tags voor dit speciale ‘bestand’ dan enorm lang zou worden. Het hernoemen van tags is niet eenvoudig. Om dit te doen moet een lijst van alle bestanden die geassocieerd zijn met de te hernoemen tag opgehaald worden. Vervolgens moet voor elk item in deze lijst de te hernoemen tag aangepast worden in het veld tags. Diezelfde methode moet gebruikt worden voor het verwijderen van een tag. Besluit Deze methode heeft erg veel nadelen voor de functionaliteit die HierTag nodig heeft en wordt dus niet gebruikt. 4.3.1.2 Twee tabellen

Figuur 4.3 Bij deze methode wordt de informatie opgedeeld in 2 tabellen: Files en Tags. Hierbij bestaat er een one-to-many relatie tussen de 2, waarbij voor elke rij in de tabel Files, meerdere rijen kunnen bestaan in de tabel Tags. Een bestand waarvan het pad opgeslagen is in de Files-tabel kan dus meerdere tags met zich geassocieerd krijgen door rijen aan te maken in de tabel Tags waarbij het veld file_id verwijst (foreign key) naar het veld id (primary key) van het bestand in de tabel Files. Tagselecties De queries zijn hier wel ingewikkelder dan bij de oplossing met slechts één tabel. Alle bestanden weergeven die getagd zijn als foto en 2009 kan bijvoorbeeld als volgt: SELECT f.id, f.pad FROM Files f JOIN Tags t ON f.id = t.file_id WHERE t.tag IN (‘foto’,’2009’) GROUP BY f.id, f.pad HAVING COUNT(f.id) = 2

Door de laatste regel weg te laten worden alle bestanden gezocht met de tag foto of 2009.

29

De COMBINE_WITH-operator kan in de SQL query gegoten worden als een voorbeeld volgende tagselectie:

UNION.

Neem als

( foto AND verjaardag ) COMBINE_WITH ( muziek AND feest )

Dit kan in een SQL query gegoten worden als volgt: SELECT f.id, f.pad FROM Files f JOIN Tags t ON f.id = t.file_id WHERE t.tag IN (‘foto’,’verjaardag’) GROUP BY f.id, f.pad HAVING COUNT(f.id) = 2 UNION SELECT f.id, f.pad FROM Files f JOIN Tags t ON f.id = t.file_id WHERE t.tag IN (‘muziek’,’feest’) GROUP BY f.id, f.pad HAVING COUNT(f.id) = 2

Hoe uitgebreider de tagselectie, en hoe meer verschillende operatoren gecombineerd worden, des te ingewikkelder wordt de SQL query. Stel dat de AND- en OR-operator gecombineerd worden in de volgende tagselectie: foto AND ( 2008 OR 2009 )

Dit kan moeilijk rechtstreeks in een SQL query gegoten worden. Door de tagselectie echter te herschrijven naar een tagselectie met hetzelfde resultaat, wordt dit wel mogelijk: ( foto AND 2008 ) COMBINE_WITH ( foto AND 2009 )

Hiervoor kan dan de UNION-methode gebruikt worden zoals eerder uitgelegd. Het performantieprobleem bij het gebruik van LIKE dat zich stelde bij de oplossing met slechts één tabel valt bij deze oplossing weg. Tags worden vergeleken met de volledige inhoud van het veld tag uit de tabel Tags en moet dus altijd volledig correct zijn. Het ophalen van alle tags is bij deze methode bovendien ook vrij eenvoudig door het gebruik van een GROUP BY op de tabel Tags: SELECT tag FROM Tags GROUP BY tag

Combineerbare tags Om de combineerbare tags op te halen bij deze methode kan de SQL query van het relevante deel van de tagselectie gecombineerd (JOIN) worden met de tabel Tags. Bij de oplossing met slechts één tabel werd besproken wat het relevante deel van de tagselectie is. Stel bijvoorbeeld dat de gebruiker aan het zoeken is naar bestanden met de tags foto en 2009, dan kan volgende SQL query gebruikt worden om een lijst te bekomen van combineerbare tags: SELECT rt.tag FROM

( SELECT f.id FROM Files f JOIN Tags t ON f.id = t.file_id WHERE t.tag IN (‘foto’,’bbq’) GROUP BY f.id HAVING COUNT(f.id) = 2

30

) as rf JOIN tags rt ON rf.id = rt.file_id WHERE rt.tag NOT IN (‘foto’,’bbq’) GROUP BY rt.tag

Deze SQL query selecteert alle tags toegepast op de resultaatbestanden die voldoen aan de tagselectie ‘foto AND 2009’, behalve de tags foto en bbq zelf. Tags toevoegen, hernoemen en verwijderen Een nadeel van deze methode is dat tags niet op zich bestaan, ze zijn altijd gelinkt aan een bestand. HierTag moet echter wel tags kunnen aanmaken alvorens ze toe te passen op een bestand. Dit kan opgelost worden door bijvoorbeeld toe te staan dat het veld file_id in de tabel Tags de waarde NULL mag hebben. Voor het hernoemen van tags moet elke rij in de tabel Tags, waarbij het veld tag de te hernoemen tag is, aangepast worden. Dit kan eenvoudig met een enkel UPDATE-commando: UPDATE Tags SET tag = ‘nieuwenaam’ WHERE tag = ‘oudenaam’

Tags verwijderen ten slotte kan door het verwijderen van alle rijen waarbij het veld tag de te verwijderen tag is. Dit kan met een enkel DELETE-commando: DELETE FROM Tags WHERE tag = ‘tagnaam’

Besluit Deze oplossing zou kunnen gebruikt worden voor HierTag. Wel een nadeel is dat queries vrij ingewikkeld kunnen worden naarmate tagselecties uitgebreider worden. 4.3.1.3 Drie tabellen

Figuur 4.4 Een laatste methode voor relationele databases is het gebruik van 3 tabellen. Dit is de meest genormaliseerde methode en gebruikt een many-to-many relatie tussen de tabel Files en de tabel Tags. Voor het beschrijven van deze relatie wordt de tussentabel Files_Tags gebruikt, welke id’s van bestanden koppelt aan id’s van tags. Tagselecties De SQL queries komen hierbij grotendeels overeen met deze van de oplossing met 2 tabellen. Hier wordt echter nog een extra JOIN gedaan. Het selecteren van de bestanden geassocieerd met de tags foto en 2009, zoals in het voorbeeld aangehaald bij de methode met 2 tabellen, kan hier door de volgende SQL query: SELECT f.id, f.pad FROM Files f JOIN Files_tags ft ON ft.file_id = f.id JOIN Tags t ON ft.tag_id = t.id WHERE t.tag IN (‘foto’,’2009’) GROUP BY f.id, f.pad HAVING COUNT(f.id) = 2

31

Tags toevoegen, hernoemen en verwijderen Verschillend met de vorige oplossing is dat een tag hier op zich kan bestaan door deze toe te voegen aan de tabel Tags, maar er (nog) niet naar te linken vanuit de tabel Files_Tags. Ook een tag hernoemen is eenvoudig, dit dient enkel te gebeuren in de tabel Tags. Een tag verwijderen is ook eenvoudig, slechts één lijn in de tabel Tags moet verwijderd worden. Bij databases waarbij de relaties tussen tabellen ingegeven kan worden en waarbij de ‘ON DELETE CASCADE’ optie gebruikt kan worden, zullen de rijen van de tabel Files_Tags die verwijzen naar de verwijderde tag automatisch verwijderd worden. Is dit niet het geval dan dient dit apart nog gedaan te worden. De ‘ON DELETE CASCADE’ optie is bijvoorbeeld beschikbaar bij MySQL (Innodb engine) en PostgreSQL. Besluit Net als de oplossing met 2 tabellen is deze oplossing bruikbaar voor HierTag. De queries zijn hier echter nog net iets ingewikkelder.

4.3.2 Xapian 4.3.2.1 Wat is Xapian? Xapian is een ‘Open Source Search Engine Library’ die het probabilistic information retrieval model en het boolean model ondersteunt. Information retrieval is de wetenschap die zich bezig houdt met het zoeken naar documenten, informatie binnen die documenten en metadata betreffende die documenten, maar ook het doorzoeken van relationele databases en het wereldwijde web (www). Het duidelijkste voorbeeld hiervan zijn zoekmachines die het mogelijk maken om het web te doorzoeken op basis van kernwoorden. In tegenstelling tot relationele databases werkt Xapian niet met tabellen. De database bestaat uit documenten, welke omschreven zijn door een collectie termen. Een document is om het even wat men wenst terug te vinden. Naast het opslaan van de termen geassocieerd met een document kan ook de positie van de term in de inhoud van het document opgeslagen worden. Van een document kan gezegd worden dat het relevant is wanneer het dat was wat de gebruiker wou vinden. Een document is dus relevant of niet. In het probabilistic model echter is er sprake van een waarschijnlijkheid (‘probability’) van relevantie. Xapian maakt het mogelijk om het probabilistic model te gebruiken bij het zoeken. De resultaten worden hierbij gerangschikt volgens hun waarschijnlijkheid van relevantie. BM25 is de effectieve naam van de rankingfunctie. Bij de ranking wordt rekening gehouden met factoren zoals term frequentie (hoe vaak komt de term voor in een document?), de posities van termen binnen de documenten (er kan bijvoorbeeld gezocht worden op zinnen, waarbij documenten waarbij de termen dichter bij elkaar staan een hogere ranking krijgen), enz. Daarnaast is het ook mogelijk het boolean model te gebruiken. Termen worden gecombineerd in een query met operatoren zoals AND, OR en NOT. Enkel documenten die volledig voldoen aan de query zijn aanwezig in de resultaatset en allen hebben ze een evenwaardige ranking. Er is geen ordening op basis van hoe ‘goed’ de resultaten zijn. Ook een nadeel hierbij is dat wanneer de gebruiker bijvoorbeeld een typefout maakt, het mogelijk is dat documenten die relevant zijn niet meer voldoen aan de query en aldus niet meer in de resultaatset terechtkomen. HierTag maakt gebruik van deze laatste methode. Immers, HierTag geeft zelf altijd een lijst weer van de mogelijke (combineerbare) tags, waardoor typefouten in principe niet voorkomen. Bij het ontwikkelen van HierTag werd gebruik gemaakt van Xapian versie 1.0.7. 32

4.3.2.2 Opslag van data Elk bestand komt overeen met een document in de Xapian database. Het pad (binnen HierTag) naar het bestand wordt opgeslagen als de inhoud van het document. Vervolgens wordt het pad opgesplitst in stukken waarbij elke map die in het pad voorkomt opgeslagen wordt als een term, geassocieerd met het document. Deze termen krijgen een speciale prefix, ‘XP’, en een volgnummer. Neem het volgende voorbeeld: /Foto’s/2009/BBQ/001.jpg

Dit pad resulteert in de volgende termen: XP/0/Foto’s XP/1/2009 XP/2/BBQ XP/3/001.jpg

Daarnaast worden de tags die geassocieerd zijn met het bestand ook opgeslagen als termen. Termen binnen Xapian hebben een lengtelimiet, namelijk 245 karakters. Aangezien bij het opslaan van de mappen in het pad als termen ook nog een prefix en volgnummer toegevoegd wordt, wordt de limiet voor een bestandsnaam en mapnaam door HierTag gezet op 230 karakters. Deze limiet wordt gehandhaafd bij het aanmaken en hernoemen van bestanden en mappen zodat er geen problemen kunnen optreden. Heeft een bestand in de achterliggende hiërarchie een te lange bestandsnaam dan kan het niet verplaatst (en dus ook niet getagd) worden. Enkel de bestandsnaam aanpassen gaat. Heeft een map in de achterliggende hiërarchie een te lange bestandsnaam dan kunnen er geen bestanden in geplaatst worden en zal de inhoud binnen HierTag steeds leeg zijn (ook al staan er in de achterliggende hiërarchie wel bestanden in). Aangezien tags (termen) steeds met een document geassocieerd worden, is het niet mogelijk om een tag toe te voegen aan de database zonder deze te koppelen aan een document. Om die reden is een speciaal document toegevoegd waaraan alle tags gekoppeld worden. De inhoud van dit document is ‘+ALL_TAGS’, en het is ook getagd als dusdanig. Daardoor kan het document er later gemakkelijk uitgefilterd worden. Alle acties naar de database gebeuren via de Xapian library. Er wordt geen gebruik gemaakt van een taal zoals SQL. Een document aanmaken komt bijvoorbeeld overeen met het aanmaken van een Document object en het toevoegen van de inhoud en termen door middel van een aantal methodes van de klasse Document. Dit Document object wordt dan ten slotte via de (Writable)Database klasse toegevoegd aan de database. Elk document dat toegevoegd wordt aan de database krijgt een uniek id, het docid, waarmee het geïdentificeerd kan worden. 4.3.2.3 Padfiltering en tagselecties Bij het zoeken naar resultaatbestanden tellen 2 factoren mee. De eerste factor is de padfiltering, waarmee de zoekopdracht gelimiteerd kan worden tot een bepaalde map (en diens submappen). /Foto’s/+FIND limiteert zo bijvoorbeeld de zoekopdracht tot de map /Foto’s. Padfiltering gebeurt niet wanneer gezocht wordt vanuit de root: /+FIND. In de query die opgesteld wordt voor de zoekopdracht (een Query object), kan deze filtering aangegeven worden door het pad op te splitsen en de mappen die erin voorkomen aan te geven als termen. /Foto’s/2009/+FIND resulteert zo bijvoorbeeld in de volgende query: XP/0/Foto’s AND XP/1/2009

33

Hierbij wordt het ook duidelijk waarom er een volgnummer gebruikt wordt bij het opslaan van de padinfo als termen. Enkel bestanden (documenten) waarbij de eerste map in het pad Foto’s is en de tweede map in het pad 2009 mogen resultaatbestanden zijn. Bestanden uit de map /2009/Foto’s tellen niet mee. Merk op dat de query niet wordt ingegeven zoals hierboven getoond. Een Query object combineert steeds 2 termen of 2 Query objecten. Bij 2 termen, zoals hierboven, kan bijvoorbeeld de Query constructor gebruikt worden met als eerste parameter de operator AND (opgehaald uit een enumeratie) en als tweede en derde parameter de 2 termen. De tweede factor bij het zoeken naar resultaatbestanden is de tagselectie. In principe kan die net als de padfiltering manueel opgebouwd worden waarbij steeds de operator tussen 2 termen of Query objecten wordt aangegeven. Xapian biedt echter ook een QueryParser klasse, die het mogelijk maakt om een tagselectie, zoals het voorbeeld hieronder, om te zetten naar een Query object. foto AND 2009 AND bbq AND hamburger

Wat HierTag dus doet is het pad dat overeenkomt met de tagselectie omzetten naar deze vorm, zodat het geparst kan worden naar een Query object. Xapian geeft prioriteit aan de AND-operator boven de OR-operator. Neem volgende tagselectie: foto AND 2008 OR 2009

Xapian interpreteert dit als: ( foto AND 2008 ) OR 2009

HierTag moet er aldus voor zorgen dat bij het omzetten van een tagselectie in padvorm naar een tagselectie om te laten parsen, het omgekeerde gebeurt: foto AND ( 2008 OR 2009 )

Xapian kent bovendien geen COMBINE_WITH-operator, dus dit moet HierTag omzetten naar een OR-operator. De volgende tagselectie: foto AND 2009 COMBINE_WITH muziek AND metal

Kan omgezet worden naar: ( foto AND 2009 ) OR ( muziek AND metal )

Bij het zoeken naar resultaatbestanden worden de 2 factoren, padfiltering en tagselectie, gecombineerd met een AND-operator. Een eenvoudig voorbeeld: /Foto’s/2009/+FIND/bbq/+OR/londen/+FILES

Dit wordt omgezet in de volgende query: ( XP/0/Foto’s AND XP/1/2009 ) AND ( bbq OR londen )

Bij het uitvoeren van de query wordt een RSet, een ‘Relevance Set’, gegenereerd. Deze kan overlopen worden om alle documenten die resultaatbestanden voorstellen terug te vinden. Door het uitlezen van de inhoud van het document kan het pad van het echte bestand achterhaald worden. De resultaatbestanden die te zien zijn in de +FILES-map hebben steeds een uniek nummer achter de bestandsnaam geplakt. Dit is het unieke docid waar eerder over gesproken werd. Het is daar voornamelijk om te zorgen dat 2 resultaatbestanden met dezelfde naam naast elkaar kunnen aanwezig zijn in de resultaatlijst, maar biedt het bijkomende voordeel dat het meteen als 34

identificeermiddel gebruikt kan worden bij operaties zoals het openen, hernoemen, verplaatsen, ... van de bestanden. Het spreekt vanzelf dat bij het verplaatsen (of hernoemen) van een bestand, het pad in de inhoud van het document dat overeenkomt met dit bestand, alsook de termen die betrekking hebben op het pad, aangepast worden. 4.3.2.4 Combineerbare tags Zoals bij de databaseoplossingen voor een RDBMS besproken, kan de lijst van combineerbare tags tijdens een tagselectie achterhaald worden door het relevante deel van de tagselectie uit te voeren op de database en alle tags die toegepast zijn op de resultaatbestanden van deze tagselectie samen te nemen. Xapian maakt het mogelijk om de RSet die de resultaatbestanden van deze relevante tagselectie bevat, om te zetten in een ESet, een ‘Expand Set’. Dit is een lijst van termen (tags) die gebruikt kunnen worden om de originele query verder uit te breiden. Met andere woorden, Xapian geeft meteen een lijst van de combineerbare tags. 4.3.2.5 Threads Xapian is niet thread safe. Dit wil zeggen dat er problemen kunnen optreden wanneer meerdere threads tegelijkertijd hetzelfde object gebruiken. FUSE gebruikt meerdere threads (hoewel het optioneel kan beperkt worden tot 1 thread). Er zou dus een probleem kunnen optreden. Hoewel voor elke toegang tot de Xapian database een nieuw Database object zou kunnen aangemaakt worden, is er binnen HierTag gewerkt met een RLock object, een ‘reentrant lock’ object. Wanneer een operatie op de database wordt uitgevoerd dient het thread dat deze operatie uitvoert het lock te bemachtigen. Vervolgens kan het alle nodige operaties ononderbroken uitvoeren. Eenmaal dit voltooid is wordt het lock vrijgegeven zodat andere threads die een operatie op de database moeten uitvoeren het kunnen bemachtigen. Immers, slechts 1 thread kan tegelijkertijd het lock bemachtigen, andere threads blocken terwijl ze wachten tot het lock bemachtigd kan worden. Een RLock verschilt van een gewoon Lock doordat het zorgt dat wanneer een thread het lock bemachtigd heeft, het dit nogmaals kan bemachtigen. Stel dat in een functie een aantal operaties dienen uitgevoerd te worden op de database. Voor de operaties wordt het lock bemachtigd, na de operaties wordt het vrijgegeven. Wanneer binnen deze operaties bijvoorbeeld een andere functie wordt aangeroepen die ook operaties uitvoert op de database, dan zal in deze laatste functie gebruik gemaakt worden van hetzelfde lock. Bij een gewoon Lock zou het thread het lock in deze tweede functie niet kunnen bemachtigen omdat het reeds bemachtigd is... door zichzelf. Bij het gebruik van een RLock kan het lock in de tweede functie echter wel bemachtigd worden omdat het hetzelfde thread is dat het lock reeds bezit.

35

5 Beperkingen Er zijn enkele beperkingen bij het gebruik van HierTag waarvan de oorzaak buiten HierTag zelf ligt. Deze zijn hier opgesomd.

5.1 Caching door bestandsbeheer-applicaties Bestandsbeheer-applicaties zoals Nautilus, Konquerer en Dolphin maken het gemakkelijk voor de gebruiker om bestanden via een grafische interface op te zoeken, te verplaatsen, te hernoemen, enz. Om de performantie te verbeteren doen zij aan caching. De inhoud van een map wordt tijdelijk opgeslagen door de applicatie. Komt de gebruiker later in dezelfde map terug dan kan de inhoud geladen worden uit het geheugen in plaats van deze opnieuw op te vragen aan het bestandssysteem. Jammer genoeg brengt dit een nadeel met zich mee. HierTag werkt met virtuele mappen (+ADD, +REMOVE, +FIND, +AND, ...), waarvan de inhoud snel kan veranderen, zonder dat de bestandsbeheer-applicatie dit door heeft. Deze baseert zich voor het weergeven van de inhoud nog op zijn cachegeheugen en toont de aanpassingen niet. In een eerste situatie is de gebruiker in de map /+FIND gegaan. De lijst van tags is opgehaald en opgeslagen in het cachegeheugen van de bestandsbeheer-applicatie. De gebruiker voegt nu een tag toe door in de map /+ADD een nieuwe map aan te maken. Hij slaat ook een bestand op dat geassocieerd wordt met die map. Wanneer de gebruiker terug gaat naar de map /+FIND laadt de bestandsbeheer-applicatie de inhoud uit zijn cache. De nieuw toegevoegde tag zit hier nog niet tussen en is dus ook niet bruikbaar (tenzij manueel ingegeven). Pas na het vernieuwen (‘refresh’) van de mapinhoud, waarbij de bestandsbeheer-applicatie de inhoud opvraagt aan het bestandssysteem zelf, wordt deze zichtbaar. In een tweede situatie voegt de gebruiker een tag toe aan een bestand. Hiertoe verplaatst hij het bestand /Documenten/Test.txt naar de map /Documenten/+ADD/test. Dit verloopt succesvol. De bestandsbeheer-applicatie gaat er daarom van uit dat het bestand Test.txt niet langer in de map /Documenten aanwezig is omdat het succesvol verplaatst is naar de map /Documenten/+ADD/test. Wanneer de gebruiker vervolgens de inhoud van de map /Documenten bekijkt haalt de bestandsbeheer-applicatie de inhoud uit zijn cache op maar toont het bestand Test.txt niet in de lijst omdat het denkt dat het verplaatst is. Als de gebruiker de inhoud van de map echter vernieuwt, en de bestandbeheer-applicatie de inhoud dus gaat opvragen aan het bestandssysteem, staat het bestand wel weer in de lijst. Andere bestandsbeheer-applicaties, waaronder Thunar, ondervinden geen last van deze beperking.

5.2 Tags verdwijnen na aanpassing bestand door sommige applicaties Wanneer bepaalde applicaties gebruikt worden voor het aanpassen van bestanden gaat de associatie van tags met het bestand (schijnbaar) verloren waardoor de bestanden niet meer terug te vinden zijn bij zoekopdrachten op basis van tags. De oorzaak hiervan is de manier waarop deze applicaties omgaan met bestanden. Een voorbeeld van een applicatie waarbij dit probleem zich stelt is Gedit, een teksteditor. Wanneer met Gedit het document /Test.txt wordt aangepast en opgeslagen gebeurt het volgende: 1. Gedit maakt een verborgen bestand aan met een uniek id, bijvoorbeeld /.gedit-saveGXETTU. Hiermee zijn geen tags geassocieerd.

36

2. Gedit hernoemt het bestand /Test.txt naar een back-upbestand dat dezelfde naam draagt, gevolgd door een tilde: /Test.txt~. In de database wordt deze aanpassing ook doorgevoerd. De tags die geassocieerd werden met het /Test.txt bestand worden nu geassocieerd met het back-upbestand /Test.txt~. 3. Gedit hernoemt het verborgen bestand /.gedit-save-GXETTU naar /Test.txt. Doordat Gedit het bestaand bestand waarmee tags geassocieerd zijn eigenlijk vervangt door een nieuw bestand waarmee geen tags geassocieerd zijn, lijkt het alsof de tags geassocieerd met het bestand verdwijnen. Ze zijn echter nog steeds geassocieerd met het back-upbestand. Doordat de naam van het back-upbestand op het einde een tilde heeft wordt het standaard echter standaard verborgen door de meeste bestandsbeheer-applicaties.

5.3 Resultaatbestanden aanpassen lukt niet met bepaalde applicaties Aanpassingen aan resultaatbestanden, bestanden in een +FILES-map die het resultaat zijn van een tagselectie, kunnen door bepaalde applicaties niet worden opgeslagen. Ook hier kan Gedit als voorbeeld aangehaald worden. Wanneer een resultaatbestand met Gedit wordt aangepast en opgeslagen geeft Gedit een melding dat het niet mogelijk was een back-upbestand aan te maken, dat het bestand kan worden opgeslagen maar dat moest er een fout optreden, het oude bestand verloren kan gaan. Zoals in puntje 5.2 uitgelegd probeert Gedit eerst een verborgen bestand aan te maken. Het is echter niet mogelijk om in de +FILES-map een bestand aan te maken. Immers, waar binnen de hiërarchie zou het opgeslagen moeten worden? En welke tags zouden ermee geassocieerd moeten worden? De enige mogelijkheid die overblijft is rechtstreeks naar het bestand schrijven. Moest er echter wat mislopen dan kan het bestand verloren gaan. Daarom geeft Gedit een melding die de gebruiker de keuze laat om dit te doen of niet. Applicaties die het beste samenwerken met HierTag zijn aldus applicaties die bestanden rechtstreeks aanpassen.

37

6 Opgeloste problemen Hieronder worden enkele problemen besproken die tijdens de ontwikkeling van HierTag opgelost werden.

6.1 Een map verwijderen resulteerde in een oneindige lus Eén van de implementeerbare methodes van de FUSE API is rmdir(). Op het eerste zicht lijkt het verwijderen van mappen dus eenvoudig. Rmdir() wordt echter enkel gebruikt voor het verwijderen van lege mappen. Wanneer een map met inhoud verwijderd wordt gebeurt het volgende: 1. De inhoud van de map wordt uitgelezen door middel van de readdir() methode. 2. Voor elk item dat readdir() returnt wordt getattr() aangeroepen, waarmee onder andere het onderscheid gemaakt kan worden tussen mappen, bestanden, symbolische links, ... 3. Voor elk item dat getattr() aangeeft als een map worden stap 1 en 2 uitgevoerd. Alle mappen worden dus recursief overlopen. 4. Elk bestand en elke lege map wordt verwijderd. Voor bestanden wordt de unlink() methode aangeroepen, voor lege mappen de rmdir() methode. 5. Als alle inhoud verwijderd is, wordt de rmdir() methode aangeroepen voor de originele map die verwijderd diende te worden. Dit is een vereenvoudigde weergave van hoe het verwijderen van een map kan gaan. De precieze werking verschilt van systeem tot systeem. Finder, de standaard bestandsbeheerapplicatie van Mac OS X, verzamelt bijvoorbeeld eerst een lijst van alle te verwijderen bestanden en mappen en start dan pas met het effectief doorvoeren van deze acties. Finder kan daardoor aan de gebruiker tonen hoeveel bestanden nog verwijderd moeten worden voor het verwijderen voltooid is. Nautilus, de standaard bestandsbeheer-applicatie voor de Gnome desktop, begint reeds met het verwijderen van bestanden en mappen terwijl het deze doorloopt. HierTag voegt in alle mappen van de hiërarchie speciale virtuele mappen toe: +ADD, +REMOVE en +FIND. Na het selecteren van +FIND, kunnen tags geselecteerd worden. Tagselecties kunnen enorm uitgebreid zijn. Door in een tagselectie de +COMBINE_WITH-operator te gebruiken is het zelfs mogelijk om als het ware een ‘nieuwe’ tagselectie te beginnen die gecombineerd wordt met de tagselectie die voor de operator stond. Dit betekent dat de +FIND-map theoretisch gezien oneindig diep is. (In de praktijk zijn er factoren als een maximum padlengte die dit limiteren.) Dit brengt een probleem met zich mee. Wanneer een map in de hiërarchie verwijderd wordt, wordt deze recursief overlopen om alle bestanden en mappen die erin staan te verwijderen. Aangezien elke hiërarchische map speciale virtuele mappen bevat, worden deze ook doorlopen. Doordat die virtuele mappen oneindig diep zijn (+FIND dan toch) blijft het recursief overlopen verdergaan in een oneindige lus. Ditzelfde probleem stelt zich bij het verwijderen van tags (voorgesteld door mappen) aangezien deze ook oneindig diep kunnen zijn. Om dit probleem op te lossen werden enkele mogelijke oplossingen bedacht die hieronder opgesomd worden.

6.1.1 Een nieuwe speciale map: +TRASH In elke map van het bestandssysteem wordt een nieuwe speciale map toegevoegd: +TRASH. Om bestanden of mappen te verwijderen worden deze verplaatst naar de +TRASH-map. Dit komt in FUSE binnen als een aanvraag voor de rename() methode. Daarin kan de actie dan opgevangen worden en kunnen de nodige acties ‘manueel’ uitgevoerd worden.

38

In een grafische omgeving zou de +TRASH-map op een handige plaats gezet worden. In de bestandsbeheer-applicatie zou dit een bladwijzer (‘bookmark’) kunnen zijn, zodat bestanden en mappen die verwijderd moeten worden rechtstreeks erin gesleept kunnen worden. Dit idee bracht echter enkele problemen met zich mee. Het is eerder een workaround dan een echte oplossing voor het probleem. Een gebruiker die per ongeluk toch op de klassieke manier een map probeert te verwijderen komt nog steeds in een oneindige lus terecht. Hetzelfde geldt voor een applicatie die zonder gebruikerstussenkomst bestanden en mappen aanmaakt en verwijdert. Daarbij is het dan maar de vraag of de applicatie dit goed afhandelt of simpelweg crasht.

6.1.2 Een verborgen .+RMDIR map Het leek erop dat wanneer een te verwijderen map recursief doorlopen wordt, dit gebeurt in de volgorde dat de readdir() methode de bestands- en mapnamen returnt, en dus niet alfabetisch. Daardoor leek het mogelijk om een speciale verborgen map toe te voegen in elke map: .+RMDIR. (bestanden die beginnen met een punt zijn verborgen in Unix-achtige besturingssystemen.) Door deze via de readdir() methode als eerste item te returnen, zou dit de eerste submap zijn waarop, bij het recursief doorlopen, de readdir() methode aangeroepen wordt. Wanneer in readdir() gemerkt wordt dat het een aanvraag is voor een .+RMDIR-map, kan de bovenliggende map (die dus vermoedelijk verwijderd wordt), toegevoegd worden aan een lijst van te verwijderen mappen. Na het doorlopen van de .+RMDIR-map wordt de readdir() methode op de volgende submap uitgevoerd. Indien dit een speciale map is (bv. +FIND), kan in de readdir() methode gecontroleerd worden of deze map zich in een te verwijderen map bevindt. Doordat bij de readdir() op de .+RMDIR-map de bovenliggende map in de lijst van te verwijderen mappen geplaatst werd is dit het geval. In dit geval returnt de readdir() op de speciale map niets: de speciale map lijkt ineens leeg. De map is dus niet meer oneindig diep en het probleem is opgelost. Dit leek in de meeste gevallen goed te werken. De .+RMDIR-map werd echter toch niet altijd als eerste map doorgelopen waardoor in sommige gevallen deze methode toch niet werkte. Daarnaast was er nog een probleem. Het toevoegen van een map aan de lijst van de te verwijderen mappen gebeurde in de readdir() methode. Dit kon niet in de rmdir() methode omdat deze methode niet altijd direct aangeroepen wordt tijdens het recursief doorlopen van de mappen. Dit betekent dus ook dat om het even wanneer een readdir() van de .+RMDIR-map gebeurt, de bovenliggende map in de lijst komt van te verwijderen mappen. Een applicatie die zonder dat de gebruiker er controle over heeft de .+RMDIR-map uitleest plaatst dus onbewust de bovenliggende map in de lijst met te verwijderen mappen. Op zich heeft dit geen desastreuze gevolgen, de speciale mappen zullen gewoon leeg lijken. Het is echter niet optimaal. Een time-out timer zou kunnen zorgen dat mappen die in de lijst met te verwijderen mappen terechtkomen maar na een bepaalde tijd toch nog niet verwijderd zijn automatisch uit de lijst worden verwijderd. Al bij al is deze methode weer het probleem omzeilen en niet het bieden van een echte oplossing. Bovendien werkt het maar een bepaald gedeelte van de tijd.

6.1.3 De speciale mappen verbergen Een laatste mogelijkheid is de speciale mappen verbergen. In dit geval wordt niet bedoeld een punt voor de naam te zetten om ze te verbergen voor de gebruiker, maar ze niet op te nemen in de lijst van bestand- en mapnamen die de readdir() methode returnt. De speciale mappen zijn dus simpelweg niet te zien. De gebruiker kan echter wel in de map gaan door deze manueel achter het pad in te vullen. Wanneer de getattr() methode wordt aangeroepen voor de speciale map wordt namelijk wel gereturnt dat deze bestaat en dat het een map is, ook al stond de map 39

niet in de lijst die readdir() returnde. Hetzelfde geldt voor de readdir() methode. Als die wordt aangeroepen voor de speciale map zal die het juiste resultaat geven. In Nautilus kan een gebruiker manueel in een map gaan door in de ‘Location bar’ de naam achter het pad te typen. Wil de gebruiker vanuit de map /Foto’s in de speciale map +FIND gaan, dan kan deze (eventueel met de snelkoppeling ctrl + L) in de ‘Location bar’ /+FIND achter /Foto’s typen. Doordat de speciale mappen niet voorkomen in de resultaten van readdir() aanvragen worden ze niet recursief doorlopen en is het probleem van het verwijderen van mappen opgelost. Dit is de enige methode die het probleem echt oplost. Dat de speciale mappen niet te zien zijn is echter enorm ongebruiksvriendelijk naar de eindgebruiker toe. Gelukkig kon een ‘trucje’ toegepast worden om de mappen toch zichtbaar te maken voor de gebruiker. Eerst en vooral wordt de naam van alle speciale mappen aangepast door er een punt voor te zetten. De werking blijft verder volledig hetzelfde. Daarnaast wordt er gezorgd dat de readdir() methode de namen van deze speciale mappen returnt, maar dan zonder het punt ervoor. Wanneer vervolgens voor elk item dat readdir() returnt getattr() aangeroepen wordt, worden die speciale mappen (zonder punt aan het begin) aangegeven als symbolische links, niet mappen. Wanneer één van die symbolische links gevolgd wordt, wat overeenkomt met het aanroepen van de symlink() methode, wordt de echte map, welke een punt voor de naam heeft, als doel aangegeven. Voor de gebruiker betekent dit dat wanneer hij een map opent, hij naast de aanwezige bestanden en mappen, symbolische links ziet staan naar de speciale mappen, die onzichtbaar zijn. Door een symbolische link te volgen komt de gebruiker in de speciale map terecht. Dit komt overeen met het manueel ingeven van het pad naar die speciale map. Als de gebruiker bijvoorbeeld de map /Foto’s opent, ziet hij de bestanden Voetbal.jpg en Basketbal.jpg, alsook 3 symbolische links: +ADD, +REMOVE en +FIND. Wanneer hij de symbolische link +ADD volgt, krijgt hij de inhoud van de map /Foto’s/.+ADD te zien. De gebruiker kan dus bijvoorbeeld naar het volgende pad gaan: /Foto’s/+FIND/voetbal/+OR/basketbal/+AND/dunk

Achterliggend wordt dit echter vertaald naar: /Foto’s/.+FIND/voetbal/.+OR/basketbal/.+AND/dunk

Bij het verwijderen van een map wordt de map recursief overlopen. Wanneer hierbij een symbolische link tegengekomen wordt, wordt de link gewoon verwijderd. De link wordt dus niet gevolgd, waardoor niet in de oneindig diepe speciale mappen gegaan wordt.

6.2 De toevoeging van +SAVE in de +ADD-map Nadat een bestand opgeslagen wordt, kan een gebruiker dit nog verder aanpassen en opnieuw opslaan, en dit zonder het gebruikte programma af te sluiten. Dit betekent dat wanneer een bestand in een map wordt opgeslagen, het ook effectief in die map moet bestaan, zodat het geüpdatet kan worden. In HierTag kunnen bij het opslaan van een bestand meteen een aantal tags geassocieerd worden met het bestand. Een gebruiker sloeg in eerdere versies van HierTag het bestand Reisverslag.txt bijvoorbeeld op in de map: /Reizen/Londen/+ADD/londen/+AND/reis/+AND/verslag

40

Dit betekende dat het bestand in de hiërarchie werd opgeslagen in de map /Reizen/Londen, en de tags londen, reis en verslag meteen geassocieerd werden met het bestand. Wanneer de gebruiker het bestand had opgeslagen wou hij het verder kunnen aanpassen en opnieuw opslaan. De gebruikte applicatie probeerde dus het volgende bestand op te slaan: /Reizen/Londen/+ADD/londen/+AND/reis/+AND/verslag/Reisverslag.txt

Het bestand bestond daar echter niet, want het was opgeslagen in de map /Reizen/Londen. Om die reden zorgde HierTag ervoor dat het bovenstaande bestand automatisch gemapt werd naar het echte bestand: /Reizen/Londen/Reisverslag.txt

Wanneer een applicatie binnen de +ADD-map dus informatie van een bestand opvroeg (getattr() methode), of een nieuwere versie opsloeg, werd dit door HierTag steeds gemapt naar het echte bestand. Dit werkte goed. Er kwam echter een probleem kijken bij het toevoegen van tags aan een bestaand bestand. Om de tag txt te associëren met het hierboven gebruikte bestand, moest het bestand verplaatst worden naar: /Reizen/Londen/+ADD/txt

De nieuwe locatie van het bestand leek aldus: /Reizen/Londen/+ADD/txt/Reisverslag.txt

Doordat dit echter ging om een bestand binnen de +ADD-map, werd het volgens de eerder omschreven regel gemapt naar het bestand in de map voor de +ADD: /Reizen/Londen/Reisverslag.txt

Met andere woorden, het originele bestand werd verplaatst naar een locatie die gemapt werd naar het originele bestand. Het gevolg was een foutmelding: het bestand bestaat al. Om dit op te lossen werd in HierTag de +SAVE-map toegevoegd binnen de +ADD-map. Wanneer een applicatie informatie over een bestand opvraagt, of een nieuwere versie opslaat, waarvan het denkt dat het in deze map zit, wordt het gemapt naar het echte bestand in de map voor de +ADD. Vraagt een applicatie echter informatie op over een bestand, waarvan het denkt dat het in de +ADD-map (of een submap met uitzondering van +SAVE) zit, dan gebeurt er geen mapping. Het bestand bestaat dus niet. Bestaande bestanden kunnen dus naar daar verplaatst worden voor het toevoegen van tags. Een voorbeeld: /Reizen/Londen/+ADD/londen/+AND/reis/+AND/verslag/+SAVE/Reisverslag.txt

Dit bestand wordt gemapt naar de map voor de +ADD, dus naar het bestand: /Reizen/Londen/Reisverslag.txt

Echter: /Reizen/Londen/+ADD/londen/+AND/reis/+AND/verslag/Reisverslag.txt

Dit bestand wordt niet gemapt naar de map voor de +ADD en bestaat dus niet. Het bestand Reisverslag.txt verplaatsen naar bijvoorbeeld /Reizen/Londen/+ADD/txt resulteert dus in het associëren van de tag txt met het bestand, en niet in een foutmelding. 41

6.3 Toevoegen van tags aan HierTag via de gebruikersinterface Zoals bij de werking van HierTag besproken, zie puntje 3.2, kunnen tags op zich toegevoegd worden door het aanmaken van een nieuwe map binnen de +ADD-map. Bepaalde bestandsbeheer-applicaties maken echter niet rechtstreeks de map aan met behulp van de mkdir() methode. Deze maken eerst een map aan met de naam ‘untitled folder’ en hernoemen deze dan naar de door de gebruiker gekozen naam. Het probleem bij deze methode is dat tags geen spaties mogen bevatten. Het is dus niet toegestaan om in de +ADD-map een submap aan te maken met spaties in de naam. Echter, sommige bestandsbeheer-applicaties doen dit uit zichzelf doordat ze eerst de map ‘untitled folder’ aanmaken. In HierTag moest aldus worden voorzien dat dit een uitzondering is die wel toegestaan wordt. Wel is ervoor gezorgd bestanden niet getagd kunnen worden met deze ‘tag’ en dat deze leeg is wanneer ze geopend wordt binnen de +ADD-map.

42

7 Toekomstmogelijkheden 7.1 Mac OS X versie MacFUSE brengt het idee van FUSE naar Mac OS X. Het biedt meerdere API’s, waarvan één een superset is van de FUSE API gebruikt op Linux. Dit betekent dat veel FUSE bestandssystemen rechtstreeks bruikbaar zijn binnen Mac OS X. Ook Xapian is beschikbaar voor Mac OS X. Python daarenboven is zelfs standaard geïnstalleerd. Door dit alles is het relatief eenvoudig om een FUSE bestandssysteem, zoals HierTag, te porten naar Mac OS X. Tijdens een korte test van HierTag in Mac OS X leek de basis te werken. Er zijn echter enkele problemen die nader bekeken zouden moeten worden voor het succesvol porten.

7.2 Eigen mapnamen voor speciale mappen In de huidige versie zijn speciale mappen zoals +ADD, +REMOVE en +FIND in de broncode vastgelegd. Ze kunnen niet zomaar aangepast worden. In een nieuwere versie zou er aanpassingsfunctionaliteit bij kunnen komen zodat bijvoorbeeld Nederlandstalige termen gebruikt kunnen worden.

7.3 Tagsuggesties Aangezien er een grote kans is dat bestanden binnen eenzelfde map overeenkomstige tags met zich geassocieerd hebben, is het nuttig om bij het opslaan van een bestand in die map, de tags geassocieerd met de andere bestanden bij elkaar te groeperen als suggesties. Dit zou kunnen geïmplementeerd worden binnen de +ADD-map. Andere tagsuggesties zouden aangereikt kunnen worden gebaseerd op mapnamen uit het pad naar de desbetreffende map alsook op de bestandsnaam. Wanneer een bestand opgeslagen wordt in /Foto’s/2009, zijn foto en 2009 tags die hoogst waarschijnlijk op het bestand toegepast kunnen worden. Suggesties zouden nog verder kunnen gaan met synoniemen en omvattende tags. Met dit laatste worden tags bedoeld die geïnsinueerd worden. Een tag heavymetal insinueert dat het gaat om een muziekbestand. De tag muziek zou aldus gesuggereerd kunnen worden. Er kan gezegd worden dat de tag muziek andere tags ‘omvat’, waaronder heavymetal, pop, rock, ...

7.4 Negaties in tagselecties Dit zijn tagselecties waarbij de resultaatbestanden bepaalde tags niet bevatten. Dit kan geïmplementeerd worden door middel van een speciale +NOT-map. Een eenvoudig voorbeeld is het weergeven van alle foto’s van de voorbije jaren. Dit kan anders omschreven worden als het weergeven van alle foto’s, met uitzondering van deze van 2009: /+FIND/foto/+NOT/2009

7.5 Tags met bepaalde functionaliteit Een andere handige toevoeging aan HierTag zou het hangen van bepaalde functionaliteit aan een tag kunnen zijn. Hiermee wordt bedoeld dat door het toevoegen van één tag aan een bestand, bepaalde functionaliteit geactiveerd wordt. Een eenvoudig voorbeeld hiervan zou zijn een bestand taggen als gedeeld. Het zou dan automatisch gedeeld worden binnen het lokale netwerk.

7.6 Totaalaantallen In de huidige versie van HierTag kan een gebruiker niet weten hoeveel resultaatbestanden er zijn, zonder de +FILES-map te openen. Zijn dit er te veel en wil de gebruiker de tagselectie verder 43

uitbreiden, dan moet hij teruggaan naar de bovenliggende map (van waaruit de geopend werd).

+FILES-map

Door achter de naam van de +FILES-map het aantal resultaten te plakken zou een gebruiker op voorhand de hoeveelheid resultaatbestanden kunnen weten en aldus inschatten of hij de tagselectie best nog verder specificeert of niet.

7.7 Uitbreiding gebruikersinterface Doordat HierTag eigenlijk als een applicatie in de user space werkt, kan hier bovenop een applicatie ontwikkeld worden. Zo zou het bijvoorbeeld mogelijk zijn een bestandsbeheerapplicatie te ontwikkelen die het gebruik van HierTag nog eenvoudiger en directer kan maken. Daarnaast zou ook simpelweg een plug-in geschreven kunnen worden voor een bestaande bestandsbeheer-applicatie zoals Nautilus. Een dergelijke plugin zou het mogelijk maken om bij een bestand de geassocieerde tags te bekijken, deze makkelijker toe te voegen en te verwijderen (zonder de nood aan het verplaatsen van het bestand), etc.

44

Besluit Hoewel het originele idee het ontwikkelen van een taggebaseerd bestandssysteem was bleek na onderzoek het integreren van zowel een hiërarchisch als taggebaseerd bestandssysteem de beste methode. HierTag is een succesvolle implementatie van het idee, waarbij het geheel voorgesteld wordt in een hiërarchische structuur. Speciale mappen worden toegevoegd aan de bestaande hiërarchie die toelaten om tags toe te voegen en te verwijderen van bestanden, alsook om te zoeken naar bestanden op basis van tags. Bij het zoeken kan bovendien gebruik gemaakt worden van AND-, OR- en COMBINE_WITH-operatoren waarmee tags op verschillende wijzen gecombineerd kunnen worden. Doordat het HierTag bestandssysteem wordt voorgesteld in een hiërarchische structuur kan het gebruikt worden binnen een bestandsbeheer-applicatie naar keuze en is het beschikbaar in dialoogvensters voor het openen en opslaan van bestanden. Er dient dus geen aparte applicatie gebruikt te worden om over de voordelen van tags te beschikken. Voor het weergeven van het systeem in een hiërarchische vorm werd FUSE gebruikt. FUSE stuurt de system calls die het besturingssysteem uitvoert voor bijvoorbeeld het opvragen van de inhoud van een map, het opvragen van informatie van een bestand en het verplaatsen van een bestand door naar HierTag. HierTag heeft een implementatie voor elk van deze system calls en voert de nodige acties uit, stuurt de nodige informatie terug, ... Tijdens het implementeren van deze system calls heb ik enorm veel bijgeleerd over de werking van een bestandssysteem. Eén actie van de gebruiker resulteert namelijk meestal in meerdere system calls. Begrijpen wat precies wanneer aangeroepen wordt is belangrijk om een correcte implementatie te kunnen doen. Als database voor het opslaan van de relaties tussen bestanden en tags werd Xapian gebruikt. Anders dan relationele databases, wat veel mensen verstaan onder ‘een database’, is Xapian een information retrieval library. Daar waar bij een relationele database tabellen aanwezig zijn die onderlinge relaties hebben, wordt bij Xapian gesproken over documenten die termen (tags) met zich geassocieerd hebben. Door termen (tags) te combineren kunnen documenten teruggevonden worden. Er wordt geen gebruik gemaakt van een taal als SQL, maar van klasses die Xapian aanlevert. Bij het onderzoek naar de werking van Xapian heb ik heel wat bijgeleerd over information retrieval, wat een wetenschap is die zich bezig houdt met het zoeken naar documenten, informatie binnen die documenten en metadata betreffende die documenten, maar ook het doorzoeken van relationele databases en het wereldwijde web (www). Zowel FUSE als Xapian waren mij volledig onbekend. Ook Python, de programmeertaal waarin HierTag geschreven is kende ik niet. Het was voor mij een uitdaging om met al deze technologieën te leren werken en er een volledig werkend systeem mee te bouwen. Gedurende de bachelorproef heb ik mijn kennis met betrekking tot bestandssystemen enorm uitgebreid. Ik heb succesvol een eigen bestandssysteem ontworpen en geïmplementeerd en heb hierbij kennis gemaakt met (voor mij) nieuwe technologieën zoals FUSE, Xapian en Python alsook nieuwe principes zoals information retrieval. Dit maakt de bachelorproef voor mij een succes.

45

Literatuurlijst FUSE, http://fuse.sourceforge.net, geraadpleegd 08-05-2009 FUSE, http://en.wikipedia.org/wiki/Filesystem_in_Userspace, geraadpleegd 08-05-2009 FUSE Wiki, http://apps.sourceforge.net/mediawiki/fuse/, geraadpleegd 08-05-2009 Tag (metadata), http://en.wikipedia.org/wiki/Tag_(metadata), geraadpleegd 08-05-2009 Stratus, http://wealthandpower.org/stratus/, geraadpleegd 09-05-2009 Tagsistant, http://www.tagsistant.net, geraadpleegd 09-05-2009 Punakea, http://www.nudgenudge.eu/punakea, geraadpleegd 09-05-2009 Leap, http://www.ironicsoftware.com/leap/, geraadpleegd 09-05-2009 XTagFS, http://code.google.com/p/xtagfs/, geraadpleegd 09-05-2009 DBFS, http://tech.inhelsinki.nl/dbfs/, geraadpleegd 09-05-2009 Python, http://www.python.org/, geraadpleegd 10-05-2009 Python (programming language), http://en.wikipedia.org/wiki/Python_(programming_language), geraadpleegd 10-05-2009 Tags: Database schemas, http://www.pui.ch/phred/archives/2005/04/tags-databaseschemas.html, geraadpleegd 11-05-2009 Tags with MySQL fulltext, http://www.pui.ch/phred/archives/2005/05/tags-with-mysqlfulltext.html, geraadpleegd 11-05-2009 Tagsystems: performance tests, http://www.pui.ch/phred/archives/2005/06/tagsystemsperformance-tests.html, geraadpleegd 11-05-2009 SQL Performance – Indexes and the LIKE clause, http://myitforum.com/cs2/blogs/jnelson/archive/2007/11/16/108354.aspx, geraadpleegd 11-05200 MySQL, http://www.mysql.com, geraadpleegd 11-05-2009 PostgreSQL, http://www.postgresql.org, geraadpleegd 11-05-2009 Xapian, http://xapian.org, geraadpleegd 11-05-2009 Xapian Documentation, http://xapian.org/docs/, geraadpleegd 11-05-2009 Xapian API overview, http://xapian.org/docs/overview.html, geraadpleegd 11-05-2009 Theoretical Background (Xapian), http://xapian.org/docs/intro_ir.html, 11-05-2009 Xapian-core Class Index, http://xapian.org/docs/apidoc/html/classes.html, geraadpleegd 11-052009 Information Retrieval, http://en.wikipedia.org/wiki/Information_retrieval, geraadpleegd 11-052009 Standard Boolean Model, http://en.wikipedia.org/wiki/Standard_Boolean_model, geraadpleegd 11-05-2009 Okapi BM25, http://en.wikipedia.org/wiki/Probabilistic_relevance_model_(BM25), geraadpleegd 11-05-2009

46