SPARQL query answering with bitmap indexes

Julien Leblay 1, 2, 3, *
* Corresponding author
1 LEO - Distributed and heterogeneous data and knowledge
UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
2 OAK - Database optimizations and architectures for complex large data
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
3 IASI
LRI - Laboratoire de Recherche en Informatique
Abstract : When querying RDF data, one may use reasoning to reach intensional data, i.e., data defined by sets of rules. This is usually achieved through forward chaining, with space and maintenance overheads, or backward chaining, with high query evaluation and optimization costs. Recent approaches rely on pre-computing the terminological closure of the data rather than the full saturation. In this setting, one can even query the data without resorting to backward chaining, using a so-called semantic index. However, these techniques are limited in the type of queries they can support. In this paper, we introduce a data storage technique which mitigates the space issues of forward-chaining. We show that it can also be used with a semantic index. We propose a new structure for the index that relies on bitmaps making it resilient to updates. Our experimental results demonstrate that our storage model significantly reduces the space required to store the data. We show that the indexes can be computed quickly and fit well in memory even for very large ontologies. Finally, we analyze how query answering is affected by the data layout.
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-00691235
Contributor : Julien Leblay <>
Submitted on : Saturday, May 26, 2012 - 7:00:12 AM
Last modification on : Monday, May 28, 2018 - 2:38:02 PM
Long-term archiving on : Thursday, December 15, 2016 - 12:50:54 AM

File

swim2012-leblay.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00691235, version 1

Collections

Citation

Julien Leblay. SPARQL query answering with bitmap indexes. SWIM - 4th International Workshop on Semantic Web Information Management - 2012, May 2012, Scottsdale, AZ, United States. ⟨hal-00691235⟩

Share

Metrics

Record views

449

Files downloads

344