Sound, Complete, and Minimal Query Rewriting for Existential Rules

König, Mélanie; Leclère, Michel; Mugnier, Marie-Laure; Thomazo, Michael

Sound, Complete, and Minimal Query Rewriting for Existential Rules

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

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 3017-3020.

Abstract

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.

Mélanie König, Michel Leclère, Marie-Laure Mugnier, and Michael Thomazo. 2013. Sound, Complete, and Minimal Query Rewriting for Existential Rules. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 3017–3020. https://ijcai.org/proceedings/2013/448

@inproceedings{ijcai2013p448,
  title     = {Sound, Complete, and Minimal Query Rewriting for Existential Rules},
  author    = {König, Mélanie and Leclère, Michel and Mugnier, Marie-Laure and Thomazo, Michael},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {3017--3020},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/448},
}

TY  - CPAPER
TI  - Sound, Complete, and Minimal Query Rewriting for Existential Rules
AU  - König, Mélanie
AU  - Leclère, Michel
AU  - Mugnier, Marie-Laure
AU  - Thomazo, Michael
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 3017
EP  - 3020
UR  - https://ijcai.org/proceedings/2013/448
ER  -