$\mathcal{A}_{r}\cup\bigcup_{G\in
K}\mathcal{A}_{G,\Sigma_{\mathsf{C}}}^{1}\cup\mathcal{A}_{G,\Sigma_{\mathsf{C}}}^{2}$

the assertions

  * •

$r(a_{C},(a_{G},1)),r(a_{C},(a_{G},2))$, for every $G\in K$;

  * •

$A_{1}(a_{G},1)$, for every $G\in K$;

  * •

$A_{1}(a_{E})$, for every tlc $\exists r.E$ of $C$;

  * •

$A_{2}(a_{G},2)$, for every $G\in K$.

We use $\mathcal{A}$ and the dtCQs $q_{\exists r.(A_{i}\sqcap D)}$ to show
that $(\mathcal{T},\Sigma_{\mathsf{C}})$ is not convex for dtCQs. The proof
that $\mathcal{A}\models(\mathcal{T},\Sigma_{\mathsf{C}},q_{\exists
r.(A_{1}\sqcap D)}\vee q_{\exists r.(A_{2}\sqcap D)})(a_{C})$ is
straightforward using the condition that $\mathcal{T}\models
C\sqsubseteq\exists r.D$ and the construction of $\mathcal{A}$
($r\in\Sigma_{\mathsf{C}}$ and all $r$-successors of $a_{C}$ in $\mathcal{A}$
are either in $A_{1}$ or in $A_{2}$). It remains to show
$\mathcal{A}\not\models(\mathcal{T},\Sigma_{\mathsf{C}},q_{\exists
r.(A_{i}\sqcap D)})(a_{C})$, for $i=1,2$. For $i=2$, construct a witness
interpretation $\mathcal{J}$ showing this by expanding all
$\mathcal{A}_{G,\Sigma_{\mathsf{C}}}^{2}$, $G\in K$, to (isomorphic copies of)
$\mathcal{I}_{G}^{2}$, all $\mathcal{A}_{G,\Sigma_{\mathsf{C}}}^{1}$, $G\in
K$, to (isomorphic copies of) $\mathcal{I}_{G}^{1}$, and $\mathcal{A}_{r}$ to
$\mathcal{I}_{r}$. Using the properties of $\mathcal{I}_{G}^{1}$ and
$\mathcal{I}_{G}^{2}$ established in the claim above, it is readily checked
that $\mathcal{J}$ is a model of $\mathcal{T}$ and $\mathcal{A}$ that respects
$\Sigma_{\mathsf{C}}$. Moreover, $a_{C}\not\in(\exists r.(A_{2}\sqcap
D))^{\mathcal{J}}$ since $(a_{G},2)\not\in D^{\mathcal{J}}$ for any $G\in K$
(by the claim above).

For $i=1$, construct a witness interpretation $\mathcal{J}$ showing this by
expanding all $\mathcal{A}_{G,\Sigma_{\mathsf{C}}}^{2}$, $G\in K$, to
(isomorphic copies of) $\mathcal{I}_{G}^{1}$, all
$\mathcal{A}_{G,\Sigma_{\mathsf{C}}}^{1}$, $G\in K$, to (isomorphic copies of)
$\mathcal{I}_{G}^{2}$, and $\mathcal{A}_{r}$ to $\mathcal{I}_{r}$. Using again
the properties of $\mathcal{I}_{G}^{1}$ and $\mathcal{I}_{G}^{2}$ established
above, it can be checked that $\mathcal{J}$ is a model of $\mathcal{T}$ and
$\mathcal{A}$ that respects $\Sigma_{\mathsf{C}}$. $a_{C}\not\in(\exists
r.(A_{1}\sqcap D))^{\mathcal{J}}$ since $a_{E}\not\in D^{\mathcal{J}}$ for any
tlc $\exists r.E$ of $C$ and since $(a_{G},1)\not\in D^{\mathcal{J}}$ for any
$G\in K$ (by the claim above). This finishes the proof of Claim 2.  $\dashv$

This finishes the proof of Point (1) of Theorem 13. We now prove Part (a) of
Point (2). The proof strategy is exactly the same as in the proof for
$\text{DL-Lite}_{\mathcal{R}}$.

######  Claim 22.

Let $(\mathcal{T},\Sigma_{\mathsf{C}})$ be a safe $\mathcal{EL}$ TBox with
closed predicates. Then for every UCQ $q$, we have

$\mathcal{A}\models(\mathcal{T},\Sigma_{\mathsf{C}},q)(\vec{a})\quad\text{ iff
}\quad\mathcal{A}\models(\mathcal{T},\emptyset,q)(\vec{a})$

for all ABoxes $\mathcal{A}$ that are consistent w.r.t.
$(\mathcal{T},\Sigma_{\mathsf{C}})$ and all
$\vec{a}\in\mathsf{Ind}(\mathcal{A})$.

Proof of claim. Let $(\mathcal{T},\Sigma_{\mathsf{C}})$ be safe and assume
that $\mathcal{A}$ is consistent w.r.t. $(\mathcal{T},\Sigma_{\mathsf{C}})$.
We consider the tree-shaped canonical model
$\mathcal{J}_{\mathcal{T},\mathcal{A}}$ introduced above. It suffices to show
that $\mathcal{J}_{\mathcal{T},\mathcal{A}}$ respects $\Sigma_{\mathsf{C}}$.
To this end it suffices to prove for all $A,r\in\Sigma_{\mathsf{C}}$:

  1. (1)

for all $a\in{\sf Ind}(\mathcal{A})$, if $a\in
A^{\mathcal{J}_{\mathcal{T},\mathcal{A}}}$, then $A(a)\in\mathcal{A}$;

  2. (2)

for all $a,b\in{\sf Ind}(\mathcal{A})$, if $r(a,b)\in
r^{\mathcal{J}_{\mathcal{T},\mathcal{A}}}$, then $r(a,b)\in\mathcal{A}$;

  3. (3)

for all $a\in{\sf Ind}(\mathcal{A})$ and $C\in{\sf sub}(\mathcal{T})$, $a\cdot
r\cdot C\not\in\Delta^{\mathcal{J}_{\mathcal{T},\mathcal{A}}}$;

  4. (4)

for all
$d\in\Delta^{\mathcal{J}_{\mathcal{T},\mathcal{A}}}\setminus\mathsf{Ind}(\mathcal{A})$,
there is no $\mathcal{EL}$ concept $D$ with $d\in
D^{\mathcal{J}_{\mathcal{T},\mathcal{A}}}$ and
$\mathsf{sig}(D)\cap\Sigma_{\mathsf{C}}\neq\emptyset$.

For Item (1), assume $a\in A^{\mathcal{J}_{\mathcal{T},\mathcal{A}}}$. By
Lemma 16, $\mathcal{A}\models(\mathcal{T},\emptyset,A(x))(a)$, and so we
obtain $\mathcal{A}\models(\mathcal{T},\Sigma_{\mathsf{C}},A(x))(a)$. By
consistency of $\mathcal{A}$ w.r.t. $(\mathcal{T},\Sigma_{\mathsf{C}})$, we
then have $A(a)\in\mathcal{A}$. Item 2 follows directly from the construction
of $\mathcal{J}_{\mathcal{T},\mathcal{A}}$. For Item (3), assume for a proof
by contradiction that there are $a\in{\sf Ind}(\mathcal{A})$,
$r\in\Sigma_{\mathsf{C}}$, and a concept $C$ such that $a\cdot r\cdot
C\in\Delta^{\mathcal{J}_{\mathcal{T},\mathcal{A}}}$. By Lemma 16, we have
$\mathcal{A}\models(\mathcal{T},\emptyset,q_{\exists r.C})(a)$. By Lemma 18,
this implies that there is some $m\geq 0$ with $\mathcal{T}\models
C_{a}^{m}\sqsubseteq\exists r.C$, where $C_{a}^{m}$ is the unfolding of
$\mathcal{A}$ at $a$ of depth $m$. We show that this contradicts the
assumption that $(\mathcal{T},\Sigma_{\mathsf{C}})$ is safe. There does not
exist a tlc $\exists r.C^{\prime}$ of $C_{a}^{m}$ with $\mathcal{T}\models
C^{\prime}\sqsubseteq C$ because otherwise there is some
$b\in\mathsf{Ind}(\mathcal{A})$ with $r(a,b)\in\mathcal{A}$ and
$\mathcal{A}\models(\mathcal{T},\emptyset,q_{C})(b)$ and thus, $a\cdot r\cdot
C$ would have never been introduced by Rule (R3) in the construction of
$\mathcal{J}_{\mathcal{T},\mathcal{A}}$. Moreover, there is no $\mathcal{EL}$
concepts $E$ with ${\sf sig}(E)\subseteq\Sigma_{\mathsf{C}}$ and
$\mathcal{T}\models C_{a}^{m}\sqsubseteq\exists r.E$ and $\mathcal{T}\models
E\sqsubseteq C$ because otherwise there is a $b\in\mathsf{Ind}(\mathcal{A})$
with $r(a,b)\in\mathcal{A}$ and $\mathcal{I}_{\mathcal{A}}\models E(b)$ since
$\mathcal{A}$ is consistent w.r.t. $(\mathcal{T},\Sigma_{\mathsf{C}})$. But
then $\mathcal{A}\models(\mathcal{T},\emptyset,q_{C})(b)$ by the fact that
$\mathcal{J}_{\mathcal{T},\mathcal{A}}$ is a model of $\mathcal{T}$ and
$\mathcal{A}$. Again, in this case, $a\cdot r\cdot C$ would have never been
introduced by Rule (R3) in the construction of
$\mathcal{J}_{\mathcal{T},\mathcal{A}}$. Hence $C_{a}^{m}\sqsubseteq\exists
r.C$ witnesses that $(\mathcal{T},\Sigma_{\mathsf{C}})$ is not safe.

For Item (4), assume for a proof by contradiction that there is a
$d\in\Delta^{\mathcal{J}_{\mathcal{T},\mathcal{A}}}\setminus\mathsf{Ind}(\mathcal{A})$
and an $\mathcal{EL}$ concept $D$ such that $d\in
D^{\mathcal{J}_{\mathcal{T},\mathcal{A}}}$ and
$\mathsf{sig}(D)\cap\Sigma_{\mathsf{C}}\neq\emptyset$. By definition,
$d=a\cdot r_{0}\cdot C_{0}\cdots r_{n}\cdot C_{n}$ for some
$a\in\mathsf{Ind}(\mathcal{A})$. Let $G=C_{0}\sqcap\exists r_{1}.\exists
r_{2}\ldots\exists r_{n}.D$. Obviously,
$\mathsf{sig}(G)\cap\Sigma_{\mathsf{C}}\neq\emptyset$ and $a\cdot r_{0}\cdot
C_{0}\in G^{\mathcal{J}_{\mathcal{T},\mathcal{A}}}$. By the latter and Lemma
16, we have $\mathcal{A}\models(\mathcal{T},\emptyset,q_{\exists
r_{0}.G})(a)$. By Lemma 18, this implies that there is some $m\geq 0$ with
$\mathcal{T}\models C_{a}^{m}\sqsubseteq\exists r_{0}.G$. We show that it
follows that $(\mathcal{T},\Sigma_{\mathsf{C}})$ is not safe. We have
$\mathsf{sig}(G)\cap\Sigma_{\mathsf{C}}\neq\emptyset$ and, by Item (3),
$r_{0}\not\in\Sigma_{\mathsf{C}}$. To show that
$(\mathcal{T},\Sigma_{\mathsf{C}})$ is not safe it remains to show that there
is no tlc $\exists r_{0}.C^{\prime}$ of $C_{a}^{m}$ with $\mathcal{T}\models
C^{\prime}\sqsubseteq G$. This is indeed the case because otherwise there is
some $b\in\mathsf{Ind}(\mathcal{A})$ with $r_{0}(a,b)\in\mathcal{A}$ and
$\mathcal{A}\models(\mathcal{T},\emptyset,q_{C_{0}})(b)$ and thus, $a\cdot
r_{0}\cdot C_{0}$ would have never been introduced by Rule (R3) in the
construction of $\mathcal{J}_{\mathcal{T},\mathcal{A}}$.  $\dashv$

This finishes the proof of Part (a) of Point (2) of Theorem 13. Before we
prove Part (b) of Point (2) we show the following observation of independent
interest.

######  Claim.

If $(\mathcal{T},\Sigma_{\mathsf{C}})$ is safe, then there exists an
$\mathcal{EL}$ TBox $\mathcal{T}^{\prime}$ equivalent to $\mathcal{T}$ such
that for any $C\sqsubseteq D\in\mathcal{T}^{\prime}$, ${\sf
sig}(D)\subseteq\Sigma_{\mathsf{C}}$ or ${\sf
sig}(D)\cap\Sigma_{\mathsf{C}}=\emptyset$.

Proof of claim. We apply the following three rules exhaustively (and
recursively) to $\mathcal{T}$:

  * •

replace any $C\sqsubseteq D_{1}\sqcap D_{2}$ by $C\sqsubseteq D_{1}$ and
$C\sqsubseteq D_{2}$;

  * •

replace any $C\sqsubseteq\exists r.D$ such that there exists a tlc $\exists
r.C^{\prime}$ of $C$ with $\mathcal{T}\models C^{\prime}\sqsubseteq D$ by
$C^{\prime}\sqsubseteq D$;

  * •

replace any $C\sqsubseteq\exists r.D$ with $r\in\Sigma_{\mathsf{C}}$ and ${\sf
sig}(D)\not\subseteq\Sigma_{\mathsf{C}}$ by $C\sqsubseteq\exists r.F$ and
$F\sqsubseteq D$, where $F$ is an $\mathcal{EL}$ concepts with ${\sf
sig}(F)\subseteq\Sigma_{\mathsf{C}}$ such that $\mathcal{T}\models
C\sqsubseteq\exists r.F$ and $\mathcal{T}\models F\sqsubseteq D$. (Note that
such a concept $F$ always exists by Condition 3(s2).)

It is straightforward to show that the resulting TBox $\mathcal{T}^{\prime}$
is as required.  $\dashv$

Recall that UCQ evaluation for $\mathcal{EL}$ TBoxes without closed predicates
is in PTime. Thus, the following claim and Part (a) directly imply Part (b) of
Theorem 13.

######  Claim 23.

Let $(\mathcal{T},\Sigma_{\mathsf{C}})$ be a safe $\mathcal{EL}$ TBox with
closed predicates. Then consistency of ABoxes w.r.t.
$(\mathcal{T},\Sigma_{\mathsf{C}})$ is in PTime.

Proof of claim. We may assume that $\mathcal{T}$ is in the form of the claim
above: for all $C\sqsubseteq D\in\mathcal{T}$, ${\sf
sig}(D)\subseteq\Sigma_{\mathsf{C}}$ or ${\sf
sig}(D)\cap\Sigma_{\mathsf{C}}=\emptyset$. We show that the following
conditions are equivalent, for every ABox $\mathcal{A}$:

  1. (1)

$\mathcal{A}$ is consistent w.r.t. $(\mathcal{T},\Sigma_{\mathsf{C}})$;

  2. (2)

for all $C\sqsubseteq F\in\mathcal{T}$ with ${\sf
sig}(F)\subseteq\Sigma_{\mathsf{C}}$ and all $a\in{\sf Ind}(\mathcal{A})$, if
$\mathcal{A}\models(\mathcal{T},\emptyset,q_{F})(a)$, then
$\mathcal{I}_{\mathcal{A}}\models F(a)$.

The implication from Condition (1) to Condition (2) is obvious. Conversely,
assume that Condition (2) holds. It suffices to show that the tree-shaped
canonical model $\mathcal{J}_{\mathcal{T},\mathcal{A}}$ respects closed
predicates $\Sigma_{\mathsf{C}}$. One can readily check that the proofs of
Points (2) and (4) of Claim 3 above do not use the condition that
$\mathcal{A}$ is consistent w.r.t. $(\mathcal{T},\Sigma_{\mathsf{C}})$. Thus,
it suffices to prove that Points (1) and (3) of Claim 3 hold for
$\mathcal{J}_{\mathcal{T},\mathcal{A}}$. But they follow directly from
Condition (2) and the construction of $\mathcal{J}_{\mathcal{T},\mathcal{A}}$.

Claim 4 now follows from the fact that Condition (2) can be checked in
polynomial time in the size of $\mathcal{A}$.  $\dashv$

This finishes the proof of Theorem 13.

##  6\. Quantified Query Case: Deciding Tractability of PTime Query Evaluation

We consider the meta problem to decide whether query evaluation w.r.t. a TBox
with closed predicates is tractable. We show that the following problems are
in PTime:

  1. (1)

decide whether UCQ evaluation w.r.t. $\text{DL-Lite}_{\mathcal{R}}$ TBoxes
with closed predicates is FO-rewritable (equivalently, in PTime); and

  2. (2)

decide whether UCQ evaluation w.r.t. $\mathcal{EL}$ TBoxes with closed
predicates is in PTime.

In both cases, we use the characterization via safeness given in the previous
section and show that safeness can be decided in PTime. For $\text{DL-
Lite}_{\mathcal{R}}$, the proof is actually straightforward: to check safeness
of a $\text{DL-Lite}_{\mathcal{R}}$ TBox with closed predicates
$(\mathcal{T},\Sigma_{\mathsf{C}})$ it suffices to consider all basic concepts
$B_{1},B_{2}$ and roles $r$ from ${\sf sig}(\mathcal{T})$ (of which there are
only polynomially many) and make satisfiability checks for basic concepts
w.r.t. $\text{DL-Lite}_{\mathcal{R}}$ TBoxes and entailment checks of
$\text{DL-Lite}_{\text{core}}$ CIs and RIs by $\text{DL-Lite}_{\mathcal{R}}$
TBoxes according to the definition of safeness. Both can be done in polynomial
time [18].

######  Theorem 24.

It is in PTime to decide whether a $\text{DL-Lite}_{\mathcal{R}}$ TBox with
closed predicates is safe.

Such a straightforward argument does not work for $\mathcal{EL}$ TBoxes since
Definition 5.3 quantifies over all $\mathcal{EL}$ concepts $C$, $D$, and $E$,
of which there are infinitely many. In the following, we show that,
nevertheless, safeness of an $\mathcal{EL}$ TBox with closed predicates
$(\mathcal{T},\Sigma_{\mathsf{C}})$ can be decided in PTime. The first step of
the proof is to convert $\mathcal{T}$ into a _reduced_ $\mathcal{EL}$ TBox
$\mathcal{T}^{*}$ with the following properties:

  1. (red1)

$\mathcal{T}^{*}$ contains no CI of the form $C\sqsubseteq D_{1}\sqcap D_{2}$;

  2. (red2)

if $C\sqsubseteq\exists r.D\in\mathcal{T}^{*}$, then there is no tlc $\exists
r.C^{\prime}$ of $C$ with $\mathcal{T}^{*}\models C^{\prime}\sqsubseteq D$.

######  Lemma 25.

For every $\mathcal{EL}$ TBox, one can compute in polynomial time an
equivalent reduced $\mathcal{EL}$ TBox.

######  Proof 6.1.

Assume that $\mathcal{T}$ is an $\mathcal{EL}$ TBox. Compute $\mathcal{T}^{*}$
by applying the following two rules exhaustively to $\mathcal{T}$:

  * •

replace any CI $C\sqsubseteq D_{1}\sqcap D_{2}$ with the CIs $C\sqsubseteq
D_{1}$ and $C\sqsubseteq D_{2}$;

  * •

replace any CI $C\sqsubseteq\exists r.D$ for which there exists a tlc $\exists
r.C^{\prime}$ of $C$ with $\mathcal{T}\models C^{\prime}\sqsubseteq D$ by
$C^{\prime}\sqsubseteq D$.

It is straightforward to prove that $\mathcal{T}^{\ast}$ is reduced,
equivalent to $\mathcal{T}$, and is constructed in polynomial time (using the
fact that checking $\mathcal{T}\models C\sqsubseteq D$ is in PTime [6]).

We now formulate a stronger version of safeness. While Definition 5.3
quantifies over all CIs $C\sqsubseteq\exists r.D$ that are _entailed_ by the
TBox $\mathcal{T}$, the stronger version only considers CIs of this form that
are _contained_ in $\mathcal{T}$. For deciding tractability based on safeness,
this is clearly a drastic improvement since only the concept $E$ from
Definition 5.3 remains universally quantified. An $\mathcal{EL}$ TBox with
closed predicates $(\mathcal{T},\Sigma_{\mathsf{C}})$ is _strongly safe_ if
there exists no $\mathcal{EL}$ CI $C\sqsubseteq\exists r.D\in\mathcal{T}$ such
that one of the following holds:

  1. (st1)

$r\not\in\Sigma_{\mathsf{C}}$ and there is some $\mathcal{EL}$ concept $E$
such that $\mathcal{T}\models D\sqsubseteq E$ and ${\sf
sig}(E)\cap\Sigma_{\mathsf{C}}\not=\emptyset$;

  2. (st2)

