Query Rewriting with Disjunctive Existential Rules and Mappings
This work addresses foundational limitations in query rewriting for knowledge representation and database systems, revealing theoretical barriers for practical applications.
The paper tackles the problem of answering unions of conjunctive queries (UCQs) using disjunctive existential rules and mappings, showing that query rewriting within UCQs is largely unaddressed. It proposes a sound and complete query rewriting operator with a breadth-first algorithm that outputs minimal UCQ-rewritings when possible, proves that some queries have no UCQ-rewriting for truly disjunctive rules, and demonstrates that determining UCQ-rewritability through disjunctive mappings is undecidable.
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.