Actuele Trends in Databases

Actuele Trends in Databases Gert Nelissen 0725614 2010 - 2011

1 1.1

Deel I Scientific RDF Databases

Michael Mertens RDF databases zijn een subset van graph gatabases. Ze zijn nuttig in bepaalde contexten omdat de semantische betekenis van onderwerpen er goed in beschreven kunnen worden. Hierdoor kan querying op een andere - intu¨ıtievere manier. In de praktijk kan er gebruik gemaakt worden van zogenaamde federal databases. Deze specifieke vorm van RDF databases splitsen queries op om ze te dispatchen naar andere databases. Dit heeft als nadeel natuurlijk de performantie.

1.2

RDF Databases & Constraints

Jeroen Appermont / Tom Hoogsteyns In een RDF database kan er meer structuur gebracht worden dankzij RDFs. Dit staat voor RDF Schema en laat toe constraints te modelleren. Er worden via functies op klasses en properties keys en foreign keys gedefinieerd. Een ASK constraint resulteert in een ja of een neen. Aan de hand van dit resultaat kan bepaald worden of er aan een bepaalde constraint al dan niet voldaan wordt. Dit was een uiteenzetting die eerder moeilijk te volgen was. Niet alleen waren er heel wat slides, ook waren die slides dan nog erg ingewikkeld. Een 50-tal slides over 25 minuten levert een halve minuut per slide op. Maar stof van dit niveau verdiient minstens vier keer die tijd. Ook opvallend was de sterke beheersing van het Engels.

1.3

Databases & Computer Games I

Thomas Van Brussel / Raf Vandeput Bij games is het gewenst dat elke vooruitgang permanent is. Het is niet vaak gewenst dat wanneer een speler sterft, of wanneer er een al dan niet hardware of softwarematige failure optreedt, dat er opnieuw objecten vrijgespeeld dienen te worden. Ook inconsistenties willen we natuurlijk vermijden. Daarom is het noodzakelijk de game-state regelmatig op te slaan. Hierrond steken zich enkele vragen de kop op. Wat moet er precies worden opgeslagen (enkel de meest recente informatie)? Naar waar slaan we dit op (log files)? En om de hoeveel tijd moet dit gebeuren? In een utopische wereld gebeurt dit elke tick, waarbij een tick een atomaire stap is in het systeem. Wanneer we over een game met een bepaalde framerate spreken, is dit dus per frame. Het opslaan van de game-state is echter reken-intensief 1

waardoor dit in de praktijk niet altijd mogelijk is. Naast het updaten pas na verschillende ticks te doen, bestaan er ook enkele algoritmes die in deze context nuttig zijn. Hiertoe behoort ARIES. Dit is echter niet game-specifiek en kan in andere praktijken gebruikt worden. Ook werd er gesproken over het algoritme wait-free-ping-pong. Hierbij worden er updates geregistreerd terwijl eerder geregistreerde updates opgeslagen worden op de hard disks.

1.4

Databases & Computer Games II

Mario De Groof / Nick Gaens We kunnen niet over computer games spreken zonder over artifici¨ele intelligentie te spreken. Vooral in MMORPG’s zijn AI’s in grote getallen aanwezig. Een artificieel karakter wordt hier een NPC genoemd. Dit staat voor non playable character. In klassieke games zijn er vaak enkele NPC’s met een geavanceerd AI-plan, terwijl de andere AI’s de eerer genoemde gewoonweg volgen, of een dommer AI-plan volgen. Het is niet mogelijk elke NPC aan een rekenintensief algoritme te onderwerpen. Er is dus sprake van een trade off tussen ofwel een complexe AI, ofwel veel NPC’s. Dankzij SGL echter, wat staat voor Scalable Gaming Language, kan er door middel van scripts intelligentie ge¨ımiteerd worden. Deze taal maakt gebruik van algebra¨ısche optimalisaties.

1.5

MapReduce