$r\in\Sigma_{\mathsf{C}}$, ${\sf sig}(D)\not\subseteq\Sigma_{\mathsf{C}}$, and
there is no $\mathcal{EL}$ concept $E$ with ${\sf
sig}(E)\subseteq\Sigma_{\mathsf{C}}$ such that $\mathcal{T}\models
C\sqsubseteq\exists r.E$ and $\mathcal{T}\models E\sqsubseteq D$.

The crucial observation is that, for $\mathcal{EL}$ TBoxes in reduced form,
the original notion of safeness can be replaced by strong safeness.

######  Lemma 26.

If $\mathcal{T}$ a reduced $\mathcal{EL}$ TBox and $\Sigma_{\mathsf{C}}$ a
signature, then $(\mathcal{T},\Sigma_{\mathsf{C}})$ is safe iff it is strongly
safe.

######  Proof 6.2.

Suppose that $\mathcal{T}$ satisfies Conditions (red1) and (red2) for reduced
$\mathcal{EL}$ TBoxes.

$(\Rightarrow)$ Suppose that $(\mathcal{T},\Sigma_{\mathsf{C}})$ is not
strongly safe, that is, there is some $C\sqsubseteq\exists r.D\in\mathcal{T}$
satisfying (st1) or (st2). If $C\sqsubseteq\exists r.D$ satisfies Condition
(st1), then $r\not\in\Sigma_{\mathsf{C}}$ and there is some concept $E$ such
that $\mathcal{T}\models D\sqsubseteq E$ and ${\sf
sig}(E)\cap\Sigma_{\mathsf{C}}\not=\emptyset$. We show that
$(\mathcal{T},\Sigma_{\mathsf{C}})$ is not safe because the CI
$C\sqsubseteq\exists r.(D\sqcap E)$ violates safeness:

  1. (1)

$\mathcal{T}\models C\sqsubseteq\exists r.(D\sqcap E)$ since
$C\sqsubseteq\exists r.D\in\mathcal{T}$ and $\mathcal{T}\models D\sqsubseteq
E$.

  2. (2)

there is no tlc $\exists r.C^{\prime}$ of $C$ with $\mathcal{T}\models
C^{\prime}\sqsubseteq D\sqcap E$; this follows from Condition (red2).

  3. (3)

Condition 3(s1) is satisfied because $r\notin\Sigma_{\mathsf{C}}$ and
$\mathsf{sig}(D\sqcap E)\cap\Sigma_{\mathsf{C}}\neq\emptyset$ since
$\mathsf{sig}(E)\cap\Sigma_{\mathsf{C}}\neq\emptyset$.

If $C\sqsubseteq\exists r.D$ satisfies Condition (st2), then it follows
directly that $(\mathcal{T},\Sigma_{\mathsf{C}})$ is not safe because
$C\sqsubseteq\exists r.D$ satisfies Condition 3(s2).

($\Leftarrow$) Suppose that $(\mathcal{T},\Sigma_{\mathsf{C}})$ is not safe.
Take any $\mathcal{EL}$ CI $C\sqsubseteq\exists r.D$ violating safeness. In
the following, we use the tree-shaped canonical model
$\mathcal{J}_{\mathcal{T},C}$ defined above. For the sake of readability
denote the individual name $p$ of $\mathcal{J}_{\mathcal{T},C}$ by $a_{p}$ (in
particular, $a_{C}$ denotes $C$). Note that Lemma 17 yields $a_{C}\in(\exists
r.D)^{\mathcal{J}_{\mathcal{T},C}}$ since $\mathcal{T}\models
C\sqsubseteq\exists r.D$. Thus there is some
$d\in\Delta^{\mathcal{J}_{\mathcal{T},C}}$ such that $(a_{C},d)\in
r^{\mathcal{J}_{\mathcal{T},C}}$ and $d\in D^{\mathcal{J}_{\mathcal{T},C}}$.
By definition of $\mathcal{J}_{\mathcal{T},C}$, $d=a_{C\cdot r\cdot E}$ for
some $\mathcal{EL}$ concept $E$. By Lemma 17 and $d\in
D^{\mathcal{J}_{\mathcal{T},C}}$, we have $\mathcal{T}\models E\sqsubseteq D$.

Let $\mathcal{A}_{C}=\mathcal{A}_{0},\mathcal{A}_{1},\dots$ be the ABoxes used
in the construction of $\mathcal{J}_{\mathcal{T},C}$. By definition of
$\mathcal{A}_{C}$ and Condition (red2), we have $C\cdot r\cdot
E\not\in\mathsf{paths}(C)$, that is, $d=a_{C\cdot r\cdot E}$ must have been
generated by (R3). Consequently, there is an $i\in\mathbb{N}$ such that
$\exists r.E(a_{C})\in\mathcal{A}_{i}$, and
$\mathcal{A}_{i+1}=\mathcal{A}_{i}\cup\\{r(a_{C},a_{C\cdot r\cdot
E}),E(a_{C\cdot r\cdot E})\\}$. Using Condition (red1) one can now easily
prove that $\exists r.E(a_{C})$ can only have been added due to an application
of (R2).

Thus, there is some $C^{\prime}\sqsubseteq\exists r.E\in\mathcal{T}$ with
$\mathcal{I}_{\mathcal{A}_{j}}\models C^{\prime}(a_{C})$. We obtain
$a_{C}\in(C^{\prime})^{\mathcal{J}_{\mathcal{T},C}}$ and this implies, by
Lemma 17, that $\mathcal{T}\models C\sqsubseteq C^{\prime}$. As
$(\mathcal{T},\Sigma_{\mathsf{C}})$ is not safe due to the CI
$C\sqsubseteq\exists r.D$, we obtain one of the following cases:

  * •

$C\sqsubseteq\exists r.D$ satisfies Condition 3(s1). Then
$r\not\in\Sigma_{\mathsf{C}}$ and
$\mathsf{sig}(D)\cap\Sigma_{\mathsf{C}}\neq\emptyset$. Since
$\mathcal{T}\models E\sqsubseteq D$, we thus have that
$C^{\prime}\sqsubseteq\exists r.E\in\mathcal{T}$ satisfies Condition (st1). We
have shown that $\mathcal{T}$ is not strongly safe.

  * •

$C\sqsubseteq\exists r.D$ satisfies Condition 3(s2). Then
$r\in\Sigma_{\mathsf{C}}$, $\mathsf{sig}(D)\not\subseteq\Sigma_{\mathsf{C}}$,
and there is no $\mathcal{EL}$ concept $F$ with ${\sf
sig}(F)\subseteq\Sigma_{\mathsf{C}}$ and $\mathcal{T}\models
C\sqsubseteq\exists r.F$ and $\mathcal{T}\models F\sqsubseteq D$. We aim at
showing that $C^{\prime}\sqsubseteq\exists r.E\in\mathcal{T}$ satisfies
Condition (st2). We already know that $r\in\Sigma_{\mathsf{C}}$. From
$\mathcal{T}\models C\sqsubseteq C^{\prime}\sqsubseteq\exists r.E$ and
$\mathcal{T}\models E\sqsubseteq D$, we obtain
$\mathsf{sig}(E)\not\subseteq\Sigma_{\mathsf{C}}$ (otherwise set $F:=E$ above
to derive a contradiction). We also obtain that there is no $\mathcal{EL}$
concept $F$ with ${\sf sig}(F)\subseteq\Sigma_{\mathsf{C}}$ and with
$\mathcal{T}\models C^{\prime}\sqsubseteq\exists r.F$ and $\mathcal{T}\models
F\sqsubseteq E$. Again it follows that $\mathcal{T}$ is not strongly safe.

######  Lemma 27.

It is in PTime to decide whether a reduced $\mathcal{EL}$ TBox with closed
predicates is strongly safe.

######  Proof 6.3.

Assume $(\mathcal{T},\Sigma_{\mathsf{C}})$ is a reduced $\mathcal{EL}$ TBox
with closed predicates. Assume $C\sqsubseteq\exists r.D\in\mathcal{T}$ is
given. It suffices to show that Conditions (st1) and (st2) can be checked in
polynomial time. For Condition (st1), it suffices to show that one can check
in polynomial time whether there exists an $\mathcal{EL}$ concept $E$ with
$\mathcal{T}\models D\sqsubseteq E$ and ${\sf
sig}(E)\cap\Sigma_{\mathsf{C}}\not=\emptyset$. We reduce this to a
reachability problem in the directed graph induced by the finite canonical
model $\mathcal{I}_{\mathcal{T},D}$. In detail, let $G=(V,R)$ be the directed
graph with $V=\Delta^{\mathcal{I}_{\mathcal{T},D}}$ and $R=\bigcup_{r\in{\sf
N_{R}}}r^{\mathcal{I}_{\mathcal{T},D}}$. Let
$T=\bigcup_{A\in\Sigma_{\mathsf{C}}}A^{\mathcal{I}_{\mathcal{T},D}}\cup\bigcup_{r\in\Sigma_{\mathsf{C}}}(\exists
r)^{\mathcal{I}_{\mathcal{T},D}}$. Using Lemma 14, it is readily checked that
there exists an $\mathcal{EL}$ concept $E$ with $\mathcal{T}\models
D\sqsubseteq E$ and ${\sf sig}(E)\cap\Sigma_{\mathsf{C}}\not=\emptyset$ iff
there exists a path from $a_{D}$ to a node in $T$ in $G$. The latter
reachability problem can be checked in polynomial time.

For Condition (st2), assume $r\in\Sigma_{\mathsf{C}}$ and let $\mathcal{A}$
denote the ABox corresponding to the $\Sigma$-reduct of
$\mathcal{I}_{\mathcal{T},C}$. We show that the following conditions are
equivalent:

  1. (1)

there exists an $\mathcal{EL}$ concept $E$ such that ${\sf
sig}(E)\subseteq\Sigma_{\mathsf{C}}$, $\mathcal{T}\models C\sqsubseteq\exists
r.E$ and $\mathcal{T}\models E\sqsubseteq D$;

  2. (2)

there exists $a\in{\sf Ind}(\mathcal{A})$ such that $(a_{C},a)\in
r^{\mathcal{I}_{\mathcal{T},C}}$ and
$\mathcal{A}\models(\mathcal{T},\emptyset,q_{D})(a)$.

For the proof of the implication from (1) to (2) take an $\mathcal{EL}$
concept $E$ satisfying (1). Then $a_{C}\in(\exists
r.E)^{\mathcal{I}_{\mathcal{T},C}}$, by Lemma 14. Then there exists $a\in{\sf
Ind}(\mathcal{A})$ such that $(a_{C},a)\in r^{\mathcal{I}_{\mathcal{T},C}}$
and $a\in E^{\mathcal{I}_{\mathcal{T},C}}$. Hence $a\in
E^{\mathcal{I}_{\mathcal{A}}}$ as ${\sf sig}(E)\subseteq\Sigma_{\mathsf{C}}$.
There is an unfolding $C_{a}^{m}$ of $\mathcal{A}$ at $a$ of depth $m$ such
that $\emptyset\models C_{a}^{m}\sqsubseteq E$. From $\mathcal{T}\models
E\sqsubseteq D$ we obtain $\mathcal{T}\models C_{a}^{m}\sqsubseteq D$. But
then, by Lemma 18, $\mathcal{A}\models(\mathcal{T},\emptyset,q_{D})(a)$, as
required.

Conversely, let $a\in{\sf Ind}(\mathcal{A})$ such that $(a_{C},a)\in
r^{\mathcal{I}_{\mathcal{T},C}}$ and
$\mathcal{A}\models(\mathcal{T},\emptyset,q_{D})(a)$. By Lemma 18, there
exists an unfolding $C_{a}^{m}$ of $\mathcal{A}$ at $a$ such that
$\mathcal{T}\models C_{a}^{m}\sqsubseteq D$. It is readily checked that
$E=C_{d}^{m}$ is as required for Condition (1).

Condition (2) can be checked in PTime since query evaluaton for OMQCs in
$(\mathcal{EL},\emptyset,\text{dtCQ})$ is in PTime (in combined complexity).

######  Theorem 28.

It is in PTime to decide whether an $\mathcal{EL}$ TBox with closed predicates
is safe.

######  Proof 6.4.

Assume $(\mathcal{T},\Sigma_{\mathsf{C}})$ is given. By Lemma 25, we can
construct, in polynomial time, a reduced $\mathcal{EL}$ TBox
$\mathcal{T}^{\prime}$ equivalent to $\mathcal{T}$. By Lemma 27, we can check
in PTime whether $(\mathcal{T}^{\prime},\Sigma_{\mathsf{C}})$ is strongly
safe. By Lemma 26, strong safeness is equivalent to safeness for
$(\mathcal{T}^{\prime},\Sigma_{\mathsf{C}})$.

##  7\. Closing Concept Names in the Fixed Query Case and Surjective CSPs

We now switch from the quantified query case to the fixed query case. In this
section, we consider OMQC languages that only allow to close concept names
while the case of closing role names is deferred to the subsequent section.
Regarding the former, our main aim is to establish a close connection between
UCQ evaluation for such OMQC languages and surjective constraint satisfaction
problems (surjective CSPs). Let BUtCQ denotes the class of Boolean queries
that can be obtained from a union of tCQs by existentially quantifying the
answer variable and let BAQ denote the class of _Boolean atomic queries_ which
take the form $\exists xA(x)$, $A$ a concept name. Then our results imply that
a PTime/coNP dichotomy for the OMQC language $(\text{DL-
Lite}_{\text{core}},{\sf N_{C}},\text{BUtCQ})$ or $(\mathcal{EL},{\sf
N_{C}},\text{BAQ})$ would imply a PTime/coNP dichotomy for surjective CSPs, a
problem that is wide open. In fact, understanding the complexity of surjective
CSPs is a very difficult, ongoing research effort. As pointed out in the
introduction, there are even concrete surjective CSPs whose complexity is
unknown and, via the established connection, these problems can be used to
derive concrete OMQCs from $(\text{DL-Lite}_{\text{core}},{\sf
N_{C}},\text{BUtCQ})$ and $(\mathcal{EL},{\sf N_{C}},\text{BAQ})$ whose
computational properties are currently not understood.

We next introduce CSPs and then give a more detailed overview of the results
obtained in this section. An interpretation $\mathcal{I}$ is a _$\Sigma$
-interpretation_ if it only interprets predicates in $\Sigma$, that is, all
other predicates are interpreted as empty. For every finite
$\Sigma$-interpretation $\mathcal{I}$ we denote by $\mathsf{CSP}(\mathcal{I})$
the following _constraint satisfaction problem (in signature $\Sigma$)_: given
a finite $\Sigma$-interpretation $\mathcal{J}$, decide whether there is a
homomorphism $h$ from $\mathcal{J}$ to $\mathcal{I}$. The _surjective
constraint satisfaction problem_ , $\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$,
is the variant of $\mathsf{CSP}(\mathcal{I})$ where we require $h$ to be
surjective. $\mathcal{I}$ is then called the _template_ of
$\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$. In this paper we only consider
CSPs with predicates of arity at most two.

In the remainder of this section, we first show that for every
$\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$, there is an OMQC $Q$ from
$(\text{DL-Lite}_{\text{core}},{\sf N_{C}},\text{BUtCQ})$ such that the
evaluation problem for $Q$ has the same complexity as the complement of
$\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$, up to polynomial time reductions.
We then observe that the same holds for $(\mathcal{EL},{\sf
N_{C}},\text{BAQ})$. For the converse direction, we construct, for every OMQC
in $(\mathcal{ALCHI},{\sf N_{C}},\text{BUtCQ})$, a _generalized_ surjective
constraint satisfaction problem of the same complexity, up to polynomial
reductions. A _generalized surjective CSP in signature $\Sigma$_ is
characterized by a _finite set_ $\Gamma$ of finite $\Sigma$-interpretations
instead of a single such interpretation, denoted
$\mathsf{CSP}(\Gamma)^{\mathsf{sur}}$. The problem is to decide, given a
$\Sigma$-interpretation $\mathcal{J}$, whether there is a surjective
homomorphism from $\mathcal{J}$ to some interpretation in $\Gamma$. The
interpretations $\mathcal{I}$ in $\Gamma$ are called the _templates_ of
$\mathsf{CSP}(\Gamma)^{\mathsf{sur}}$. Note that, in the non-surjective case,
every generalized CSP can be translated into an equivalent non-generalized CSP
[26]. In the surjective case, such a translation is not known, so there
remains a gap in our analysis. Closing this gap is primarily a CSP question
rather than a question about ontology-mediated query answering.

Consider $\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$ in signature $\Sigma$. Let
$A$, $V$, and $V_{d}$, $d\in\Delta^{\mathcal{I}}$, be concept names not in
$\Sigma$, and ${\sf val}$, ${\sf aux}_{d}$, and ${\sf force}_{d}$,
$d\in\Delta^{\mathcal{I}}$, be role names not in $\Sigma$. Define the OMQC
$Q=(\mathcal{T},\Sigma_{\mathsf{A}},\Sigma_{\mathsf{C}},q)$ from $(\text{DL-
Lite}_{\text{core}},{\sf N_{C}},\text{BUtCQ})$ as follows:

$\begin{array}[]{rcl}\mathcal{T}&=&\\{A\sqsubseteq\exists\mathsf{val},\
\exists\mathsf{val}^{-}\sqsubseteq V\\}\,\cup\\\\[2.84526pt]
&&\\{A\sqsubseteq\exists\mathsf{aux}_{d},\
\exists\mathsf{aux}_{d}^{-}\sqsubseteq V\sqcap V_{d}\mid
d\in\Delta^{\mathcal{I}}\\}\,\cup\\\\[2.84526pt]
&&\\{A\sqsubseteq\exists\mathsf{force}_{d},\
\exists\mathsf{force}^{-}_{d}\sqsubseteq A\mid
d\in\Delta^{\mathcal{I}}\\}\\\\[5.69054pt]
\Sigma_{\mathsf{C}}&=&\\{A,V\\}\cup\\{V_{d}\mid
d\in\Delta^{\mathcal{I}}\\}\\\\[5.69054pt]
\Sigma_{\mathsf{A}}&=&\Sigma\cup\Sigma_{\mathsf{C}}\\\\[5.69054pt]
q&=&q_{1}\lor q_{2}\lor q_{3}\lor q_{4}\end{array}$

where

