Optimizing Reformulation-based Query Answering in RDF

Damian Bursztyn 1, 2 François Goasdoué 3 Ioana Manolescu 1, 2
1 OAK - Database optimizations and architectures for complex large data
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
3 PILGRIM - Gradedness, Imprecision, and Mediation in Database Management Systems
IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : Reformulation-based query answering is a query processing technique aiming at answering queries under constraints. It consists of reformulating the query based on the constraints, so that evaluating the reformulated query directly against the data (i.e., without considering any more the constraints) produces the correct answer set. In this paper, we consider optimizing reformulation-based query answering in the setting of ontology-based data access, where SPARQL conjunctive queries are posed against RDF facts on which constraints expressed by an RDF Schema hold. The literature provides query reformulation algorithms for many fragments of RDF. However, reformulated queries may be complex, thus may not be efficiently processed by a query engine; well established query engines even fail processing them in some cases. Our contribution is (i) to generalize prior query reformu-lation languages, leading to investigating a space of refor-mulated queries we call JUCQs (joins of unions of conjunctive queries), instead of a single reformulation; and (ii) an effective and efficient cost-based algorithm for selecting from this space, the reformulated query with the lowest estimated cost. Our experiments show that our technique enables reformulation-based query answering where the state-of-the-art approaches are simply unfeasible, while it may decrease its cost by orders of magnitude in other cases.
Document type :
Conference papers
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01143068
Contributor : Damian Bursztyn <>
Submitted on : Thursday, April 16, 2015 - 3:59:51 PM
Last modification on : Thursday, November 15, 2018 - 11:57:40 AM
Long-term archiving on : Tuesday, April 18, 2017 - 10:19:43 PM

File

paper-88.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01143068, version 1

Citation

Damian Bursztyn, François Goasdoué, Ioana Manolescu. Optimizing Reformulation-based Query Answering in RDF. EDBT: 18th International Conference on Extending Database Technology, Mar 2015, Brussels, Belgium. ⟨hal-01143068⟩

Share

Metrics

Record views

976

Files downloads

305