Kristof Bamps / Wouter Deroey Het World Wide Web bestaat uit miljoenen webpages verspreid over verschillende systemen. Als bijvoorbeeld een zoekmachine als Google hier bewerkingen over wil doen, of deze pages wil opslaan, stellen we ons hierbij enkele praktische vragen. Hoe gaat de communicatie in zijn werk? Wa met machine failure? Wat met optimisatie? Wat met lokaliteit? De oplossing hiervoor is MapReduce. Dit is een framework door Google waardoor er zeer snel zeer veel data verwerkt kan worden. Dit kan omdat een taak vaak opgesplitst kan worden in meerdere deeltaken. Via de functie Map wordt een taak opgedeeld (divide). De functie Reduce verzamelt deze data als resultaat (conquer). Een master node beheert dit proces. Deze methode is schaalbaar en fouttolerant. Er heerst de vraag wie de verwerkte data verzamelt uit de handen van de worker nodes en doorgeeft aan de reduce nodes. Dit is namelijk een intensief gebeuren. Het zou dus sterk zijn dat enkel de master node hierin een rol speelt. Er wordt gesuggereerd dat het framework dit behandeld, maar hierrond bevindt zich een grijze mist.

1.6

MapReduce Demo

Wim Leers Een voorbeeld van een implementatie van MapReduce is Hadoop. Dit is volledig geschreven in Java waardoor het werkt op een groot aantal systemen. Als voorgestelde drawback wordt er gesuggereerd dat dit een sterke vertraging met zich meebrengt, maar tegenwoordig is Java lang niet meer zo traag als bijvoorbeeld C++. Dit is zo omdat de huidige Java Virtual Machine op voorhand code compileert naar optimale omstandigheden en dus meer dan een interpreter is. Verder blijkt dat Hadoop erg moeilijk te installeren is en lijdt aan zogenaamde Zombies. Dit zijn processen die in feite niets meer doen, maar wel nog actief blijven.

2

1.7

Web Link Structure and its Usage for Sponsored Search Markets

Jimmy Michiels / Daniele Alfarone Op het web is er in grote mate sprake van een markt. Websites bevatten namelijk vaak advertenties en andere vormen van betaalde items die liefst zo veel mogelijk bekeken worden. Een website kan zo geld krijgen als er een andere website bezocht wordt via hun website. Daarom moeten er zoveel mogelijk bezoekers op een webpage komen zodat ze daar - al dan niet ongewild - reclame kunnen zien en op links klikken. Het is dus gewenst voor een website om hoog te staan in de zoekresultaten van een zoekmachine. Een zoekmachine gebruikte verschillende algoritmes om pagina’s te rangschikken in de volgorde die volgens hun gewenst is door hun gebruikers. Deze ranking gebeurt op het aantal keywoorden, meta-data, word-density, enzovoort. Ook het aantal links dat naar de webpage verwijzen en het aantal links van op de webpage in kwestie naar andere webpages spelen een rol. Bovendien worden links en pages gewaardeerd volgens dit systeem. Linken naar een page die als slecht gemarkeerd is levert dus een slecht reputatie-punt op. Hierdoor zal de eigen page lager staan in de rankings. Om een page hoger te krijgen in een ranking zijn er zogenaamde white hat search engine optimisations die we eerder in deze paragraaf al besproken hebben, maar ook black hat SEO’s. Dit zijn praktijken als artikels overnemen van andere pages, al dan niet lichtjes gewijzigd met de hand of door woordenboeken, of onzichtbare tekst plaatsen zodat bepaalde keywords opgenomen worden door de webcrawler, enzovoort. Een webcrawler kan deze vorm van misbruik echter niet altijd detecteren.

1.8

Network Dynamics: Population Models - Information Cascades

Thomas De Craemer / Mario De Groof Na een leuk experiment werd er uitgelegd dat mensen informatie overnemen van mensen rondom zich in de mate waarop deze informatie verspreid is onder die mensen. Wanneer iemand vijf vrienden een bepaalde link ziet Twitteren, is de kans groot dat hij zelf deze link zal retweeten of op zijn minst bekijken. Ook wanneer er een foto op Facebook staat zal deze meer aandacht krijgen wanneer er hierop vele reacties zijn. De mens beschikt namelijk net als andere dieren over een sterke kuddegeest die zich laat zien in zulke situaties. Hierrond heet Bayes enkele rules opgesteld waarmee kansen berekend kunnen worden in deze context. Deze kansen zijn echter mathematisch en houden weinig tot geen met de emotie van de mens. Hierdoor zullen deze regels in vele gevallen en op de grote getallen vaak wel kloppen, maar klaarblijkelijk niet altijd, zo blijkt uit het eerder genoemde experiment! Deze psychologie kan natuurlijk wel gebruikt worden in (online) viral marketing.

