# Query Rewriting with Disjunctive Existential Rules and Mappings

Michel Leclère, Marie-Laure Mugnier, Guillaume Pérution-Kihli

► To cite this version:

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

HAL Id: lirmm-04272014

https://hal-lirmm.ccsd.cnrs.fr/lirmm-04272014

Submitted on 6 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# Query Rewriting with Disjunctive Existential Rules and Mappings

Michel Leclère, Marie-Laure Mugnier, Guillaume Pérution-Kihli

LIRMM, Inria, University of Montpellier, CNRS, France

{leclere,mugnier}@lirmm.fr, guillaume.perution-kihli@inria.fr

## Abstract

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.

## 1 Introduction

Existential rules (Calì, Gottlob, and Kifer 2008; Baget et al. 2009; Calì, Gottlob, and Lukasiewicz 2009), aka tuple generating dependencies (Beeri and Vardi 1984), are an extension of datalog (i.e., first-order function-free Horn rules), which allows for existentially quantified variables in the rule heads, e.g., $\forall x(\mathit{human}(x) \rightarrow \exists y \mathit{isParent}(y, x))$. They have become a popular language to model ontologies and do reasoning on data. Then, a key issue is *ontology-mediated query answering*, which consists of computing the answers to a query on a knowledge base (KB), composed of a set of facts (or data) *F* and an ontology *O*. In this context, most works focus on the prominent class of (unions of) conjunctive queries ((U)CQs). There are two main dual techniques to compute the answers to a query *Q*: the *chase*, which enriches the facts *F* by performing a fixpoint computation with the ontology *O* until a canonical model of *F* and *O* is obtained (then *Q* is evaluated on this canonical model), and *query rewriting*, where *Q* is rewritten using *O* into a query $Q'$, such that for any set of facts *F*, the evaluation of $Q'$ on *F* yields the answers to *Q* on the KB. Query answering with general existential rules is undecidable, however a wide range of decidable subclasses have been defined, based on syntactic restrictions that ensure the termination of chase-like or query rewriting techniques. Tuple generating

dependencies (TGDs) are also the main formalism to represent *schema mappings*, which are high-level specifications of the relationships between two database schemas (Fagin et al. 2005). Schema mappings are at the core of many data interoperability tasks, such as data exchange, data integration or peer data management. More specifically, a mapping is a set of TGDs, with bodies and heads expressed on disjoint sets of predicates, namely *S* and *T*, called the *source* and the *target* schemas. Given a database instance *I* on *S* and a mapping *M*, a query expressed on *T* is posed on the set of facts produced from *I* by triggering *M*; again, query answering can be solved by *chasing* *I* with *M* or *rewriting* *Q* with *M* into a query that is evaluated on *I*. Since mappings are inherently nonrecursive, both techniques always terminate. Finally, in the Ontology-Based Data Access (OBDA) framework (Poggi et al. 2008), mappings specify relationships between a database schema and an ontology. Here, existential rules can be used as a uniform language to express both the ontology and the mapping (Buron, Mugnier, and Thomazo 2021).

Existential rules generalize popular description logics (DLs) used to do reasoning on data, such as DL-Lite (Calvanese et al. 2007), *EL* (Baader, Brandt, and Lutz 2005; Lutz, Toman, and Wolter 2009) and more expressive Horn-DLs (Krötzsch, Rudolph, and Hitzler 2006). However, they do not capture *nondeterministic* features, as offered by some key DLs such as *ALC* (Schmidt-Schauß and Smolka 1991) or the Semantic Web ontology language OWL (W3C 2009).

In this paper, we consider the extension of existential rules with *disjunction*, e.g., $\forall x \forall y(\mathit{isGrandParent}(x, y) \rightarrow \exists z_1 (\mathit{isParent}(x, z_1) \land \mathit{isMother}(z_1, y)) \lor \exists z_2 (\mathit{isParent}(x, z_2) \land \mathit{isFather}(z_2, y)))$. From a KR perspective, the usefulness of such rules has long been acknowledged for ontology modeling, but also for expressing nondeterministic guessing in problem solving, see e.g., (Eiter, Gottlob, and Mannila 1997). From a database perspective, disjunction in schema mappings received considerable attention in the context of *mapping management*, where mapping composition and inversion emerged as fundamental operators (Bernstein and Ho 2007; Arenas et al. 2010). Indeed, disjunction is required to express several kinds of inverse mappings, like so-called quasi-inverses or maximum recovery mappings (Fagin et al. 2008; Arenas, Pérez, and Riveros 2008). Beside the issue of
constructing such mappings, the design of associated query answering techniques is highly relevant. For instance, in a peer data management system, a mapping $\mathcal{M}$ from peer $P_1$ to peer $P_2$ allows to rewrite a query on $P_2$ in terms of $P_1$, while an inverse of $\mathcal{M}$ allows to rewrite a query on $P_1$ in terms of $P_2$. As another example, consider a mapping $\mathcal{M}$ from schema A to schema B, and assume that A evolves into A', which is expressed by a mapping $\mathcal{M}'$; the relation between A' and B can be obtained by inverting $\mathcal{M}'$ and composing it with $\mathcal{M}$; then, a query on B can be translated into a query on $A'$ by rewriting it first with $\mathcal{M}$, then with the inverse of $\mathcal{M}'$ (Pérez 2013). Such scenario is also relevant in OBDA, taking for B an ontology instead of a schema.

So far, reasoning with disjunctive existential rules has been mainly studied through the *chase*. It was shown that decidable classes of (conjunctive) existential rules, based on the behavior of the chase, can be generalized to disjunctive rules in a quite natural way, whether in relation to acyclicity notions (Carral, Dragoste, and Krötzsch 2017) or based on guardedness (Alviano et al. 2012; Gottlob et al. 2012; Bourhis et al. 2016), although these generalizations come with a huge increase in the complexity of query answering.

In contrast, *query rewriting* within UCQs has been barely addressed yet. A notable exception is the work in (Alfonso, Chortaras, and Stamou 2021), which provides a rewriting technique based on first-order resolution (see Section 3). A large body of work has studied the rewritability of ontology-mediated queries, i.e., pairs of the form $(Q, O)$ with $Q$ a (U)CQ and $O$ an ontology, into query languages of various expressivity. However, for ontologies expressed in fragments of disjunctive existential rules, most studies target expressive rewriting languages, like disjunctive datalog (Bienvenu et al. 2014; Ahmetaj, Ortiz, and Simkus 2018). As far as we are aware, the only result directly relevant to our purpose comes from the fine-grained complexity study in (Gerasimova et al. 2020), which provides syntactic rewritability conditions for ontology-mediated queries where the ontology is composed of a single specific disjunctive rule, called a covering axiom (see Section 4).

Our contributions are the following:

* We first define a sound and complete query rewriting operator for UCQs and disjunctive existential rules, which has the advantage of establishing a tight relationship between a chase step and a rewriting step (Theorem 3). The associated breadth-first query rewriting algorithm outputs a minimal UCQ-rewriting when one exists (Theorem 4).

* We then turn our attention to the notion of *finite unification sets (fus)*, which denotes sets of existential rules for which any UCQ is UCQ-rewritable, i.e., admits a finite sound and complete rewriting under the form of a UCQ. Noting that the known *fus* classes for conjunctive existential rules do not seem to be generalizable to disjunctive rules, we show that, in fact, for any "truly disjunctive" nonrecursive rule, there is a CQ that is not UCQ-rewritable (Theorem 5). This leads to question the relevance of *fus* for disjunctive rules and to consider the problem of whether a specific UCQ is UCQ-rewritable.

* Finally, considering (disjunctive) mappings, we show that the problem of determining whether a given UCQ on the target schema admits a UCQ-rewriting on the source schema is undecidable (Theorem 6).

Based on these results, we conclude with a number of open problems. Detailed proofs are available in a technical report (Leclère, Mugnier, and Pérution-Kihli 2023).

## 2 Preliminaries

**Generalities.** We consider logical vocabularies of the form $\mathcal{V} = (\mathcal{P}, \mathcal{C})$, where $\mathcal{P}$ is a finite set of predicates and $\mathcal{C}$ is a (possibly infinite) set of constants. A term on $\mathcal{V}$ is a constant from $\mathcal{C}$ or a variable. An atom on $\mathcal{V}$ has the form $p(t)$ where $p \in \mathcal{P}$ is a predicate of arity $n$ and $t$ is a tuple of terms on $\mathcal{V}$ with $|t| = n$. An atom with predicate $p$ is also called a $p$-atom. Given a formula or set of formulas $S$, we denote by $\text{vars}(S)$, $\text{consts}(S)$ and $\text{terms}(S)$ its sets of variables, constants and terms, respectively. We will often see a tuple $x$ of pairwise distinct variables as a set. We denote by $|\equiv|$ and $|\equiv\equiv$ classical logical entailment and equivalence, respectively. Given two sets of atoms $S_1$ and $S_2$, a homomorphism $h$ from $S_1$ to $S_2$ is a substitution of $\text{vars}(S_1)$ by $\text{terms}(S_2)$ such that $h(S_1) \subseteq S_2$ (we say that $S_1$ maps to $S_2$ by $h$). It is well-known that, when we see $S_1$ and $S_2$ as existentially closed conjunctions of atoms, $S_2 \models S_1$ iff $S_1$ maps to $S_2$.

A safe copy of an atom set $S$ is obtained from $S$ by a bijec- tive renaming of its variables with fresh variables (i.e., that do not occur elsewhere in the context of the computation).

**Knowledge base.** A set of facts $F$ is a possibly infinite set of atoms, logically seen as an existentially closed con- junction. When this set is finite we call it a *fact base*. A disjunctive existential rule $R$ (or simply rule hereafter) is a closed formula of the form

