Foundations of SPARQL Query Optimization

Simple item page
dc.creatorSchmidt, Michael
dc.creatorMeier, Michael
dc.creatorLausen, Georg
dc.date2008-12-19
dc.date2009-01-26
dc.date.accessioned2026-07-07T12:34:06Z
dc.date.available2026-07-07T12:34:06Z
dc.descriptionThe SPARQL query language is a recent W3C standard for processing RDF data, a format that has been developed to encode information in a machine-readable way. We investigate the foundations of SPARQL query optimization and (a) provide novel complexity results for the SPARQL evaluation problem, showing that the main source of complexity is operator OPTIONAL alone; (b) propose a comprehensive set of algebraic query rewriting rules; (c) present a framework for constraint-based SPARQL optimization based upon the well-known chase procedure for Conjunctive Query minimization. In this line, we develop two novel termination conditions for the chase. They subsume the strongest conditions known so far and do not increase the complexity of the recognition problem, thus making a larger class of both Conjunctive and SPARQL queries amenable to constraint-based optimization. Our results are of immediate practical interest and might empower any SPARQL query optimizer.
dc.identifierhttps://arxiv.org/abs/0812.3788
dc.identifierhttp://arxiv.org/abs/0812.3788
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/217305
dc.subjectDatabases
dc.titleFoundations of SPARQL Query Optimization
dc.typetext

Files

Collections

arXiv