Query Rewriting for Existential Rules with Compiled Preorder

Mélanie König 1 Michel Leclère 1 Marie-Laure Mugnier 1
1 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We address the issue of Ontology-Based Query Answering (OBQA), which seeks to exploit knowledge expressed in ontologies when querying data. Ontologies are represented in the framework of ex-istential rules (aka Datalog±). A commonly used technique consists in rewriting queries into unions of conjunctive queries (UCQs). However, the obtained queries can be prohibitively large in practice. A well-known source of combinatorial explosion are very simple rules, typically expressing taxonomies and relation signatures. We propose a rewriting technique, which consists in compiling these rules into a preorder on atoms and embedding this preorder into the rewriting process. This allows to compute compact rewritings that can be considered as " pivotal " representations, in the sense that they can be evaluated by different kinds of database systems. The provided algorithm computes a sound, complete and minimal UCQ rewriting , if one exists. Experiments show that this technique leads to substantial gains, in terms of size and runtime, and scales on very large ontologies. We also compare to other tools for OBQA with existen-tial rules and related lightweight description logics.
Type de document :
Communication dans un congrès
IJCAI: International Joint Conference on Artificial Intelligence, Jul 2015, Buenos Aires, Argentina. 24th International Joint Conference on Artificial Intelligence, 2015, 〈http://ijcai-15.org〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01164851
Contributeur : Michel Leclère <>
Soumis le : jeudi 18 juin 2015 - 08:18:46
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mardi 25 avril 2017 - 11:15:48

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01164851, version 1

Collections

Citation

Mélanie König, Michel Leclère, Marie-Laure Mugnier. Query Rewriting for Existential Rules with Compiled Preorder. IJCAI: International Joint Conference on Artificial Intelligence, Jul 2015, Buenos Aires, Argentina. 24th International Joint Conference on Artificial Intelligence, 2015, 〈http://ijcai-15.org〉. 〈lirmm-01164851〉

Partager

Métriques

Consultations de la notice

209

Téléchargements de fichiers

400