$$ \forall x \forall y ( B[x, y] \rightarrow \bigvee_{i=1}^{n} \exists z_i H_i[x_i, z_i] ) $$

where $n \ge 1$, $B$ and the $H_i$ are non-empty finite conjunc- tions of atoms with $\text{vars}(B) = x \cup y$ and $\text{vars}(H_i) = x_i \cup z_i$, $x = \bigcup_{i=1}^{n} x_i$ and $x, y$ and the $z_i$ are pairwise dis- joint; $B$ is the *body* of $R$, also denoted by $\text{body}(R)$, and $\{H_1, \dots, H_n\}$ is the *head* of $R$, also denoted by $\text{head}(R)$. We also denote by $\text{head}_i(R)$ the i-th disjunct $H_i$ of the head of $R$. The set $x$ is the *frontier* of $R$ and is denoted by $\text{fr}(R)$. Its elements are called frontier variables. The set $z_i$ is the set of *existential variables* of $H_i$, also denoted by $\text{exist}(H_i)$, and the union of all the $\text{exist}(H_i)$ is the set of existen- tial variables of $R$, also denoted by $\text{exist}(R)$. Note that constants may occur anywhere. For brevity, we often de- note by $B \rightarrow H_1 \lor \dots \lor H_n$ a rule with body $B$ and head $\{H_1, \dots, H_n\}$. A rule $R$ is *conjunctive* if $n = 1$. A (dis- junctive) rule $R$ is (disjunctive) *datalog* if $\text{exist}(R) = \emptyset$.

A (disjunctive) *knowledge base* (KB) is a pair $(F, \mathcal{R})$, where $F$ is a fact base and $\mathcal{R}$ is a finite set of (disjunctive) existential rules. We assume w.l.o.g. that distinct rules in $\mathcal{R}$ have disjoint sets of variables. In examples, we may reuse variables for simplicity.
**Disjunctive chase.** A rule $R = B \rightarrow H_1 \vee \dots \vee H_n$ is applicable on a fact base $F$ if there is a homomorphism $h$ from body($R$) to $F$. The pair $(R, h)$ is called a *trigger* on $F$. The application of $(R, h)$ to $F$ is denoted by $\alpha_\vee(F, R, h)$; it produces a set of $n$ fact bases, each obtained by adding to $F$ a set of atoms obtained from $\text{head}_i(R)$ by replacing each frontier variable $x$ by $h(x)$ and each existential variable by a fresh variable. We denote by $h^{\text{safe}_i}$ the extension of $h$ that safely renames $\text{exist}(\text{head}_i(R))$ by fresh variables. Then:

$$ \alpha_\vee(F, R, h) = \{F \cup h^{\text{safe}_i}(\text{head}_i(R)) \mid 1 \le i \le n\} $$

The disjunctive chase procedure iteratively applies triggers towards a fixpoint. This procedure is often seen as the construction of a tree, see in particular (Bourhis et al. 2016; Carral, Dragoste, and Krötzsch 2017).

**Definition 1 (Derivation tree).** A derivation tree $\mathcal{T}$ of a KB $(F, \mathcal{R})$ is a (possibly infinite) rooted labeled tree $(V, E, \lambda)$, where $V$ is the set of vertices, $E$ the set of edges, and $\lambda$ a vertex labeling function inductively defined as follows:

* $\lambda(r) = F$ for the root $r$ of $\mathcal{T}$;

* For each vertex $v$ with children $\{v_1, \dots, v_n\}$, there is a trigger $(R, h)$ on $\lambda(v)$ with $R = B \rightarrow H_1 \vee \dots \vee H_n \in \mathcal{R}$ and the restriction of $\lambda$ to the domain $\{v_1, \dots, v_n\}$ is a bijection to $\alpha_\vee(\lambda(v), R, h)$.

Note that we do not impose any criterion of trigger applicability, as we do not aim at studying a particular chase strategy. A branch $\gamma$ of a rooted tree is a maximal path from the root; we denote by $\text{nodes}(\gamma)$ its set of vertices. Given a derivation tree $\mathcal{T}$, we denote by $\Gamma(\mathcal{T})$ the set of all its branches. A trigger $(R, h)$ on $F$ is satisfied (by $F$) if there is an extension $h'$ of $h$ with $h'(\text{head}_i(R)) \subseteq F$ for some $i$. A derivation tree $(V, E, \lambda)$ is fair if, for each branch $\gamma$ and each vertex $v \in \text{nodes}(\gamma)$, any trigger on $\lambda(v)$ is satisfied in a $\lambda(v')$ with $v' \in \text{nodes}(\gamma)$. Finally, a chase tree is a fair derivation tree.

**Definition 2 (Disjunctive chase result).** The result of a disjunctive chase of $F$ by $\mathcal{R}$ is chase$(F, \mathcal{R}) = \{ \bigcup_{v \in \text{nodes}(\gamma)} \lambda(v) \mid \gamma \in \Gamma(\mathcal{T}) \}$ where $\mathcal{T}$ is a chase tree and

$\lambda$ its labeling function.

From a logical viewpoint, the chase result is a disjunction of existentially closed conjunctions of atoms. Neither the chase tree nor the chase result are unique, however all the results entail the same queries (see next Theorem 1). Although the degree of each vertex in a chase tree is bounded by the maximal number of disjuncts in a rule head, the tree may have infinite branches, and an infinite number of them. When the chase tree is finite, the result of the chase is the (finite) set of fact bases associated with its leaves.

It is sometimes convenient to consider a linearization of a finite derivation tree, which we call a derivation. A derivation of $(\{F\}, \mathcal{R})$ is a finite sequence of sets of fact bases and triggers $\mathcal{D} = (\mathcal{F}_0 = \{F\}) \xrightarrow{t_1} \mathcal{F}_1 \xrightarrow{t_2} \dots \xrightarrow{t_k} \mathcal{F}_k$ where $t_i = (R, h)$ is a trigger of $R \in \mathcal{R}$ on an $F_j \in \mathcal{F}_{i-1}$ and $\mathcal{F}_i = (\mathcal{F}_{i-1} \setminus \{F_j\}) \cup \alpha_\vee(F_j, R, h)$, for all $1 \le i \le k$. To each finite derivation tree can be assigned a derivation

obtained from any total ordering of the trigger applications associated with the inner vertices in the tree, in a compatible way with the parent-child partial order. When $\mathcal{R}$ is a set of conjunctive rules, a derivation tree is a path and the $\mathcal{F}_i$ in a derivation are singletons; then, a derivation can be seen as a sequence of fact bases (instead of sets of fact bases).

**Query Answering.** A conjunctive query (CQ) $Q$ takes the form $\exists y \phi[x, y]$, where $x$ and $y$ are disjoint tuples of variables, and $\phi$ is a finite conjunction of atoms with $\text{vars}(\phi) = \{x \cup y\}$. The variables in $x$ are called answer variables. A Boolean CQ has no answer variables. In a full CQ, all variables are answer variables. An atomic CQ has a single atom. A (Boolean) union of conjunctive queries (UCQ) is a disjunction of (Boolean) CQs with the same tuple of answer variables $x$. For clarity, we denote a UCQ by $Q$ and a CQ by $Q$. A set of facts $F$ answers positively to a Boolean CQ $Q$ if $F \models Q$. More generally, a tuple of constants $c$ is an answer to a CQ $Q$ on $F$ if there is a substitution $s$ such that $s(x) = c$ and $F \models s(Q)$. This extends to a UCQ $Q$ and a set of sets of facts $\mathcal{F}$: a tuple of constants $c$ is an answer to $Q$ on $\mathcal{F}$ if for every $F_i \in \mathcal{F}$, there is a CQ $Q_j \in Q$ such that $c$ is an answer to $Q_j$ on $F_i$.

W.l.o.g. we focus in this paper on Boolean queries, to avoid technicalities related to answer variables. Hence, in the following, by UCQ and CQ we refer to Boolean queries, unless otherwise specified. We will often see a CQ as a set of atoms, and a UCQ as a set of atoms sets.

The following theorem states that the disjunctive chase provides a sound and complete procedure to decide whether a UCQ is entailed by a disjunctive KB.

**Theorem 1 (from (Bourhis et al. 2016)).** Let $Q$ be a (Boolean) UCQ and $(F, \mathcal{R})$ be a disjunctive KB. Then $F, \mathcal{R} \models Q$ iff chase$(F, \mathcal{R}) \models Q$ (i.e., $F_i \models Q$ for all $F_i \in \text{chase}(F, \mathcal{R}))$).

**Example 1 (Colorability).** Let $F$ be a fact base on predicates $v$ (vertex) and $e$ (edge) describing a graph $G$. Let $R = v(x) \rightarrow g(x) \vee r(x)$ ("Every vertex has color green or red"). Then, chase$(F, \{R\})$ yields all ways of coloring each vertex. Let the UCQ $Q = \{Q_1, Q_2\}$ with $Q_1 = \{g(u), e(u, w), g(w)\}$ and $Q_2 = \{r(u), e(u, w), r(w)\}$. The KB $(F, \{R\})$ answers positively to $Q$ iff $G$ is not 2-colorable.

