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.
Fichier principal
Vignette du fichier
kr2023-0042-leclere-et-al.pdf (214.64 Ko) Télécharger le fichier
Origin Publisher files allowed on an open archive
Public Domain

Dates and versions

lirmm-04272014 , 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. KR 2023 - 20th International Conference on Principles of Knowledge Representation and Reasoning, Sep 2023, Rhodes, Greece. pp.429-439, ⟨10.24963/kr.2023/42⟩. ⟨lirmm-04272014⟩
38 View
21 Download



Gmail Mastodon Facebook X LinkedIn More