SPARQL query answering with bitmap indexes

Julien Leblay 1, 2, 3, *
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
ACM. SWIM - 4th International Workshop on Semantic Web Information Management - 2012, May 2012, Scottsdale, AZ, United States. 2012
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00691235
Contributeur : Julien Leblay <>
Soumis le : samedi 26 mai 2012 - 07:00:12
Dernière modification le : jeudi 11 janvier 2018 - 06:26:58
Document(s) archivé(s) le : jeudi 15 décembre 2016 - 00:50:54

Fichier

swim2012-leblay.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00691235, version 1

Citation

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

Partager

Métriques

Consultations de la notice

293

Téléchargements de fichiers

229