| Abstract: | Het beantwoorden van een SPARQL SELECT query die een grote hoeveelheid gegevens manipuleert is een rekenintensieve taak die een resultaat heeft dat kan worden hergebruikt om toekomstige query's (gedeeltelijk) te beantwoorden, zolang het up-to-date is. Daarom is het cachen van dit resultaat en het up-to-date houden (materialiseren) zinvol om het te hergebruiken voor toekomstige query's. Echter, het materialiseren van het antwoord op een gegeven query resulteert in een gematerialiseerde weergave die alleen gelijkwaardige query's kan beantwoorden, wat leidt tot duplicatie tussen de weergaven van query's waarvan de antwoorden elkaar overlappen. In plaats daarvan stellen we voor om de query eerst te herschrijven en vervolgens te ontbinden in een verzameling subquery's waarvan de antwoorden, en dus de gematerialiseerde views, kunnen worden samengevoegd om het antwoord op de oorspronkelijke query te vormen. Op deze manier resulteert de materialisatie van een query in een aantal gematerialiseerde weergaven van subquery's die vaker kunnen worden hergebruikt, waardoor de ruimte die gematerialiseerde weergaven van query's innemen, wordt verminderd. We ontwikkelen en implementeren het herschrijvings- en het decompositiealgoritme en evalueren ze door het materialiseren van algemene query's met en zonder algoritmes te vergelijken. We demonstreren twee scenario's waarin de gematerialiseerde weergaven die door de eerste zijn gemaakt, kunnen worden hergebruikt, terwijl de laatste een nieuwe gematerialiseerde weergave creëert die bestaande gegevens dupliceert. |
|---|
| Abstract (Eng): | Answering a SPARQL SELECT query that manipulates a large amount of data is a computationally intensive task that has a result that may be reused to (partially) answer future queries, as long as it is up-to-date. Hence, caching this result and keeping it up-to-date (materializing it) makes sense to reuse it for future queries. However, materializing a provided query's answer results in a materialized view that can only answer equivalent queries, leading to duplication between the views of queries whose answers overlap. Instead, we propose to first rewrite and then decompose the query into a collection of subqueries whose answers, and hence materialized views, can be concatenated to form the answer to the original query. This way, the materialization of a query results in a number of materialized subquery views that can be reused more often, thereby reducing the space taken up by materialized views of queries. We develop a generic algorithm to rewrite queries so that they can be decomposed into a collection of subqueries that meet this requirement, with a simple algorithm. Furthermore, we demonstrate that the rewritten query has the exact same answer as the original, and that the order of the applied rewrite operations can be changed without affecting the termination or result of the algorithm. Finally, we implement both this rewriting and decomposition algorithm and evaluate them by comparing the materialization of general-purpose queries with and without them. We demonstrate two scenarios in which the materialized views created by the former can be reused, whereas the latter creates a new materialized view that duplicates existing data. Additionally, we show that the overhead in view size of materializing a query from scratch is minimal. |
|---|