Sound, Complete, and Minimal Query Rewriting for Existential Rules

From International Center for Computational Logic

Toggle side column

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
Sound, Complete, and Minimal Query Rewriting for Existential Rules


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
  • 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}
}