$\begin{array}[]{r@{\,}c@{\,}l}q_{1}&=&\,\,\,\,\displaystyle\bigvee_{d,d^{\prime}\in\Delta^{\mathcal{I}}\mid
d\neq d^{\prime}}\exists x\exists y_{1}\exists
y_{2}\,A(x)\wedge\mathsf{val}(x,y_{1})\;\wedge\\\\[-8.53581pt] &&\hskip
91.04872pt\mathsf{val}(x,y_{2})\wedge V_{d}(y_{1})\wedge
V_{d^{\prime}}(y_{2})\\\\[2.84526pt]
q_{2}&=&\displaystyle\bigvee_{d\in\Delta^{\mathcal{I}},E\in\Sigma\mid d\not\in
E^{\mathcal{I}}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\exists x\exists
y\,A(x)\wedge E(x)\;\wedge\\\\[-8.53581pt] &&\hskip
91.04872pt\mathsf{val}(x,y)\wedge V_{d}(y)\\\\[2.84526pt]
q_{3}&=&\\!\\!\\!\\!\\!\displaystyle\bigvee_{d,d^{\prime}\in\Delta^{\mathcal{I}},r\in\Sigma\mid(d,d^{\prime})\notin
r^{\mathcal{I}}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\exists x\exists y\exists
x_{1}\exists y_{1}\,A(x)\wedge A(y)\wedge r(x,y)\;\wedge\\\\[-8.53581pt]
&&\hskip
91.04872pt\mathsf{val}(x,x_{1})\wedge\mathsf{val}(y,y_{1})\;\wedge\\\\[4.2679pt]
&&\hskip 91.04872ptV_{d}(x_{1})\wedge V_{d^{\prime}}(y_{1})\\\\[2.84526pt]
q_{4}&=&\,\,\,\,\displaystyle\bigvee_{d,d^{\prime}\in\Delta^{\mathcal{I}}\mid
d\neq d^{\prime}}\exists x\exists y\exists
z\,A(x)\wedge\mathsf{force}_{d}(z,x)\;\wedge\\\\[-8.53581pt] &&\hskip
91.04872pt\mathsf{val}(x,y)\wedge V_{d^{\prime}}(y).\end{array}$

The following lemma links $\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$ to the
constructed OMQC $Q$.

######  Lemma 29.

The complement of $\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$ and the
evaluation problem for $Q$ are polynomially reducible to each other.

######  Proof 7.1.

Assume that $\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$ is given. For the
polynomial reduction of $\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$ to the
evaluation problem for $Q$, let $\mathcal{J}$ be a $\Sigma$-interpretation
that is an input of $\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$. Let
$\mathcal{A}_{\mathcal{J}}$ be the ABox corresponding to $\mathcal{J}$.
Introduce, for every $d\in\Delta^{\mathcal{I}}$, a fresh individual name
$a_{d}$ and let the ABox $\mathcal{A}$ be defined as

$\mathcal{A}_{\mathcal{J}}\cup\\{A(d)\mid
d\in\Delta^{\mathcal{J}}\\}\cup\\{V(a_{d}),V_{d}(a_{d})\mid
d\in\Delta^{\mathcal{I}}\\}.$

Obviously, $\mathcal{A}$ can be constructed in polynomial time. We claim that
$\mathcal{J}\in\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$ iff
$\mathcal{A}\not\models Q$.

$(\Rightarrow)$ Suppose that there is a surjective homomorphism $h$ from
$\mathcal{J}$ to $\mathcal{I}$. Define the interpretation
$\mathcal{I}^{\prime}$ as follows:

$\displaystyle\Delta^{\mathcal{I}^{\prime}}$ $\displaystyle=$
$\displaystyle\mathsf{Ind}(\mathcal{A})$ $\displaystyle
A^{\mathcal{I}^{\prime}}$ $\displaystyle=$
$\displaystyle\mathsf{Ind}(\mathcal{A}_{\mathcal{J}})$ $\displaystyle
V^{\mathcal{I}^{\prime}}$ $\displaystyle=$ $\displaystyle\Delta^{\mathcal{I}}$
$\displaystyle V_{d}^{\mathcal{I}^{\prime}}$ $\displaystyle=$
$\displaystyle\\{a_{d}\\},\text{ for all }d\in\Delta^{\mathcal{I}}$
$\displaystyle\mathsf{val}^{\mathcal{I}^{\prime}}$ $\displaystyle=$
$\displaystyle\\{(a,a_{h(a)})\mid
a\in\mathsf{Ind}(\mathcal{A}_{\mathcal{J}})\\}$
$\displaystyle\mathsf{aux}_{d}^{\mathcal{I}^{\prime}}$ $\displaystyle=$
$\displaystyle\\{(a,a_{d})\mid
a\in\mathsf{Ind}(\mathcal{A}_{\mathcal{J}})\\}\text{, for all
}d\in\Delta^{\mathcal{I}}$
$\displaystyle\mathsf{force}_{d}^{\mathcal{I}^{\prime}}$ $\displaystyle=$
$\displaystyle\\{(a,a^{\prime})\in\mathsf{Ind}(\mathcal{A}_{\mathcal{J}})\times\mathsf{Ind}(\mathcal{A}_{\mathcal{J}})\mid
h(a^{\prime})=d\\}$ $\displaystyle P^{\mathcal{I}^{\prime}}$ $\displaystyle=$
$\displaystyle P^{\mathcal{J}}\text{, for all predicates $P$ not in }$
$\displaystyle(\\{A,V,\mathsf{val}\\}\cup\\{V_{d},\mathsf{aux}_{d},\mathsf{force}_{d}\mid
d\in\Delta^{\mathcal{I}}\\})$

One can now verify that $\mathcal{I}^{\prime}$ is a model of $\mathcal{T}$ and
$\mathcal{A}$ that respects closed predicates $\Sigma_{\mathsf{C}}$, and that
$\mathcal{I}^{\prime}\not\models q$. Thus, $\mathcal{A}\not\models Q$, as
required.

$(\Leftarrow)$ Suppose $\mathcal{A}\not\models Q$. Then there is a model
$\mathcal{I}^{\prime}$ of $\mathcal{T}$ and $\mathcal{A}$ that respects closed
predicates $\Sigma_{\mathsf{C}}$ and such that
$\mathcal{I}^{\prime}\not\models q$. Define
$h=\\{(d,a_{e})\in\mathsf{val}^{\mathcal{I}^{\prime}}\mid
d\in\Delta^{\mathcal{J}}\\}$. We show that $h$ is a surjective homomorphism
from $\mathcal{J}$ to $\mathcal{I}$.

We first show that the relation $h$ is a function. Assume that this is not the
case, that is, there are $d\in\Delta^{\mathcal{J}}$ and
$e_{1},e_{2}\in\Delta^{\mathcal{I}}$ such that $e_{1}\neq e_{2}$ and
$(d,a_{e_{i}})\in\mathsf{val}^{\mathcal{I}^{\prime}}$ for $i\in\\{1,2\\}$.
Note that $a_{e_{i}}\in V_{e_{i}}^{\mathcal{I}^{\prime}}$. Thus we get
$\mathcal{I}^{\prime}\models q_{1}$, which is a contradiction against our
choice of $\mathcal{I}^{\prime}$.

To show that $h$ is total, take some $d\in\Delta^{\mathcal{J}}$. Then $d\in
A^{\mathcal{I}^{\prime}}$ and thus the first line of $\mathcal{T}$ yields an
$f\in V^{\mathcal{J}}$ with $(d,f)\in\mathsf{val}^{\mathcal{I}^{\prime}}$.
Since $V$ is closed, we must have $f=a_{e}$ for some $e$, and thus
$h(a_{e})=f$.

We show that $h$ is a homomorphism. We show, using $q_{3}$, that $h$ preserves
role names. Using $q_{2}$, one can show in the same way that $h$ preserves
concept names. Assume for a contradiction that there is $(d,e)\in
r^{\mathcal{J}}$ with $(h(d),h(e))\not\in r^{\mathcal{I}}$. The latter implies
that the following is a disjunct of $q_{3}$:

$\begin{array}[]{l}\exists x\exists y\exists x_{1}\exists y_{1}\,A(x)\wedge
A(y)\wedge r(x,y)\wedge\mathsf{val}(x,x_{1})\;\wedge\\\\[2.84526pt] \hskip
56.9055pt\mathsf{val}(y,y_{1})\wedge V_{h(d)}(x_{1})\wedge
V_{h(e)}(y_{1}).\end{array}$

Note that $d,e\in A^{\mathcal{I}^{\prime}}$,
$(d,a_{h(a)}),(e,a_{h(e)})\in\mathsf{val}^{\mathcal{I}^{\prime}}$,
$a_{h(d)}\in V^{\mathcal{I}^{\prime}}_{h(d)}$, and $a_{h(e)}\in
V^{\mathcal{I}^{\prime}}_{h(e)}$. Thus $\mathcal{I}^{\prime}\models q_{3}$,
which contradicts our choice of $\mathcal{I}^{\prime}$.

It remains to show that $h$ is surjective. Fix a $d\in\Delta^{\mathcal{I}}$.
We have to show that there is an $e\in\Delta^{\mathcal{J}}$ with $h(e)=d$.
Take some $f\in\Delta^{\mathcal{J}}$. Then by the third line of $\mathcal{T}$
and since $A$ is closed, there is some $e\in\Delta^{\mathcal{J}}$ such that
$(f,e)\in\mathsf{force}_{d}^{\mathcal{I}^{\prime}}$. We show that $e$ is as
required. Assume to the contrary that $h(e)\neq d$. Then the following is a
disjunct of $q_{4}$:

$A(x)\wedge\mathsf{force}_{d}(z,x)\wedge\mathsf{val}(x,y)\wedge V_{h(e)}(y).$

Note that $f\in A^{\mathcal{I}^{\prime}}$,
$(e,a_{h(e)})\in\mathsf{val}^{\mathcal{I}^{\prime}}$, and $a_{h(e)}\in
V_{h(e)}^{\mathcal{I}^{\prime}}$. Thus, $\mathcal{I}^{\prime}\models q_{4}$
which contradicts our choice of $\mathcal{I}^{\prime}$. This finishes the
proof of the reduction from $\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$ to
evaluating $Q$.

We now give the polynomial reduction of the evaluation problem for $Q$ to
$\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$. Assume a
$\Sigma_{\mathsf{A}}$-ABox $\mathcal{A}$ is given. To decide whether
$\mathcal{A}\models Q$, we start with the following:

  1. (1)

If $\mathcal{A}$ does not contain any assertion of the form $A(a)$, then
$\mathcal{A}\not\models Q$. In fact, let $\mathcal{I}_{\mathcal{A}}$ be
$\mathcal{A}$ viewed as an interpretation. Then $\mathcal{I}_{\mathcal{A}}$ is
a model of $\mathcal{A}$ that respects closed predicates
$\Sigma_{\mathsf{C}}$. Since $\mathcal{A}$ does not contain any assertion of
the form $A(a)$, $\mathcal{I}_{\mathcal{A}}$ is also a model of $\mathcal{T}$
and satisfies $\mathcal{I}_{\mathcal{A}}\not\models q$ (note that each
disjunct of $q$ demands the existence of an instance of $A$). Thus answer
‘$\mathcal{A}\not\models Q$’.

  2. (2)

Otherwise, if $\mathcal{A}$ does not contain for each
$d\in\Delta^{\mathcal{I}}$ an individual name $a$ with
$V(a),V_{d}(a)\in\mathcal{A}$, then $\mathcal{A}$ is not consistent w.r.t.
$(\mathcal{T},\Sigma_{\mathsf{C}})$. Thus answer ‘$\mathcal{A}\models Q$’.

  3. (3)

Otherwise, if $\mathcal{A}$ contains for each $d\in\Delta^{\mathcal{I}}$ an
individual name $a$ with $V(a)\in\mathcal{A}$ and
$V_{d}(a)\not\in\mathcal{A}$, then $\mathcal{A}\models Q$ iff
$\mathcal{I}_{\mathcal{A}}\models q$. In fact, Line 1 of $\mathcal{T}$ can be
satisfied by linking every element to $a$ via $\mathsf{val}$; Line 2 can be
satisfied since Case (2) above does not apply; Line 3 can be satisfied since
Case (1) above does not apply. If an interpretation $\mathcal{I}$ is built in
this way (taking all remaining choices in an arbitrary way), then it can be
easily verified that $\mathcal{A}\models Q$ iff $\mathcal{I}\models q$ iff
$\mathcal{I}_{\mathcal{A}}\models q$. Thus check in polynomial time whether
$\mathcal{I}_{\mathcal{A}}\models q$ and answer accordingly.

If none of the above applies, let $\mathcal{A}_{|A}$ be the restriction of
$\mathcal{A}$ to $\\{a\in{\sf Ind}(\mathcal{A})\mid A(a)\in\mathcal{A}\\}$.
Since Case (1) above does not apply, $\mathcal{A}_{|A}$ is non-empty. Let
$\mathcal{J}_{A}$ be the $\Sigma$-reduct of the interpretation corresponding
to $\mathcal{A}_{|A}$. We show that
$\mathcal{J}_{A}\in\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$ iff
$\mathcal{A}\not\models Q$.

$(\Leftarrow)$. Assume that $\mathcal{A}\not\models Q$. Then there is a model
$\mathcal{J}$ of $\mathcal{T}$ and $\mathcal{A}$ that respects closed
predicates $\Sigma_{\mathsf{C}}$ and such that $\mathcal{J}\not\models q$. By
the first line of $\mathcal{T}$, since $V$ is closed, Case (3) does not apply,
and by $q_{1}$, for each $a\in\mathsf{Ind}(\mathcal{A}_{|A})$ there is exactly
one $d\in\Delta^{\mathcal{I}}$ such that
$a\in(\exists\mathsf{val}.V_{d})^{\mathcal{J}}$. Define a homomorphism
$h:\mathcal{J}_{A}\rightarrow\mathcal{I}$ by mapping each $a$ in
$\mathcal{A}_{|A}$ to the value $d\in\Delta^{\mathcal{I}}$ thus determined. By
$q_{2}$ and $q_{3}$, $h$ is indeed a homomorphism. By the third line of
$\mathcal{T}$ and $q_{4}$ and since $A$ is closed, $h$ must be surjective.

$(\Rightarrow)$. Assume that
$\mathcal{J}_{A}\in\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$, and let $h$ be a
surjective homomorphism from $\mathcal{J}_{A}$ to $\mathcal{I}$. Build an
interpretation $\mathcal{J}$ as follows. Start by setting
$\mathcal{J}=\mathcal{I}_{\mathcal{A}}$. Since Case (2) above does not apply,
for each $d\in\Delta^{\mathcal{I}}$ we can select an individual name $a_{d}$
of $\mathcal{A}$ such that $V(a_{d})$ and $V_{d}(a_{d})$ are in $\mathcal{A}$.
For each individual name $a$ in $\mathcal{A}_{|A}$, extend $\mathcal{J}$ by
adding $(a,a_{h(a)})$ to $\mathsf{val}^{\mathcal{J}}$ and $(a,a_{d})$ to
$\mathsf{aux}_{d}^{\mathcal{J}}$ for each $d\in\Delta^{\mathcal{I}}$. Since
$h$ is surjective, for each $d\in\Delta^{\mathcal{I}}$ there must be an
individual name $a_{d}^{\prime}$ of $\mathcal{A}_{|A}$ with
$h(a_{d}^{\prime})=d$. Further extend $\mathcal{J}$ by adding
$(a,a_{d}^{\prime})$ to $\mathsf{force}_{d}^{\mathcal{J}}$ for all
$a\in\mathsf{Ind}(\mathcal{A}_{|A})$ and all $d\in\Delta^{\mathcal{I}}$. It is
readily checked that $\mathcal{J}$ is a model of $\mathcal{T}$ and
$\mathcal{A}$ that respects closed predicates $\Sigma_{\mathsf{C}}$, and that
$\mathcal{J}\not\models q$. Thus, $\mathcal{A}\not\models Q$, as required.

Note that the same reduction works when $\text{DL-Lite}_{\text{core}}$ is
replaced with $\mathcal{EL}$. One simply has to replace the TBox $\mathcal{T}$
by the $\mathcal{EL}$ TBox

$\begin{array}[]{rcl}\mathcal{T}^{\prime}&=&\\{A\sqsubseteq\exists\mathsf{val}.V\\}\,\cup\\\\[2.84526pt]
&&\\{A\sqsubseteq\exists\mathsf{aux}_{d}.(V\sqcap V_{d})\mid
d\in\Delta^{\mathcal{I}}\\}\,\cup\\\\[2.84526pt]
&&\\{A\sqsubseteq\exists\mathsf{force}_{d}.A\mid
d\in\Delta^{\mathcal{I}}\\}\end{array}$

and to observe that all CQs in $q$ have the form $\exists xq^{\prime}(x)$ with
$q^{\prime}(x)$ a dtCQ which enables the following modification: introduce a
fresh concept name $B$, then for each CQ $\exists xq^{\prime}(x)$ in $q$, take
the $\mathcal{EL}$ concepts $C_{q^{\prime}}$ that corresponds to
$q^{\prime}(x)$ and extend $\mathcal{T}^{\prime}$ with
$C_{q^{\prime}}\sqsubseteq B$, and finally replace $q$ with the BAQ $\exists
x\,B(x)$. In summary, we have obtained the following result.

######  Theorem 30.

For every $\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$, there is an OMQC $Q$ in
$(\text{DL-Lite}_{\text{core}},{\sf N_{C}},\text{BUtCQ})$ such that the
complement of $\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$ has the same
complexity as the evaluation problem for $Q$, up to polynomial time
reductions. The same holds for $(\mathcal{EL},{\sf N_{C}},\text{BAQ})$.

We note that, as can easily be verified by checking the constructions in the
proof of Lemma 29, the complement of
$\mathsf{CSP}(\mathcal{I})^{\mathsf{sur}}$ and the evaluation problem for $Q$
actually have the same complexity up to _FO reductions_ [32]. This links the
complexity of the two problems even closer. For example, if one is complete
for LogSpace or in AC0, then so is the other.

We now establish (almost) a converse of Theorem 30 by showing that for every
OMQC $Q$ from $(\mathcal{ALC}\mathcal{HI},{\sf N_{C}},\text{BUtCQ})$, there is
a generalized surjective CSP that has the same complexity as the complement of
the evaluation problem for $Q$, up to polynomial time reductions.

Let $Q=(\mathcal{T},\Sigma_{\mathsf{A}},\Sigma_{\mathsf{C}},q)$ be an OMQC
from $(\mathcal{ALC}\mathcal{HI},{\sf N_{C}},\text{BUtCQ})$. We can assume
w.l.o.g. that $q$ is a BAQ, essentially because every tCQ can be rewritten
into an $\mathcal{ALCI}$ concept; see the remark on $\mathcal{EL}$ and BAQs
made after the proof of Lemma 29. Thus, let $q=\exists x\,A_{0}(x)$ with
$A_{0}$ a concept name in $\mathcal{T}$. We use the notation for types
introduced in Section 5. A subset $T$ of the set ${\sf TP}(\mathcal{T})$ of
$\mathcal{T}$-types is _realizable in a countermodel_ if there is a
$\Sigma_{\mathsf{A}}$-ABox $\mathcal{A}$ and model $\mathcal{I}$ of
$\mathcal{T}$ and $\mathcal{A}$ that respects closed predicates
$\Sigma_{\mathsf{C}}$ such that $\mathcal{I}\not\models q$ and
$T=\\{\mathsf{tp}_{\mathcal{I}}(a)\mid a\in\mathsf{Ind}(\mathcal{A})\\}$. The
desired surjective generalized CSP is defined by taking one template for each
$T\subseteq\mathsf{TP}(\mathcal{T})$ that is realizable in a countermodel. The
signature $\Sigma$ of the CSP comprises the predicates in
$\Sigma_{\mathsf{A}}$, one concept name $\overline{A}$ for each concept name
in $\Sigma_{\mathsf{C}}$, and the concept name $A_{0}$ from $q$. We assume
w.l.o.g. that there is at least one concept name in $\Sigma_{\mathsf{C}}$ and
at least one concept name
$A_{\mathsf{open}}\in\Sigma_{\mathsf{A}}\setminus\Sigma_{\mathsf{C}}$.

Pick for every $A\in\Sigma_{\mathsf{C}}$ an element $d_{A}$. Then for each
$T\subseteq\mathsf{TP}(\mathcal{T})$ realizable in a countermodel we define
the template $\mathcal{I}_{T}$ as follows:

$\begin{array}[]{rcl}\Delta^{\mathcal{I}_{T}}&=&T\uplus\\{d_{A}\mid
A\in\Sigma_{\mathsf{C}}\\}\\\\[2.84526pt] A^{\mathcal{I}_{T}}&=&\\{t\in T\mid
A\in t\\}\cup\\{d_{B}\mid
B\in\Sigma_{\mathsf{C}}\setminus\\{A\\}\\}\\\\[2.84526pt]
\overline{A}^{\mathcal{I}_{T}}&=&\\{t\in T\mid A\notin t\\}\cup\\{d_{B}\mid
B\in\Sigma_{\mathsf{C}}\setminus\\{A\\}\\}\\\\[2.84526pt]
r^{\mathcal{I}_{T}}&=&\\{(t,t^{\prime})\in T\times T\mid
t\rightsquigarrow_{r}t^{\prime}\\}\,\cup\\\\[2.84526pt]
&&\\{(d,d^{\prime})\in\Delta^{\mathcal{I}_{T}}\times\Delta^{\mathcal{I}_{T}}\mid\\{d,d^{\prime}\\}\setminus
T\neq\emptyset\\}.\end{array}$

Note that, in $\mathcal{I}_{T}$ restricted to domain $T$, $\overline{A}$ is
interpreted as the complement of $A$. At each element $d_{A}$, all concept
names except $A$ and $\overline{A}$ are true, and these elements are connected
to all elements with all roles. Intuitively, we need the concept names
$\overline{A}$ to ensure that when an assertion $A(a)$ is missing in an ABox
$\mathcal{A}$ with $A$ closed, then $a$ can only be mapped to a template
element that does not make $A$ true; this is done by extending $\mathcal{A}$
with $\overline{A}(a)$ and exploiting that $\overline{A}$ is essentially the
complement of $A$ in each $\mathcal{I}_{T}$. The elements $d_{A}$ are then
needed to deal with inputs to the CSP where some point satisfies neither $A$
nor $\overline{A}$. Let $\Gamma$ be the set of all interpretations
$\mathcal{I}_{T}$ obtained in the described way.

######  Lemma 31.

The evaluation problem for $Q$ reduces in polynomial time to the complement of
$\mathsf{CSP}(\Gamma)^{\mathsf{sur}}$.

######  Proof 7.2.

Let $\mathcal{A}$ be a $\Sigma_{\mathsf{A}}$-ABox that is an input for $Q$ and
let $\mathcal{A}^{\prime}$ be its extension with

  * •

all assertions $\overline{A}(a)$ such that $A\in\Sigma_{\mathsf{C}}$,
$a\in{\sf Ind}(\mathcal{A})$, and $A(a)\notin\mathcal{A}$;

  * •

assertions $A_{\mathsf{open}}(a_{B})$, where $a_{B}$ is a fresh individual
name for each $B\in\Sigma_{\mathsf{C}}$.

We claim that $\mathcal{A}\not\models Q$ iff there is an interpretation
$\mathcal{I}_{T}\in\Gamma$ such that there exists a surjective homomorphism
from $\mathcal{I}_{\mathcal{A}^{\prime}}$ to $\mathcal{I}_{T}$.

($\Leftarrow$). Let $\mathcal{I}_{T}\in\Gamma$ and let $h$ be a surjective
homomorphism from $\mathcal{I}_{\mathcal{A}^{\prime}}$ to $\mathcal{I}_{T}$.
Note that each element $a$ of ${\sf Ind}(\mathcal{A})$ is mapped by $h$ to
some element $t\in T$ of $\mathcal{I}_{T}$ because
$A(a)\in\mathcal{A}^{\prime}$ or $\overline{A}(a)\in\mathcal{A}^{\prime}$ for
every $A\in\Sigma_{\mathsf{C}}$ (which is non-empty). Since
$\mathcal{I}_{T}\in\Gamma$, there is a $\Sigma_{\mathsf{A}}$-ABox
$\mathcal{B}$ and model $\mathcal{I}$ of $\mathcal{T}$ and $\mathcal{B}$ that
respects closed predicates $\Sigma_{\mathsf{C}}$ such that
$\mathcal{I}\not\models q$ and $T=\\{\mathsf{tp}_{\mathcal{I}}(a)\mid
a\in\mathsf{Ind}(\mathcal{B})\\}$. For each $a\in\mathsf{Ind}(\mathcal{A})$,
set $t_{a}=h(a)\in T$ and for each $d\in\Delta^{\mathcal{I}}$, set
$t_{d}=\mathsf{tp}_{\mathcal{I}}(d)$. Construct an interpretation
$\mathcal{J}$ as follows:

$\begin{array}[]{rcl}\Delta^{\mathcal{J}}&=&\mathsf{Ind}(\mathcal{A})\cup(\Delta^{\mathcal{I}}\setminus\mathsf{Ind}(\mathcal{B}))\\\\[2.84526pt]
A^{\mathcal{J}}&=&\\{d\in\Delta^{\mathcal{J}}\mid A\in t_{d}\\}\\\\[2.84526pt]
r^{\mathcal{J}}&=&\\{(d,e)\in\Delta^{\mathcal{J}}\times\Delta^{\mathcal{J}}\mid
t_{d}\rightsquigarrow_{r}t_{e}\\}.\end{array}$

First note that $\mathcal{J}$ is clearly a model of $\mathcal{A}$ that
respects closed predicates $\Sigma_{\mathsf{C}}$. Specifically, if
$A(a)\in\mathcal{A}$, then $h(a)\in A^{\mathcal{I}_{T}}$, thus $A\in
h(a)=t_{a}$ by construction of $\mathcal{I}_{T}$ which yields $a\in
A^{\mathcal{J}}$ by construction of $\mathcal{J}$; if $r(a,b)\in\mathcal{A}$,
then $(h(a),h(b))\in r^{\mathcal{I}_{T}}$, thus
$t_{a}\rightsquigarrow_{r}t_{b}$ implying $(a,b)\in r^{\mathcal{J}}$; finally
if $A\in\Sigma_{\mathsf{C}}$ and $d\in A^{\mathcal{J}}$, then we must have
$d=a$ for some $a\in\mathsf{Ind}(\mathcal{A})$ by definition of $\mathcal{J}$
and since $d\notin A^{\mathcal{I}}$ for all
$d\in\Delta^{\mathcal{I}}\setminus\mathsf{Ind}(\mathcal{B})$. Thus, $A\in
t_{a}=h(a)$ by construction of $\mathcal{J}$. This implies
$A(a)\in\mathcal{A}$ since otherwise $\overline{A}(a)\in\mathcal{A}^{\prime}$,
which would imply $\overline{A}\in h(a)$, in contradiction to $A\in h(a)$.

It thus remains to show that $\mathcal{J}$ is a model of $\mathcal{T}$ and
$\mathcal{J}\not\models q$. By definition, $\mathcal{J}$ satisfies all RIs in
$\mathcal{T}$. Satisfaction of the CIs in $\mathcal{T}$ and
$\mathcal{J}\not\models q$ follows from the subsequent claim together with the
condition that no type in $T$ contains $A_{0}$ and each type in
$\mathcal{I}_{T}$ is satisfied in a model of $\mathcal{T}$.

######  Claim.

For all $d\in\Delta^{\mathcal{J}}$ and $C\in\mathsf{cl}(\mathcal{T})$, we have
$d\in C^{\mathcal{J}}$ iff $C\in t_{d}$.

Proof of claim. The proof is by induction on the structure of $C$, with the
induction start and the cases $C=\neg D$ and $C=D_{1}\sqcap D_{2}$ being
trivial. Thus let $C=\exists r.D$ and first assume $d\in C^{\mathcal{J}}$.
Then there is an $e\in D^{\mathcal{J}}$ with $(d,e)\in r^{\mathcal{J}}$. Thus
$t_{d}\rightsquigarrow_{r}t_{e}$ by definition of $\mathcal{J}$, and IH yields
$D\in t_{e}$. By definition of ‘$\rightsquigarrow_{r}$’, we must thus have
$C\in t_{d}$ as required. Now let $C\in t_{d}$. We distinguish two cases:

  * •

$d=a\in\mathsf{Ind}(\mathcal{A})$.

Let $a^{\prime}\in\mathsf{Ind}(\mathcal{B})$ be such that
$h(a)=\mathsf{tp}_{\mathcal{I}}(a^{\prime})$. Since $t_{a}=h(a)$, we must have
$a^{\prime}\in C^{\mathcal{I}}$ and thus there is some $e\in D^{\mathcal{I}}$
with $(a^{\prime},e)\in r^{\mathcal{I}}$, which yields
$\mathsf{tp}_{\mathcal{I}}(a^{\prime})\rightsquigarrow_{r}\mathsf{tp}_{\mathcal{I}}(e)$
and $D\in\mathsf{tp}_{\mathcal{I}}(e)$. If
$e=b^{\prime}\in\mathsf{Ind}(\mathcal{B})$, then since $h$ is surjective there
is some $b\in\mathsf{Ind}(\mathcal{A})$ with
$h(b)=\mathsf{tp}_{\mathcal{I}}(b^{\prime})$. We have
$t_{a}=\mathsf{tp}_{\mathcal{I}}(a^{\prime})$ and
$t_{b}=\mathsf{tp}_{\mathcal{I}}(b^{\prime})$, thus
$t_{a}\rightsquigarrow_{r}t_{b}$ which yields $(a,b)\in r^{\mathcal{J}}$ by
definition of $\mathcal{J}$. We also have $D\in t_{b}$, which by IH yields
$b\in D^{\mathcal{J}}$.

  * •

$d\notin\mathsf{Ind}(\mathcal{A})$.

Then $d\in\Delta^{\mathcal{I}}\setminus\mathsf{Ind}(\mathcal{B})$. Since $C\in
t_{d}$, we thus have $C\in\mathsf{tp}_{\mathcal{I}}(d)$. Thus, there is an
$e\in D^{\mathcal{I}}$ with $(d,e)\in r^{\mathcal{I}}$, which implies
$\mathsf{tp}_{\mathcal{I}}(d)\rightsquigarrow_{r}\mathsf{tp}_{\mathcal{I}}(e)$
and $D\in\mathsf{tp}_{\mathcal{I}}(e)$. If $e\notin\mathsf{Ind}(\mathcal{B})$,
then the definition of $\mathcal{J}$ and IH yields $d\in C^{\mathcal{J}}$.
Thus assume $e=b^{\prime}\in\mathsf{Ind}(\mathcal{B})$. Since $h$ is
surjective, there is some $b\in\mathsf{Ind}(\mathcal{A})$ with
$h(b)=\mathsf{tp}_{\mathcal{I}}(b^{\prime})$. Since
$t_{d}=\mathsf{tp}_{\mathcal{I}}(d)$ and $t_{b}=h(b)$, we have
$t_{d}\rightsquigarrow_{r}t_{b}$, thus $(d,b)\in r^{\mathcal{J}}$. By IH,
$D\in\mathsf{tp}_{\mathcal{I}}(b^{\prime})=h(b)$ yields $b\in
D^{\mathcal{J}}$.

$\dashv$

$(\Rightarrow)$. Assume that $\mathcal{A}\not\models Q$. Then there is a model
$\mathcal{I}$ of $\mathcal{T}$ and $\mathcal{A}$ that respects closed
predicates $\Sigma_{\mathsf{C}}$ and such that $\mathcal{I}\not\models q$. Let
$\mathcal{I}_{T}\in\Gamma$ be the corresponding template, that is,
$T=\\{\mathsf{tp}_{\mathcal{I}}(a)\mid a\in\mathsf{Ind}(\mathcal{A})\\}$. For
each $a\in\mathsf{Ind}(\mathcal{A})$, set $h(a)=\mathsf{tp}_{\mathcal{I}}(a)$;
for each
$a_{B}\in\mathsf{Ind}(\mathcal{A}^{\prime})\setminus\mathsf{Ind}(\mathcal{A})$,
set $h(a_{B})=d_{B}$. It is readily checked that $h$ is a surjective
homomorphism from $\mathcal{I}_{\mathcal{A}^{\prime}}$ to $\mathcal{I}_{T}$.
In particular, $\overline{A}(a)\in\mathcal{A}^{\prime}$ implies
$A(a)\notin\mathcal{A}^{\prime}$, thus $A\notin\mathsf{tp}_{\mathcal{I}}(a)$
(since $A$ is closed), which yields
$h(a)=\mathsf{tp}_{\mathcal{I}}(a)\in\overline{A}^{\mathcal{I}_{\mathcal{T}}}$
by definition of $\mathcal{I}_{\mathcal{T}}$.

######  Lemma 32.

$\mathsf{CSP}(\Gamma)^{\mathsf{sur}}$ polynomially reduces to the complement
of the evaluation problem for $Q$.

######  Proof 7.3.

Let $\mathcal{A}^{\prime}$ be the ABox corresponding to an input $\mathcal{J}$
for $\mathsf{CSP}(\Gamma)^{\mathsf{sur}}$. An element $a$ of ${\sf
Ind}(\mathcal{A}^{\prime})$ is _special for_ $A\in\Sigma_{\mathsf{C}}$ if
$A(a)\notin\mathcal{A}^{\prime}$ and
$\overline{A}(a)\notin\mathcal{A}^{\prime}$; it is _special_ if it is special
for some $A\in\Sigma_{\mathsf{C}}$. First perform the following checks:

  1. (1)

if there is a non-special element $a$ of ${\sf Ind}(\mathcal{A}^{\prime})$
such that $A(a)\in\mathcal{A}^{\prime}$ and
$\overline{A}(a)\in\mathcal{A}^{\prime}$ for some $A\in\Sigma_{\mathsf{C}}$,
then return ‘no’ (there is no template in $\Gamma$ that has any element to
which $a$ can be mapped by a homomorphism);

  2. (2)

if $\mathcal{A}^{\prime}$ does not contain a family of distinct elements
$(a_{A})_{A\in\Sigma_{\mathsf{C}}}$, such that each $a_{A}$ is special for
$A$, then return ‘no’ (we cannot map surjectively to the elements $d_{A}$ of
the templates in $\Gamma$).

Note that, to check Condition 2, we can go through all candidate families in
polytime since the size of $\Sigma_{\mathsf{C}}$ is constant. If none of the
above checks succeeds, then let $\mathcal{A}$ be the ABox obtained from
$\mathcal{A}^{\prime}$ by

  * •

deleting all assertions of the form $\overline{A}(a)$ and

  * •

deleting all special elements.

We have to show that $\mathcal{A}\not\models Q$ iff there exists an
$\mathcal{I}_{T}\in\Gamma$ such that there is a surjective homomorphism from
$\mathcal{J}$ to $\mathcal{I}_{T}$.

($\Leftarrow$). Let $\mathcal{I}_{T}\in\Gamma$ and let $h$ be a surjective
homomorphism from $\mathcal{J}$ to $\mathcal{I}_{T}$. Note that each element
$a$ of ${\sf Ind}(\mathcal{A})$ is mapped by $h$ to some element $t\in T$ of
$\mathcal{I}_{T}$ because $A(a)\in\mathcal{A}^{\prime}$ or
$\overline{A}(a)\in\mathcal{A}^{\prime}$ for every $A\in\Sigma_{\mathsf{C}}$
(which is non-empty). Since $\mathcal{I}_{T}\in\Gamma$, there is a
$\Sigma_{\mathsf{A}}$-ABox $\mathcal{B}$ and model $\mathcal{I}$ of
$\mathcal{T}$ and $\mathcal{B}$ that respects closed predicates
$\Sigma_{\mathsf{C}}$ and such that $\mathcal{I}\not\models q$ and
$T=\\{\mathsf{tp}_{\mathcal{I}}(a)\mid a\in\mathsf{Ind}(\mathcal{B})\\}$. We
can now proceed as in the proof of Lemma 31 to build a model
$\mathcal{J}^{\prime}$ of $\mathcal{T}$ and $\mathcal{A}$ that respects closed
predicates $\Sigma_{\mathsf{C}}$ and such that
$\mathcal{J}^{\prime}\not\models q$.

($\Rightarrow$). Assume that $\mathcal{A}\not\models Q$. Then there is a model
$\mathcal{I}$ of $\mathcal{T}$ and $\mathcal{A}$ that respects closed
predicates $\Sigma_{\mathsf{C}}$ and such that $\mathcal{I}\not\models q$. Let
$\mathcal{I}_{T}\in\Gamma$ be the corresponding template, that is,
$T=\\{\mathsf{tp}_{\mathcal{I}}(a)\mid a\in\mathsf{Ind}(\mathcal{A})\\}$. For
each $a\in\mathsf{Ind}(\mathcal{A})$, set $h(a)=\mathsf{tp}_{\mathcal{I}}(a)$;
for each element
$a\in\mathsf{Ind}(\mathcal{A}^{\prime})\setminus\mathsf{Ind}(\mathcal{A})$, we
can choose some $A\in\Sigma_{\mathsf{C}}$ such that
$A(a)\notin\mathcal{A}^{\prime}$ and
$\overline{A}(a)\notin\mathcal{A}^{\prime}$, and set $h(a)=d_{A}$; by Check 2
above, these choices can be made such that the resulting map $h$ is
surjective. Moreover, it is readily checked that $h$ is a homomorphism from
$\mathcal{J}$ to $\mathcal{I}_{T}$. In particular,
$\overline{A}(a)\in\mathcal{A}^{\prime}$ implies
$A(a)\notin\mathcal{A}^{\prime}$ by Check 1, thus
$A\notin\mathsf{tp}_{\mathcal{I}}(a)$ (since $A$ is closed), which yields
$h(a)=\mathsf{tp}_{\mathcal{I}}(a)\in\overline{A}^{\mathcal{I}_{\mathcal{T}}}$
by definition of $\mathcal{I}_{\mathcal{T}}$.

We have thus established the following result.

######  Theorem 33.

For every OMQC $Q$ from $(\mathcal{ALC}\mathcal{HI},{\sf
N_{C}},\text{BUtCQ})$, there is a generalized
$\mathsf{CSP}(\Gamma)^{\mathsf{sur}}$ such that the evaluation problem for $Q$
has the same complexity as the complement of
$\mathsf{CSP}(\Gamma)^{\mathsf{sur}}$, up to polynomial time reductions.

Again, the theorem can easily be strengthened to state the same complexity up
to FO reductions. Note that the DL $\mathcal{ALC}\mathcal{HI}$ used in Theorem
33 is a significant extension of the DLs referred to in Theorem 30 and thus
our results apply to a remarkable range of DLs: all DLs between $\text{DL-
Lite}_{\text{core}}$ and $\mathcal{ALC}\mathcal{HI}$ as well as all DLs
between $\mathcal{EL}$ and $\mathcal{ALC}\mathcal{HI}$.

##  8\. Closing Role Names in the Fixed Query Case: Turing Machine Equivalence

We generalize the setup from the previous section by allowing also role names
to be closed. Our main results are that for every non-determinstic polynomial
time Turing machine $M$, there is an OMQC $Q$ in $(\text{DL-
Lite}_{\mathcal{R}},{\sf N_{C}}\cup{\sf N_{R}},\text{BUtCQ})$ such that
evaluating $Q$ and the complement of $M$’s word problem are polynomial time
reducible to each other, and that it is undecidable whether evaluating OMQCs
in $(\text{DL-Lite}_{\mathcal{R}},{\sf N_{C}}\cup{\sf N_{R}},\text{BUtCQ})$ is
in PTime (unless PTime = NP). By Ladner’s theorem, it follows that there are
coNP-intermediate OMQCs (unless PTime = NP) and that a full complexity
classification of the OMQCs in this language is beyond reach. As in the
previous section, the same results hold for $(\mathcal{EL},{\sf N_{C}}\cup{\sf
N_{R}},\text{BAQ})$.

To establish these results, we utilize two related results from [42, 13]: (1)
for every NP Turing machine $M$, there is an ontology-mediated query $Q$ from
$(\mathcal{ALCF},\emptyset,\text{BAQ})$ such that evaluating $Q$ is reducible
in polynomial time to the complement of $M$’s word problem and vice versa,
where $\mathcal{ALCF}$ is the extension of $\mathcal{ALC}$ with functional
roles; and (2) it is undecidable whether an OMQC from
$(\mathcal{ALCF},\emptyset,\text{BAQ})$ is in PTime. For using these results
in our context, however, it is more convenient to phrase them in terms of (a
certain kind of) monadic disjunctive datalog programs with inequality rather
than in terms of OMQCs from $(\mathcal{ALCF},\emptyset,\text{BAQ})$. This is
what we do in the following, starting with the introduction of a suitable
version of monadic disjunctive datalog. For a more thorough introduction, see
to [23].

A _monadic disjunctive datalog rule (MDD rule)_ $\rho$ takes the form

$P_{1}(x)\vee\cdots\vee P_{m}(x)\leftarrow R_{1}(\vec{x}_{1})\land\cdots\land
R_{n}(\vec{x}_{n})\quad\mbox{ or }\quad{\sf goal}\leftarrow
R_{1}(\vec{x}_{1})\land\cdots\land R_{n}(\vec{x}_{n})$

with $m,n>0$ and where all $P_{i}$ are unary predicates, ${\sf goal}$ is the
_goal predicate_ of arity $0$, and all $R_{i}$ are predicates of arity one or
two, including possibly the non-equality predicate $\not=$. We refer to
$P_{1}(x)\vee\cdots\vee P_{m}(x)$ and, respectively, ${\sf goal}$ as the
_head_ of $\rho$, and to $R_{1}(\vec{x}_{1})\wedge\cdots\wedge
R_{n}(\vec{x}_{n})$ as the _body_. A _monadic disjunctive datalog (MDD)
program_ $\Pi$ is a finite set of MDD rules containing at least one rule with
the goal predicate in its head and no rule with the goal predicate in its
body. Predicates that occur in the head of at least one rule of $\Pi$ are
_intensional (IDB) predicates_ , denoted ${\sf IDB}(\Pi)$, and all remaining
predicates in $\Pi$ are _extensional (EDB) predicates_ , denoted ${\sf
EDB}(\Pi)$. An interpretation $\mathcal{I}$ is a _model_ of $\Pi$ if it
satisfies all rules in $\Pi$ (viewed as universally quantified first-order
sentences). $\Pi$ is _entailed on_ a ${\sf EDB}(\Pi)$-ABox $\mathcal{A}$, in
symbols $\mathcal{A}\models\Pi$, iff ${\sf goal}$ is true in every model of
$\Pi$ and $\mathcal{A}$. Note that it suffices to consider models that respect
closed predicates ${\sf EDB}(\Pi)$. The _evaluation problem for $\Pi$_ is the
problem to decide whether $\Pi$ is entailed by an ${\sf EDB}(\Pi)$-ABox
$\mathcal{A}$.

For our reduction, we use the following kind of MDD programs that we call
basic. A binary predicate $r$ is _functional in an ABox_ $\mathcal{A}$ if
$r(a,b_{1}),r(a,b_{2})\in\mathcal{A}$ implies $b_{1}=b_{2}$ and $r$ is _empty
in_ $\mathcal{A}$ if $r$ does not occur in $\mathcal{A}$. Then an MDD program
$\Pi$ is _basic_ if

  * •

$\Pi$ uses exactly two binary predicates, $r_{1},r_{2}$, and contains exactly
the following functionality rules, for $i=1,2$:

${\sf goal}\leftarrow r_{i}(x,y)\wedge r_{i}(x,z)\wedge(y\not=z)$

  * •

all remaining rules of $\Pi$ are of the form

$P_{1}(x)\vee\cdots\vee P_{n}(x)\leftarrow q\quad\mbox{ or }\quad{\sf
goal}\leftarrow q$

where $n\geq 1$ and $q$ is a dtCQ with root $x$ (with the quantifier prefix
removed).

  * •

if $r_{1},r_{2}$ are functional and at least one $r_{i}$ is empty in an ${\sf
EDB}(\Pi)$-ABox $\mathcal{A}$, then $\mathcal{A}\not\models\Pi$.

The following result can be obtained by starting from the results for
$(\mathcal{ALCF},\emptyset,\text{BAQ})$ from [42, 13] mentioned above and
translating the involved OMQs into a basic MDD program. Such a translation is
given in [13] for the case of $\mathcal{ALC}$ TBoxes and MDD programs without
inequality, but the extension to functional roles and inequality is trivial.

######  Theorem 34.

  1. (1)

For every non-deterministic polynomial time Turing machine $M$, there exists a
basic MDD program $\Pi$ such that the evaluation problem for $\Pi$ and the
complement of $M$’s word problem are polynomial time reducible to each other.

  2. (2)

It is undecidable whether the evaluation problem for a basic MDD program is in
PTime (unless PTime =NP).

We next prove the following central theorem.

######  Theorem 35.

For every basic MDD program $\Pi$, one can construct an OMQC $Q$ in the
language $(\mathcal{EL},{\sf N_{C}}\cup{\sf N_{R}},\text{BAQ})$ such that the
evaluation problem for $Q$ and $\Pi$ are polynomial time reducible to each
other. The same is true for $(\text{DL-Lite}_{\mathcal{R}},{\sf N_{C}}\cup{\sf
N_{R}},\text{BUtCQ})$.

######  Proof 8.1.

Assume a basic MDD program $\Pi$ of the form defined above is given. We first
construct an OMQC
$Q_{\Pi}=(\mathcal{T}_{\Pi},\Sigma_{\Pi},\Sigma_{\Pi},q_{\Pi})$ in
$(\mathcal{EL},{\sf N_{C}}\cup{\sf N_{R}},\text{BUtCQ})$ and then obtain the
required OMQCs in $(\mathcal{EL},{\sf N_{C}}\cup{\sf N_{R}},\text{BAQ})$ and
$(\text{DL-Lite}_{\mathcal{R}},{\sf N_{C}}\cup{\sf N_{R}},\text{BUtCQ})$ by
rather straightforward modifications of $Q_{\Pi}$. Note that we construct a
$Q_{\Pi}$ in which the ABox signature and set of closed predicates coincide.
We set $\Sigma_{\Pi}={\sf EDB}(\Pi)\cup\\{T,F,V\\}$, where $T,F,V$ are fresh
concept names. We also use auxiliary predicates which are not in the ABox
signature of $Q_{\Pi}$: role names ${\sf val}_{P}$ for every unary $P\in{\sf
IDB}(\Pi)$ and role names $s_{i}$ and concept names $A_{i},B_{i}$, for
$i=1,2$. $\mathcal{T}_{\Pi}$ contains the following CIs:

$\begin{array}[]{rcl}T&\sqsubseteq&V\\\\[2.84526pt]
F&\sqsubseteq&V\\\\[2.84526pt] \top&\sqsubseteq&\exists{\sf val}_{P}.V,\text{
for all unary $P\in{\sf IDB}(\Pi)$ }\\\\[2.84526pt] \top&\sqsubseteq&\exists
s_{i}.(\exists r_{i}.A_{i}\sqcap\exists r_{i}.B_{i}),\text{ for $i=1,2$
}.\end{array}$

Using $\mathcal{T}_{\Pi}$, we encode the truth value of IDB predicates $P$
using the CQs

$P^{T}(x,y):=({\sf val}_{P}(x,y)\wedge T(y)),\quad P^{F}(x,y):=({\sf
val}_{P}(x,y)\wedge F(y)).$

For any tCQ $q$, we denote by $q^{T}$ the result of replacing every occurrence
of an IDB $P(x)$ in $q$ by $P^{T}(x,y_{0})$, where the variable $y_{0}$ is
fresh for every occurrence of $P(x)$, and existentially quantified. Thus,
$q^{T}$ is again a tCQ (and a dtCQ if $q$ is already a dtCQ). The final CI is
used to encode functionality of the roles $r_{1},r_{2}$. We set
$q_{\mathcal{F}}=q_{\mathcal{F}}^{1}\wedge q_{\mathcal{F}}^{2}$, where

$q_{\mathcal{F}}^{i}=(s_{i}(x,x_{i})\wedge r_{i}(x_{i},y_{i})\wedge
A_{i}(y_{i})\wedge B_{i}(y_{i}))$

Then, for $Q_{i}=(\\{\top\sqsubseteq\exists s_{i}.(\exists
r_{i}.A_{i}\sqcap\exists r_{i}.B_{i})\\},\Sigma_{\Pi},\exists x_{i}\,\exists
y_{i}\,q_{\mathcal{F}}^{i})$, and any $\Sigma_{\Pi}$-ABox $\mathcal{A}$:

  * •

if $r_{i}$ is empty in $\mathcal{A}$, then $\mathcal{A}$ is not consistent
w.r.t. $(\\{\top\sqsubseteq\exists s_{i}.(\exists r_{i}.A_{i}\sqcap\exists
r_{i}.B_{i})\\},\Sigma_{\Pi})$, and

  * •

if $r_{i}$ is not empty in $\mathcal{A}$, then $r_{i}$ is functional in
$\mathcal{A}$ iff $\mathcal{A}\models Q_{i}(a)$, for some (equivalently, all)
$a\in{\sf Ind}(\mathcal{A})$.

Define $q_{\Pi}$ as the union of the following Boolean CQs, where for brevity
we omit the existential quantifiers:

  * •

$q_{\mathcal{F}}\wedge q^{T}$, for every rule ${\sf goal}\leftarrow q\in\Pi$,
where we assume that the only variable shared by $q_{\mathcal{F}}$ and $q^{T}$
is $x$.

  * •

$q_{\mathcal{F}}\wedge q^{T}\wedge\bigwedge_{1\leq i\leq n}P_{i}^{F}$, for
every $P_{1}(x)\vee\cdots\vee P_{n}(x)\leftarrow q\in\Pi$, where we assume
again that the only variable shared by any two of the conjuncts
$q_{\mathcal{F}}$, $q^{T}$, $P_{i}^{F}$, $1\leq i\leq n$, is $x$.

We prove the following

######  Claim.

The problem of evaluating $\Pi$ and the problem of evaluating $Q_{\Pi}$ are
polynomial time reducible to each other.

Proof of claim. ($\Rightarrow$) Assume an $\mathsf{EDB}(\Pi)$-ABox
$\mathcal{A}$ is given as an input to $\Pi$. If $r_{1}$ or $r_{2}$ is not
functional in $\mathcal{A}$, then output ‘$\mathcal{A}\models\Pi$’. Otherwise,
if $r_{1}$ or $r_{2}$ is empty, then output ‘$\mathcal{A}\not\models\Pi$’. Now
assume that $r_{1}$ and $r_{2}$ are not empty and both are functional in
$\mathcal{A}$. Let

$\mathcal{A}^{\prime}=\mathcal{A}\cup\\{T(a),F(b),V(a),V(b)\\},$

where we asume w.l.o.g. that $a,b$ occur in ${\sf Ind}(\mathcal{A})$. We show
that $\mathcal{A}\models\Pi$ iff $\mathcal{A}^{\prime}\models Q_{\Pi}$.

Assume first that $\mathcal{A}\not\models\Pi$. Let $\mathcal{I}$ be a model of
$\mathcal{A}$ and $\Pi$ that respects closed predicates $\mathsf{EDB}(\Pi)$
and satisfies no body of any rule ${\sf goal}\leftarrow q\in\Pi$. Define
$\mathcal{I}^{\prime}$ in the same way as $\mathcal{I}$ except that

  * •

$T^{\mathcal{I}^{\prime}}=\\{a\\}$, $F^{\mathcal{I}^{\prime}}=\\{b\\}$, and
$V^{\mathcal{I}^{\prime}}=\\{a,b\\}$;

  * •

$s_{i}^{\mathcal{I}^{\prime}}=\Delta^{\mathcal{I}}\times{\sf
dom}(r_{i}^{\mathcal{I}})$ and
$A_{i}^{\mathcal{I}^{\prime}}=B_{i}^{\mathcal{I}^{\prime}}=\Delta^{\mathcal{I}}$,
for $i=1,2$, where ${\sf dom}(r^{\mathcal{I}})$ denotes the domain of
$r^{\mathcal{I}}$;

  * •

${\sf
val}_{P}^{\mathcal{I}^{\prime}}=(P^{\mathcal{I}}\times\\{a\\})\cup((\Delta^{\mathcal{I}}\setminus
P^{\mathcal{I}})\times\\{b\\})$, for all unary $P\in{\sf IDB}(\Pi)$.

It is straightforward to show that $\mathcal{I}^{\prime}$ is a model of
$\mathcal{T}_{\Pi}$ and $\mathcal{A}^{\prime}$ that respects closed predicates
$\Sigma_{\Pi}$. It remains to show that $\mathcal{I}^{\prime}\not\models
q_{\Pi}$. To this end it is sufficient to show that

  1. (1)

No $q^{T}$ with ${\sf goal}\leftarrow q\in\Pi$ is satisfied in
$\mathcal{I}^{\prime}$;

  2. (2)

No $q^{T}\wedge\bigwedge_{1\leq i\leq n}P_{i}^{F}$ with
$P_{1}(x)\vee\cdots\vee P_{n}(x)\leftarrow q\in\Pi$ is satisfied in
$\mathcal{I}^{\prime}$.

Point (1) holds since
$P^{\mathcal{I}}=\\{d\mid\mathcal{I}^{\prime}\models\exists y\,P^{T}(d,y))\\}$
for all unary $P\in{\sf IDB}(\Pi)$, by definition of $\mathcal{I}^{\prime}$
and since $q$ is not satisfied in $\mathcal{I}$ for any rule ${\sf
goal}()\leftarrow q\in\Pi$. Point (2) holds since all rules
$P_{1}(x)\vee\cdots\vee P_{n}(x)\leftarrow q\in\Pi$ are satisfied in
$\mathcal{I}$ and
$P^{\mathcal{I}}=\Delta^{\mathcal{I}}\setminus\\{d\mid\mathcal{I}^{\prime}\models\exists
y\,P^{F}(d,y)\\}$ for all unary $P\in{\sf IDB}(\Pi)$.

Assume now that $\mathcal{A}^{\prime}\not\models Q_{\Pi}$. Take a model
$\mathcal{I}$ of $\mathcal{A}^{\prime}$ that respects closed predicates
$\Sigma_{\Pi}$ and such that $\mathcal{I}\not\models q_{\Pi}$. Define a model
$\mathcal{I}^{\prime}$ by modifying $\mathcal{I}$ by setting
$P^{\mathcal{I}^{\prime}}=\\{d\mid\mathcal{I}\models\exists y\,P^{T}(d,y)\\}$,
for all unary $P\in{\sf IDB}(\Pi)$. It follows from the condition that
$r_{1},r_{2}$ are non-empty and functional in $\mathcal{A}^{\prime}$ that
$\mathcal{I}\models\forall x\exists x_{1},x_{2},y_{1},y_{2}\,q_{\mathcal{F}}$.
From $\mathcal{I}\not\models q_{\Pi}$ we obtain that no $q$ with ${\sf
goal}()\leftarrow q\in\Pi$ is satisfied in $\mathcal{I}^{\prime}$ and that all
rules $P_{1}(x)\vee\cdots\vee P_{n}(x)\leftarrow q\in\Pi$ are satisfied in
$\mathcal{I}^{\prime}$. Thus, $\mathcal{I}^{\prime}$ is a model of
$\mathcal{A}$ and $\Pi$ witnessing that $\mathcal{A}\not\models\Pi$.

($\Leftarrow$) Assume a $\Sigma_{\Pi}$-ABox $\mathcal{A}$ is given as an input
to $Q_{\Pi}$. There exists a model of $\mathcal{T}_{\Pi}$ and $\mathcal{A}$
that respects closed predicates $\Sigma_{\Pi}$ iff (i) $V$ is non-empty in
$\mathcal{A}$, (ii) $T,F$ are both contained in $V$ in $\mathcal{A}$, and
(iii) $r_{1},r_{2}$ are non-empty in $\mathcal{A}$. Thus, output
‘$\mathcal{A}\models Q_{\Pi}$’ whenever (i), (ii), or (iii) is violated. Now
assume (i), (ii), and (iii) hold. If $r_{1}$ or $r_{2}$ are not functional in
$\mathcal{A}$, then we can construct a model of $\mathcal{T}_{\Pi}$ and
$\mathcal{A}$ that respects closed predicates $\Sigma_{\Pi}$ and such that
$q_{\mathcal{F}}$ is not satisfied in $\mathcal{I}$. Hence, we output
‘$\mathcal{A}\not\models Q_{\Pi}$’. Thus, assume in addition to (i), (ii) and
(iii) that $r_{1}$ and $r_{2}$ are functional in $\mathcal{A}$. We distinguish
five cases. We only consider the first case in detail, the remaining cases are
proved similarly.

  1. (1)

If $F^{\mathcal{I}_{\mathcal{A}}}\cup
T^{\mathcal{I}_{\mathcal{A}}}\not=V^{\mathcal{I}_{\mathcal{A}}}$, then output
‘$\mathcal{A}\models Q_{\Pi}$’ if there exists a rule ${\sf goal}\leftarrow
q\in\Pi$ such that $q$ contains not IDBs and $q$ (which then equals $q^{T}$)
is satisfied in $\mathcal{I}_{\mathcal{A}}$. This is clearly correct since
$\mathcal{A}\models(\mathcal{T}_{\Pi},\Sigma_{\Pi},q_{\mathcal{F}}\wedge
q^{T})$ follows. Otherwise output ‘$\mathcal{A}\not\models Q_{\Pi}$’. To prove
correctness, let $a\in
V^{\mathcal{I}_{\mathcal{A}}}\setminus(F^{\mathcal{I}_{\mathcal{A}}}\cup
T^{\mathcal{I}_{\mathcal{A}}})$. Construct a model $\mathcal{I}$ of
$\mathcal{T}_{\Pi}$ and $\mathcal{A}$ that respects $\Sigma_{\Pi}$ by
extending $\mathcal{I}_{\mathcal{A}}$ by setting ${\sf
val}_{P}^{\mathcal{I}}=\Delta^{\mathcal{I}}\times\\{a\\}$ for all unary IDB
predicates $P$ and defining
$s_{i}^{\mathcal{I}},A_{i}^{\mathcal{I}},B_{i}^{\mathcal{I}}$, $i=1,2$,
arbitrarily so that $\mathcal{T}_{\Pi}$ is satisfied. Then no $q^{T}$ with
${\sf goal}\leftarrow q\in\Pi$ and no $\bigwedge_{1\leq i\leq n}P_{i}^{F}$
with $P_{1}(x)\vee\cdots\vee P_{n}(x)\leftarrow q\in\Pi$ is satisfied in
$\mathcal{I}$. Thus $\mathcal{I}\not\models q_{\Pi}$.

  2. (2)

If
$T^{\mathcal{I}_{\mathcal{A}}}=F^{\mathcal{I}_{\mathcal{A}}}=V^{\mathcal{I}_{\mathcal{A}}}$,
then output ‘$\mathcal{A}\models Q_{\Pi}$’ if there exists a rule ${\sf
goal}\leftarrow q\in\Pi$ or $P_{1}(x)\vee\cdots\vee P_{n}(x)\leftarrow
q\in\Pi$ such that $q^{\prime}$ is satisfied in $\mathcal{I}_{\mathcal{A}}$
for the query $q^{\prime}$ obtained from $q$ by removing every atom $P(y)$
from $q$ with $P$ a unary IDB. Otherwise output ‘$\mathcal{A}\not\models
Q_{\Pi}$’.

  3. (3)

If $T^{\mathcal{I}_{\mathcal{A}}}=V^{\mathcal{I}_{\mathcal{A}}}$ and
$F^{\mathcal{I}_{\mathcal{A}}}\not=V^{\mathcal{I}_{\mathcal{A}}}$, then output
‘$\mathcal{A}\models Q_{\Pi}$’ if there exists a rule ${\sf goal}\leftarrow
q\in\Pi$ such that $q^{\prime}$ is satisfied in $\mathcal{I}_{\mathcal{A}}$
for the query $q^{\prime}$ obtained from $q$ by removing every atom $P(y)$
from $q$ with $P$ a unary IDB. Otherwise output ‘$\mathcal{A}\not\models
Q_{\Pi}$’.

  4. (4)

If $F^{\mathcal{I}_{\mathcal{A}}}=V^{\mathcal{I}_{\mathcal{A}}}$ and
$T^{\mathcal{I}_{\mathcal{A}}}\not=V^{\mathcal{I}_{\mathcal{A}}}$, then output
‘$\mathcal{A}\models Q_{\Pi}$’ if there exists a rule ${\sf goal}\leftarrow
q\in\Pi$ or $P_{1}(x)\vee\cdots\vee P_{n}(x)\leftarrow q\in\Pi$ such that $q$
does not contain any IDB and $q$ is satisfied in $\mathcal{I}_{\mathcal{A}}$.
Otherwise output ‘$\mathcal{A}\not\models Q_{\Pi}$’.

  5. (5)

If none of the four cases above apply, obtain $\mathcal{A}^{\prime}$ from
$\mathcal{A}$ by removing all assertions using $T,F$, or $V$. Then
$\mathcal{A}^{\prime}\models\Pi$ iff $\mathcal{A}\models Q$, and we have
established the polynomial time reduction.

$\dashv$

The modification of $Q_{\Pi}$ needed to obtain an OMQC from
$(\mathcal{EL},{\sf N_{C}}\cup{\sf N_{R}},\text{BAQ})$ is the same as in the
proof of Theorem 30: the query $q_{\Pi}$ is a BUdtCQ and so we can replace it
with a query of the form $\exists x\,A(x)$: as the disjuncts of $q_{\Pi}$ are
of the form $\exists x\,q^{\prime}(x)$ with $q^{\prime}(x)$ a dtCQ, we can
take the $\mathcal{EL}$ concepts $C_{q^{\prime}}$ corresponding to
$q^{\prime}(x)$ and extend $\mathcal{T}_{\Pi}$ with $C_{q^{\prime}}\sqsubseteq
A$ for every such disjunct $\exists x\,q^{\prime}(x)$ of $q$.

It remains to show how one can modify $Q_{\Pi}$ to obtain an equivalent OMQC
$Q_{\Pi}^{\prime}$ from the language $(\text{DL-Lite}_{\mathcal{R}},{\sf
N_{C}}\cup{\sf N_{R}},\text{BUtCQ})$. First, to eliminate $\top$ on the left-
hand-side of CIs in $\mathcal{T}_{\Pi}$, we replace each CI $\top\sqsubseteq
C$ by the CIs $A\sqsubseteq C$, $\exists r\sqsubseteq C$, and $\exists
r^{-}\sqsubseteq C$ for any concept name $A\in\Sigma_{\Pi}$ and role name
$r\in\Sigma_{\Pi}$. Second, we employ the standard encoding of qualified
existential restrictions in $\text{DL-Lite}_{\mathcal{R}}$ by replacing
exhaustively any $B\sqsubseteq\exists r.D$ by $B\sqsubseteq\exists s$,
$\exists s^{-}\sqsubseteq A_{D}$, $A_{D}\sqsubseteq D$, and $s\sqsubseteq r$,
where $A_{D}$ is a fresh concept name and $s$ is a fresh role name. Let
$\mathcal{T}_{\Pi}^{\prime}$ be the resulting TBox. Then
$Q_{\Pi}^{\prime}=(\mathcal{T}_{\Pi}^{\prime},\Sigma_{\Pi},\Sigma_{\Pi},q_{\Pi})$
is as required.

From Theorems 34 and 35, we obtain the main result of this section.

######  Theorem 36.

  1. (1)

For every non-deterministic polynomial time Turing machine $M$ one can
construct a OMQC $Q$ in the languages $(\mathcal{EL},{\sf N_{C}}\cup{\sf
N_{R}},\text{BAQ})$ and $(\text{DL-Lite}_{\mathcal{R}},{\sf N_{C}}\cup{\sf
N_{R}},\text{BUtCQ})$ such that the evaluation problem for $Q$ and $M$’s word
problem are polynomial time reducible to each other.

  2. (2)

It is undecidable whether the evaluation problem for OMQCs in
$(\mathcal{EL},{\sf N_{C}}\cup{\sf N_{R}},\text{BAQ})$ and $(\text{DL-
Lite}_{\mathcal{R}},{\sf N_{C}}\cup{\sf N_{R}},\text{BUtCQ})$ is in PTime
(unless PTime =NP).

Note that Theorem 36 does not cover $\text{$\text{DL-Lite}$}_{\text{core}}$.
In fact, the computational status of the language $(\text{$\text{DL-
Lite}$}_{\text{core}},{\sf N_{C}}\cup{\sf N_{R}},\text{BUtCQ})$ remains open,
and in particular it remains open whether Theorem 36 can be strengthened to
this case.

##  9\. Quantifier-Free UCQs and FO-Rewritability

The results in the previous sections have shown that intractability comes
quickly when predicates are closed. The aim of this section is to identify a
useful OMQC language whose UCQs are guaranteed to be FO-rewritable. It turns
out that one can obtain such a language by combining $\text{DL-
Lite}_{\mathcal{R}}$ with quantifier-free UCQs, that is, unions of quantifier-
free CQs; we denote this class of queries with UqfCQ. Our main result is that
all OMQCs from the language $(\text{DL-Lite}_{\mathcal{R}},{\sf N_{C}}\cup{\sf
N_{R}},\text{UqfCQ})$ are FO-rewritable under the mild restriction that there
is no RI which requires an open role to be contained in a closed one. We
believe that this class of OMQCs is potentially relevant for practical
applications. Note that the query language SPARQL, which is used in many web
applications, is closely related to UqfCQs and, in fact, does not admit
existential quantification under its standard entailment regimes [28]. We also
prove that the restriction on RIs is needed for tractability, by constructing
a coNP-hard OMQC in $(\text{DL-Lite}_{\mathcal{R}},{\sf N_{C}}\cup{\sf
N_{R}},\text{UqfCQ})$.

######  Theorem 37.

Every OMQC $(\mathcal{T},\Sigma_{\mathsf{A}},\Sigma_{\mathsf{C}},q)$ from
$(\text{DL-Lite}_{\mathcal{R}},{\sf N_{C}}\cup{\sf N_{R}},\text{UqfCQ})$ such
that $\mathcal{T}$ contains no RI of the form $s\sqsubseteq r$ with ${\sf
sig}(s)\not\subseteq\Sigma_{\mathsf{C}}$ and ${\sf
sig}(r)\subseteq\Sigma_{\mathsf{C}}$ is FO-rewritable.

We first show that ABox consistency w.r.t.
$(\mathcal{T},\Sigma_{\mathsf{A}},\Sigma_{\mathsf{C}})$ is FO-rewritable, for
every $\text{DL-Lite}_{\mathcal{R}}$ TBox $\mathcal{T}$ not containing any RI
of the form $s\sqsubseteq r$ with ${\sf
sig}(s)\not\subseteq\Sigma_{\mathsf{C}}$ and ${\sf
sig}(r)\subseteq\Sigma_{\mathsf{C}}$. We make use of Theorem 1 and assume
w.l.o.g. that $\Sigma_{\mathsf{C}}=\Sigma_{\mathsf{A}}$. Let
$\mathsf{con}(\mathcal{T})$ be the set of all concept names in $\mathcal{T}$,
and all concepts $\exists r,\exists r^{-}$ such that $r$ is a role name that
occurs in $\mathcal{T}$. A _$\mathcal{T}$ -type_ is a set
$t\subseteq\mathsf{con}(\mathcal{T})$ such that for all
$B_{1},B_{2}\in\mathsf{con}(\mathcal{T})$:

  * •

if $B_{1}\in t$ and $\mathcal{T}\models B_{1}\sqsubseteq B_{2}$, then
$B_{2}\in t$;

  * •

if $B_{1}\in t$ and $\mathcal{T}\models B_{1}\sqsubseteq\neg B_{2}$, then
$B_{2}\notin t$.

A _$\mathcal{T}$ -typing_ is a set $T$ of $\mathcal{T}$-types. A _path in $T$_
is a sequence $t,r_{1},\ldots,r_{n}$ where $t\in T$, $\exists
r_{1},\dots,\exists r_{n}\in\mathsf{con}(\mathcal{T})$ use no predicates from
$\Sigma_{\mathsf{C}}$, $\exists r_{1}\in t$ and for $i\in\\{1,\ldots,n-1\\}$,
$\mathcal{T}\models\exists r_{i}^{-}\sqsubseteq\exists r_{i+1}$ and
$r_{i}^{-}\neq r_{i+1}$. The path is _$\Sigma_{\mathsf{C}}$ -participating_ if
for all $i\in\\{1,\dots,n-1\\}$, there is no $B\in\mathsf{con}(\mathcal{T})$
with $\mathsf{sig}(B)\subseteq\Sigma_{\mathsf{C}}$ and
$\mathcal{T}\models\exists r_{i}^{-}\sqsubseteq B$ while there is such a $B$
for $i=n$. A $\mathcal{T}$-typing $T$ is _$\Sigma_{\mathsf{C}}$ -realizable_
if for every $\Sigma_{\mathsf{C}}$-participating path $t,r_{1},\ldots,r_{n}$
in $T$, there is some $u\in T$ such that
$\\{B\in\mathsf{con}(\mathcal{T})\mid\mathcal{T}\models\exists
r^{-}_{n}\sqsubseteq B\\}\subseteq u$.

A $\mathcal{T}$-typing $T$ provides partial information about a model
$\mathcal{I}$ of $\mathcal{T}$ and a $\Sigma_{\mathsf{C}}$-ABox $\mathcal{A}$
by taking $T$ to contain the types that are realized in $\mathcal{I}$ by ABox
elements. $\Sigma_{\mathsf{C}}$-realizability then ensures that we can build
from $T$ a model that respects the closed predicates in $\Sigma_{\mathsf{C}}$.
To make this more precise, define a _$\mathcal{T}$ -decoration of_ a
$\Sigma_{\mathsf{C}}$-ABox $\mathcal{A}$ to be a mapping $f$ that assigns to
each $a\in\mathsf{Ind}(\mathcal{A})$ a $\mathcal{T}$-type $f(a)$ such that
$f(a)|_{\Sigma_{\mathsf{C}}}=t^{a}_{\mathcal{A}}|_{\Sigma_{\mathsf{C}}}$ where
$t^{a}_{\mathcal{A}}=\\{B\in\mathsf{con}(\mathcal{T})\mid a\in
B^{\mathcal{I}_{\mathcal{A}}}\\}$ and $S|_{\Sigma_{\mathsf{C}}}$ denotes the
restriction of the set $S$ of concepts to those members that only use
predicates from $\Sigma_{\mathsf{C}}$. For brevity, let
$R_{\Sigma_{\mathsf{C}}}=\\{s\sqsubseteq r\mid\mathcal{T}\models s\sqsubseteq
r\text{ and }\mathsf{sig}(s\sqsubseteq r)\subseteq\Sigma_{\mathsf{C}}\\}$.

######  Lemma 38.

A $\Sigma_{\mathsf{C}}$-ABox $\mathcal{A}$ is consistent w.r.t.
$(\mathcal{T},\Sigma_{\mathsf{C}})$ iff

  1. (1)

$\mathcal{A}$ has a $\mathcal{T}$-decoration $f$ whose image is a
$\Sigma$-realizable $\mathcal{T}$-typing and

  2. (2)

$s(a,b)\in\mathcal{A}$ and $s\sqsubseteq r\in R_{\Sigma}$ implies
$r(a,b)\in\mathcal{A}$.

######  Proof 9.1.

$(\Rightarrow)$ Let $\mathcal{I}$ be a model of $\mathcal{A}$ and
$\mathcal{T}$ that respects closed predicates $\Sigma_{\mathsf{C}}$. For each
$d\in\Delta^{\mathcal{I}}$, let
$t_{\mathcal{I}}^{d}=\\{B\in\mathsf{con}(\mathcal{T})\mid d\in
B^{\mathcal{I}}\\}$ and let $T_{\mathcal{I}}=\\{t_{\mathcal{I}}^{a}\mid
a\in\mathsf{Ind}(\mathcal{A})\\}$. We next show that the $\mathcal{T}$-typing
$T_{\mathcal{I}}$ is $\Sigma_{\mathsf{C}}$-realizable. Let
$t_{\mathcal{I}}^{a},r_{1},\ldots,r_{n}$ be a
$\Sigma_{\mathsf{C}}$-participating path in $T_{\mathcal{I}}$. Using
$\mathcal{I}$, we find a mapping
$g:\\{0,\ldots,n\\}\rightarrow\Delta^{\mathcal{I}}$ such that $g(0)=a$ and for
each $i\in\\{1,\ldots,n\\}$, we have

  * (a)

$(g(i-1),g(i))\in r_{i}^{\mathcal{I}}$,

  * (b)

$g(i)\in B^{\mathcal{I}}$ for all $B\in\mathsf{sub}(\mathcal{T})$ with
$\mathcal{T}\models\exists r^{-}_{i}\sqsubseteq B$.

By definition of $\Sigma_{\mathsf{C}}$-participating paths, there is some
$B^{\star}\in\mathsf{con}(\mathcal{T})$ with
$\mathsf{sig}(B^{\star})\subseteq\Sigma_{\mathsf{C}}$ such that
$\mathcal{T}\models\exists r_{n}^{-}\sqsubseteq B^{\star}$. By Point (b), we
obtain $g(n)\in{B^{\star}}^{\mathcal{I}}$. Since $\mathcal{I}$ is a model of
$\mathcal{A}$ and $\mathcal{T}$ that respects closed predicates
$\Sigma_{\mathsf{C}}$, we have $g(n)=b$ for some
$b\in\mathsf{Ind}(\mathcal{A})$. By Point (b), $\mathcal{T}\models\exists
r_{n}^{-}\sqsubseteq B$ implies $B\in t_{\mathcal{I}}^{b}$ for any
$B\in\mathsf{con}(\mathcal{T})$. Thus, $T_{\mathcal{I}}$ is
$\Sigma_{\mathsf{C}}$-realizable. Let $f(a)=t^{a}_{\mathcal{I}}$ for all
$a\in\mathsf{Ind}(\mathcal{A})$. It is clear that $f$ is a
$\mathcal{T}$-decoration of $\mathcal{A}$. The image of $f$ is
$T_{\mathcal{I}}$, thus a $\Sigma_{\mathsf{C}}$-realizable
$\mathcal{T}$-typing. Hence we conclude that $\mathcal{A}$ satisfies Point (1)
from Lemma 38. Point (2) holds by the fact that $\mathcal{I}$ is a model of
$\mathcal{T}$ and $\mathcal{A}$ that respects closed predicates
$\Sigma_{\mathsf{C}}$.

$(\Leftarrow)$ Suppose that $\mathcal{A}$ satisfies Points 1 and 2 from Lemma
38 and let $f$ be a $\mathcal{T}$-decoration of $\mathcal{A}$ whose image $T$
is a $\Sigma_{\mathsf{C}}$-realizable $\mathcal{T}$-typing. Our goal is to
construct a model $\mathcal{I}$ of $\mathcal{T}$ and $\mathcal{A}$ that
respects closed predicates $\Sigma_{\mathsf{C}}$ as the limit of a sequence of
interpretations $\mathcal{I}_{0},\mathcal{I}_{1},\dots$. The domains of these
interpretations consist of the individual names from
$\mathsf{Ind}(\mathcal{A})$ and of paths in $T$ that are not
$\Sigma_{\mathsf{C}}$-participating. The construction will ensure that for all
$i$, we have

  1. (a)

for all $a\in\mathsf{Ind}(\mathcal{A})$, we have
$t^{a}_{\mathcal{I}_{i}}\subseteq f(a)$;

  2. (b)

for all $p=t,r_{1},\dots,r_{n}\in\Delta^{\mathcal{I}_{i}}$, we have
$t^{p}_{\mathcal{I}_{i}}\subseteq\\{B\in\mathsf{con}(\mathcal{T})\mid\mathcal{T}\models\exists
r_{n}^{-}\sqsubseteq B\\}$.

Define $\mathcal{I}_{0}=(\Delta^{\mathcal{I}_{0}},\cdot^{\mathcal{I}_{0}})$
where

$\displaystyle\Delta^{\mathcal{I}_{0}}$ $\displaystyle=$
$\displaystyle\mathsf{Ind}(\mathcal{A})$ $\displaystyle r^{\mathcal{I}_{0}}$
$\displaystyle=$ $\displaystyle\\{(a,b)\mid s(a,b)\in\mathcal{A}\text{ and
}\mathcal{T}\models s\sqsubseteq r\\}$ $\displaystyle A^{\mathcal{I}_{0}}$
$\displaystyle=$ $\displaystyle\\{a\mid A\in f(a)\\}$

To construct $\mathcal{I}_{i+1}$ from $\mathcal{I}_{i}$, choose
$d\in\Delta^{\mathcal{I}_{i}}$ and $\exists s\in\mathsf{con}(\mathcal{T})$
such that $\mathsf{sig}(s)\cap\Sigma_{\mathsf{C}}=\emptyset$,
$\mathcal{T}\models\bigsqcap t^{d}_{\mathcal{I}_{i}}\sqsubseteq\exists s$ and
there is no $(d,e)\in s^{\mathcal{I}_{i}}$. Let $q=f(a),s$ if
$d=a\in\mathsf{Ind}(\mathcal{A})$ and $q=d,s$ otherwise. Using Conditions (a)
and (b), it is easy to verify that $q$ is a path in $T$. If $q$ is not
$\Sigma_{\mathsf{C}}$-participating, then define $\mathcal{I}_{i+1}$ as
follows:

$\displaystyle\Delta^{\mathcal{I}_{i+1}}$ $\displaystyle=$
$\displaystyle\Delta^{\mathcal{I}_{i}}\uplus\\{q\\}$ $\displaystyle
r^{\mathcal{I}_{i+1}}$ $\displaystyle=$
$\displaystyle\begin{cases}r^{\mathcal{I}_{i}}\cup\\{(d,q)\\}&\text{if
}\mathcal{T}\models s\sqsubseteq r\\\
r^{\mathcal{I}_{i}}&\text{otherwise}\end{cases}$ $\displaystyle
A^{\mathcal{I}_{i+1}}$ $\displaystyle=$
$\displaystyle\begin{cases}A^{\mathcal{I}_{i}}\cup\\{q\\}&\text{if
}\mathcal{T}\models\exists s^{-}\sqsubseteq A\\\ A^{\mathcal{I}_{i}}&\text{
otherwise.}\end{cases}$

If $q$ is $\Sigma_{\mathsf{C}}$-participating, then by the fact that $T$ is
$\Sigma_{\mathsf{C}}$-realizable, there is some $t\in T$ such that
$\\{B\in\mathsf{con}(\mathcal{T})\mid\mathcal{T}\models\exists
s^{-}\sqsubseteq B\\}\subseteq t$. We find a $b\in\mathsf{Ind}(\mathcal{A})$
with $t=f(b)$. Define $\mathcal{I}_{i+1}$ as follows:

$\displaystyle\Delta^{\mathcal{I}_{i+1}}$ $\displaystyle=$
$\displaystyle\Delta^{\mathcal{I}_{i}}$ $\displaystyle r^{\mathcal{I}_{i+1}}$
$\displaystyle=$
$\displaystyle\begin{cases}r^{\mathcal{I}_{i}}\cup\\{(d,b)\\}&\text{if
}\mathcal{T}\models s\sqsubseteq r\\\
r^{\mathcal{I}_{i}}&\text{otherwise}\end{cases}$ $\displaystyle
A^{\mathcal{I}_{i+1}}$ $\displaystyle=$ $\displaystyle A^{\mathcal{I}_{i}}.$

Assume that the choice of $d\in\Delta^{\mathcal{I}_{i}}$ and $\exists
s\in\mathsf{con}(\mathcal{T})$ is fair so that every possible combination of
$d$ and $\exists s$ is eventually chosen. Let $\mathcal{I}$ be the limit of
the sequence $\mathcal{I}_{0},\mathcal{I}_{1},\dots$ (cf. the proof of Lemma
4). We claim that $\mathcal{I}$ is a model of $\mathcal{T}$ and $\mathcal{A}$
that respects closed predicates $\Sigma_{\mathsf{C}}$. By definition of
$\mathcal{I}_{0}$ and of $\mathcal{T}$-decorations, it is straightforward to
see that $\mathcal{I}\models\mathcal{A}$. Moreover, the RIs in $\mathcal{T}$
are clearly satisfied. To show that the CIs are satisfied as well, it is
straightforward to first establish the following strengthenings of Conditions
(a) and (b) above (details omitted):

  1. (a′)

for all $a\in\mathsf{Ind}(\mathcal{A})$, we have $t^{a}_{\mathcal{I}}=f(a)$;

  2. (b′)

for all $p=t,r_{1}\dots,r_{n}\in\Delta^{\mathcal{I}}$, we have
$t^{p}_{\mathcal{I}_{i}}=\\{B\in\mathsf{con}(\mathcal{T})\mid\mathcal{T}\models\exists
r_{n}^{-}\sqsubseteq B\\}$.

Let $a\in\mathsf{Ind}(\mathcal{A})$, $a\in B_{1}^{\mathcal{I}}$, and
$B_{1}\sqsubseteq B_{2}\in\mathcal{T}$ (or $B_{1}\sqsubseteq\neg
B_{2}\in\mathcal{T}$). Then by Condition $(a^{\prime})$ and since $f(a)$ is a
$\mathcal{T}$-type, we have $a\in B_{2}^{\mathcal{I}}$ (resp. $a\not\in
B_{2}^{\mathcal{I}}$). Now let $d=t,r_{1},\ldots,r_{n}$ be a path. First
suppose $d\in B_{1}^{\mathcal{I}}$ and $B_{1}\sqsubseteq B_{2}\in\mathcal{T}$.
By Condition (b′), we conclude that $\mathcal{T}\models\exists
r_{n}^{-}\sqsubseteq B_{1}$. Since $B_{1}\sqsubseteq B_{2}\in\mathcal{T}$, it
follows that $\mathcal{T}\models\exists r_{n}^{-}\sqsubseteq B_{2}$ and thus
again by the property above, $d\in B_{2}^{\mathcal{I}}$. Finally, suppose
$d\in B_{1}^{\mathcal{I}}$ and $B_{1}\sqsubseteq\neg B_{2}\in\mathcal{T}$. By
Condition (b′) and $B_{1}\sqsubseteq\neg B_{2}\in\mathcal{T}$, we conclude
$\mathcal{T}\models\exists r_{n}^{-}\sqsubseteq\neg B_{2}$. For a proof by
contradiction assume that $d\in B_{2}^{\mathcal{I}}$ and thus
$\mathcal{T}\models\exists r_{n}^{-}\sqsubseteq B_{2}$ and we already have
$\mathcal{T}\models\exists r_{n}^{-}\sqsubseteq\neg B_{2}$. Hence
$\mathcal{T}\models\exists r^{-}_{n}\sqsubseteq\bot$. But then
$\mathcal{T}\models\exists r_{n}\sqsubseteq\bot$. It follows that
$\mathcal{T}\models\exists r_{1}\sqsubseteq\bot$. This implies in particular
$\mathcal{T}\models\exists r_{1}\sqsubseteq\exists r_{1}$ and
$\mathcal{T}\models\exists r_{1}\sqsubseteq\neg\exists r_{1}$. By definition
we have $\exists r_{1}\in f(a)$ and by $\mathcal{T}\models\exists
r_{1}\sqsubseteq\neg\exists r_{1}$ and the fact $f(a)$ is a
$\mathcal{T}$-type, we obtain $\exists r_{1}\not\in f(a)$, i.e., a
contradiction. Hence $d\not\in B_{2}^{\mathcal{I}}$ which finishes the proof
that $\mathcal{I}\models\mathcal{T}$.

What remains to be shown are the following properties:

  * •

for all $A\in\Sigma_{\mathsf{C}}$, $A^{\mathcal{I}}=\\{a\mid
A(a)\in\mathcal{A}\\}$;

  * •

for all $r\in\Sigma_{\mathsf{C}}$, $r^{\mathcal{I}}=\\{(a,b)\mid
r(a,b)\in\mathcal{A}\\}$.

We show for each $i\geq 0$ that $\mathcal{I}_{i}$ satisfies the properties
above.

Suppose $i=0$. First let $A(a)\in\mathcal{A}$ with $A\in\Sigma_{\mathsf{C}}$.
Then $a\in A^{\mathcal{I}_{0}}$ by definition of $\mathcal{I}_{0}$. For the
other direction, let $a\in A^{\mathcal{I}_{0}}$ for an
$A\in\Sigma_{\mathsf{C}}$. Then $A\in f(a)$. The definition of
$\mathcal{T}$-decorations yields $A\in t^{a}_{\mathcal{A}}$, and thus
$A(a)\in\mathcal{A}$. Now let $r(a,b)\in\mathcal{A}$ with
$r\in\Sigma_{\mathsf{C}}$. Then $(a,b)\in r^{\mathcal{I}_{0}}$ by definition
of $\mathcal{I}_{0}$. For the other direction, let $(a,b)\in
r^{\mathcal{I}_{0}}$ for some $r\in\Sigma_{\mathsf{C}}$. Then there is some
role $s$ such that $s(a,b)\in\mathcal{A}$ and $\mathcal{T}\models s\sqsubseteq
r$. By the adopted restriction on the allowed RIs, it follows that
$\mathsf{sig}(s)\subseteq\Sigma$. This yields $r(a,b)\in\mathcal{A}$ since
$\mathcal{A}$ satisfies Point 2 of Lemma 38.

For $i>0$, we show that the extension of $\Sigma_{\mathsf{C}}$-predicates is
not modified when constructing $\mathcal{I}_{i+1}$ from $\mathcal{I}_{i}$.
Indeed, assume that $\mathcal{I}_{i+1}$ was obtained from $\mathcal{I}_{i}$ by
choosing $d\in\Delta^{\mathcal{I}_{i}}$ and $\exists
s\in\mathsf{con}(\mathcal{T})$ and let $q=f(a),s$ if
$d=a\in\mathsf{Ind}(\mathcal{A})$ and $q=d,s$ otherwise. Then
$\mathsf{sig}(s)\cap\Sigma_{\mathsf{C}}=\emptyset$ and by the restriction on
RIs, $\mathsf{sig}(r)\cap\Sigma_{\mathsf{C}}=\emptyset$ for any role $r$ with
$\mathcal{T}\models s\sqsubseteq r$. Consequently, none of the role names
modified in the construction of $\mathcal{I}_{i+1}$ is from
$\Sigma_{\mathsf{C}}$ (no matter whether $q$ is
$\Sigma_{\mathsf{C}}$-participating or not). In the case where $q$ is
$\Sigma_{\mathsf{C}}$-participating, there is nothing else to show. If $q$ is
not $\Sigma_{\mathsf{C}}$-participating, then each concept name $A$ with
$\mathcal{T}\models\exists s^{-}\sqsubseteq A$ is not from
$\Sigma_{\mathsf{C}}$. Thus also none of the concept names modified in the
construction of $\mathcal{I}_{i+1}$ is from $\Sigma_{\mathsf{C}}$.

We now construct the required FOQ. For all role names $r$ and variables $x,y$,
define $\psi_{r}(x,y)=r(x,y)$ and $\psi_{r^{-}}(x,y)=r(y,x)$. For all concept
names $A$ and roles $r$, define $\psi_{A}(x)=A(x)$ and $\psi_{\exists
r}(x)=\exists y\,\psi_{r}(x,y)$. For each $\mathcal{T}$-type $t$, set

$\psi_{t}(x)=\bigwedge_{B\in\mathsf{con}(\mathcal{T})\setminus t\text{ with
}\mathsf{sig}(B)\subseteq\Sigma_{\mathsf{C}}}\neg\psi_{B}(x)\land\bigwedge_{B\in
t\text{ with }\mathsf{sig}(B)\subseteq\Sigma_{\mathsf{C}}}\psi_{B}(x)$

and for each $\mathcal{T}$-typing $T=\\{t_{1},\dots,t_{n}\\}$, set

$\psi_{T}=\forall x\bigvee_{t\in T}\psi_{t}(x)\land\exists x_{1}\cdots\exists
x_{n}(\bigwedge_{i\neq j}x_{i}\neq
x_{j}\land\bigwedge_{i}\psi_{t_{i}}(x_{i})).$

Let $\mathcal{R}$ be the set of all $\Sigma_{\mathsf{C}}$-realizable typings
and set

$\Psi_{\mathcal{T},\Sigma_{\mathsf{C}}}=\bigvee_{T\in\mathcal{R}}\psi_{T}\wedge\bigwedge_{s\sqsubseteq
r\in R_{\Sigma_{\mathsf{C}}}}\forall x\forall
y(\psi_{s}(x,y)\rightarrow\psi_{r}(x,y)).$

Note that the two conjuncts of $\Psi_{\mathcal{T},\Sigma_{\mathsf{C}}}$
express exactly Points 1 and 2 of Lemma 38. We have thus shown the following.

######  Proposition 39.

A $\Sigma_{\mathsf{C}}$-ABox $\mathcal{A}$ is consistent w.r.t.
$(\mathcal{T},\Sigma_{\mathsf{C}})$ iff
$\mathcal{I}_{\mathcal{A}}\models\Psi_{\mathcal{T},\Sigma_{\mathsf{C}}}$.

The next step is to construct an FO-rewriting of
$Q=(\mathcal{T},\Sigma_{\mathsf{C}},\Sigma_{\mathsf{C}},q)$ over
$\Sigma_{\mathsf{C}}$-ABoxes that are consistent w.r.t.
$(\mathcal{T},\Sigma_{\mathsf{C}})$. Whereas the FO-rewriting
$\Psi_{\mathcal{T},\Sigma_{\mathsf{C}}}$ above is Boolean and identifies
ABoxes that have a common model with $\mathcal{T}$ respecting closed
predicates $\Sigma_{\mathsf{C}}$, we now aim to construct a FOQ
$\Phi_{Q}(\vec{x})$ such that for all $\Sigma_{\mathsf{C}}$-ABoxes
$\mathcal{A}$ consistent w.r.t. $(\mathcal{T},\Sigma_{\mathsf{C}})$ and
$\vec{a}\in\mathsf{Ind}(\mathcal{A})$, we have
$\mathcal{I}_{\mathcal{A}}\models\Phi_{Q}(\vec{a})$ iff $\mathcal{A}\models
Q(\vec{a})$. The desired FO-rewriting of $Q$ is then constructed as
$\neg\Psi_{\mathcal{T},\Sigma_{\mathsf{C}}}\vee\Phi_{Q}(\vec{x})$. The
construction of $\Phi_{Q}(\vec{x})$ is based on an extended notion of
$\mathcal{T}$-typing called _$\mathcal{T},q$ -typing_ that provides partial
information about a model $\mathcal{I}$ of $\mathcal{T}$ and a
$\Sigma_{\mathsf{C}}$-ABox $\mathcal{A}$ respecting $\Sigma_{\mathsf{C}}$
which avoids an assignment from $\vec{x}$ to certain individual names
$\vec{a}$.

Let $q=\bigvee_{i\in I}q_{i}$ with answer variables
$\vec{x}=x_{1},\ldots,x_{n}$. A $\mathcal{T},q$-_typing_ $T$ is a quadruple
$(\sim,f_{0},\Gamma,\Delta)$ where

  * •

$\sim$ is an equivalence relation on $\\{x_{1},\ldots,x_{n}\\}$;

  * •

$f_{0}$ is a function that assigns a $\mathcal{T}$-type $f_{0}(x_{i})$ to each
$x_{i}$, $1\leq i\leq n$, such that $f_{0}(x_{i})=f_{0}(x_{j})$ when
$x_{i}\sim x_{j}$;

  * •

$\Gamma$ is a $\mathcal{T}$-typing;

  * •

$\Delta$ is a set of atoms $s(x_{i},x_{j})$, $s\in\Sigma_{\mathsf{C}}$, such
that $s(x_{i},x_{j})\in\Delta$ iff $s(x_{i}^{\prime},x_{j}^{\prime})\in\Delta$
when $x_{i}\sim x_{i}^{\prime}$ and $x_{j}\sim x_{j}^{\prime}$.

Intuitively, $\sim$ describes the answer variables that are identified by an
assignment $\pi$ for $q$ in an ABox $\mathcal{A}$, $f_{0}(x_{i})$ describes
the $\mathcal{T}$-type of the ABox individual name $\pi(x_{i})$, $\Gamma$
describes the $\mathcal{T}$-types of ABox individual names that are not in the
range of $\pi$, and $\Delta$ fixes role relationships that do _not_ hold
between the $\pi(x_{i})$. Let $X=\\{\alpha_{i}\mid i\in I\\}$ be a set of
atoms with $\alpha_{i}$ in $q_{i}$ for all $i\in I$. Then $T$ _avoids $X$_ if
the following conditions hold:

1\. if $A\in f_{0}(x)$, then $A(x)\not\in X$ for any atom $A(x)$;

2\. if $\exists s\in f_{0}(x)$, then (i)
$S=\\{B\in\mathsf{con}(\mathcal{T})\mid\mathcal{T}\models\exists
s^{-}\sqsubseteq B\\}$ contains no predicate from $\Sigma_{\mathsf{C}}$ or
(ii) there is a $u\in\Gamma$ such that $S\subseteq u$ or (iii) there is a $y$
such that $S\subseteq f_{0}(y)$ and there are no $x^{\prime}\sim x$ and
$y^{\prime}\sim y$ such that $r(x^{\prime},y^{\prime})\in X$ or
$r(y^{\prime},x^{\prime})\in X$ and $\mathcal{T}\models s\sqsubseteq r$ or
$\mathcal{T}\models s\sqsubseteq r^{-}$, respectively;

3\. if $r(x,y)\in X$, then $\Delta$ contains all $s(x,y)$ with
$s\in\Sigma_{\mathsf{C}}$ and $\mathcal{T}\models s\sqsubseteq r$ and all
$s(y,x)$ with $s\in\Sigma_{\mathsf{C}}$ and $\mathcal{T}\models
s^{-}\sqsubseteq r$.

$T$ _avoids_ $q$ if it avoids some set $\\{\alpha_{i}\mid i\in I\\}$ with
$\alpha_{i}$ in $q_{i}$ for all $i\in I$. We use $\mathsf{tp}(T)$ to denote
the $\mathcal{T}$-typing $\Gamma$ extended with all $\mathcal{T}$-types in the
range of $f_{0}$. Let $\mathcal{A}$ be a $\Sigma_{\mathsf{C}}$-ABox and let
$\pi$ assign individual names $\pi(x_{i})$ to $x_{i}$, $1\leq i\leq n$, such
that $\pi(x_{i})=\pi(x_{j})$ iff $x_{i}\sim x_{j}$. A $\mathcal{T}$-decoration
$f$ of $\mathcal{A}$ _realizes_ $T=(\sim,f_{0},\Gamma,\Delta)$ _using_ $\pi$
iff $\mathsf{tp}(T)$ is the range of $f$, $f_{0}(x_{i})=f(\pi(x_{i}))$ for
$1\leq i\leq n$, and $r(\pi(x_{i}),\pi(x_{j}))\not\in\mathcal{A}$ if
$r(x_{i},x_{j})\in\Delta$ for $1\leq i,j\leq n$ and all
$r\in\Sigma_{\mathsf{C}}$. $\mathcal{A}$ _realizes_ $T$ using $\pi$ if there
exists a $\mathcal{T}$-decoration $f$ that realizes $T$ using $\pi$.

######  Lemma 40.

Let $\mathcal{A}$ be a $\Sigma_{\mathsf{C}}$-ABox that is consistent w.r.t.
$(\mathcal{T},\Sigma_{\mathsf{C}})$. Then $\mathcal{A}\not\models
Q(\pi(x_{1}),\ldots,\pi(x_{n}))$ iff $\mathcal{A}$ realizes some
$\mathcal{T},q$-typing $T$ using $\pi$ that avoids $q$ and such that
$\mathsf{tp}(T)$ is $\Sigma_{\mathsf{C}}$-realizable.

######  Proof 9.2.

The proof is a modification of the proof of Lemma 38. We only sketch the
differences.

($\Rightarrow$) Let $\mathcal{A}\not\models Q(\pi(x_{1}),\ldots,\pi(x_{n}))$.
We start with a model $\mathcal{I}$ of $\mathcal{T}$ and $\mathcal{A}$ that
respects closed predicates $\Sigma_{\mathsf{C}}$ such that
$\mathcal{I}\not\models q(\pi(x_{1}),\ldots,\pi(x_{n}))$. Read off a
$\mathcal{T},q$-typing

$T_{\mathcal{I}}=(\sim,f_{0},\Gamma,\Delta)$

from $\mathcal{I}$ by setting

  * •

$x_{i}\sim x_{j}$ iff $\pi(x_{i})=\pi(x_{j})$;

  * •

$f_{0}(x_{i})=t^{\pi(x_{i})}_{\mathcal{I}}$ for all $1\leq i\leq n$;

  * •

$\Gamma=\\{t^{a}_{\mathcal{I}}\mid
a\in\mathsf{Ind}(\mathcal{A})\\}\setminus\\{\pi(x_{1}),\ldots,\pi(x_{n})\\}$;

  * •

$\Delta=\\{r(x_{i},x_{j})\mid
r\in\Sigma_{\mathsf{C}},r(\pi(x_{i}),\pi(x_{j}))\not\in\mathcal{A}\\}$.

We show that $T_{\mathcal{I}}$ avoids $q=\bigvee_{i\in I}q_{i}$. Since
$\mathcal{I}\not\models q(\pi(x_{1}),\ldots,\pi(x_{n}))$ we find for every
$i\in I$ an atom $\alpha_{i}$ in $q_{i}$ such that
$\mathcal{I}\not\models\alpha_{i}(\pi(x_{1}),\ldots,\pi(x_{n}))$. We show that
$T_{\mathcal{I}}$ avoids $X=\\{\alpha_{i}\mid i\in I\\}$. We distinguish the
following cases:

  * •

Let $A(x)\in X$. Then $A\not\in t^{\pi(x)}_{\mathcal{I}}$ and so $A\not\in
f_{0}(x)$, as required.

  * •

Let $\exists s\in f_{0}(x)$. Then $\exists s\in t^{\pi(x)}_{\mathcal{I}}$.
Thus, there exists $d\in\Delta^{\mathcal{I}}$ such that $(\pi(x),d)\in
s^{\mathcal{I}}$. If
$d\in\Delta^{\mathcal{I}}\setminus\mathsf{Ind}(\mathcal{A})$, then
$\mathsf{sig}(B)\cap\Sigma_{\mathsf{C}}=\emptyset$ for all $B\in
t^{d}_{\mathcal{I}}$. Thus (i) holds. If
$d\in\mathsf{Ind}(\mathcal{A})\setminus\\{\pi(x_{1}),\ldots,\pi(x_{n})\\}$,
then (ii) holds. Now assume that $d=\pi(y)$ for some
$y\in\\{\pi(x_{1}),\ldots,\pi(x_{n})\\}$. Then $y$ satisfies the conditions
for (iii).

  * •

Let $r(x,y)\in X$. Then $(\pi(x),\pi(y))\not\in r^{\mathcal{I}}$. Hence
$(\pi(x),\pi(y))\not\in s^{\mathcal{I}}$ for any $s\in\Sigma_{\mathsf{C}}$
with $\mathcal{T}\models s\sqsubseteq r$. Thus $s(x,y)\in\Delta$ for any such
$s$. Moreover, $(\pi(y),\pi(x))\not\in s^{\mathcal{I}}$ for any
$s\in\Sigma_{\mathsf{C}}$ with $\mathcal{T}\models s^{-}\sqsubseteq r$. Thus
$s(y,x)\in\Delta$ for any such $s$.

($\Leftarrow$) Assume that a $\Sigma_{\mathsf{C}}$-Abox $\mathcal{A}$ that is
consistent w.r.t. $(\mathcal{T},\Sigma_{\mathsf{C}})$ realizes some
$\mathcal{T},q$-typing $T=(\sim,f_{0},\Gamma,\Delta)$ using $\pi$ that avoids
$q$. Assume $f$ is a $\mathcal{T},q$-decoration of $\mathcal{A}$ that realizes
$T$ using $\pi$. Let $X=\\{\alpha_{i}\mid i\in I\\}$ with $\alpha_{i}$ in
$q_{i}$ such that $T$ avoids $X$ using $\pi$. We construct a model
$\mathcal{I}$ of $\mathcal{A}$ and $\mathcal{T}$ that respects closed
predicates $\Sigma_{\mathsf{C}}$ such that
$\mathcal{I}\not\models\alpha_{i}[\pi(x_{1}),\ldots,\pi(x_{n})]$ for $i\in I$.
We build $\mathcal{I}$ as in the proof of Lemma 38 based on $\mathsf{tp}(T)$.
Some care is required in the construction of $\mathcal{I}_{i+1}$. Assume
$\mathcal{I}_{i}$ has been constructed. Choose $d\in\Delta^{\mathcal{I}_{i}}$
and $\exists s\in\mathsf{con}(\mathcal{T})$ such that
$\mathsf{sig}(s)\cap\Sigma_{\mathsf{C}}=\emptyset$,
$\mathcal{T}\models\bigsqcap t^{d}_{\mathcal{I}_{i}}\sqsubseteq\exists s$ and
there is no $(d,e)\in s^{\mathcal{I}_{i}}$. If
$d\not\in\\{\pi(x_{1}),\ldots,\pi(x_{n})\\}$ or
$\\{B\in\mathsf{con}(\mathcal{T})\mid\mathcal{T}\models\exists
s^{-}\sqsubseteq B\\}$ does not contain a $B$ with
$\mathsf{sig}(B)\subseteq\Sigma_{\mathsf{C}}$ proceed as in the proof of Lemma
38. Now assume that $d=\pi(x)$. In the proof of Lemma 38 we chose an
_arbitrary_ $b\in\mathsf{Ind}(\mathcal{A})$ with
$\\{B\in\mathsf{con}(\mathcal{T})\mid\exists s^{-}\sqsubseteq B\\}\subseteq t$
and $t=f(b)$ and added $(a,b)$ to $r^{\mathcal{I}_{i+1}}$ whenever
$\mathcal{T}\models s\sqsubseteq r$. Since we want to refute all atoms
$\alpha_{i}(\pi(x_{1}),\ldots,\pi(x_{n}))$ with $i\in I$, we now have to
choose $b$ more carefully. If there exists
$b\in\mathsf{Ind}(\mathcal{A})\setminus\\{\pi(x_{1}),\ldots,\pi(x_{n})\\}$
with $\\{B\in\mathsf{con}(\mathcal{T})\mid\exists s^{-}\sqsubseteq
B\\}\subseteq t$ and $t=f(b)$, then we choose such a $b$ and proceed as in
Lemma 38. Otherwise, since $f$ is a $\mathcal{T},q$-decoration of
$\mathcal{A}$ that realizes $T$ using $\pi$ and avoids $X$, there is $y$ such
that $\\{B\in\mathsf{con}(\mathcal{T})\mid\mathcal{T}\models\exists
s^{-}\sqsubseteq B\\}\subseteq f_{0}(y)$ such that there is no $\alpha_{i}\in
X$ of the form $t(x^{\prime},y^{\prime})$ or $t(y^{\prime},x^{\prime})$ with
$x^{\prime}\sim x$ and $y^{\prime}\sim y$ such that $\mathcal{T}\models
s\sqsubseteq t$ or $\mathcal{T}\models s\sqsubseteq t^{-}$, respectively. We
set $b=\pi(y)$ and proceed as in the proof of Lemma 38.

The resulting interpretation $\mathcal{I}$ is a model of $\mathcal{T}$ and
$\mathcal{A}$ that respects closed predicates $\Sigma_{\mathsf{C}}$. Moreover
$\mathcal{I}\not\models\alpha_{i}(\pi(x_{1}),\ldots,\pi(x_{n}))$ for all $i\in
I$. Thus, $\mathcal{I}\not\models q(\pi(x_{1}),\ldots,\pi(x_{n}))$, as
required.

We now construct the actual rewriting $\Phi_{Q}(\vec{x})$. For every
$\mathcal{T},q$-typing $T=(\sim,f_{0},\Gamma,\Delta)$ with
$\Gamma=\\{t_{1},\ldots,t_{k}\\}$ let $\Psi_{T}(\vec{x})$ be the conjunction
of the following:

$\bigwedge_{1\leq i\leq n}\psi_{f_{0}(x_{i})}(x_{i})\wedge\bigwedge_{x_{i}\sim
x_{j}}(x_{i}=x_{j})\wedge\bigwedge_{x_{i}\not\sim x_{j}}(x_{i}\not=x_{j})$
$\bigwedge_{r(x_{i},x_{j})\in\Delta}\neg r(x_{i},x_{j})\wedge\forall
y(\bigwedge_{1\leq i\leq
n}(y\not=x_{i})\rightarrow\bigvee_{t\in\Gamma}\psi_{t}(y))$ $\exists
y_{1}\cdots\exists y_{k}(\bigwedge_{j\neq i}y_{j}\neq
y_{i}\wedge\bigwedge_{j\leq k,i\leq n}x_{i}\neq y_{j}\wedge\bigwedge_{j\leq
k}\psi_{t_{j}}(y_{j}))$

Then $\Phi_{Q}(\vec{x})$ is the conjunction over all $\neg\Psi_{T}(\vec{x})$
such that $T$ avoids $q$ and $\mathsf{tp}(T)$ is
$\Sigma_{\mathsf{C}}$-realizable.

######  Proposition 41.

Let $\mathcal{A}$ be a $\Sigma_{\mathsf{C}}$-ABox that is consistent w.r.t.
$(\mathcal{T},\Sigma_{\mathsf{C}})$. Then $\mathcal{A}\models Q(\vec{a})$ iff
$\mathcal{I}_{\mathcal{A}}\models\Phi_{Q}(\vec{a})$, for all $\vec{a}$ in
$\mathsf{Ind}(\mathcal{A})$.

######  Proof 9.3.

Let $\vec{a}=(a_{1},\ldots,a_{n})$. Assume $\mathcal{A}\not\models
Q(a_{1},\ldots,a_{n})$. Let $\pi(x_{i})=a_{i}$ for $1\leq i\leq n$. By Lemma
40, $\mathcal{A}$ realizes some $\mathcal{T},q$-typing $T$ using $\pi$ that
avoids $q$ such that ${\sf tp}(T)$ is $\Sigma_{\mathsf{C}}$-realizable. It is
readily checked that
$\mathcal{I}_{\mathcal{A}}\models\Psi_{T}(\pi_{1}(x_{1}),\ldots,\pi(x_{n}))$.
Thus, $\mathcal{I}_{\mathcal{A}}\not\models\Phi_{Q}(a_{1},\ldots,a_{n})$

Conversely, assume that
$\mathcal{I}_{\mathcal{A}}\not\models\Phi_{Q}(a_{1},\ldots,a_{n})$. Take a
$\mathcal{T},q$-typing $T$ that avoids $q$ such that ${\sf tp}(T)$ is
$\Sigma_{\mathsf{C}}$-realizable and
$\mathcal{I}_{\mathcal{A}}\models\Psi_{T}(a_{1},\ldots,a_{n})$. Let
$\pi(x_{i})=a_{i}$ for $1\leq i\leq n$. It is readily checked that
$\mathcal{A}$ realizes $T$ using $\pi$. Thus $\mathcal{A}\not\models
Q(a_{1},\ldots,a_{n})$, by Lemma 40.

This finishes the proof of Theorem 37.

We now show that without the restriction on RIs adopted in Theorem 37, OMQCs
from $(\text{DL-Lite}_{\mathcal{R}},{\sf N_{C}}\cup{\sf N_{R}},\text{UqfCQ})$
are no longer FO-rewritable. In fact, we prove the following, slightly
stronger result by reduction from propositional satisfiability.

######  Theorem 42.

There is a $\text{DL-Lite}_{\mathcal{R}}$ TBox with closed predicates
$(\mathcal{T},\Sigma_{\mathsf{C}})$ such that ABox consistency w.r.t.
$(\mathcal{T},\Sigma_{\mathsf{C}})$ is NP-complete.

######  Proof 9.4.

The proof is by reduction of the satisfiability problem for propositional
formulas in conjunctive normal form (CNF). Consider a propositional formula in
CNF $\varphi=c_{1}\wedge\cdots\wedge c_{n}$, where each $c_{i}$ is a
disjunction of literals. We write $\ell\in c_{i}$ if $\ell$ is a disjunct in
$c_{i}$. Let $x_{1},\ldots,x_{m}$ be the propositional variables in $\varphi$.
Define an ABox $\mathcal{A}_{\varphi}$ with individual names
$c_{1},\ldots,c_{n}$ and $x_{i}^{\top}$, $x_{i}^{\bot}$, $x_{i}^{{\sf aux}}$
for $1\leq i\leq m$, a concept name $A$, and role names $r,r^{\prime}$ as the
following set of assertions:

  * •

$r(c_{i},x_{j}^{\top})$, for all $x_{j}\in c_{i}$ and $1\leq i\leq n$;

  * •

$r(c_{i},x_{j}^{\bot})$, for all $\neg x_{j}\in c_{i}$ and $1\leq i\leq n$;

  * •

$r^{\prime}(x_{j}^{\top},x_{j}^{\bot})$, $r^{\prime}(x_{j}^{\bot},x_{j}^{{\sf
aux}})$, for $1\leq j\leq m$;

  * •

$A(c_{i})$, for $1\leq i\leq n$.

Let $s$ and $s^{\prime}$ be additional role names and let

$\mathcal{T}=\\{s\sqsubseteq r,A\sqsubseteq\exists s,\exists
s^{-}\sqsubseteq\exists s^{\prime},s^{\prime}\sqsubseteq r^{\prime},\exists
s^{\prime-}\sqcap\exists s^{-}\sqsubseteq\bot\\}.$

Let $\Sigma_{\mathsf{C}}=\\{A,r,r^{\prime}\\}$. We show that
$\mathcal{A}_{\varphi}$ is consistent w.r.t.
$(\mathcal{T},\Sigma_{\mathsf{C}})$ iff $\varphi$ is satisfiable. Assume first
that $\mathcal{A}_{\varphi}$ is consistent w.r.t.
$(\mathcal{T},\Sigma_{\mathsf{C}})$. Let $\mathcal{I}$ be a model of
$\mathcal{T}$ and $\mathcal{A}_{\varphi}$ that respects closed predicates
$\Sigma_{\mathsf{C}}$. Define a propositional valuation $v$ by setting
$v(x_{j})=1$ if there exists $i$ such that $(c_{i},x_{j}^{\top})\in
s^{\mathcal{I}}$ and set $v(x_{j})=0$ if there exists $i$ such that
$(c_{i},x_{j}^{\bot})\in s^{\mathcal{I}}$. Observe that $v$ is well-defined
since if $(c_{i},x_{j}^{\top})\in s^{\mathcal{I}},(c_{k},x_{j}^{\bot})\in
s^{\mathcal{I}}$, then $(x_{j}^{\top},x_{j}^{\bot})\in s^{\prime\mathcal{I}}$
and so $x_{j}^{\bot}\in(\exists s^{\prime-}\sqcap\exists s^{-})^{\mathcal{I}}$
which contradicts the assumption that $\mathcal{I}$ satisfies $\exists
s^{\prime-}\sqcap\exists s^{-}\sqsubseteq\bot$. Next observe that for every
$c_{i}$ there exists a disjunct $\ell\in c_{i}$ such that
$(c_{i},x_{j}^{\top})\in s^{\mathcal{I}}$ if $\ell=x_{j}$ and
$(c_{i},x_{j}^{\bot})\in s^{\mathcal{I}}$ if $\ell=\neg x_{j}$. Thus,
$v(\varphi)=1$ and $\varphi$ is satisfiable.

Conversely, assume that $\varphi$ is satisfiable and let $v$ be an assignment
with $v(\varphi)=1$. Define an interpretation $\mathcal{I}$ by expanding
$\mathcal{I}_{\mathcal{A}_{\varphi}}$ as follows:

$\displaystyle s^{\mathcal{I}}$ $\displaystyle=$
$\displaystyle\\{(c_{i},x_{j}^{\top})\\}\mid x_{j}\in c_{i},v(x_{j})=1,i\leq
n\\}\cup\\{(c_{i},x_{j}^{\bot})\mid\neg x_{j}\in c_{i},v(x_{j})=0,i\leq n\\}$
$\displaystyle s^{\prime\mathcal{I}}$ $\displaystyle=$
$\displaystyle\\{(x_{j}^{\top},x_{j}^{\bot})\mid
v(x_{j})=1\\}\cup\\{(x_{j}^{\bot},x_{j}^{{\sf aux}})\mid v(x_{j})=0\\}$