2 2.1

Deel II Flash Databases

Nick Gaens Flash geheugen brengt enkele problemen met zich mee wanneer we spreken over filsystems. Flash geheugen is sneller dan een klassieke harde schijf, en heeft een kleinere access time. Het is echter wel duurder en kent een 3

kortere levensduur. Na een honderdduizend tot een miljoen cycles worden geheugencellen namelijk onbruikbaar. Het topic is daarom niet enorm actief in de onderzoekswereld. Er zijn twee soorten flash geheugen, namelijk NAND en NOR. De eerste geniet een snellere erasemogelijkheid. De tweede kent een minder lange levensduur maar wordt door de snelheid vaak gebruikt in computerchips. Verder kennen we het verschil tussen de enkelcellige SLC en de tweecellige MLC. We wensen de levensduur van flash geheugen te verlengen. Daarom zullen we de vernielende erasings proberen te verspreiden. Opmerkelijk is ook dat sommige datastructuren op flash geheugen niet optimaal werken. Daarom wordt er gegrepen naar bijvoorbeeld FTL, wat staat voor Flash Transition Layer. Dit filesystem hoeft geen seek optimalisatie, maar wel re-use optimalisatie en wearlevelling. Een andere manier is het gebruiken van controllers die ervoor zorgt dat het voor externen niet nodig is rekening te houden met het type geheugen. Voor bijvoorbeeld het gebruikende operating system lijkt het alsof er gewerkt wordt met een gewone hard disk. Flash geheugen kent eventueel een toekomst in de games, met name de artifici¨ele intelligentie. Er kan dan namelijk gebruik gemaakt worden van mass data.

2.2

Flash Databases

Sibren Polders / Lesley Van Der Wee Flash drives zijn sneller, hebben minder energie nodig, zijn schokbestendig, betrouwbaar en bieden een hoge leessnelheid. Het kent echter wel een trage schrijfsnelheid, is duur als er per eenheid van opslagcapaciteit gekeken wordt en kent lagere zogenaamde density. Conclusie van deze benchmarkpresentatie is dat mechanische harde schijven sneller zijn bij sequenti¨ele reads, maar dat flash geheugen sneller is bij random reads. Bij queries moet er bekeken worden hoeveel percent van de totale data geaccessed moet worden. Flash is bij random access zoals gezegd sneller, maar vanaf een bepaald percentage (al beginnende van 0.1 %) is een mechanische harde schijf sneller. Dit is zo omdat er dan hele blokken tegelijk gelezen kunnen worden. Flash geheugen moet telkens de volledige B-tree doorlopen hetgeen een groot aantal te accessen blokken geeft. Verder werd de performantie van verschillende soorten joins opgemeten.

2.3

The Application of MapReduce in the Yahoo data center

Dominique Fonteyn / Wim Leers Piglatin is een vorm van SQL die een specifiek query execution plan biedt. Dit zou gemakkelijker zijn voor programmeurs. Soms moet een query omgewisseld worden opdat deze optimaler uitgevoerd kan worden. Piglatin kent een genest data model. Er kan gebruik gemaakt worden van user defined functions. Yahoo heeft een eigen debugging environment. Enkele gekende keywords zijn COGROUP, FLATTEN en FILTER. PigUnit biedt unit tests, regressie testing en prototype testing. PigLaten werkt met MapReduce en Hadoop.

4

2.4

Comparison between MapReduce and parallel database systems

