SPARQL query answering with bitmap indexes
| Autor: | Julien Leblay |
|---|---|
| Přispěvatelé: | Distributed and heterogeneous data and knowledge (LEO), Université Paris-Sud - Paris 11 (UP11)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Database optimizations and architectures for complex large data (OAK), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), IASI, Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), ACM |
| Rok vydání: | 2012 |
| Předmět: |
ACM: H.: Information Systems/H.2: DATABASE MANAGEMENT/H.2.4: Systems/H.2.4.5: Query processing
Computer science Backward chaining 0102 computer and information sciences 02 engineering and technology Query optimization computer.software_genre SPARQL 01 natural sciences Storage model RDF query answering [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] ACM: H.: Information Systems/H.2: DATABASE MANAGEMENT/H.2.2: Physical Design 020204 information systems Forward chaining 0202 electrical engineering electronic engineering information engineering computer.programming_language [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB] Information retrieval Languages Performance Experimentation computer.file_format 010201 computation theory & mathematics Bitmap index storage model Sargable Data mining computer RDF query language |
| Zdroj: | SWIM SWIM-4th International Workshop on Semantic Web Information Management-2012 SWIM-4th International Workshop on Semantic Web Information Management-2012, May 2012, Scottsdale, AZ, United States |
| DOI: | 10.1145/2237867.2237876 |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|