Given UCQs $Q_1$ and $Q_2$, we say that $Q_1$ is more specific than $Q_2$ if $Q_1 \models Q_2$. Note that $Q_1 \models Q_2$ iff for all $Q_1 \in \mathcal{Q}_1$, there is $Q_2 \in \mathcal{Q}_2$ such that $Q_1 \models Q_2$ (i.e., $Q_2$ maps to $Q_1$ by homomorphism). A CQ $Q$ is minimal if it has no strict subset $Q' \subsetneq Q$ such that $Q' \equiv Q$ (i.e., $Q' \models Q$). A UCQ $Q$ is minimal if it has no strict subset $Q' \subsetneq Q$ such that $Q \equiv Q'$ (whether each CQ in the UCQ is itself minimal is not relevant for our results). A cover of a UCQ $Q$ is a minimal subset $Q' \subseteq Q$ such that $Q \equiv Q'$. It is known that, given two equivalent UCQs $Q_1$ and $Q_2$, there is a bijection from any cover of $Q_1$ to any cover of $Q_2$ that maps each CQ in $Q_1$ to an equivalent CQ in $Q_2$ (see, e.g., (König et al. 2015)).
**Mappings.** Given two disjoint sets of predicates *S* and *T*, respectively called the *source* and the *target* predicates, a *source-to-target* (or *S*-to-*T*) rule *R* is such that *body*(*R*) uses predicates in *S* and *head*(*R*) uses predicates in *T*. A (disjunctive) mapping *M* on (*S*, *T*) is a finite set of *S*-to-*T* (disjunctive) rules. In this setting, a fact base (or database instance) is expressed on *S* and a query on *T*. Note that the chase of a fact base with a mapping is always finite.

**UCQ rewritability.** In the following, by rewriting of a UCQ *Q* with a set of rules *R*, we mean a possibly infinite set of CQs *Q'*, such that for all fact base *F*, if *F* |= *Q'* then *F*, *R* |= *Q* (in other words, a rewriting is by definition sound). A rewriting *Q'* of *Q* with *R* is complete if for all fact base *F*, if *F*, *R* |= *Q* then *F* |= *Q'*. A finite complete rewriting is called a *UCQ-rewriting*. A pair (*Q*, *R*) is called *UCQ-rewritable* if it admits a UCQ-rewriting. The set *R* itself is called *UCQ-rewritable* if for any UCQ *Q*, the pair (*Q*, *R*) is UCQ-rewritable. In the framework of conjunctive existential rules, a UCQ-rewritable set is also called a *finite unification set (fus)* (Baget et al. 2011). We shall extend this term to disjunctive rules.

**Example 2 (Transitivity).** Let $R = p(x, y) \wedge p(y, z) \rightarrow p(x, z)$. The (Boolean) CQ $Q_1 = \{p(a, b)\}$, where a and b are constants, has no UCQ-rewriting with $\{R\}$, while the (Boolean) CQ $Q_2 = \{p(u, v)\}$ has one, which is $\{Q_2\}$. Indeed, any complete rewriting of $Q_1$ is infinite as it contains all the “paths” of p-atoms from a to b, which are pairwise incomparable by homomorphism. In contrast, the atom $p(u, v)$ maps by homomorphism to any path of p-atoms.

Finally, we recall some fundamental notions on rewriting
with *conjunctive* existential rules. We will rely on these to
define rewriting with disjunctive rules.

**Query rewriting with conjunctive existential rules** In the setting of conjunctive existential rules, query rewriting can be performed using *piece-unifiers*; these are a generalization of classical unifiers that take care of existential variables in rule heads by unifying sets of atoms instead of single atoms (Salvat and Mugnier 1996; Baget et al. 2009). In short, a piece-unifier unifies a subset *Q'* of a CQ *Q* and a subset *H'* of a rule head, such that existential variables from *H'* are unified only with variables of *Q'* that do not occur in *Q* \ *Q'*. Next, we call *separating variables* of *Q'* (w.r.t. *Q*) the variables of *Q'* that also occur in *Q* \ *Q'*. It is convenient to represent a unifier as a partition of a set of terms rather than a substitution. Hence, we say that a partition *P* of a set of terms is *admissible* if no class of *P* contains two constants; we associate a substitution *u* with an admissible partition *P*<sub>u</sub> by selecting one term in each class with priority given to constants: for each class *C* in *P*<sub>u</sub>, let *t*<sub>i</sub> be the selected term, then for every *t*<sub>j</sub> ∈ *C*, we set *u*(*t*<sub>j</sub>) = *t*<sub>i</sub>.

**Definition 3 (Piece-unifier).** <fnref n="1" /> Let *Q* be a CQ and *R* = *B* → *H* be a conjunctive existential rule such that *vars*(*Q*) ∩ *vars*(*B* ∪ *H*) = ∅. A piece-unifier of *Q* with *R* is a triple

$\mu = (Q', H', P_u)$ with $Q' \neq \emptyset$, $Q' \subseteq Q$, $H' \subseteq H$, and $P_u$ is an admissible partition on $\text{terms}(Q') \cup \text{terms}(H')$ such that:

1. $u(Q') = u(H')$, with $u$ a substitution associated with $P_u$;

2. If a class $C \in P_u$ contains an existential variable (from $H'$), then the other terms in $C$ are non-separating variables from $Q'$.

Let $\mu = (Q', H', P_u)$ be a piece-unifier of $Q$ with $R$ :
$B \to H$ and $u$ a substitution associated with $P_u$. The appli-
cation of $\mu$ produces the following CQ:

$$
\beta(Q, R, \mu) = u(B) \cup u(Q \setminus Q')
$$

**Example 3 (Piece-Unifier).** Let $R = p(x, y) \rightarrow \exists z p_1(x, z) \wedge p_2(y, z)$ and $Q_1 = \{p_1(u, v), s(v)\}$. There is no piece-unifier of $Q_1$ with $R$ since $v$ is a separating variable of $Q'_1 = \{p_1(u, v)\}$, hence cannot be unified with $z$. Let $Q_2 = \{p_1(u, v), s(u)\}$: now, there is a piece-unifier of $Q_2$ with $R$, namely $\mu_2 = (\{p_1(u, v)\}, \{p_1(x, z)\}, P_{u_2})$ with $P_{u_2} = \{\{x, u\}, \{y\}, \{z, v\}\}$. Taking the substitution $u_2 = \{u \mapsto x, v \mapsto z\}$, we obtain $\beta(Q_2, R, \mu_2) = \{p(x, y), s(x)\}$. Finally, let $Q_3 = \{p_1(u, v), p_2(u, w), p_1(t, v), s(t)\}$, and $Q'_3 = Q_3 \setminus \{s(t)\}$. The triple $\mu_3 = (Q'_3, \text{head}(R), P_{u_3})$ with $P_{u_3} = \{\{x, y, t, u\}, \{z, v, w\}\}$ is a piece-unifier of $Q_3$ with $R$. If we select $x$ and $z$ in $P_{u_3}$, $\beta(Q_3, R, \mu_3) = \{p(x, x), s(x)\}$.

A piece-rewriting of a UCQ *Q* with a (conjunctive) rule set *R* is a UCQ *Q*<sub>*k*</sub> obtained by a finite sequence of piece-unifier applications, i.e., (*Q*<sub>0</sub> = *Q*), . . . , *Q*<sub>*k*</sub> (*k* ≥ 0) such that, for all 0 < *i* ≤ *k*, there is a piece-unifier *µ* of *Q* ∈ *Q*<sub>*i*−1</sub> with *R* ∈ *R* such that *Q*<sub>*i*</sub> = *Q*<sub>*i*−1</sub> ∪ {β(*Q*, *R*, *µ*)}.

As stated below, piece-unifiers provide a sound and complete query rewriting procedure:

**Theorem 2** (from (Baget et al. 2011)). For any (conjunctive) KB (*F*, *R*) and UCQ *Q*, there is a derivation of (*F*, *R*) leading to an *F*<sub>*i*</sub> such that *F*<sub>*i*</sub> |= *Q* iff there is a piece-rewriting *Q*<sub>*j*</sub> of *Q* with *R* such that *F* |= *Q*<sub>*j*</sub>.

It follows that, when a pair (*Q*, *R*) is UCQ-rewritable, a
UCQ-rewriting can be obtained as a piece-rewriting. Let
us point out that a conjunctive mapping is always UCQ-
rewritable (or fus). Indeed, since it is made of *S*-to-*T* rules,
the application of a piece-unifier of a CQ *Q* produces a CQ
with strictly fewer atoms on *T* than *Q*. Also, CQs that con-
tain predicates on *T* are useless in a rewriting.

3 Query Rewriting with Disjunctive Rules

Our generalization of query rewriting to disjunctive rules relies on a simple idea: a query *Q* can be rewritten with a rule *R* = *B* → *H*₁ ∨ ... ∨ *H*ₙ if each *H*ᵢ contributes to partially answer *Q*. Therefore, a unification step consists of unifying each *H*ᵢ (using a piece-unifier) with a safe copy *Q*ᵢ of a CQ from *Q*; safe copies ensure that the CQs involved in the unification have pairwise disjoint sets of variables. Note that several safe copies of the same CQ from *Q* can be involved. This yields a new CQ made of *body*(*R*) and the remaining parts of the unified CQs, according to some aggregation of the piece-unifiers. We need a few auxiliary notions to specify this aggregation. Let *P* be a set of partitions

<footnote n="1">¹In non-Boolean queries, answer variables have to be treated as
separating variables.</footnote>
(not necessarily of the same set). The join of $\mathcal{P}$, denoted by join($\mathcal{P}$), is the partition obtained from $\mathcal{P}$ by making the union of the partitions in $\mathcal{P}$, then merging all non-disjoint classes until fixed point. E.g., given $\mathcal{P}$ composed of partitions $\{\{x, u\}, \{y, v\}, \{z, w\}\}$ and $\{\{x, y, a\}, \{z', t\}\}$, we obtain join($\mathcal{P}$) = $\{\{x, u, y, v, a\}, \{z, w\}, \{z', t\}\}$. We say that a set of partitions associated with piece-unifiers is admissible if its join is an admissible partition (i.e., it does not contain a class with two constants).

**Definition 4** (Disjunctive Piece-Unifier and One-step Piece-Rewriting). Let a rule $R = B \rightarrow H_1 \lor \dots \lor H_n$ and a UCQ $Q$. A disjunctive piece-unifier $\mu_\vee$ of $Q$ with $R$ is a set $\{\mu_1, \dots, \mu_n\}$ such that:

* for $1 \le i \le n$, $\mu_i = (Q'_i, H'_i, P_{u_i})$ is a (conjunctive) piece-unifier of $Q_i$, a safe copy of a CQ from $Q$, with the (conjunctive) rule $B \rightarrow H_i$;

* and $P_{u_\vee} = \{P_{u_1}, \dots, P_{u_n}\}$ is admissible.

Given a substitution $u_\vee$ associated with join($P_{u_\vee}$), the application of $\mu_\vee$ produces the CQ

$$ \beta_\vee(Q, R, \mu_\vee) = u_\vee(B) \cup \bigcup_{1 \le i \le n} u_\vee(Q_i \setminus Q'_i) $$

The one-step piece-rewriting of $Q$ w.r.t. $\mu_\vee$ is

$$ Q \cup \{\beta_\vee(Q, R, \mu_\vee)\} $$

**Example 4.** Let $R = p(x, y) \rightarrow \exists z_1 r(x, z_1) \lor \exists z_2 r(y, z_2)$ and the UCQ $Q = \{Q\}$ with $Q = \{s(u), r(u, v)\}$. Let $Q_1 = \{s(u_1), r(u_1, v_1)\}$ and $Q_2 = \{s(u_2), r(u_2, v_2)\}$ be two safe copies of $Q$, and let $\mu_\vee = \{\mu_1, \mu_2\}$ with $\mu_1 = (\{r(u_1, v_1)\}, \{r(x, z_1)\}, \{\{u_1, x\}, \{v_1, z_1\}\})$ and $\mu_2 = (\{r(u_2, v_2)\}, \{r(y, z_2)\}, \{\{u_2, y\}, \{v_2, z_2\}\})$. Assume we give priority to variables from $R$, i.e., we take the substitution $u_\vee = \{u_1 \mapsto x, v_1 \mapsto z_1, u_2 \mapsto y, v_2 \mapsto z_2\}$. Then $\beta_\vee(Q, R, \mu_\vee) = \{p(x, y), s(x), s(y)\}$.

**Definition 5** (Piece-Rewriting). Given a disjunctive rule set $\mathcal{R}$, a UCQ $Q'$ is a piece-rewriting (or simply rewriting when clear from the context) of a UCQ $Q$ with $\mathcal{R}$ if there is a finite sequence (called rewriting sequence) $Q = Q_0, Q_1, \dots, Q_k = Q'(k \ge 0)$, such that for all $0 < i \le k$, there is a disjunctive piece-unifier $\mu_\vee$ of $Q_{i-1}$ with $R \in \mathcal{R}$ such that $Q_i$ is the one-step rewriting of $Q_{i-1}$ w.r.t. $\mu_\vee$.

The following lemmas highlight fundamental properties of $\alpha_\vee$ and $\beta_\vee$.

**Lemma 1** (Preservation of entailment by $\alpha_\vee$ and $\beta_\vee$). Let $R$ be a disjunctive rule.

1. For any fact bases $F_1$ and $F_2$ such that $F_2 \models F_1$: if there is a trigger $(R, h_1)$ on $F_1$ then there is a trigger $(R, h_2)$ on $F_2$ such that $\alpha_\vee(F_2, R, h_2) \models \alpha_\vee(F_1, R, h_1)$.

2. For any UCQs $Q_1$ and $Q_2$ such that $Q_2 \models Q_1$: if there is a (disjunctive) piece-unifier $\mu_2$ of $Q_2$ with $R$ then either $\beta_\vee(Q_2, R, \mu_2) \models Q_1$, or there is a (disjunctive) piece-unifier $\mu_1$ of $Q_1$ with $R$ such that $\beta_\vee(Q_2, R, \mu_2) \models \beta_\vee(Q_1, R, \mu_1)$.

The second lemma clarifies the tight relationship between $\alpha_\vee$ and $\beta_\vee$ (we recall that fact bases and CQs have the same logical form; this is also true of finite sets of fact bases and UCQs).

<figure><img src="image_1.png" /><figcaption>Figure 1: Correspondences between $\beta_\vee$ (in blue) and $\alpha_\vee$ (in red)</figcaption></figure>

**Lemma 2** (Composition of $\alpha_\vee$ and $\beta_\vee$). Let $R$ be a disjunctive rule.

1. For any fact base $F$: if there is a trigger $(R, h)$ on $F$ then there is a (disjunctive) piece-unifier $\mu$ of $\alpha_\vee(F, R, h)$ with $R$ such that $F \models \beta_\vee(\alpha_\vee(F, R, h), R, \mu)$.

2. For any UCQ $Q$: if there is a piece-unifier $\mu$ of $Q$ with $R$ then there is a trigger $(R, h)$ on $\beta_\vee(Q, R, \mu)$ such that $\alpha_\vee(\beta_\vee(Q, R, \mu), R, h) \models Q$.

These two lemmas are keys to establish the soundness and completeness of piece-rewriting, as stated next.

**Theorem 3** (Soundness and completeness of piece-rewriting). Let $\mathcal{R}$ be a set of disjunctive rules and $Q$ be a UCQ. Then, for any fact base $F$, holds $F, \mathcal{R} \models Q$ iff there is a piece-rewriting $Q'$ of $Q$ such that $F \models Q'$.

*Proof.* (Sketch) We show that there is a derivation of $(\{F\}, \mathcal{R})$ leading to an $\mathcal{F}_i$ such that $\mathcal{F}_i \models Q$ iff there is a rewriting $Q_j$ of $Q$ with $\mathcal{R}$ such that $F \models Q_j$ (with moreover $j \le i$). This equivalence relies on the following two lemmas, which are corollaries of previous Lemmas 1 and 2. Given any Boolean UCQ $Q$, disjunctive rule $R$ and fact base $F$, the following holds (see Figure 1):

* (Backward-forward Lemma) For any disjunctive piece-unifier $\mu_\vee$ of $Q$ with $R$, if $F \models \beta_\vee(Q, R, \mu_\vee)$ then there is a trigger $(R, h)$ on $F$ such that $\alpha_\vee(F, R, h) \models Q$;

* (Forward-backward Lemma) For any trigger $(R, h)$ on $F$, if $\alpha_\vee(F, R, h) \models Q$ then either $F \models Q$ or there is a disjunctive piece-unifier $\mu_\vee$ of $Q$ with $R$, such that $F \models \beta_\vee(Q, R, \mu_\vee)$.

The ($\Rightarrow$) direction of the theorem is proved by induction on the length $k$ of a derivation from $\{F\}$ to $\mathcal{F}_k$ such that $\mathcal{F}_k \models Q$, using forward-backward Lemma (which itself follows from Lemma 2 (Point 1) and Lemma 1 (Point 2)). The ($\Leftarrow$) direction is proved by induction on the length $k$ of a rewriting sequence from $Q$ to $Q_k$ such that $F \models Q_k$, using backward-forward Lemma (which itself follows from Lemma 2 (Point 2) and Lemma 1 (Point 1)). $\square$

To actually compute a UCQ-rewriting of $Q$ when one exists, it is convenient to proceed in a breadth-first manner, i.e., extend $Q$ at each step with all the CQs that can be generated with (new) disjunctive piece-unifiers. More specifically, we inductively define the following operator $W$, which takes as input a UCQ $Q$ and a disjunctive rule set $\mathcal{R}$, and returns a possibly infinite set of CQs:

* $W_0(Q, \mathcal{R}) = Q$
• For $i > 0$, $W_i(Q, \mathcal{R}) = W_{i-1}(Q, \mathcal{R}) \cup \{\beta_\vee(W_{i-1}(Q, \mathcal{R}), R, \mu_\vee) | \mu_\vee \text{ piece-unifier with } R \in \mathcal{R}\}$

• Finally, $W(Q, \mathcal{R}) = \bigcup_{i \in \mathbb{N}} W_i(Q, \mathcal{R})$.

**Proposition 1 (Properties of W).** For any UCQ $Q$ and disjunctive rule set $\mathcal{R}$, the following holds:

1. $W(Q, \mathcal{R})$ is a complete rewriting of $(Q, \mathcal{R})$.

2. If $(Q, \mathcal{R})$ admits a UCQ-rewriting $Q'$, then there is $i \ge 0$ such that $Q' \equiv W_i(Q, \mathcal{R})$.

*Proof.* (1) Each $W_i(Q, \mathcal{R})$ is a piece-rewriting of $Q$ with $\mathcal{R}$ and, for any piece-rewriting $Q'$ of $Q$ with $\mathcal{R}$, there is $i$ such that $Q' \subseteq W_i(Q, \mathcal{R})$. Hence, the union of all the $W_i(Q, \mathcal{R})$ is a complete rewriting of $Q$. (2) If $(Q, \mathcal{R})$ admits a UCQ-rewriting $Q'$, then by Theorem 3 it admits a complete piece-rewriting $Q''$, and both are necessarily equivalent. Then, $Q'' \subseteq W_i(Q, \mathcal{R})$ for some $i$ and, since $Q''$ is complete, $Q'' \equiv W_i(Q, \mathcal{R})$. $\square$

We propose a query rewriting algorithm (see Algorithm 1) that mimics the computation of $W(Q, \mathcal{R})$, while including two optimizations at each step $i > 0$. First, it only considers new disjunctive piece-unifiers, i.e., those that involve at least one CQ generated at step $i-1$. Second, it removes redundant CQs in the rewriting under construction, by the computation of a cover. More specifically, $Q^*$ denotes the rewriting under construction and $Q_{new}$ the set of CQs generated at a given step. The function **cover** (Lines 1 and 6) returns a cover of the given set. The function **generate** (Line 5) takes as input the current rewriting $Q^*$, its subset $Q_{prev}$ of CQs generated at the previous step, as well as $\mathcal{R}$, and returns the set of generated CQs, i.e., all the $\beta_\vee(Q^*, R, \mu_\vee)$ where $\mu_\vee$ is a new disjunctive piece-unifier. This yields the set $Q_{new}$. To compute a cover of $Q^* \cup Q_{new}$, priority is given to $Q^*$ in case of query equivalence, for termination reasons. The function **removeMoreSpecific** takes as input two sets of CQs and returns the first set minus its queries more specific than a query of the second set. The computation of a cover of $Q^* \cup Q_{new}$ is decomposed into three steps (Lines 6-8): compute a cover of $Q_{new}$; remove from $Q_{new}$ the queries more specific than a query from $Q^*$; and remove from $Q^*$ the queries more specific than a query from $Q_{new}$. Then, $Q_{new}$ is added to $Q^*$ (Line 9). We remind that a query may have rewrites of unbounded size but still a UCQ-rewriting (see Example 2), hence the role of the cover computation is not only to remove redundancies but also to ensure that the algorithm halts when a UCQ-rewriting has been found.

The correctness of the algorithm is based on the soundness and completeness of the $W$ operator, however attention should be paid to the potential impact of query removal on completeness (Lines 6 to 8). Indeed, when a CQ $Q_2$ is removed because it is more specific than another CQ $Q_1$, we have to ensure that any CQ that could be generated using $Q_2$ is more specific than another CQ already present in the current rewriting, or than a CQ that can be generated using $Q_1$. Fortunately, this property is ensured by Lemma 1 (Point 2), considering $Q^*$ and $Q_{new}$ at the end of Line 5, then taking $Q_2 = Q^* \cup Q_{new}$ and $Q_1 = Q_2 \setminus \{Q_2\}$.

**Algorithm 1: BREADTH-FIRST REWRITING**

**Data:** UBCQ $Q$ and set of disjunctive rules $\mathcal{R}$

**Result:** A sound and complete rewriting of $Q$

1. $Q_{new} \leftarrow \text{cover}(Q); \text{ // new CQs}$

2. $Q^* \leftarrow Q_{new}; \text{ // result}$

3. while $Q_{new} \neq \emptyset$ do

4. &nbsp;&nbsp;&nbsp;&nbsp; $Q_{prev} \leftarrow Q_{new} \text{ // CQs from the preceding step}$

5. &nbsp;&nbsp;&nbsp;&nbsp; $Q_{new} \leftarrow \text{generate}(Q^*, Q_{prev}, \mathcal{R}); \text{ // new CQs}$

6. &nbsp;&nbsp;&nbsp;&nbsp; $Q_{new} \leftarrow \text{cover}(Q_{new})$

7. &nbsp;&nbsp;&nbsp;&nbsp; $Q_{new} \leftarrow \text{removeMoreSpecific}(Q_{new}, Q^*)$

8. &nbsp;&nbsp;&nbsp;&nbsp; $Q^* \leftarrow \text{removeMoreSpecific}(Q^*, Q_{new})$

9. &nbsp;&nbsp;&nbsp;&nbsp; $Q^* \leftarrow Q^* \cup Q_{new}$

10. return $Q^*$

**Theorem 4.** *Algorithm 1 computes a sound and complete rewriting. Moreover, it halts and outputs a minimal rewriting when $(Q, \mathcal{R})$ is UCQ-rewritable.*

*Proof.* By induction on the number of iterations of the while loop, we prove the following invariant of the algorithm, using Lemma 1 (Point 2): after step $i$, $Q^*$ is equivalent to $W_i(Q, \mathcal{R})$. Then, soundness and completeness follow from Proposition 1. Line 7 ensures that $Q_{new}$ becomes empty when $Q^*$ is a complete rewriting. Since a cover of $Q^*$ is computed at each step, the output set is of minimal size. $\square$

**Further remarks on completeness.** When it comes to practical implementations, one may find simpler to rely on (conjunctive) piece-unifiers that unify the smallest possible subsets of a CQ. Such piece-unifiers are called single-piece (König et al. 2015). In the specific case of datalog, a single-piece unifier unifies a single atom of a CQ with a rule head. Piece-rewriting restricted to single-piece unifiers is complete for conjunctive rules (König et al. 2015), but it is no longer so with disjunctive rules. This occurs already in the case of disjunctive datalog, as illustrated next.

**Example 5.** Consider again the colorability example (Ex. 1) with $R = v(x) \rightarrow g(x) \vee r(x)$ and $Q = \{Q_1, Q_2\}$ with $Q_1 = \{g(u), e(u, w), g(w)\}$ and $Q_2 = \{r(u), e(u, w), r(w)\}$. With single-piece unifiers we obtain CQs that have the shape of “chains” with a g-atom or an r-atom at each extremity. However, there are also rewrites without any occurrence of g nor r, and the only way of obtaining them is to unify two query atoms together. For instance, the CQ $\{v(u), e(u, u)\}$ is obtained by unifying, on the one hand both g-atoms of a safe copy of $Q_1$ with $g(x)$, and on the other hand both r-atoms of a safe copy of $Q_2$ with $r(x)$. More generally, using such piece-unifiers, one can produce all the CQs that describe the odd-length cycles in the graph. Note that these CQs are incomparable with the CQs generated with single-piece unifiers. This example also shows that a UCQ may have no UCQ-rewriting although each of its CQs has one (which is here the CQ itself).
**Related work.** To the best of our knowledge, (Alfonso, Chortaras, and Stamou 2021) is the only previous work proposing a UCQ rewriting technique for general disjunctive existential rules. This technique is based on a restricted form of first-order resolution, where at each step a CQ is unified with a disjunct of a rule head (using a conjunctive piece-unifier), which produces a new disjunctive rule with fewer disjunctions; when the unified rule is conjunctive, (the negation of) a CQ is produced. In comparison, the main advantages of our proposal are the following: (1) a rewriting step directly produces a CQ and not a rule, (2) intermediate rules, which may not lead to a CQ, are avoided, and (3) there is a direct correspondence between a chase step and a rewriting step, which makes it easier to study the properties of query rewriting, especially as the rule set is not updated.

## 4 What are fus Disjunctive Rules?

We now address the question of identifying classes of disjunctive rules that are UCQ-rewritable. By extension of the term coined for conjunctive existential rules, we also call them fus. To the best of our knowledge, the only fus class of disjunctive rules mentioned in the literature (Alfonso, Chortaras, and Stamou 2021) is actually a slight extension of fus conjunctive rules: this class consists of disjunctive rules with an empty frontier and it is shown that such rules can be safely added to a set of fus conjunctive rules. As a matter of fact, known fus classes of conjunctive rules do not seem to be extensible to the disjunctive case. And worse, the straightforward extension of syntactic criteria that underlie fus in the conjunctive case seems to easily lead to undecidability of query answering, as shown for example in (Morak 2021) for the syntactic restriction called stickiness (Calì, Gottlob, and Pieris 2010).

At first glance, one may expect nonrecursive disjunctive rule sets to be fus, as it happens for conjunctive rules. However, it is not the case, as shown by the next example: a CQ (on unary predicates) may have no UCQ-rewriting even with a single non-recursive body-atomic (disjunctive) data-log rule.

**Example 6.** Let the rule $R = p(x, y) \rightarrow t_1(x) \lor t_2(y)$ and the BCQ $Q = \{t_1(u), t_2(u)\}$. Then the pair $(\{Q\}, \{R\})$ has no UCQ-rewriting. Indeed, a complete rewriting contains all the CQs of the following shape for any $n \in \mathbb{N}$:

$$t_2(u_0) \land \left( \bigwedge_{i=1}^{n} p(u_{i-1}, u_i) \right) \land t_1(u_n)$$

All these queries are pairwise incomparable w.r.t. homomorphism. Let us detail the first rewriting step. To unify $\{Q\}$ with $R$, we have to make two safe copies of $Q$, let $Q_1$ and $Q_2$, which are respectively unified with $t_1(x)$ and $t_2(y)$. This produces the CQ $\{t_2(x), p(x, y), t_1(y)\}$, isomorphic to $\{t_2(u_0), p(u_0, u_1), t_1(u_1)\}$. If we switch the unified atoms of head($R$), we obtain an isomorphic CQ. All subsequent rewriting steps lead to longer paths of p-atoms.

A similar observation follows from (Gerasimova et al. 2020), which focuses on a specific disjunctive rule of the form $A(x) \rightarrow T(x) \lor F(x)$, called a covering axiom and

denoted by $cov_A$; their complexity results imply that the singleton set $\{cov_A\}$ is not fus,<fnref n="2" /> which can be checked for instance by considering the query $Q = \{T(u), p(u, v), F(v)\}$.

Next, we show that such observations can be generalized to almost any source-to-target disjunctive rule. Evidently, we have to exclude disjunctive rules that are equivalent to a conjunctive rule, as classes of fus conjunctive rules are known. We also exclude disconnected rules, i.e., rules $R$ such that body($R$) $\cup$ head($R$) is not a connected set of atoms (where connectivity is defined in the obvious way based on shared variables). Note that a rule with a head $H_i$ that has an empty frontier is disconnected, as well as a rule whose body has a connected component with an empty frontier. However, a rule with a disconnected body may not be disconnected, since head atoms may connect several connected components of the body (e.g., a “product” rule like $b_1(x) \land b_2(y) \rightarrow t_1(x) \lor t_2(y) \lor p(x, y)$ is not disconnected).

**Example 7 (Fus disconnected rule).** Let the disconnected rule $R = b(x) \rightarrow t_1(x) \lor \exists z t_2(z)$. $R$ is not equivalent to a conjunctive rule. Let us check that it is fus. Given any UCQ $Q$, let $Q_2$ be the subset of $Q$ that contains all the CQs that can be unified with $\exists z t_2(z)$. Any $Q \in Q_2$ necessarily contains a disconnected component of the form $\exists u t_2(u)$. Moreover, it is useless to unify $Q$ with $t_1(x)$: in such case, let $Q_2$ be the CQ unified with $\exists z t_2(z)$, then the obtained rewriting is more specific than $Q_2$. Hence, we can ignore all the produced CQs that contain a connected component of the form $\exists u t_2(u)$. Rewriting $Q$ with $\{R\}$ amounts to rewriting $Q \setminus Q_2$ with the conjunctive rule set $R = \{b(x) \land (Q_2 \setminus \{\exists u t_2(u)\}) \rightarrow t_1(x) \mid Q_2 \in Q_2\}$, which belongs to the fus class called domain restricted (Baget et al. 2011).

In the next theorem, we restrict the head of the rule to a disjunction of two atom sets, to keep the proof simple.

**Theorem 5.** Let $R = B \rightarrow H_1 \lor H_2$ be a source-to-target rule that is not disconnected nor equivalent to a conjunctive rule. Then, there is a CQ $Q$ such that $(\{Q\}, \{R\})$ is not UCQ-rewritable.

*Proof.* (Sketch) Let $R = B[\mathbf{x}_1, \mathbf{x}_2, y] \rightarrow \exists \mathbf{z}_1 H_1[\mathbf{x}_1, \mathbf{z}_1] \lor \exists \mathbf{z}_2 H_2[\mathbf{x}_2, \mathbf{z}_2]$, where:

* $\mathrm{fr}(R) = \mathbf{x}_1 \cup \mathbf{x}_2$; $\mathbf{x}_1$ and $\mathbf{x}_2$ may share variables;

* $\mathbf{x}_1 \neq \emptyset$ ($i = 1, 2$) since $R$ is not disconnected.

We build the following (Boolean) CQ:

$$Q = \{H_1^s[\mathbf{v}_1, \mathbf{w}_1], p(\mathbf{v}_1, \mathbf{v}_2), H_2^s[\mathbf{v}_2, \mathbf{w}_2]\}$$

where each $H_i^s[\mathbf{v}_i, \mathbf{w}_i]$ is a safe copy of $H_i[\mathbf{x}_i, \mathbf{z}_i]$ and $p$ is a fresh predicate. Note that, since $R$ is connected, both $H_1$

<footnote n="2">²That paper studies syntactic conditions on ontology-mediated CQs of the form $(Q, cov_A)$ that determine the data complexity of query answering and the rewritability in some target query language. In particular, it is shown that if a (connected) CQ $Q$ has no term $x$ with both atoms $T(x)$ and $F(x)$ and contains at least one $F$-atom and one $T$-atom then answering $(Q, cov_A)$ is L-hard for data complexity. Since answering a UCQ-rewritable ontology-mediated query is in $AC^0$ for data complexity, and $AC^0 \subset L$, it follows that no $cov_A$ is fus.</footnote>
and $H_2$ have a frontier variable, and frontier variables being renamed in each $H_i^s$, the arity of $p$ is at least 2. In $p(v_1, v_2)$ the order on the variables is important: a fixed order is chosen on $x_i$ (hence, $v_i$) and the tuple $v_1$ comes before the tuple $v_2$. Hence, $p(v_1, v_2)$ can be seen as "directed" from $v_1$ to $v_2$. We then proceed in two steps.

1. We show that we can produce an infinite set $\mathcal{Q}$ whose element CQs are pairwise incomparable by homomorphism. Let $Q_0 = \mathcal{Q}$. At each step $i \ge 1$, $Q_i$ is produced from a safe copy of $\mathcal{Q}$ unified with $H_1$ and a safe copy of $Q_{i-1}$ unified with $H_2$. The piece-unifiers unify $H_1^s$ (resp. $H_2^s$) in $\mathcal{Q}$ (resp. $Q_{i-1}$) according to the isomorphism from $H_1^s$ (resp. $H_2^s$) to $H_1$ (resp. $H_2$). Any CQ $Q_k$ in $\mathcal{Q}$ is connected and follows the "pattern" $H_2^s \cdot p.(B.p)^k \cdot H_1^s$, where occurrences of $p$-atoms all have the same direction; hence, two "adjacent" $p$-atoms, i.e., that share variables with the same copy $B_i$ of a $B$, cannot be mapped one onto the other (by a homomorphism that maps $B_i$ to itself).

2. We show that no CQ $Q'$ that can be produced by piece-rewriting maps by homomorphism to a CQ from $\mathcal{Q}$, except by isomorphism. When there is no (conjunctive) piece-unifier that unifies $H_1[v_1, w_1]$ in $\mathcal{Q}$ with $H_2[x_2, z_2]$ (the same holds if we exchange $H_1$ and $H_2$), all the produced $Q'$ are more specific than (including isomorphic to) CQs from $\mathcal{Q}$. Otherwise, assume that a CQ $Q'$ is produced by unifying $H_1[v_1, w_1]$ with $H_2[x_2, z_2]$. If $Q'$ can be mapped by homomorphism to a $Q_n \in \mathcal{Q}$, the arguments of any $p$-atom in $Q'$ must be pairwise distinct variables. We show that it leads to have $R$ equivalent to the conjunctive rule $B \to H_i$ (with $i=1$ or $i=2$), which contradicts the hypothesis on $R$.

It follows that $\mathcal{Q}$ is a subset of any sound and complete rewriting of $\{Q\}$ with $\{R\}$, hence the pair $(\{Q\}, \{R\})$ does not admit a UCQ-rewriting. $\square$

One interest of the above proof is to provide a general construction that applies to any rule (fulfilling the conditions of the theorem). Also, the proof can be generalized to a rule head with $k$ disjuncts, taking $\mathcal{Q}$ containing a safe copy of each $H_i$ plus a $p$-atom that connects these copies through their frontier variables.

Given this result, the notion of fus disjunctive rules does not seem to be particularly relevant. Studying the problem of deciding whether a pair $(\mathcal{Q}, \mathcal{R})$ is UCQ-rewritable seems more interesting, although it is known to be undecidable already for (conjunctive) datalog rules.<fnref n="3" /> Again, little is known about classes of disjunctive rules and UCQs for which this problem would be decidable. Let us point out a few immediate cases of UCQ-rewritable pairs $(\mathcal{Q}, \mathcal{R})$:

* $\mathcal{Q}$ is composed of atomic CQs and $\mathcal{R}$ is a set of disjunctive linear existential rules (i.e., rules with an atomic body).

Indeed, only atomic CQs can be produced, and there is a finite number of them on a given set of predicates. This case was already noticed in (Bourhis et al. 2016).

* $\mathcal{Q}$ is composed of atomic queries and $\mathcal{R}$ is a set of $\mathcal{S}$-to-$\mathcal{T}$ rules. The produced CQs are obtained from the rule bodies by specializing their frontier (i.e., merging variables and replacing them by constants occurring in $\mathcal{Q}$ and rule heads). Hence, there is a finite number of them.

* $\mathcal{Q}$ is composed of variable-free CQs<fnref n="4" /> and $\mathcal{R}$ is a set of lossless existential rules (i.e., such that all the variables in a rule body are frontier). Then, no variable is introduced by rewriting, hence the number of terms in a CQ is bounded by $|\text{consts}(\mathcal{Q}) \cup \text{consts}(\mathcal{R})|$.

## 5 Disjunctive Mappings

We now consider UCQ-rewritability with (disjunctive) mappings. Let $\mathcal{S}$ and $\mathcal{T}$ be the sets of source and target predicates, respectively, and let $\mathcal{M}$ be a mapping on $(\mathcal{S}, \mathcal{T})$. Given a query on $\mathcal{T}$, the aim is to obtain a complete rewriting w.r.t. fact bases on $\mathcal{S}$. Because $\mathcal{S}$ and $\mathcal{T}$ are disjoint, CQs that contain atoms on $\mathcal{T}$ are useless in a rewriting. Hence, we define a *mapping rewriting* as a rewriting on $\mathcal{S}$ and use the notation *S-rewriting* to distinguish it from a rewriting on $\mathcal{S} \cup \mathcal{T}$. An *S-rewriting* $Q'$ of a UCQ $\mathcal{Q}$ with $\mathcal{M}$ is complete if, for all fact base $F$ on $\mathcal{S}$, if $F, \mathcal{M} \models \mathcal{Q}$ then $F \models Q'$. A finite complete *S-rewriting* is called a *UCQ-S-rewriting*.

**Example 8 (Colorability).** We adapt Example 5 to transform the rule into a mapping. Let $\mathcal{S} = \{v, e\}$, $\mathcal{T} = \{\hat{e}, g, r\}$ and $\mathcal{M} = \{m_1, m_2\}$, with:

$$m_1 = e(x, y) \rightarrow \hat{e}(x, y)$$

$$m_2 = v(x) \rightarrow g(x) \lor r(x).$$

Let $\mathcal{Q} = \{Q_1, Q_2\}$ with $Q_1 = \{g(u), \hat{e}(u, w), g(w)\}$ and $Q_2 = \{r(u), \hat{e}(u, w), r(w)\}$. Any complete *S-rewriting* of $\mathcal{Q}$ contains CQs that describe all the cycles of odd length (in other words, it defines non-2-colorability). All the other CQs that can be produced by piece-rewriting contain predicates $g$ and $r$, hence are discarded.

Note that a query may have a UCQ-*S*-rewriting, while it does not have any UCQ-rewriting (on $\mathcal{S} \cup \mathcal{T}$), as illustrated by the next example.

**Example 9.** Let $\mathcal{S} = \{p\}$ and $\mathcal{T} = \{t_1, t_2\}$. Consider the (Boolean) CQ $\mathcal{Q} = \{t_1(u), t_2(u)\}$ and the rule $R = p(x, y) \rightarrow t_1(x) \lor t_2(y)$ from Example 6. While the pair $(\{Q\}, \{R\})$ has no UCQ-rewriting, it has a UCQ-*S*-rewriting, which is empty. Indeed, all the CQs that can be obtained by piece-rewriting contain an atom on $\mathcal{T}$.

Let disjunctive mapping rewritability be the following problem: Given a disjunctive mapping $\mathcal{M}$ on $(\mathcal{S}, \mathcal{T})$ and a UCQ $\mathcal{Q}$ on $\mathcal{T}$, does $(\mathcal{Q}, \mathcal{M})$ have a UCQ-*S*-rewriting?

**Theorem 6.** Disjunctive mapping rewritability is undecidable.

*Proof.* (Sketch) We build a reduction from the following undecidable problem: Given a (Boolean) CQ $\mathcal{Q}$ and a set of

<footnote n="3">³This follows from the undecidability of determining whether a datalog program is uniformly bounded (Gaifman et al. 1993). Indeed, a datalog program $\mathcal{R}$ is uniformly bounded iff the pair $(\mathcal{Q}, \mathcal{R})$ is UCQ-rewritable for any full atomic query $\mathcal{Q}$. In turn, UCQ-rewritability of $(\mathcal{Q}, \mathcal{R})$ can be reduced to UCQ-rewritability of $(\mathcal{Q}', \mathcal{R}')$ with $\mathcal{Q}'$ a Boolean CQ.</footnote>

<footnote n="4">⁴If non-Boolean CQs are considered, $\mathcal{Q}$ can be extended to a set of full CQs.</footnote>
(conjunctive) datalog rules $\mathcal{R}$, is the pair $\{\{Q\}, \mathcal{R}\}$ UCQ-rewritable? W.l.o.g. we assume that rules in $\mathcal{R}$ have no constants (and an atomic head). The reduction translates each instance $(Q, \mathcal{R})$ defined on a set of predicates $\mathcal{P}$, into an instance $(\mathcal{Q}^{\mathcal{R}}, \mathcal{M}^{\mathcal{R}})$ of the disjunctive mapping rewritability problem, defined on a pair of predicates sets $(S, \mathcal{T})$ such that:

* $S = \mathcal{P} \cup \{T\}$, where $T$ is a fresh unary predicate,

* $\mathcal{T}$ is the union of: (1) a set of predicates in bijection with $S$, where $\hat{p}$ denotes the predicate obtained from $p \in S$, and (2) a set of fresh predicates in bijection with $\mathcal{R}$, where $p_{R_i}$ denotes the predicate associated with the rule $R_i$; the arity of each $p_{R_i}$ is $|\mathrm{fr}(R_i)|$.

Given a conjunction $Q$ (on $\mathcal{P}$), we denote by $Q^T$ the conjunction (on $\mathcal{S}$) obtained from $Q$ by adding a $T$-atom on each term; given a conjunction $Q$ (on $S$), we denote by $\hat{Q}$ the conjunction (on $\mathcal{T}$) obtained from $Q$ by renaming all the predicates $p$ into $\hat{p}$. Hence, $\hat{Q}^T$ is obtained by performing the first operation, then the second. Given $\mathbf{x} = x_1, \dots, x_n$, $T[\mathbf{x}]$ denotes the conjunction $T(x_1) \wedge \dots \wedge T(x_n)$. Similarly, $\hat{T}[\mathbf{x}] = \hat{T}(x_1) \wedge \dots \wedge \hat{T}(x_n)$.

Let $Q$ and $\mathcal{R} = \{R_1, \dots, R_n\}$, where $R_i = B_i[\mathbf{x}_i, \mathbf{y}_i] \to H_i[\mathbf{x}_i]$. The instance $(\mathcal{Q}^{\mathcal{R}}, \mathcal{M}^{\mathcal{R}})$ is defined as follows:

* $\mathcal{Q}^{\mathcal{R}} = \{Q_Q\} \cup \mathcal{Q}_{\mathcal{R}}$ with:

$$Q_Q = \hat{Q}^T,$$

$$\mathcal{Q}_{\mathcal{R}} = \{Q_{R_i} = \exists \mathbf{x}_i, \mathbf{y}_i (\widehat{B_i}^T[\mathbf{x}_i, \mathbf{y}_i] \wedge p_{R_i}(\mathbf{x}_i) | R_i \in \mathcal{R}\}$$

* $\mathcal{M}^{\mathcal{R}} = \mathcal{M}_{\mathcal{R}} \cup \mathcal{M}_{trans}$ with:

$$\mathcal{M}_{\mathcal{R}} = \{m_{R_i} = T[\mathbf{x}_i] \to p_{R_i}(\mathbf{x}_i) \lor \hat{H}_i(\mathbf{x}_i) \mid R_i \in \mathcal{R}\}$$

$$\mathcal{M}_{trans} = \{p(\mathbf{x}) \to \hat{p}(\mathbf{x}) \mid p \in S\}$$

Based on the natural bijection between the CQs $Q_P$ defined on $\mathcal{P}$ and the CQs $(Q_P)^T$ defined on $S$, we prove that $Q_P$ belongs to a rewriting of $\{Q\}$ with $\mathcal{R}$ iff $(Q_P)^T$ belongs to a rewriting of $\mathcal{Q}^{\mathcal{R}}$ with $\mathcal{M}^{\mathcal{R}}$. Note that set membership is up to isomorphism throughout the proof. More specifically, we first prove the following lemmas:

1. For any CQ $Q_w$ in a piece-rewriting of $\{Q\}$ with $\mathcal{R}$, $(Q_w)^T$ belongs to a piece-rewriting of $\mathcal{Q}^{\mathcal{R}}$ with $\mathcal{M}^{\mathcal{R}}$. Indeed, to each $R_i$ are associated a CQ $Q_{R_i}$ and a rule $m_{R_i}$ that allow to simulate any rewriting step performed with $R_i$, using fresh predicate $p_{R_i}$.

2. Any CQ $Q_S$ in an $\mathcal{S}$-rewriting of $\mathcal{Q}^{\mathcal{R}}$ with $\mathcal{M}^{\mathcal{R}}$ is of the form $Q_S = (Q_P)^T$, with $Q_P$ the subset of $Q_S$ on $\mathcal{P}$.

3. For any CQ of the form $(Q_P)^T$, with $Q_P$ on $\mathcal{P}$, that belongs a piece-rewriting of $\mathcal{Q}^{\mathcal{R}}$ with $\mathcal{M}^{\mathcal{R}}$, $Q_P$ belongs to a piece-rewriting of $\{Q\}$ with $\mathcal{R}^*$, where $\mathcal{R}^*$ is the reflexive and transitive closure of $\mathcal{R}$ by unfolding (i.e., rule composition). Note that $\mathcal{R}^*$ is logically equivalent to $\mathcal{R}$.

We rely on these lemmas to prove the following: if there is a UCQ-rewriting of $(\{Q\}, \mathcal{R})$ then there is a UCQ-$\mathcal{S}$-rewriting of $(\mathcal{Q}^{\mathcal{R}}, \mathcal{M}^{\mathcal{R}})$. The proof of the opposite direction is similar. Let $Q$ be a UCQ-rewriting of $(\{Q\}, \mathcal{R})$. Then there is a piece-rewriting $Q_i$ of $\{Q\}$ with $\mathcal{R}$ such that $Q_i \equiv Q$. By Lemma 1, there is a piece-rewriting

$Q_j$ of $\mathcal{Q}^{\mathcal{R}}$ with $\mathcal{M}^{\mathcal{R}}$ that contains all the CQs of the form $(Q_w)^T$ in bijection with the $Q_w$ in $Q_i$. By definition, $Q_j$ is a finite rewriting of $(\mathcal{Q}^{\mathcal{R}}, \mathcal{M}^{\mathcal{R}})$ and the subset $\mathcal{Q}_j^S$ of $Q_j$ that contains only the CQs on $S$ is a finite $\mathcal{S}$-rewriting of $(\mathcal{Q}^{\mathcal{R}}, \mathcal{M}^{\mathcal{R}})$. Now, assume $\mathcal{Q}_j^S$ is not complete, i.e., there is a CQ that belongs to an $\mathcal{S}$-rewriting of $(\mathcal{Q}^{\mathcal{R}}, \mathcal{M}^{\mathcal{R}})$ but that is not more specific than a CQ in $\mathcal{Q}_j^S$; by Lemma 2, such CQ is of the form $(Q_P)^T$. Then there is a piece-rewriting $Q'_j$ of $\mathcal{Q}^{\mathcal{R}}$ with $\mathcal{M}^{\mathcal{R}}$ that contains a CQ entailed by $(Q_P)^T$; hence such CQ is also on $S$, and by Lemma 2 it is of the form $(Q'_P)^T$. By Lemma 3, $Q'_P$ belongs to a piece-rewriting of $\{Q\}$ with $\mathcal{R}^*$. Since $\mathcal{R}^* \equiv \mathcal{R}$, there is a CQ equivalent to $Q'_P$ in some rewriting of $(\{Q\}, \mathcal{R})$. Since $Q_i$ is complete, there is $Q_c \in Q_i$ such that $Q'_P \models Q_c$. Hence, $(Q'_P)^T \models (Q_c)^T$, so $(Q_P)^T \models (Q_c)^T$; by Lemma 1, $(Q_c)^T \in Q_j$, hence $(Q_c)^T \in \mathcal{Q}_j^S$, which contradicts the fact that $(Q_P)^T$ is not more specific than a CQ in $\mathcal{Q}_j^S$. $\square$

# 6 Perspectives

In conclusion, UCQ rewriting with disjunctive existential rules appears to be extremely challenging. The main classes that ensure termination for conjunctive rules fail to be generalized. As suggested by previous work in (Gerasimova et al. 2020) and our Theorem 5, the fus notion applied to disjunctive rules does not seem to add much w.r.t. fus conjunctive rules. However, it might be more relevant in the context of mappings (when it becomes UCQ-$\mathcal{S}$-rewritability), which still has to be studied. Beside, a number of interesting issues remain open, in relationship with the finite rewritability of a pair $(Q, \mathcal{R})$. We list here some of them:

1. Clarify the boundary between decidability and undecidability for the problem of determining whether a pair $(Q, \mathcal{R})$ is UCQ-rewritable, according to specific classes of rules (and queries). In particular, UCQ-rewritability is decidable for guarded conjunctive rules and some of their generalizations (Barceló et al. 2018), does this extend to the disjunctive case?

2. We have shown that the UCQ-$\mathcal{S}$-rewritability of a pair $(Q, \mathcal{M})$ is undecidable (Theorem 6). Is it still the case for a pair $(\{Q\}, \mathcal{M})$ where $Q$ is a CQ?

3. Our undecidability proof for UCQ-$\mathcal{S}$-rewritability (Theorem 6) exploits the fact that rewritings are restricted to predicates in $\mathcal{S}$. If we consider instead UCQ-rewritings with source-to-target rules, we know that the problem can only be simpler, as there is an easy reduction from UCQ-rewritability with $\mathcal{S}$-to-$\mathcal{T}$-rules to UCQ-$\mathcal{S}$-rewritability with mappings (one simply has to add a mapping rule per target predicate to give it an existence at the source level). Is the UCQ-rewritability of a pair $(Q, \mathcal{R})$ decidable when $\mathcal{R}$ is a set of $\mathcal{S}$-to-$\mathcal{T}$ rules?

4. Design an algorithm that, given a pair $(Q, \mathcal{M})$, outputs a UCQ-$\mathcal{S}$-rewriting for this pair when one exists.
Acknowledgements

This work is partly supported by the ANR project CQFD (ANR-18-CE23-0003).

References

Ahmetaj, S.; Ortiz, M.; and Simkus, M. 2018. Rewriting guarded existential rules into small datalog programs. In *21st International Conference on Database Theory, ICDT 2018*, volume 98 of LIPIcs, 4:1–4:24.

Alfonso, E. M.; Chortaras, A.; and Stamou, G. 2021. Ucq-rewritings for disjunctive knowledge and queries with negated atoms. *Semantic Web* 12(4):685–709.

Alviano, M.; Faber, W.; Leone, N.; and Manna, M. 2012. Disjunctive datalog with existential quantifiers: Semantics, decidability, and complexity issues. *Theory Pract. Log. Procedium*. 12(4-5):701–718.

Arenas, M.; Pérez, J.; Reutter, J. L.; and Riveros, C. 2010. Foundations of schema mapping management. In *29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010*, 227–238. ACM.

Arenas, M.; Pérez, J.; and Riveros, C. 2008. The recovery of a schema mapping: bringing exchanged data back. In *27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2008*, 13–22. ACM.

Baader, F.; Brandt, S.; and Lutz, C. 2005. Pushing the EL envelope. In *19th International Joint Conference on Artificial Intelligence, IJCAI 2005*, 364–369.

Baget, J.-F.; Leclère, M.; Mugnier, M.-L.; and Salvat, E. 2009. Extending Decidable Cases for Rules with Existential Variables. In *21st International Joint Conference on Artificial Intelligence, IJCAI 2009*, 677–682.

Baget, J.; Leclère, M.; Mugnier, M.; and Salvat, E. 2011. On rules with existential variables: Walking the decidability line. *Artif. Intell.* 175(9-10):1620–1654.

Barceló, P.; Berger, G.; Lutz, C.; and Pieris, A. 2018. First-order rewritability of frontier-guarded ontology-mediated queries. In *27th International Joint Conference on Artificial Intelligence, IJCAI 2018*, 1707–1713. ijcai.org.

Beeri, C., and Vardi, M. Y. 1984. A proof procedure for data dependencies. *J. ACM* 31(4):718–741.

Bernstein, P. A., and Ho, H. 2007. Model management and schema mappings: Theory and practice. In *33rd International Conference on Very Large Data Bases, VLDB, 2007*, 1439–1440. ACM.

Bienvenu, M.; ten Cate, B.; Lutz, C.; and Wolter, F. 2014. Ontology-based data access: A study through disjunctive datalog, csp, and MMSNP. *ACM Trans. Database Syst.* 39(4):33:1–33:44.

Bourhis, P.; Manna, M.; Morak, M.; and Pieris, A. 2016. Guarded-Based Disjunctive Tuple-Generating Dependencies. *ACM Trans. Database Syst.* 41(4):27:1–27:45.

Buron, M.; Mugnier, M.; and Thomazo, M. 2021. Parallelisable existential rules: a story of pieces. In *18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021*, 162–173.

Calì, A.; Gottlob, G.; and Kifer, M. 2008. Taming the infinite chase: Query answering under expressive relational constraints. In *11th International Conference on Principles of Knowledge Representation and Reasoning, KR 2008*, 70–80. AAAI Press.

Calì, A.; Gottlob, G.; and Lukasiewicz, T. 2009. A General Datalog-Based Framework for Tractable Query Answering over Ontologies. In *28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2009*, 77–86. ACM.

Calì, A.; Gottlob, G.; and Pieris, A. 2010. Advanced processing for ontological queries. *VLDB Endow.* 3(1):554–565.

Calvanese, D.; De Giacomo, G.; Lembo, D.; Lenzerini, M.; and Rosati, R. 2007. Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family. *Journal of Automated Reasoning* 39(3):385–429.

Carral, D.; Dragoste, I.; and Krötzsch, M. 2017. Restricted Chase (Non)Termination for Existential Rules with Disjunctions. In *26th International Joint Conference on Artificial Intelligence, IJCAI 2017*, 922–928. ijcai.org.

Eiter, T.; Gottlob, G.; and Mannila, H. 1997. Disjunctive datalog. *ACM Trans. Database Syst.* 22(3):364–418.

Fagin, R.; Kolaitis, P. G.; Miller, R. J.; and Popa, L. 2005. Data exchange: semantics and query answering. *Theor. Comput. Sci.* 336(1):89–124.

Fagin, R.; Kolaitis, P. G.; Popa, L.; and Tan, W. C. 2008. Quasi-inverses of schema mappings. *ACM Trans. Database Syst.* 33(2):11:1–11:52.

Gaifman, H.; Mairson, H. G.; Sagiv, Y.; and Vardi, M. Y. 1993. Undecidable optimization problems for database logic programs. *J. ACM* 40(3):683–713.

Gerasimova, O.; Kikot, S.; Kurucz, A.; Podolskii, V. V.; and Zakharyaschev, M. 2020. A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom. In *17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020*, 403–413.

Gottlob, G.; Manna, M.; Morak, M.; and Pieris, A. 2012. On the complexity of ontological reasoning under disjunctive existential rules. In *Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012*, volume 7464 of LNCS, 1–18. Springer.

König, M.; Leclère, M.; Mugnier, M.; and Thomazo, M. 2015. Sound, complete and minimal ucq-rewriting for existential rules. *Semantic Web* 6(5):451–475.

Krötzsch, M.; Rudolph, S.; and Hitzler, P. 2006. On the complexity of Horn description logics. In *2nd Workshop on OWL: Experiences and Directions*, volume 216 of CEUR WS Proceedings. CEUR-WS.org.

Leclère, M.; Mugnier, M.; and Pérution-Kihli, G. 2023. Query rewriting with disjunctive existential rules and mappings. CoRR abs/2306.05973.

Lutz, C.; Toman, D.; and Wolter, F. 2009. Conjunctive Query Answering in the Description Logic *EL* Using a Re
lational Database System. In *21st International Joint Conference on Artificial Intelligence, IJCAI 2009*, 2070–2075.

Morak, M. 2021. Sticky Existential Rules and Disjunction are Incompatible. In *18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021*, 691–695.

Pérez, J. 2013. The inverse of a schema mapping. In *Data Exchange, Integration, and Streams*, volume 5 of *Dagstuhl Follow-Ups*. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 69–95.

Poggi, A.; Lembo, D.; Calvanese, D.; Giacomo, G. D.; Lenzerini, M.; and Rosati, R. 2008. Linking Data to Ontologies. *J. Data Semant.* 10:133–173.

Salvat, E., and Mugnier, M. 1996. Sound and Complete Forward and Backward Chainings of Graph Rules. In *4th International Conference on Conceptual Structures, ICCS 1996*, volume 1115 of *Lecture Notes in Computer Science*, 248–262. Springer.

Schmidt-Schauß, M., and Smolka, G. 1991. Attributive concept descriptions with complements. *Artif. Intell.* 48(1):1–26.

W3C. 2009. *OWL 2 Web Ontology Language: Document Overview*. http://www.w3.org/TR/owl2-overview/.