It is readily checked that $\mathcal{I}$ is a model of $\mathcal{T}$ and
$\mathcal{A}_{\varphi}$ that respects closed predicates $\Sigma_{\mathsf{C}}$.

We close this section with noting that, for the case of $\mathcal{EL}$,
quantifier-free queries are computationally no more well-behaved than
unrestricted queries. In fact, we have seen that OMQCs in $\mathcal{EL}$ using
dtUCQs can be equivalently expressed using atomic database queries $A(x)$ by
adding CIs of the form $C_{q}\sqsubseteq A$ to the TBox.

##  10\. Conclusion

We have investigated the data complexity of ontology-mediated query evaluation
with closed predicates, focussing on a non-uniform analysis. At the TBox level
we have obtained PTime/coNP dichotomy results for the lightweight DLs
$\mathcal{EL}$ and $\text{DL-Lite}_{\mathcal{R}}$. At the query level, the
situation is drastically different: there is provably no PTime/coNP dichotomy
for neither $\text{DL-Lite}_{\mathcal{R}}$ nor $\mathcal{EL}$ (unless PTime
=coNP) and even without closing role names, understanding the complexity of
queries is as hard as the surjective constraint satisfaction problem. We have
also shown that by combining $\text{DL-Lite}_{\mathcal{R}}$ with quantifier-
free database queries one obtains FO-rewritable queries and that even for
expressive DLs query evaluation is always in coNP. Many challenging open
questions remain.