Bart Ketelslegers / Thomas De Craemer Het aantal data stijgt dus ook de benodigde rekenkracht stijgt. Een mogelijke oplossing hiervoor is cloudcomputin volgens een shared/nothing architectuur. Naast MapReduce kennen we parallele databases, deze verdeelt de lasten over verschillende computers door queries op te splitsen. MapReduce vereist niet dat de data in een specifiek schema gekend is. DBMS laadt de data in aan de hand van een relationeel schema. Er worden B-trees en hashtrees gebruikt voor de indices en er kan gebruikt gemaakt worden van SQL en user defined functies. Data wordt gepusht van operator naar operator. Wat met rollbacks? Wat met heterogeniteit? Er moeten namelijk verschillende soorten systemen gebruikt kunnen worden. Een benchmark geeft aan dat een DBMS meer tijd nodig heeft om data in te laden, maar qua uitvoer wel sneller is dan bijvoorbeeld Hadoop. Hadoop heeft namelijk extra reduce operaties nodig. MapReduce is quick and dirty, maar wel gratis. Een DBMS heeft een sterke performantie maar is niet goed schaalbaar. Bovendien is het moeilijk een DBMS op te zetten. Een hybride tussen deze twee vormen is HadoopDB. De twee systemen kunnen dus perfect naast elkaar werken.

2.5

HadoopDB: Marriage between the DBMS-approach and the MapReduce approach The Best of Two Worlds

Inneke Ponet / Bart Ketelslegers Analytische databases nemen een groot gedeelte van het totaal aantal databases in. We wensen dus paralelle databases te gebruiken, maar ook MapReduce klinkt aantrekkelijk. We kijken daarom naar de hybride variant, namelijk HadoopDB. Dit is gratis en open source. Voor de performantie willen we het niveau van paralelle databases bereiken. Qua schaalbaarheid en heterogeniteit is echter MapReduce weer beter. Ook de fouttolerantie (succesvolle commits, vooruitgang maken in een bepaalde workload, . . . ) is een belangrijk punt. Hiernaast ook een flexibele query interface. HadoopDB kent drie lagen, een communicatielaag (Hadoop), een database (PostgreSQL) en translation (Hive). Hadoop werkt met Hadoop File System (HDFS) en het MapReduce Framework. Hive zet SQL om in Hadoop queries via MapReduce acties. Er wordt gebruik gemaakt van een database connector dewelke een interface biedt tussen de database systemen. Ook een catalogus die meta-informatie biedt over de database (in de vorm van een XML file in HDFS) is aanwezig. Deze catalogus wordt gebruikt door zowel de master als de slave nodes. Dataloader. SQL/SMS-planner. De conclusie is dat we kunnen spreken van een betere performantie.

2.6

Network Dynamics: Population Models - Network Effects

Wouter Deroey / Gert Nelissen Ik heb de co-presentatie van dit onderwerp gepresenteerd dus ik zal hierover geen samenvatting schrijven maar een volledig verslag.

5

2.7

Network Dynamics: Population Models

Lesley Van Der Wee / Michael Mertens We wensen een model voor spreiding in de wereld te modelleren. Een netwerk wordt een graaf en buren nodes die naast elkaar liggen met een edge tussen - kunnen elkaar be¨ınvloeden. In een netwerk is er zo sprake van initi¨ele adapters. Buren nemen dit over, en zo worden er clusters van dichtheid gevormd. Elke cluster heeft een bepaalde dichtheid, en zo kunnen ook clusters elkaar be¨ınvloeden.

3 3.1

Deel III Resolving Data Conflicts for Integration

Tom Hoogsteyns / Thomas Van Brussel Verschillende bronnen van data zijn heterogeen. Ze kunnen wel over hetzelfde onderwerp gaan, maar hebben een andere structuur. Bijvoorbeeld in een relationele database kan een bepaalde tabel attributen hebben die in een bepaalde context niet zinvol zijn. Er moet dus een mapping gedefinieerd kunnen worden tussen verschillende bronnen van data. Een voorbeeld van zo een mapping zijn de getallen 1 en 2 mappen op de geslachten mannelijk en vrouwelijk. Blocking zoekt groepen van gelijkaardige records. Conflicterende data dient opgelost te worden. Doel van integratie is: compleetheid, correctheid en compactheid. Data fusion is het oplossen van deze drie componenten. Data fusion draait dus volledig rond het vinden van de juiste waardes. Standaardwaarde kan gekozen worden, maar kan ook beslist worden aan de hand van de andere waardes. Een voorbeeld hiervan is een gemiddelde nemen. Om dit resultaat te bekomen zijn er enkele operators. Hieronder behoren bijvoorbeeld de relationele operators minimum union, complement union, full disjunction, merge & prioritized merge en grouping & aggregation.

