De materialisatie van SPARQL schalen door middel van query decompositie

Het Semantische Web breidt het huidige web uit met het Resource Description Framework (RDF). Dit maakt het mogelijk om informatie op een manier te beschrijven die leesbaar en begrijpelijk is voor machines, waardoor zij in staat zijn complexere vragen te beantwoorden. Een belangrijk onderdeel van dit systeem is een expressieve querytaal, die het manipuleren van grote hoeveelheden data mogelijk maakt. Dit kan echter leiden tot rekenintensieve processen, waardoor het beschikbaar stellen van een aanzienlijke hoeveelheid RDF-informatie op webschaal al snel een krachtige (en kostbare) machine vereist om het benodigde rekenwerk tijdig te kunnen leveren.

Een voor de hand liggende manier om het rekenwerk te verminderen, is het opslaan van de resultaten van query's, zodat ze later (indien mogelijk) hergebruikt kunnen worden. De antwoorden op door gebruikers gegenereerde query's zijn echter vaak niet direct herbruikbaar en vereisen bovendien aanzienlijke opslagruimte.

In dit onderzoek is daarom een algoritme ontwikkeld dat een query herschrijft en opsplitst in subquery's die eenvoudiger hergebruikt kunnen worden en efficiënt gecombineerd kunnen worden. Eerst wordt formeel aangetoond dat het herschrijven van een query door het algoritme het uiteindelijke antwoord erop niet verandert. Vervolgens wordt empirisch aangetoond dat dit algoritme ervoor zorgt dat meer query's beantwoord kunnen worden met resultaten van eerder uitgevoerde query's. Dit leidt tot het sneller verkrijgen antwoorden op query'sen een vermindering van de benodigde opslagruimte voor die antwoorden.

Het bewijs hiervoor wordt gegeven door verschillende verzamelingen van query's in alle mogelijke permutaties te beantwoorden, zowel met als zonder het ontwikkelde algoritme. Daarbij worden de benodigde tijd om elke query te beantwoorden en de opslagruimte voor de resultaten gemeten. Twee scenario's worden gepresenteerd waarin het algoritme het mogelijk maakt om tussenresultaten van eerdere query's te benutten.

De scriptie is beschikbaar via Bibliotheek UGent