Query Rewriting with Disjunctive Existential Rules and Mappings - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2023

Query Rewriting with Disjunctive Existential Rules and Mappings


We consider the issue of answering unions of conjunctive queries (UCQs) with disjunctive existential rules and mappings. While this issue has already been well studied from a chase perspective, query rewriting within UCQs has hardly been addressed yet. We first propose a sound and complete query rewriting operator, which has the advantage of establishing a tight relationship between a chase step and a rewriting step. The associated breadth-first query rewriting algorithm outputs a minimal UCQ-rewriting when one exists. Second, we show that for any ``truly disjunctive'' nonrecursive rule, there exists a conjunctive query that has no UCQ-rewriting. It follows that the notion of finite unification sets (fus), which denotes sets of existential rules such that any UCQ admits a UCQ-rewriting, seems to have little relevance in this setting. Finally, turning our attention to mappings, we show that the problem of determining whether a UCQ admits a UCQ-rewriting through a disjunctive mapping is undecidable. We conclude with a number of open problems.

Dates and versions

lirmm-04272033 , version 1 (06-11-2023)


Public Domain



Michel Leclère, Marie-Laure Mugnier, Guillaume Pérution-Kihli. Query Rewriting with Disjunctive Existential Rules and Mappings. BDA 2023 - 39e Conférence sur la Gestion de Données - Principes, Technologies et Applications, Oct 2023, Montpellier, France. ⟨10.48550/arXiv.2306.05973⟩. ⟨lirmm-04272033⟩
26 View
0 Download



Gmail Facebook X LinkedIn More