3.2

A Live Demo of Pig

Brecht Schoolmeesters / Jimmy Michiels Pig werkt bovenop Hadoop, dus een installatie van Hadoop is noodzakelijk. Het is dus moeilijk te configureren, maar eens het systeem ingesteld is, zijn er geen problemen meer en werkt Pig soepel. Er zijn twee modi, local mode en MapReduce mode. Local mode dient voor het draaien op een enkel systeem. MapReduce wordt gedraaid op een cluster van systemen. Er dient een data-file ingeladen te worden, dit bevat een uit te voeren script. Dit script wordt uitgevoerd - tijdens deze demo in local mode. De output wordt opgeslagen in een bepaalde file. In MapReduce mode dient de data file geupload te worden naar het Hadoop filesyseem HDFS. Vervolgens kunnen we het script in deze modus uitvoeren. De output is echter hetzelfde. Het is mogelijk gecomprimeerde data in te laden. PigPen wordt gebruikt om Pig te debuggen. Als input wordt er een Pig Latin programma gegeven. De output bestaat een verzameling van voorbeeld-bags. Deze bags moeten consistent en compact zijn.

3.3

The Application of MapReduce at Google: BigTable

Robin Timmermans / Jeroen Appermont Bigtable is een distributed storage system voor gestructureerde data. Door Google en enkel en alleen bij

6

Google. De tabel is een driedimensionele tabel bestaande uit 2 strings en een integer. Qua implementatie zijn er 3 componenten, master server, tablet servers en clients. De master server kent tablets toe aan tablet servers op een gebalanceerde manier. Deze server beheert ook de tablet servers (als er een tablet server faalt moet de master server dit opvangen, bijvoorbeeld). Verder worden ook schema changes behandeld door de master server. De tablet servers behandelen een verzameling van tablets. Ze kunnen deze inlezen, wegschrijve en splitsen. Ook communiceren ze met de clients. In de praktijk wordt een tabel opgesplitst in tables. Dit wordt toegepast op onder meer Google Analytics, Google Earth en Google App Engine. Opmerking: sequential reeds zijn snel omdat er parallel gewerkt kan worden.

3.4

Google Fusion Tables, a Cloud Application for Personal Information Management

Raf Vandeput / Inneke Ponet Google Fusion Tables is een web-service, een cloud applicatie. De nadruk ligt op visualisatie en collaboratie. Dit is overigens ge¨ımplementeerd bovenop Bigtable. Het doel is om meerdere gebruikers te strikken voor database-related gebruik. Vooral non-IT’ers vormen een doelpubliek. Gebruiksvriendelijkheid is een troef. Om data te delen worden er instellingen voorzien zodat gebruikers kunnen instellen in welke mate diens data beschikbaar is voor de buitenwereld. Ook collaboratie is erg belangrijk. Zo kunnen er tabellen van meerdere gebruikers gecombineerd worden met elkaar, zodat data samen gebracht en gebruikt kan worden. Ook commentaar geven op elkaars data is een mogelijkheid. Over de technische mogelijkheden van Fusion Tables; data kan handmatig ingevoerd worden, maar ook files kunnen ge¨ upload en ge¨ınterpreteerd worden. Bijvoorbeeld bij een CSV -file wordt het schema door Google zelf onttrokken aan de data. Publieke datasets kunnen bezocht worden via HTML-pagina’s. Deze kunnen dan ook gecrawld worden door search engines. Queries gebeuren niet aan de hand van SQL of een andere taal, maar via een interface. Er wordt een API geboden zodat externe pages deze data kunnen gebruiken. Voor de opslag van de gegevens wordt gebruik gemaakt van Bigtable. Alle bestaande tuples worden opgeslagen in ´e´en grote tabel genaamd Rows. Dit is een key-value relatie, waarbij de key bestaat uit de fusion table in combinatie met de regelnummering van de betreffende tupel. De tupel zelf wordt geconverteerd in een atomaire waarde tot de value.