Regarding the data complexity classification at TBox level, it is shown in
[40] that the dichotomy proof given for $\text{DL-Lite}_{\mathcal{R}}$ and
$\mathcal{EL}$ does not go through for the extension $\mathcal{ELI}$ of
$\mathcal{EL}$ with inverse roles. In fact, in contrast to $\text{DL-
Lite}_{\mathcal{R}}$ and $\mathcal{EL}$, there are $\mathcal{ELI}$ TBoxes with
closed predicates $(\mathcal{T},\Sigma_{\mathsf{C}})$ such that CQ evaluation
w.r.t. $(\mathcal{T},\Sigma_{\mathsf{C}})$ is in PTime, but
$(\mathcal{T},\Sigma_{\mathsf{C}})$ and $(\mathcal{T},\emptyset)$ are not CQ-
inseparable on consistent ABoxes. In particular, it remains open whether there
is a PTime/coNP dichotomy for TBoxes with closed predicates in
$\mathcal{ELI}$. The same question remains open for $\mathcal{ALCHI}$ TBoxes
(recall that there is a PTime/coNP dichotomy for for $\mathcal{ALCHI}$ TBoxes
without closed predicates [42, 30]) and for expressive Horn languages such as
Horn-$\mathcal{SHIQ}$. Also of interest are ontologies consisting of tuple-
generating dependencies (tgds) which generalizes both DL-LiteR and
$\mathcal{EL}$. In this case, however, the coNP upper bound established here
for $\mathcal{ALCHI}$ does not hold, even for the moderate extension
consisting of linear tgds [9, 8].

