2023/06/09 by Michel Leclère, Marie-Laure Mugnier, Leclère, Michel +3
Computer Science · #Advanced Database Systems and Queries #Artificial Intelligence (cs.AI) #Databases (cs.DB) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2306.05973
openalex publication_date 2023/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.