3.5

Google WebTables

Wout Bittremieux / Sibren Polders Web bestaat uit onverzamelde documenten. Documenten krijgen ook vorm door het invullen van formulieren. Hier kan een deep web crawler mee omgaan. Er zijn echter ook veel tabellen op het internet. Sommige van deze tabellen dienen enkel voor de interface, anderen bevatten wel degelijk data. Hierop moet er gefilterd worden zodat enkel de nuttige tabellen overblijven. Tabellen dienen geranked te worden. Hiervoor zijn er vier verschillende methodes. Hiertoe behoren onder andere na¨ıve ranking, feature ranking en schema ranking. Indexing wordt gebruikt om tabellen sneller op te vragen. Enkele voorbeeldapplicaties van ACSDb. In schema’s worden er onderling tussen attributen synoniemen gezocht. Dit is ook in de context van schrijffouten of andere talen. 7

3.6

Deep Web Crawler

Daniele Alfarone / Mathy Vanhoef Deep web crawler zoekt achter HTMLformulieren. Traditionele crawlers kunnen dit niet gezien deze enkel statische links volgen. Er zit echter 10 keer meer data achter zulke formulieren, dan dat er data rechtstreeks toegankelijk is. Er zijn verschillende manieren om deze data te bereiken. Een bepaalde methode is de surfacing approach. Voor een bepaalde set van queries worden alle resultaten weergegeven. De pagina’s worden als verschillende pagina’s behandeld. Een andere methode is de Google approach. Deze kijkt eerst naar de formulieren an sich en bepaalt dan welke queries er ingevuld kunnen worden. Er zijn verschillende soorten van inputs. Zo zijn er tekstuele inputs, maar ook keuzevelden zoals radio buttons enzovoort. Deze laatsten restricten de content. Ook bestaan er zogenaamde presentatievelden. Voor bepaalde velden wordt er bepaald of deze velden informatief zijn. Informatieve velden worden aanzien als zogenaamde template en kunnen daarom verder gebruikt worden om nieuwe selectiekeuzes te maken. Het resultaat hiervan is dat er uiteindelijk minder selectie-mogelijkheden overblijven. Verschillende optimisaties worden gegeven.

3.7

Network Dynamics: Structural Models - Epidemics

Mathy Vanhoef / Wout Bittremieux Sociale netwerken verspreiden informatie net zoals een epidemie zich verspreidt. Dit is ook van toepassing op virussen, maar niet perse via een netwerk. Dit kan ook via bijvoorbeeld een USB-stick. Er worden verschillende modellen gepresenteerd die het epidemiefenomeen modelleren. Een informatiebron geeft informatie door aan k anderen, dit staat gekend als de eerste wave. Deze eerste wave geeft de informatie dan weer door aan k 2 nodes, enzovoort. Dit vormt een graaf. Deze graaf kan in principe ook als boom voorgesteld worden omdat er geen cycles mogelijk zijn. Once infected, always infected. Elke node kan zich in 1 van de 3 volgende states bevinden. Susceptible, Infectious, Removed. In dit geval spreken we wel niet over een tree maar over een standaard gerichte graaf. Gericht omdat een ziekte altijd in 1 richting gebeurt. We spreken dus van assymetrische relaties. Er zijn op deze modellen extensies mogelijk die bijvoorbeeld de kwetsbaarheid van een bepaalde persoon in achting nemen. Ook kan bijvoorbeeld de infection-probability aangepast worden aan de hand van hoelang de drager deze infectie reeds heeft. Bijvoorbeeld, op het begin is iemand meer doorgeef-gevoelig of net andersom. Een ander model introduceert een vorm van genezing zodat men opnieuw en opnieuw kan ge¨ınfecteerd geraken. Link met databases? Data repliceren is een virus. Multicasten is het zogenaamde doorgeven aan anderen.

3.8

Graph Databases

Gert Nelissen / Dominique Fonteyn Ik presenteer dit topic dus zal hierover geen samenvatting maar een volledig verslag schrijven.

8