Sound, Complete, and Minimal Query Rewriting for Existential Rules

Mélanie KönigMélanie König, Michel LeclèreMichel Leclère, Marie-Laure MugnierMarie-Laure Mugnier, Michaël ThomazoMichaël Thomazo

Mélanie König, Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo
Sound, Complete, and Minimal Query Rewriting for Existential Rules
Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13), 3017-3025, 2013

Details
Bibtex

KurzfassungAbstract
We address the issue of Ontology-Based Data Access which consists of exploiting the semantics expressed in ontologies while querying data. Ontologies are represented in the framework of existential rules, also known as Datalog+/-. We focus on the backward chaining paradigm, which involves rewriting the query (assumed to be a conjunctive query, CQ) into a set of CQs (seen as a union of CQs). The proposed algorithm accepts any set of existential rules as input and stops for so-called finite unification sets of rules (fus). The rewriting step relies on a graph notion, called a piece, which allows to identify subsets of atoms from the query that must be processed together. We first show that our rewriting method computes a minimal set of CQs when this set is finite, i.e., the set of rules is a fus. We then focus on optimizing the rewriting step. First experiments are reported in the associated technical report.
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{KLMT2013,
  author    = {M{\'{e}}lanie K{\"{o}}nig and Michel Lecl{\`{e}}re and
               Marie-Laure Mugnier and Micha{\"{e}}l Thomazo},
  title     = {Sound, Complete, and Minimal Query Rewriting for Existential
               Rules},
  booktitle = {Proceedings of the 23rd International Joint Conference on
               Artificial Intelligence (IJCAI'13)},
  year      = {2013},
  pages     = {3017-3025}
}