---
title: "Sound, Complete, and Minimal Query Rewriting for Existential Rules"
authors:
  - "Mélanie König"
  - "Michel Leclère"
  - "Marie-Laure Mugnier"
  - "Michaël Thomazo"
doi: ""
url: "https://ijcai.org/proceedings/2013/448"
pdf: "https://ijcai.org/proceedings/2013/0448.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "3017-3020"
track: ""
keywords:
---

# Sound, Complete, and Minimal Query Rewriting for Existential Rules

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

*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.