Regarding the data complexity classification at the OMQC level, it would be of
interest to consider $\text{$\text{DL-Lite}$}_{\text{core}}$: it remains open
whether there is a PTime/coNP dichotomy for the language $(\text{$\text{DL-
Lite}$}_{\text{core}},{\sf N_{C}}\cup{\sf N_{R}},\text{BUtCQ})$ and whether
Theorem 36 can be strengthened to this case.

Acknowledgments. Frank Wolter was supported by EPSRC grant EP/M012646/1.
Carsten Lutz was supported by the ERC Consolidator Grant 647289 CODA.

## References

  * [1] Serge Abiteboul, Richard Hull, and Victor Vianu.  Foundations of Databases.  Addison-Wesley, 1995.
  * [2] Shqiponja Ahmetaj, Magdalena Ortiz, and Mantas Simkus.  Polynomial datalog rewritings for expressive description logics with closed predicates.  In Proc. of IJCAI, pages 878–885, 2016.
  * [3] Giovanni Amendola, Nicola Leone, Marco Manna, and Pierfrancesco Veltri.  Enhancing existential rules by closed-world variables.  In Proc. of IJCAI, pages 1676–1682, 2018.
  * [4] Alessandro Artale, Diego Calvanese, Roman Kontchakov, and Michael Zakharyaschev.  The DL-Lite family and relations.  Journal of Artificial Intelligence Research, 36:1–69, 2009.
  * [5] F. Baader, D. Calvanese, D. McGuiness, D. Nardi, and P. Patel-Schneider.  The Description Logic Handbook: Theory, implementation and applications.  Cambridge University Press, 2003.
  * [6] Franz Baader, Sebastian Brandt, and Carsten Lutz.  Pushing the $\mathcal{EL}$ envelope.  In IJCAI, 2005.
  * [7] Franz Baader, Ian Horrocks, Carsten Lutz, and Ulrike Sattler.  An Introduction to Description Logic.  Cambridge University Press, 2017.
  * [8] Michael Benedikt and Pierre Bourhis.  Pspace hardness of mixed world query answering for atomic queries under guarded tgds.  Technical report, University of Oxford, 2018.
  * [9] Michael Benedikt, Pierre Bourhis, Balder ten Cate, and Gabriele Puppis.  Querying visible and invisible information.  In Proc. of LICS, pages 297–306, 2016.
  * [10] Meghyn Bienvenu, Peter Hansen, Carsten Lutz, and Frank Wolter.  First order-rewritability and containment of conjunctive queries in horn description logics.  In Proc. of IJCAI, pages 965–971, 2016.
  * [11] Meghyn Bienvenu, Carsten Lutz, and Frank Wolter.  First-order rewritability of atomic queries in horn description logics.  In Proc. of IJCAI, pages 754–760, 2013.
  * [12] Meghyn Bienvenu and Magdalena Ortiz.  Ontology-mediated query answering with data-tractable description logics.  In Proc. of Reasoning Web, pages 218–307, 2015.
  * [13] Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter.  Ontology-based data access: A study through disjunctive datalog, CSP, and MMSNP.  ACM Trans. Database Syst., 39(4):33, 2014.
  * [14] Manuel Bodirsky, Jan Kára, and Barnaby Martin.  The complexity of surjective homomorphism problems–—a survey.  Discrete Applied Mathematics, 160(12):1680–1690, 2012.
  * [15] Elena Botoeva, Boris Konev, Carsten Lutz, Vladislav Ryzhikov, Frank Wolter, and Michael Zakharyaschev.  Inseparability and conservative extensions of description logic ontologies: A survey.  In Proc. of Reasoning Web, pages 27–89, 2016.
  * [16] Elena Botoeva, Roman Kontchakov, Vladislav Ryzhikov, Frank Wolter, and Michael Zakharyaschev.  Games for query inseparability of description logic knowledge bases.  Artif. Intell., 234:78–119, 2016.
  * [17] Andrei A. Bulatov.  A dichotomy theorem for nonuniform csps.  In Proc. of FOCS, pages 319–330, 2017.
  * [18] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati.  Tractable reasoning and efficient query answering in description logics: The DL-Lite family.  Journal of Automated Reasoning, 39(3):385–429, 2007.
  * [19] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati.  Data complexity of query answering in description logics.  In KR, pages 260–270, 2006.
  * [20] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati.  EQL-Lite: Effective first-order query processing in description logics.  In IJCAI, 2007.
  * [21] Hubie Chen.  An algebraic hardness criterion for surjective constraint satisfaction.  Algebra Universalis, 72(4):393–401, 2014.
  * [22] Francesco M. Donini, Daniele Nardi, and Riccardo Rosati.  Description logics of minimal knowledge and negation as failure.  ACM Transactions on Computational Logic, 3(2):177–225, 2002.
  * [23] Thomas Eiter, Georg Gottlob, and Heikki Mannila.  Disjunctive datalog.  ACM Trans. Database Syst., 22(3):364–418, 1997.
  * [24] Tomás Feder and Moshe Y. Vardi.  Monotone monadic SNP and constraint satisfaction.  In STOC, pages 612–622, 1993.
  * [25] Cristina Feier, Antti Kuusisto, and Carsten Lutz.  Rewritability in monadic disjunctive datalog, mmsnp, and expressive description logics (invited talk).  In Proc. ICDT, pages 1:1–1:17, 2017.
  * [26] Jan Foniok, Jaroslav Nesetril, and Claude Tardif.  Generalised dualities and maximal finite antichains in the homomorphism order of relational structures.  Eur. J. Comb., 29(4):881–899, 2008.
  * [27] Enrico Franconi, Yazmin Angélica Ibáñez-García, and İnanç Seylan.  Query answering with DBoxes is hard.  Electronic Notes in Theoretical Computer Science, 278:71–84, 2011\.
  * [28] Birte Glimm and Markus Krötzsch.  SPARQL beyond subgraph matching.  In ISWC, volume 6496 of LNCS, pages 241–256. Springer, 2010\.
  * [29] Stephan Grimm and Boris Motik.  Closed world reasoning in the semantic web through epistemic operators.  In OWLED, 2005.
  * [30] André Hernich, Carsten Lutz, Fabio Papacchini, and Frank Wolter.  Dichotomies in ontology-mediated querying with the guarded fragment.  In Proc. of PODS, pages 185–199, 2017.
  * [31] Ullrich Hustadt, Boris Motik, and Ulrike Sattler.  Data complexity of reasoning in very expressive description logics.  In Proc. of IJCAI, pages 466–471, 2005.
  * [32] Neil Immerman.  Descriptive Complexity.  Springer, 1999.
  * [33] İnanç Seylan, Enrico Franconi, and Jos de Bruijn.  Effective query rewriting with ontologies over DBoxes.  In IJCAI, 2009.
  * [34] Roman Kontchakov, Carsten Lutz, David Toman, Frank Wolter, and Michael Zakharyaschev.  The combined approach to query answering in DL-Lite.  In KR, 2010.
  * [35] Roman Kontchakov and Michael Zakharyaschev.  An introduction to description logics and query rewriting.  In Proc. of Reasoning Web, pages 195–244, 2014.
  * [36] Adila Krisnadhi and Carsten Lutz.  Data complexity in the _EL_ family of description logics.  In Proc. LPAR, pages 333–347, 2007.
  * [37] Markus Krötzsch, Frederick Maier, Adila Krisnadhi, and Pascal Hitzler.  A better uncle for OWL: nominal schemas for integrating rules and ontologies.  In Proc. of WWW, pages 645–654. ACM, 2011.
  * [38] Markus Krötzsch and Sebastian Rudolph.  Nominal schemas in description logics: Complexities clarified.  In Proc. of KR. AAAI Press, 2014.
  * [39] Carsten Lutz, Inanç Seylan, and Frank Wolter.  Ontology-mediated queries with closed predicates.  In Proc. of IJCAI, pages 3120–3126. AAAI Press, 2015.
  * [40] Carsten Lutz, İnanç Seylan, and Frank Wolter.  Ontology-based data access with closed predicates is inherently intractable (sometimes).  In Proc. of IJCAI, pages 1024–1030, 2013.
  * [41] Carsten Lutz and Frank Wolter.  Deciding inseparability and conservative extensions in the description logic $\mathcal{EL}$.  Journal of Symbolic Computation, 45(2):194–228, 2010.
  * [42] Carsten Lutz and Frank Wolter.  The data complexity of description logic ontologies.  Logical Methods in Computer Science, 13(4), 2017.
  * [43] Anees Mehdi, Sebastian Rudolph, and Stephan Grimm.  Epistemic querying of OWL knowledge bases.  In ESWC, 2011.
  * [44] Boris Motik, Ian Horrocks, and Ulrike Sattler.  Bridging the gap between OWL and relational databases.  Journal of Web Semantics, 7(2):74–89, 2009.
  * [45] Boris Motik and Riccardo Rosati.  Reconciling description logics and rules.  Journal of the ACM, 57(5):1–62, 2010.
  * [46] Nhung Ngo, Magdalena Ortiz, and Mantas Simkus.  Closed predicates in description logics: Results on combined complexity.  In Proc. of KR, pages 237–246, 2016.
  * [47] Magdalena Ortiz, Diego Calvanese, and Thomas Eiter.  Data complexity of query answering in expressive description logics via tableaux.  Journal of Automated Reasoning, 41(1):61–98, 2008.
  * [48] Antonella Poggi, Domenico Lembo, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Riccardo Rosati.  Linking data to ontologies.  J. Data Semantics, 10:133–173, 2008.
  * [49] Raymond Reiter.  What should a database know?  Journal of Logic Programming, 14(1&2):127–153, 1992.
  * [50] Andrea Schaerf.  On the complexity of the instance checking problem in concept languages with existential quantification.  Journal of Intelligent Information Systems, 2:265–278, 1993.
  * [51] Kunal Sengupta, Adila Alfa Krisnadhi, and Pascal Hitzler.  Local closed world semantics: Grounded circumscription for OWL.  In ISWC, 2011.
  * [52] Balder ten Cate, Enrico Franconi, and İnanç Seylan.  Beth definability in expressive description logics.  Journal of Artificial Intelligence Research, 48:347–414, 2013.
  * [53] Guohui Xiao, Diego Calvanese, Roman Kontchakov, Domenico Lembo, Antonella Poggi, Riccardo Rosati, and Michael Zakharyaschev.  Ontology-based data access: A survey.  In Proc. of IJCAI, pages 5511–5519, 2018.
  * [54] Dmitriy Zhuk.  A proof of CSP dichotomy conjecture.  In Proc. of FOCS, pages 331–342, 2017.