# Controlled Query Evaluation through Epistemic Dependencies

Gianluca Cima1 Domenico Lembo1 Lorenzo Marconi1
Riccardo Rosati1&Domenico Fabio Savo2
1Sapienza University of Rome
2University of Bergamo
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we propose the use of epistemic dependencies to express data
protection policies in Controlled Query Evaluation (CQE), which is a form of
confidentiality-preserving query answering over ontologies and databases. The
resulting policy language goes significantly beyond those proposed in the
literature on CQE so far, allowing for very rich and practically interesting
forms of data protection rules. We show the expressive abilities of our
framework and study the data complexity of CQE for (unions of) conjunctive
queries when ontologies are specified in the Description Logic $\text{DL-
Lite}_{\mathcal{R}}$. Interestingly, while we show that the problem is in
general intractable, we prove tractability for the case of acyclic epistemic
dependencies by providing a suitable query rewriting algorithm. The latter
result paves the way towards the implementation and practical application of
this new approach to CQE.

##  1 Introduction

Controlled Query Evaluation (CQE) is a confidentiality-preserving query
answering approach that protects sensitive information by filtering query
answers in such a way that a user cannot deduce information declared
confidential by a data protection policy Biskup (2000); Biskup and Bonatti
(2004); Bonatti and Sauro (2013); Cuenca Grau et al. (2013).

In CQE, one crucial aspect concerns the expressiveness of the policy language,
which determines the form of the logic formulas definable in the policy,
consequently influencing a designer’s capacity to declare which pieces of
information must not be disclosed. Previous literature has mainly considered
only policies consisting of sentences, i.e. closed formulas, as in Sicherman
et al. (1983); Biskup and Bonatti (2004); Bonatti and Sauro (2013); Lembo et
al. (2019). Through this approach, it is only possible to impose that the
truth value of a sentence in the policy cannot be inferred from the system by
asking queries. For example, Lembo et al. (2019) study CQE when policy
statements take the form $\forall\vec{x}(q(\vec{x})\rightarrow\bot)$, referred
to as denial. Enforcing one such denial over the data means refraining from
disclosing the inference of the Boolean conjunctive query (BCQ)
$\exists\vec{x}~{}q(\vec{x})$ by the system, even if the inference has
occurred. For instance, the rule

$\delta_{1}=\forall
x,y(\mathsf{Patient}(x)\wedge\mathsf{admitted}(x,y)\rightarrow\bot)$
---

says that it is confidential whether there exists a patient admitted in a
hospital department. However, if the aim is to hide admitted patients, the
above dependency is imposing an excessively stringent level of protection,
since it is denying the presence of patients in the hospital to protect their
identity, which is implausible in practice. A more effective approach would be
instead to require that the system must not answer the _open_ query
$q(x):\exists y(\mathsf{Patient}(x)\wedge\mathsf{admitted}(x,y))$.
Intuitively, specifying a rule of this kind means imposing that the set of
patients that the system _knows_ to be admitted to the hospital has not to be
disclosed.

To properly capture this behavior, we propose to use an epistemic operator $K$
in policy formulas, in the spirit of Calvanese et al. (2007b); Console and
Lenzerini (2020). This allows us to formalize the epistemic state of the user,
that is, what the system can tell to the user without disclosing sensitive
information. In our example, the policy rule is as follows:

$\delta_{2}=\forall x\big{(}K\,\exists
y(\mathsf{Patient}(x)\wedge\mathsf{admitted}(x,y))\rightarrow K\bot\big{)}$
---

Rule $\delta_{2}$ imposes that, in the epistemic state of the user, the set of
admitted patients must be empty (but this does not exclude that the user knows
that some patients have been admitted).

In fact, our proposal enables us to accomplish more than just that. In a more
advanced scenario, concealing the relationship between a patient and a
hospital should apply only if the patient has not signed a consensus form.
This can be expressed by the following formula:

$\delta_{3}=\forall x\big{(}K\,\exists
y(\mathsf{Patient}(x)\wedge\mathsf{admitted}(x,y))\rightarrow$
---
$K\mathsf{Consent}(x)\big{)}$

Intuitively, the formula is saying that if a user knows that a patient has
been admitted, then she must know that the patient has signed a consensus
form. Thus, if a patient did not sign a consensus form, the system cannot
disclose that this patient has been admitted. In general, this kind of policy
is well-suited for encoding the principle of _privacy by default_ , which is a
desirable property in data protection (as expressly outlined in Article 25 of
GDPR European Union (2016)).

We remark once again that policy rules of the form just described have not
been previously considered in the literature. It is however worth noticing
that in Cuenca Grau et al. (2015) CQE is studied for a policy consisting of
_one single open_ CQ. In this latter framework, a rule analogous to
$\delta_{2}$ of our example can be in fact specified, but richer policies, as
those requiring more denials and/or rules as $\delta_{3}$ above, are non-
expressible.

Formulas as $\delta_{2}$ and $\delta_{3}$ are called _epistemic dependencies_
(EDs). EDs have been originally introduced in Console and Lenzerini (2020) to
express integrity constraints in ontology-based data management and are indeed
a special case of _domain-independent EQL-Lite(CQ)_ sentences Calvanese et al.
(2007a). In the present paper, we use EDs as policy rules that must be
satisfied to preserve data confidentiality over Description Logic (DL)
ontologies, similarly as integrity constraints must be satisfied to guarantee
data consistency. However, our aim is totally different from that of Console
and Lenzerini (2020), where the focus is on consistency checking.

After defining the policy language, to completely characterize our CQE
framework, we need to specify its semantics. This issue is addressed in CQE
through _censors_. In this paper, we use _CQ-censors_ introduced in Lembo et
al. (2019). In a nutshell, given an ontology $\mathcal{O}$, an _optimal CQ-
censor_ is a maximal subset $\mathcal{C}$ of the set of all BCQs inferred by
$\mathcal{O}$, such that $\mathcal{C}$ coupled with the intensional component
of $\mathcal{O}$ (i.e. its TBox $\mathcal{T}$) satisfies all rules in the
policy (i.e. no secrets are disclosed through standard query answering over
$\mathcal{T}\cup\mathcal{C}$). As in Lembo et al. (2019), we then define CQE
as the problem of computing the query answers that are in the intersection of
the answer sets returned by all optimal censors. We call this problem _SC-
entailment_ (Skeptical entailment under CQ-censors). This form of CQE does not
suffer of the problem of having to arbitrarily select an optimal censor among
several incomparable ones, as done, e.g., in Bonatti and Sauro (2013); Cuenca
Grau et al. (2015). We point out that CQ-censors are particularly interesting
from a practical perspective, since, for ontologies specified $\text{DL-
Lite}_{\mathcal{R}}$ Calvanese et al. (2007b), a DL suited for modeling data
intensive ontologies, and policies expressed as denials, SC-entailment of BCQs
is tractable in data complexity Lembo et al. (2019). One of the aims of the
present paper is then to study data complexity of SC-entailment of BCQs under
epistemic policies for $\text{DL-Lite}_{\mathcal{R}}$ ontologies, with the
ultimate goal of identifying conditions ensuring tractability in this case.

Besides the computational complexity study, we also carry out an analysis of
the robustness of SC-entailment with respect to confidentiality-preservation.
In Biskup and Weibert (2008); Bonatti and Sauro (2013); Bonatti (2022), it is
shown that censoring mechanisms based on an indistinguishability criterion are
indeed more secure than others. In abstract terms, according to such a
criterion, confidentiality is guaranteed only if query answers returned over a
data instance with sensitive information coincide with those returned over a
data instance without secrets (which is thus indistinguishable from the other
instance). In this paper, we investigate whether the entailment we consider
enjoys indistinguishability.

Specifically, our main results are for ontologies in $\text{DL-
Lite}_{\mathcal{R}}$ and policies that are sets of EDs. In more detail:

  * •

As for indistinguishability, we show that SC-entailment of BCQs preserves
confidentiality as defined in Biskup and Weibert (2008), but that this result
does not carry over to unions of BCQs (BUCQs). We however prove that the
property holds even for BUCQs in the case of IC-entailment, a sound
approximation of SC-Entailment that considers a single censor given by the
intersection of all optimal CQ-censors (Section 4);

  * •

We show that SC-entailment and IC-entailment of BCQs and BUCQs are coNP-
complete in data complexity (Section 5.1);

  * •

For _acyclic EDs_ , we exhibit a rewriting algorithm that allows us to prove
that SC-entailment and IC-entailment of BCQs and BUCQs are first-order
rewritable, and thus in AC0 in data complexity (Section 5.2).

Policy | Query |  Confidentiality | Data
---|---|---|---
language |  preservation | complexity
|  SC-ent. |  IC-ent. |  SC-ent. |  IC-ent.
Acyclic | BCQ | yes | in $\mathrm{AC}^{0}$
Arbitrary | BCQ | yes | coNP-c
Acyclic | BUCQ | no | yes | in $\mathrm{AC}^{0}$ | in $\mathrm{AC}^{0}$
Arbitrary | BUCQ | no | yes | coNP-c | coNP-c
Table 1: Results on data complexity and confidentiality preservation. coNP-c
stands for coNP-complete.

All our results are summarized in Table 1. Complete proofs are given in the
appendix.

##  2 Preliminaries

We employ standard notions of function-free first-order logic (FO), and
consider FO formulas using only unary and binary predicates called _concepts_
and _roles_ , respectively, as in Description Logics, which are fragments of
FO suited for conceptual modeling Baader et al. (2020). We assume the
existence of pairwise-disjoint countably-infinite sets $\Gamma_{C}$,
$\Gamma_{R}$, $\Gamma_{I}$, $\Gamma_{N}$, and $\Gamma_{V}$ containing _atomic
concepts_ , _atomic roles_ , _constants_ (also known as _individuals_),
_labeled nulls_ , and _variables_ , respectively. An FO formula $\phi$ is
sometimes denoted as $\phi(\vec{x})$, where $\vec{x}$ is the sequence of the
free variables occurring in $\phi$. We also use the term _query_ as a synonym
of FO formula and _Boolean query_ as a synonym of closed FO formula (also
called sentence). An FO theory $\Phi$ is a set of FO sentences. The semantics
of $\Phi$ is given in terms of FO interpretations over
$\Gamma_{C}\cup\Gamma_{R}\cup\Gamma_{I}$.W.l.o.g., we consider interpretations
sharing the same infinite countable domain $\Delta=\Gamma_{I}$, so that every
element in $\Gamma_{I}$ is interpreted by itself. In other terms, we use
_standard names_ , as often customary when one deals with epistemic operators
Calvanese et al. (2007a). We write $\textit{eval}(\phi,\mathcal{I})$ to
indicate the evaluation of an FO sentence $\phi$ over an FO interpretation
$\mathcal{I}$. A _model_ of an FO theory $\Phi$ is an FO interpretation
satisfying all sentences in $\Phi$. We say that $\Phi$ _entails_ an FO
sentence $\phi$, denoted by $\Phi\models\phi$, if
$\textit{eval}(\phi,\mathcal{I})$ is true in every model $\mathcal{I}$ of
$\Phi$.

A _Description Logic (DL) ontology_ $\mathcal{O}=\mathcal{T}\cup\mathcal{A}$
consists of a TBox $\mathcal{T}$ and an ABox $\mathcal{A}$, representing
intensional and extensional knowledge, respectively. In this paper, an ABox is
a finite set of atoms using predicate symbols from $\Gamma_{C}\cup\Gamma_{R}$
and terms from $\Gamma_{I}\cup\Gamma_{N}$ (ABoxes of this form are also called
quantified ABoxes Baader et al. (2020)). A model of an ontology
$\mathcal{T}\cup\mathcal{A}$ is any model of the FO theory
$\mathcal{T}\cup\\{\exists\vec{x}\,\phi_{\mathcal{A}}(\vec{x})\\}$, where
$\vec{x}$ is a sequence of variables from $\Gamma_{V}$ and
$\phi_{\mathcal{A}}(\vec{x})$ is the conjunction of all the atoms of
$\mathcal{A}$ in which each labeled null is replaced with a distinct variable
$x\in\vec{x}$. With a little abuse of notation, we sometimes treat an ontology
$\mathcal{T}\cup\mathcal{A}$ (resp. $\mathcal{A}$) as the FO theory
$\mathcal{T}\cup\\{\exists\vec{x}\,\phi_{\mathcal{A}}(\vec{x})\\}$ (resp.
$\\{\exists\vec{x}\,\phi_{\mathcal{A}}(\vec{x})\\}$). For instance, this
allows us to write $\mathcal{T}\cup\mathcal{A}\models\phi$ to intend
$\mathcal{T}\cup\\{\exists\vec{x}\,\phi_{\mathcal{A}}(\vec{x})\\}\models\phi$,
where $\phi$ is an FO sentence.

Our complexity results are given for ontologies expressed in $\text{DL-
Lite}_{\mathcal{R}}$, a member of the well-known DL-Lite family of DLs
Calvanese et al. (2007b). A $\text{DL-Lite}_{\mathcal{R}}$ TBox $\mathcal{T}$
is a finite set of axioms of the form $B\sqsubseteq B^{\prime}$ and
$R\sqsubseteq R^{\prime}$ (called concept and role inclusions), or
$B\sqsubseteq\neg B^{\prime}$ and $R\sqsubseteq\neg R^{\prime}$ (called
concept and role disjointnesses), where $B$ and $B^{\prime}$ (resp., $R$ and
$R^{\prime}$) are predicates of the form $A$, $\exists S$ or $\exists S^{-}$
(resp., $S$ or $S^{-}$) such that $A\in\Gamma_{C}$, $S\in\Gamma_{R}$, $S^{-}$
is the inverse of $S$, and the _unqualified existential restrictions_ $\exists
S$ and $\exists S^{-}$ represent the set of objects appearing as the first and
second argument of $S$, respectively.

As usual when studying query answering over DL ontologies, we focus on the
language of conjunctive queries (and variants thereof). A _conjunctive query_
(_CQ_) takes the form of an FO formula $\exists\vec{y}\phi(\vec{x},\vec{y})$,
where $\vec{x}\cup\vec{y}\subseteq\Gamma_{V}$ and $\phi(\vec{x},\vec{y})$ is a
finite, non-empty conjunction of atoms of the form $\alpha(\vec{t})$, where
$\alpha\in\Gamma_{C}\cup\Gamma_{R}$, and each term in $\vec{t}$ is either a
constant in $\Gamma_{I}$ or a variable in $\vec{x}\cup\vec{y}$. We also
consider the special CQ $\bot$ and assume that
$\textit{eval}(\bot,\mathcal{I})$ is false for every FO interpretation
$\mathcal{I}$. A _union of conjunctive queries_ (_UCQ_) is a disjunction
$q_{1}(\vec{x})\lor\ldots\lor q_{n}(\vec{x})$ of CQs. For convenience,
sometimes we treat UCQs as sets of CQs. Boolean CQs and UCQs, for short, are
respectively indicated as _BCQs_ and _BUCQs_.

Given a CQ $q$, we denote by $\textit{Len}(q)$ the number of atoms in $q$.
Given a UCQ $q$, $\textit{MaxLenCQ}(q)=\max_{q^{\prime}\in
q}\textit{Len}(q^{\prime})$. We denote by BCQ (resp. BUCQ) the language of all
the BCQs (resp. BUCQs), and, for a positive integer $k$, by $\textbf{BCQ}_{k}$
(resp. $\textbf{BUCQ}_{k}$) the language of BCQs (resp. BUCQs) $q$ such that
$\textit{Len}(q)\leq k$ (resp., $\textit{MaxLenCQ}(q)\leq k$). Given a TBox
$\mathcal{T}$, an ABox $\mathcal{A}$, and a Boolean query language
$\mathcal{L}_{q}\subseteq\textbf{BCQ}$, we denote by
$\mathcal{L}_{q}$-$\textit{Cons}(\mathcal{T}\cup\mathcal{A})$ the set of
Boolean queries $q\in\mathcal{L}_{q}$ that are logical consequences of
$\mathcal{T}\cup\mathcal{A}$. Formally:
$\mathcal{L}_{q}$-$\textit{Cons}(\mathcal{T}\cup\mathcal{A})=\\{q\in\mathcal{L}_{q}\mid\mathcal{T}\cup\mathcal{A}\models
q\\}$

A _ground substitution_ for a sequence $\vec{x}=x_{1},\ldots,x_{k}$ of
variables is a sequence of constants $\vec{c}=c_{1},\ldots,c_{k}$.
Furthermore, if $\vec{x}$ are the free variables of a FO formula
$\phi(\vec{x})$, we indicate as $\phi(\vec{c})$ the FO sentence obtained from
$\phi(\vec{x})$ by replacing each $x_{i}$ with $c_{i}$, for $1\leq i\leq k$.

We recall that query answering of UCQs in $\text{DL-Lite}_{\mathcal{R}}$ is
first-order rewritable, i.e. for every $\text{DL-Lite}_{\mathcal{R}}$ TBox
$\mathcal{T}$ and UCQ $q(\vec{x})$, it is possible to compute an FO query
$q_{r}(\vec{x})$ such that, for every ground substitution $\vec{c}$ of
$\vec{x}$, $\mathcal{T}\cup\mathcal{A}\models q(\vec{c})$ iff
$\mathcal{A}\models q_{r}(\vec{c})$. To compute $q_{r}(\vec{x})$, we use the
algorithm PerfectRef presented in Calvanese et al. (2007b), for which the
following property holds.

######  Proposition 1.

Let $\mathcal{T}$ be a $\text{DL-Lite}_{\mathcal{R}}$ TBox and let
$q(\vec{x})$ be a UCQ. For every ABox $\mathcal{A}$ and every ground
substitution $\vec{c}$ for $\vec{x}$, we have that
$\mathcal{T}\cup\mathcal{A}\models q(\vec{c})$ if and only if
$\mathcal{A}\models q_{r}(\vec{c})$, where
$q_{r}(\vec{x})=\textit{PerfectRef}(q(\vec{x}),\mathcal{T})$.

We point out that, by construction, $q_{r}=\textit{PerfectRef}(q,\mathcal{T})$
is a UCQ and that $\textit{MaxLenCQ}(q_{r})=\textit{MaxLenCQ}(q)$.

##  3 Framework

In this section, we describe our CQE framework. We first give the notion of
epistemic dependencies that we use in the policies, then present the notion of
censor, and finally provide two notions of query entailment in our novel
framework.

Epistemic dependencies. The policy $\mathcal{P}$ of our framework is a finite
set of _epistemic dependencies_ , each of which can be seen as a _domain-
independent EQL-Lite(CQ)_ Calvanese et al. (2007a) sentence defined as
follows.

######  Definition 1.

An _epistemic dependency (ED)_ is a sentence $\delta$ of the following form:

$\begin{array}[]{l}\forall\vec{x}_{1},\vec{x}_{2}(Kq_{b}(\vec{x}_{1},\vec{x}_{2})\rightarrow
Kq_{h}(\vec{x}_{2}))\end{array}$ (1)

where $q_{b}(\vec{x}_{1},\vec{x}_{2})$ is a CQ with free variables
$\vec{x}_{1}\cup\vec{x}_{2}$, $q_{h}(\vec{x}_{2})$ is a CQ with free variables
$\vec{x}_{2}$, and $K$ is a modal operator. The variables $\vec{x}_{2}$ are
called the frontier variables of $\delta$.

Intuitively, an ED of form (1) should be read as follows: if the sentence
$q_{b}(\vec{c}_{1},\vec{c}_{2})$ is _known_ to hold, then the sentence
$q_{h}(\vec{c}_{2})$ is _known_ to hold, for any ground substitutions
$\vec{c}_{1}$ and $\vec{c}_{2}$ for $\vec{x}_{1}$ and $\vec{x}_{2}$,
respectively. More formally, we define when an FO theory $\Phi$ _satisfies_ an
ED $\delta$, denoted $\Phi\models_{\mathsf{EQL}}\delta$. To this aim, we
consider the set $E$ of all FO models of $\Phi$, and say that
$\Phi\models_{\mathsf{EQL}}\delta$ if, for every ground substitutions
$\vec{c}_{1}$ for $\vec{x}_{1}$ and $\vec{c}_{2}$ for $\vec{x}_{2}$, the fact
that $\textit{eval}(q_{b}(\vec{c}_{1},\vec{c}_{2}),\mathcal{I})$ is true for
every $\mathcal{I}\in E$ implies that
$\textit{eval}(q_{h}(\vec{c}_{2}),\mathcal{I})$ is true for every
$\mathcal{I}\in E$.

We say that $\Phi$ _satisfies_ a policy $\mathcal{P}$ (denoted
$\Phi\models_{\mathsf{EQL}}\mathcal{P}$) if $\Phi$ satisfies $\delta$, for
each $\delta\in\mathcal{P}$. We remark that, as already said, EDs of the form
(1) have been originally introduced in Console and Lenzerini (2020), although
in a slightly more general form, to express integrity constraints in ontology-
based data management.Then, the notion of ED satisfaction defined above is
essentially as in Console and Lenzerini (2020).

######  Example 1.

Suppose that company CA wants to share certain user-profiling data with a
company CB for targeted advertising. This is not allowed in general, but only
in some countries with a special regulation that enables sharing based on the
users’ consent. CA may use the following ED in the policy to enable CB to
access only data compliant with the above requirements:

$\delta_{4}=\forall x,y\big{(}$ |  $K\mathsf{profiledActivity}(x,y)\rightarrow$
---|---
| $K\,\exists
z(\mathsf{citOf}(x,z)\land\mathsf{SR}(z)\land\mathsf{Consent}(x))\big{)}$

In the rule, $\mathsf{profiledActivity}$ associates a user with her profiling-
data, $\mathsf{citOf}$ relates a user to the country of which she is a
citizen, $\mathsf{SR}$ denotes countries with special regulation, and
$\mathsf{Consent}$ denotes users who have given their consent.

Suppose that CA also wants CB not to be able to associate a user with her real
identity, and that this is possible by collecting the person’s name and her
date of birth at the same time. To this aim, CA also specifies the following
ED:

$\delta_{5}=\forall x,y,z\big{(}K(\mathsf{name}(x,y)\land\mathsf{dateB}$ |  $(x,z))\rightarrow K\bot\big{)}$
---|---

CQ-censors. As already said, censors are used to enforce confidentiality on an
ontology coupled with a data protection policy. Among various definitions of
censors proposed in the literature, we adapt here the one investigated in
Lembo et al. (2019) to properly deal with policies constituted by sets of EDs.
To this aim, it is convenient to first define CQE instances in our novel
epistemic CQE framework.

######  Definition 2 (CQE instance).

An $\mathcal{L}_{\mathcal{T}}$ _CQE instance_ is a triple
$\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$, where
$\mathcal{T}$ is a TBox in the DL $\mathcal{L}_{\mathcal{T}}$, $\mathcal{A}$
is an ABox such that $\mathcal{T}\cup\mathcal{A}$ has at least one model, and
$\mathcal{P}$ is a policy (i.e., a finite set of EDs) such that
$\mathcal{T}\models_{\mathsf{EQL}}\mathcal{P}$.

Hereinafter, if the DL $\mathcal{L}_{\mathcal{T}}$ is not specified, we
implicitly intend any possible DL.

The notion of (optimal) CQ-censors is then as follows.

######  Definition 3 ((optimal) CQ-censor).

A _CQ-censor_ of a CQE instance
$\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ is a subset
$\mathcal{C}$ of $\textit{{BCQ}}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$ such
that $\mathcal{T}\cup\mathcal{C}\models_{\mathsf{EQL}}\mathcal{P}$.

An _optimal CQ-censor_ of a CQE instance
$\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ is a CQ-censor
of $\mathcal{E}$ such that there exists no CQ-censor $\mathcal{C}^{\prime}$ of
$\mathcal{E}$ such that $\mathcal{C}^{\prime}\supset\mathcal{C}$. We denote by
$\textit{OptCQCens}(\mathcal{E})$ the set of optimal CQ-censors of
$\mathcal{E}$.

Entailment. As in Lembo et al. (2019), in this paper CQE amounts to reason
over all the possible optimal censors, according to the following definition
of SC-entailment.

######  Definition 4 (SC-entailment).

A CQE instance $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$
_Skeptically-entails a BUCQ $q$ under CQ-Censors_ (in short, _SC -entails_
$q$), denoted by $\mathcal{E}\models_{\text{SC}}q$, if
$\mathcal{T}\cup\mathcal{C}\models q$ for every
$\mathcal{C}\in\textit{OptCQCens}(\mathcal{E})$.

We also consider the following sound approximation of SC-entailment.

######  Definition 5 (IC-entailment).

A CQE instance $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$
_entails a BUCQ $q$ under the Intersection of CQ-Censors_ (in short, _IC
-entails $q$_), denoted by $\mathcal{E}\models_{\text{IC}}q$, if
$\mathcal{T}\cup\mathcal{C}_{\mathit{int}}(\mathcal{E})\models q$, where
$\mathcal{C}_{\mathit{int}}(\mathcal{E})=\bigcap_{\mathcal{C}\in\textit{OptCQCens}(\mathcal{E})}\mathcal{C}$.

######  Example 2.

Consider the CQE instance
$\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$, where
$\mathcal{T}=\emptyset$, $\mathcal{P}=\\{\delta_{4},\delta_{5}\\}$, with
$\delta_{4}$ and $\delta_{5}$ being the EDs illustrated in Example 1, and the
ABox $\mathcal{A}$ is as follows:

$\mathcal{A}=\\{$ | $\mathsf{profiledActivity}(\mathsf{p_{1}},\mathsf{act_{1}}),\mathsf{Consent}(\mathsf{p_{1}}),\mathsf{citOf}(\mathsf{p_{1}},n_{1}),$
---|---
|
$\mathsf{SR}(n_{1}),\mathsf{name}(\mathsf{p_{1}},\mathsf{ann}),\mathsf{dateB}(\mathsf{p_{1}},\mathsf{date_{1}}),$
|
$\mathsf{profiledActivity}(\mathsf{p_{2}},\mathsf{act_{2}}),\mathsf{citOf}(\mathsf{p_{2}},n_{1})\\}$,

where $n_{1}\in\Gamma_{N}$ while all the other terms used in $\mathcal{A}$ are
constants in $\Gamma_{I}$. Now, consider the following four BCQs:
$q_{1}=\exists
y\,(\mathsf{profiledActivity}(\mathsf{p_{1}},\mathsf{act_{1}})\land\mathsf{citOf}(\mathsf{p_{1}},y)\land\mathsf{SR}(y))$
$q_{2}=\mathsf{profiledActivity}(\mathsf{p_{2}},\mathsf{act_{2}})$
$q_{3}=\exists y\,\mathsf{profiledActivity}(y,\mathsf{act_{2}})$
$q_{4}=\mathsf{profiledActivity}(\mathsf{p_{1}},\mathsf{act_{1}})\land\mathsf{name}(\mathsf{p_{1}},\mathsf{ann})$
For $X\in\\{\text{SC},~{}\text{IC}\\}$, one can verify that
$\mathcal{E}\models_{X}q_{1}$ because $\mathsf{p_{1}}$ gave the consent and
she is a citizen of some country ($n_{1}$) with special regulation.
Conversely, one can see that $\mathcal{E}\not\models_{X}q_{2}$ because
$\mathsf{p_{2}}$ did not give the consent. Nevertheless, it is easy to verify
that $q_{3}\in\mathcal{C}$ for each optimal CQ-censor $\mathcal{C}$ of
$\mathcal{E}$, and therefore $\mathcal{E}\models_{X}q_{3}$. Finally, we have
that $\mathcal{E}\not\models_{X}q_{4}$ because there exists an optimal CQ-
censor $\mathcal{C}$ of $\mathcal{E}$ such that
$\mathsf{dateB}(\mathsf{p_{1}},\mathsf{date_{1}})\in\mathcal{C}$, thus
implying that $\mathsf{name}(\mathsf{p_{1}},\mathsf{ann})\not\in\mathcal{C}$
(otherwise $\delta_{5}$ would be violated).

In the above example, note that SC\- and IC-entailment coincide for all
queries. As shown in the subsequent result, this always holds in the case of
entailment of BCQs.

######  Theorem 1.

For every CQE instance
$\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ and for every
BCQ $q$, we have that $\mathcal{E}\models_{\text{SC}}q$ iff
$\mathcal{E}\models_{\text{IC}}q$.

###### Proof.

First, it is easy to verify that, for every $\mathcal{C}$ that is an optimal
CQ-censor of $\mathcal{E}$, and for every BCQ $q$,
$\mathcal{T}\cup\mathcal{C}\models q$ iff $q\in\mathcal{C}$; moreover,
$\mathcal{T}\cup\mathcal{C}_{\mathit{int}}(\mathcal{E})\models q$ iff
$q\in\mathcal{C}_{\mathit{int}}(\mathcal{E})$. Now, let $q$ be a BCQ. If
$\mathcal{E}\models_{\text{SC}}q$, then $q$ belongs to all the optimal CQ-
censors of $\mathcal{E}$, and thus
$q\in\mathcal{C}_{\mathit{int}}(\mathcal{E})$, which implies that
$\mathcal{E}\models_{\text{IC}}q$. Conversely, if
$\mathcal{E}\not\models_{\text{SC}}q$, then there exists an optimal CQ-censor
of $\mathcal{E}$ that does not contain $q$, hence
$q\not\in\mathcal{C}_{\mathit{int}}(\mathcal{E})$, which implies that
$\mathcal{E}\not\models_{\text{IC}}q$. ∎

On the other hand, the next example shows that the same result does not hold
for entailment of BUCQs.

######  Example 3.

Recall Example 2, and consider the BUCQ
$q=\mathsf{name}(\mathsf{p_{1}},\mathsf{ann})\vee\mathsf{dateB}(\mathsf{p_{1}},\mathsf{date_{1}})$.
While we have that $\mathcal{E}\models_{\text{SC}}q$, because either
$\mathsf{name}(\mathsf{p_{1}},\mathsf{ann})\in\mathcal{C}$ or
$\mathsf{dateB}(\mathsf{p_{1}},\mathsf{date_{1}})\in\mathcal{C}$ holds for
every $\mathcal{C}\in\textit{OptCQCens}(\mathcal{E})$, it is easy to see that
$\mathcal{E}\not\models_{\text{IC}}q$ as neither
$\mathsf{name}(\mathsf{p_{1}},\mathsf{ann})$ nor
$\mathsf{dateB}(\mathsf{p_{1}},\mathsf{date_{1}})$ belong to
$\mathcal{C}_{\mathit{int}}(\mathcal{E})=\bigcap_{\mathcal{C}\in\textit{OptCQCens}(\mathcal{E})}\mathcal{C}$.

##  4 Confidentiality preservation

In this section, we investigate the notion of confidentiality used in this
paper. We adopt a similar approach to the one described in Biskup and Weibert
(2008) for relational databases. Intuitively, under such an approach an
entailment semantics preserves confidentiality if, for every CQE instance
$\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ and every finite set
$\mathcal{Q}$ of queries, the answers to such queries are the same as if they
were obtained from another CQE instance
$\langle\mathcal{T},\mathcal{A}^{\prime},\mathcal{P}\rangle$ such that
$\mathcal{T}\cup\mathcal{A}^{\prime}\models_{\mathsf{EQL}}\mathcal{P}$.

We now describe this property formally. First, for a TBox $\mathcal{T}$, a
policy $\mathcal{P}$, two ABoxes $\mathcal{A}$ and $\mathcal{A}^{\prime}$, a
set $\mathcal{Q}$ of BUCQs, and $X\in\\{\text{SC},~{}\text{IC}\\}$, we say
that $\mathcal{A}$ and $\mathcal{A}^{\prime}$ are _$\mathcal{Q}$
-indistinguishable for $X$-entailment with respect to
$(\mathcal{T},\mathcal{P})$_ if, for every $q\in\mathcal{Q}$, we have that
$\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle\models_{X}q$ iff
$\langle\mathcal{T},\mathcal{A}^{\prime},\mathcal{P}\rangle\models_{X}q$.

######  Definition 6.

Given a query language $\mathcal{L}_{q}\subseteq\textbf{BUCQ}$ and a DL
$\mathcal{L}_{\mathcal{T}}$, for $X\in\\{\text{SC},~{}\text{IC}\\}$, we say
that _$X$ -entailment preserves confidentiality for $\mathcal{L}_{q}$ in
$\mathcal{L}_{\mathcal{T}}$_ if, for every $\mathcal{L}_{\mathcal{T}}$ CQE
instance $\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$, and for every
finite set $\mathcal{Q}\subseteq\mathcal{L}_{q}$, there exists an ABox
$\mathcal{A}^{\prime}$ such that $(i)$
$\mathcal{T}\cup\mathcal{A}^{\prime}\models_{\mathsf{EQL}}\mathcal{P}$ and
$(ii)$ $\mathcal{A}$ and $\mathcal{A}^{\prime}$ are
$\mathcal{Q}$-indistinguishable for X-entailment w.r.t.
$(\mathcal{T},\mathcal{P})$.

For both SC-entailment and IC-entailment, we now investigate confidentiality-
preservation for BUCQ in $\text{DL-Lite}_{\mathcal{R}}$.

Hereinafter, with a slight abuse of notation, given a policy $\mathcal{P}$, we
denote by $\textit{MaxLenCQ}(\mathcal{P})$ the maximum length (number of
atoms) of a CQ occurring within the scope of the $K$ operator in
$\mathcal{P}$.

######  Proposition 2.

Let $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ be a
$\text{DL-Lite}_{\mathcal{R}}$ CQE instance. For every integer $k>0$, there
exists a $\text{DL-Lite}_{\mathcal{R}}$ CQE instance
$\mathcal{E}^{\prime}=\langle\mathcal{T},\mathcal{A}^{\prime},\mathcal{P}\rangle$
such that $(i)$
$\mathcal{T}\cup\mathcal{A}^{\prime}\models_{\mathsf{EQL}}\mathcal{P}$ and
$(ii)$ for every $q\in\textbf{BCQ}_{k}$, $\mathcal{E}\models_{\text{SC}}q$ iff
$\mathcal{E}^{\prime}\models_{\text{SC}}q$.

Proof (sketch).  Let $\mathcal{A}^{\prime}$ be the ABox isomorphic to the
finite set of BCQs
$\\{q\in\textbf{BCQ}_{h}\mid\mathcal{E}\models_{\text{SC}}q\\}$, where
$h=\max(k,\textit{MaxLenCQ}(\mathcal{P}))$. It is easy to verify that
$\mathcal{T}\cup\mathcal{A}^{\prime}\models_{\mathsf{EQL}}\mathcal{P}$, from
which it follows that $\mathcal{E}\models_{\text{SC}}q$ iff
$\mathcal{E}^{\prime}\models_{\text{SC}}q$ for every $q\in\textbf{BCQ}_{k}$. ∎

With the above property at hand, we can prove that SC-entailment preserves
confidentiality for BCQ in $\text{DL-Lite}_{\mathcal{R}}$. We show, however,
that the same does not hold for BUCQ.

######  Theorem 2.

SC-entailment preserves confidentiality for BCQ in $\text{DL-
Lite}_{\mathcal{R}}$, whereas it does not preserve confidentiality for BUCQ in
$\text{DL-Lite}_{\mathcal{R}}$.

###### Proof.

The first statement is an easy consequence of Proposition 2, when we assume
that $k$ is the maximum length of a BCQ in $\mathcal{Q}$. For the second
statement, we give a counterexample. Let
$\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$, where
$\mathcal{T}=\emptyset$, $\mathcal{A}=\\{C_{1}(o),C_{2}(o)\\}$ and
$\mathcal{P}=\\{\forall x(K(C_{1}(x)\land C_{2}(x))\rightarrow K\bot)\\}$.
Consider also the BUCQ $q=C_{1}(o)\lor C_{2}(o)$. It is easy to see that no
ABox $\mathcal{A}^{\prime}$ is such that
$\mathcal{T}\cup\mathcal{A}^{\prime}\models_{\mathsf{EQL}}\mathcal{P}$, and
$\mathcal{A}$ and $\mathcal{A}^{\prime}$ are $\\{q\\}$-indistinguishable for
SC-entailment w.r.t. $(\mathcal{T},\mathcal{P})$. ∎

The above proof also shows that SC-entailment does not preserve
confidentiality for BUCQ in $\text{DL-Lite}_{\mathcal{R}}$ even when EDs are
restricted to be acyclic (see Definition 8).

However, it turns out that confidentiality in the case of BUCQs in $\text{DL-
Lite}_{\mathcal{R}}$ is preserved by IC-entailment.

######  Proposition 3.

Let $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ be a
$\text{DL-Lite}_{\mathcal{R}}$ CQE instance. For every integer $k>0$, there
exists a $\text{DL-Lite}_{\mathcal{R}}$ CQE instance
$\mathcal{E}^{\prime}=\langle\mathcal{T},\mathcal{A}^{\prime},\mathcal{P}\rangle$
such that $(i)$
$\mathcal{T}\cup\mathcal{A}^{\prime}\models_{\mathsf{EQL}}\mathcal{P}$ and
$(ii)$ for every $q\in\textbf{BUCQ}_{k}$, $\mathcal{E}\models_{\text{IC}}q$
iff $\mathcal{E}^{\prime}\models_{\text{IC}}q$.

From the above property, we get the following result.

######  Theorem 3.

IC-entailment preserves confidentiality for BUCQ in $\text{DL-
Lite}_{\mathcal{R}}$.

##  5 Algorithms and complexity results

In this section, we analyze the data complexity of SC\- and IC-entailment of
B(U)CQs for $\text{DL-Lite}_{\mathcal{R}}$ CQE instances.

We study the decision problems associated with the query answering problem
under SC\- and IC-entailment. Specifically, we consider the following
recognition problem $X$-REC[$\mathcal{L}_{q}$], which is parametric w.r.t. a
Boolean query language $\mathcal{L}_{q}$ and
$X\in\\{\text{SC},~{}\text{IC}\\}$:

> Input: A $\text{DL-Lite}_{\mathcal{R}}$ CQE instance
> $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$, a Boolean
> query $q\in\mathcal{L}_{q}$
> Question: Does $\mathcal{E}\models_{X}q$?

We are interested in the data complexity Vardi (1982) version of the above
problem, which is the complexity where only the ABox $\mathcal{A}$ is regarded
as the input while all the other components are assumed to be fixed.

###  5.1 Arbitrary policies

We start by analyzing the complexity of SC-entailment of BCQs and BUCQs.

######  Lemma 1.

SC-REC[BCQ] is coNP-hard in data complexity.

Proof (sketch).  We show a reduction of 3-CNF, a well-known NP-hard problem,
to the complement of SC-REC[BCQ]. Let $\mathcal{T}$ be the empty TBox, and let
$\mathcal{P}$ contain the following EDs:

$\begin{array}[]{r@{}l}\forall x,y,v,z\,\big{(}K(&C_{1}(x,y)\wedge
V_{1}(x,v)\wedge V(y,v)\wedge\\\ &\quad N(x,z)\wedge S(x))\rightarrow
KS(z)\big{)}\\\ \forall x,y,v,z\,\big{(}K(&C_{2}(x,y)\wedge V_{2}(x,v)\wedge
V(y,v)\wedge\\\ &\quad N(x,z)\wedge S(x))\rightarrow KS(z)\big{)}\\\ \forall
x,y,v,z\,\big{(}K(&C_{3}(x,y)\wedge V_{3}(x,v)\wedge V(y,v)\wedge\\\ &\quad
N(x,z)\wedge S(x))\rightarrow KS(z)\big{)}\\\ \forall
x\,\big{(}K(&V(x,f)\wedge V(x,t))\rightarrow K\bot\big{)}\end{array}$

Given a 3-CNF formula $\phi$ with $m$ clauses, we represent every clause of
$\phi$ in the ABox $\mathcal{A}$ through the roles
$C_{1},C_{2},C_{3},V_{1},V_{2},V_{3}$: e.g., if the $i$-th clause of $\phi$ is
$\neg a\vee b\vee\neg c$, we add to $\mathcal{A}$ the assertions
$C_{1}(i,a),C_{2}(i,b),C_{3}(i,c),V_{1}(i,f),V_{2}(i,t),V_{3}(i,f)$. Moreover,
$\mathcal{A}$ contains the assertions

$\begin{array}[]{l}\\{V(a,f),V(a,t)\mid a\in\textit{PV}(\phi)\\}\>\cup\\\
\\{S(i),N(i,i+1)\mid 1\leq i\leq m\\}\end{array}$

where $\textit{PV}(\phi)$ are the propositional variables of $\phi$. It can be
verified that $\phi$ is satisfiable iff
$\langle\emptyset,\mathcal{A},\mathcal{P}\rangle\not\models_{\text{SC}}S(1)$.
∎

In order to prove a matching coNP upper bound for SC-REC[BUCQ], we introduce a
notion of consequences of a set of BCQs $\mathcal{C}$ with respect to a TBox
$\mathcal{T}$ and a policy $\mathcal{P}$.

######  Definition 7.

Let $\mathcal{T}$ be a $\text{DL-Lite}_{\mathcal{R}}$ TBox, $\mathcal{P}$ a
policy and $\mathcal{C}\subseteq\textbf{BCQ}$. We define
$\textit{PolicyCons}(\mathcal{T},\mathcal{P},\mathcal{C})$ as the smallest set
$\mathcal{S}\subseteq\textbf{BCQ}$ such that:

  * (i)

$\mathcal{C}\subseteq\mathcal{S}$;

  * (ii)

for every ED
$\forall\vec{x}_{1},\vec{x}_{2}(Kq_{b}(\vec{x}_{1},\vec{x}_{2})\rightarrow
Kq_{h}(\vec{x}_{2}))$ in $\mathcal{P}$ and ground substitutions $\vec{t}_{1}$
and $\vec{t}_{2}$ for $\vec{x}_{1}$ and $\vec{x}_{2}$, respectively, if
$\mathcal{T}\cup\mathcal{S}\models q_{b}(\vec{t}_{1},\vec{t}_{2})$ then
$q_{h}(\vec{t}_{2})\in\mathcal{S}$.

It can be immediately verified that
$\textit{PolicyCons}(\mathcal{T},\mathcal{P},\mathcal{C})$ can be computed in
polynomial time w.r.t. the size of $\mathcal{C}$.

The following property can be easily derived from the previous definition and
the definition of optimal CQ-censor.

######  Lemma 2.

Let $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ be a
$\text{DL-Lite}_{\mathcal{R}}$ CQE instance. For every
$\mathcal{C}\subseteq\textbf{BCQ}$, there exists an optimal CQ-censor of
$\mathcal{E}$ containing $\mathcal{C}$ iff
$\textit{PolicyCons}(\mathcal{T},\mathcal{P},\mathcal{C})\subseteq\textit{{BCQ}}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$.

We are now ready to provide an algorithm for checking SC-entailment of BUCQs.

input : $\text{DL-Lite}_{\mathcal{R}}$ CQE instance
$\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$, BUCQ $q$

1 $k\leftarrow\max(\textit{MaxLenCQ}(q),\textit{MaxLenCQ}(\mathcal{P}))$;

if  _there exists
$\mathcal{C}\subseteq\textit{{BCQ}}_{k}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$
such that  $(i)$ $\mathcal{T}\cup\mathcal{C}\models_{\mathsf{EQL}}\mathcal{P}$
and $(ii)$ $\mathcal{T}\cup\mathcal{C}\not\models q$ and 2$(iii)$ for every
$q^{\prime}\in\textit{{BCQ}}_{k}\text{-}Cons(\mathcal{T}\cup\mathcal{A})\setminus\mathcal{C}$,
_

3
$\textit{PolicyCons}(\mathcal{T},\mathcal{P},\mathcal{C}\cup\\{q^{\prime}\\})\not\subseteq\textit{{BCQ}}_{k}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$
then return $false$;

return $true$;

Algorithm 1 SC-Entails($\mathcal{E},q$)

######  Example 4.

Let $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$, where
$\mathcal{T}=\\{A\sqsubseteq D\\}$, $\mathcal{P}=\\{\forall x(K(D(x)\wedge
C(x))\rightarrow K\bot),~{}\forall x(KB(x)\rightarrow KA(x))\\}$, and
$\mathcal{A}=\\{A(o),B(o),C(o)\\}$.

Let now $\mathcal{C}$ be a maximal subset of
$\textbf{BCQ}_{2}\textit{-Cons}(\mathcal{T}\cup\mathcal{A})$ such that
$\mathcal{T}\cup\mathcal{C}\not\models A(o)\vee B(o)\vee D(o)$. One can see
that, for the BCQ $q=B(o)$, SC-Entails($\mathcal{E},q$) returns false as
$\mathcal{C}$ satisfies conditions $(i)$, $(ii)$, and $(iii)$ of the
algorithm. In particular,
$\textit{PolicyCons}(\mathcal{T},\mathcal{P},\mathcal{C}\cup\\{q\\})$ contains
$B(o)$, $A(o)$, $D(o)$, and $\bot$, hence it is not a subset of
$\textbf{BCQ}_{2}\textit{-Cons}(\mathcal{T}\cup\mathcal{A})$.

######  Lemma 3.

Let $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ be a
$\text{DL-Lite}_{\mathcal{R}}$ CQE instance, and let $q$ be a BUCQ. The
algorithm SC-Entails($\mathcal{E},q$) returns true iff
$\mathcal{E}\models_{\text{SC}}q$.

Proof (sketch).  First, using Lemma 2, it is easy to derive that a set of BCQs
$\mathcal{C}$ that satisfies conditions (i), (ii), and (iii) exists iff there
exists an optimal CQ-censor of $\mathcal{E}$ containing $\mathcal{C}$ and not
containing $q$ (and therefore iff $\mathcal{E}\not\models_{\text{SC}}q$).
Then, it can be shown that, for a $\text{DL-Lite}_{\mathcal{R}}$ TBox
$\mathcal{T}$ and a set $\mathcal{C}$ of BCQs that is closed under subqueries
(i.e., for every BCQ $q\in\mathcal{C}$, $\mathcal{C}$ contains all the
subqueries of $q$), $\mathcal{T}\cup\mathcal{C}\models q$ iff
$\mathcal{T}\cup\mathcal{C}_{h}\models q$, where $h=\textit{MaxLenCQ}(q)$ and
$\mathcal{C}_{h}=\mathcal{C}\cap\textbf{BCQ}_{k}$. This is the key property
that allows for proving that, if a set of BCQs $\mathcal{C}$ satisfying
conditions (i), (ii), and (iii) exists, then there exists a set of BCQs
$\mathcal{C}\subset\textit{{BCQ}}_{k}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$
that satisfies the above conditions, which implies the correctness of the
algorithm. ∎

The next theorem follows from Lemma 1, Lemma 3, and from the fact that the
previous algorithm can be executed in nondeterministic polynomial time in data
complexity.

######  Theorem 4.

SC-REC[BUCQ] is coNP-complete in data complexity.

We now give a second algorithm, which makes use of the above algorithm SC-
Entails to check IC-entailment.

input : $\text{DL-Lite}_{\mathcal{R}}$ CQE instance
$\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$, BUCQ $q$

1 foreach  _BCQ $q^{\prime}\in q$_ do

2 if  _SC -Entails($\mathcal{E},q^{\prime}$)_ then return $true$;

3

return $false$;

Algorithm 2 IC-Entails($\mathcal{E},q$)

######  Lemma 4.

Let $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ be a
$\text{DL-Lite}_{\mathcal{R}}$ CQE instance and let $q$ be a BUCQ. The
algorithm IC-Entails($\mathcal{E},q$) returns true iff
$\mathcal{E}\models_{\text{IC}}q$.

###### Proof.

First, from Definition 5, if $\mathcal{T}$ is a $\text{DL-Lite}_{\mathcal{R}}$
TBox, then $\mathcal{E}\models_{\text{IC}}q$ iff there exists a BCQ
$q^{\prime}\in q$ such that $\mathcal{E}\models_{\text{IC}}q^{\prime}$. Then,
by Theorem 1, $\mathcal{E}\models_{\text{IC}}q^{\prime}$ iff
$\mathcal{E}\models_{\text{SC}}q^{\prime}$. Therefore, by Lemma 3 the thesis
follows. ∎

From Lemma 1, Lemma 4, Theorem 1, and from the fact that the algorithm SC-
Entails($\mathcal{E},q$) can be executed in nondeterministic polynomial time
in data complexity, we obtain:

######  Theorem 5.

IC-REC[BUCQ] is coNP-complete in data complexity.

###  5.2 Acyclic policies

Given the intractability results for the set of all $\text{DL-
Lite}_{\mathcal{R}}$ CQE instances presented above, in this section we focus
on a subclass of $\text{DL-Lite}_{\mathcal{R}}$ CQE instances, whose policies
enjoy an acyclicity property.

First, we extend the notion of first-order rewritability defined over ground
ABoxes to the case of ABoxes with labeled nulls and to the problems of SC-
entailment and IC-entailment of BUCQs. Given an ABox $\mathcal{A}$, we define
the FO interpretation $\mathcal{I}_{\mathcal{A}}$ over the predicates
$\Gamma_{C}\cup\Gamma_{R}$ plus the additional new concept Ind, and the
constants $\Gamma_{I}\cup\Gamma_{N}$ (i.e. in $\mathcal{I}_{\mathcal{A}}$ we
consider the symbols from $\Gamma_{N}$ as ordinary constants):

  * •

$\Delta^{\mathcal{I}_{\mathcal{A}}}=\Gamma_{I}\cup\Gamma_{N}$;

  * •

$a^{\mathcal{I}_{\mathcal{A}}}=a$ for every $a\in\Gamma_{I}\cup\Gamma_{N}$;

  * •

for every concept name $C$, $C^{\mathcal{I}_{\mathcal{A}}}=\\{a\mid
C(a)\in\mathcal{A}\\}$;

  * •

for every role name $R$, $R^{\mathcal{I}_{\mathcal{A}}}=\\{(a,b)\mid
R(a,b)\in\mathcal{A}\\}$;

  * •

$\textit{Ind}^{\mathcal{I}_{\mathcal{A}}}=\Gamma_{I}$.

Given a TBox $\mathcal{T}$, a policy $\mathcal{P}$ and a BUCQ $q$, and
$X\in\\{\text{SC},~{}\text{IC}\\}$, we say that a FO sentence $q^{\prime}$ is
a _first-order rewriting of $X$-entailment of $q$ for $\mathcal{T}$ and
$\mathcal{P}$_ if, for every ABox $\mathcal{A}$,
$\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle\models_{X}q$ iff
$\textit{eval}(q^{\prime},\mathcal{I}_{\mathcal{A}})$ is true.

Our goal now is to define an algorithm that, for a $\text{DL-
Lite}_{\mathcal{R}}$ TBox $\mathcal{T}$ and a policy $\mathcal{P}$, is able to
construct a first-order rewriting of SC-entailment of $q$ for $\mathcal{T}$
and $\mathcal{P}$. This is not possible in general, given the coNP-
completeness result provided by Theorem 5. Therefore, we now define the
subclass of policies that are acyclic for a $\text{DL-Lite}_{\mathcal{R}}$
TBox.

Given a $\text{DL-Lite}_{\mathcal{R}}$ TBox $\mathcal{T}$ and a policy
$\mathcal{P}$, the _dependency graph_ of $\mathcal{T}$ and $\mathcal{P}$,
denoted by $G(\mathcal{T},\mathcal{P})$, is the directed graph defined as
follows: (i) the set of nodes of $G(\mathcal{T},\mathcal{P})$ is the set of
predicates occurring in $\mathcal{T}\cup\mathcal{P}$; (ii) there is a P-edge
from node $p_{1}$ to node $p_{2}$ in $G(\mathcal{T},\mathcal{P})$ if and only
if there exists an epistemic dependency of the form (1) in $\mathcal{P}$ such
that $p_{1}$ occurs in $q_{b}$ and $p_{2}$ occurs in $q_{h}$; (iii) there is a
T-edge from node $p_{1}$ to node $p_{2}$ in $G(\mathcal{T},\mathcal{P})$ if
and only if there is a concept or role inclusion in $\mathcal{T}$ such that
$p_{1}$ occurs in the left-hand side and $p_{2}$ occurs in the right-hand side
of the inclusion.

######  Definition 8.

Given a $\text{DL-Lite}_{\mathcal{R}}$ TBox $\mathcal{T}$ and a policy
$\mathcal{P}$, we say that $\mathcal{P}$ is _acyclic for $\mathcal{T}$_ if
there exists no cycle in $G(\mathcal{T},\mathcal{P})$ involving a P-edge.

Informally, the graph $G(\mathcal{T},\mathcal{P})$ represents the logical
dependencies between the predicates in $\mathcal{T}$ and $\mathcal{P}$: a
P-edge (resp., a T-edge) from $p_{1}$ to $p_{2}$ means that predicate $p_{1}$
may have a direct implication on $p_{2}$ through $\mathcal{P}$ (resp., through
$\mathcal{T}$). The notion of acyclicity defined above guarantees that, if
$(p_{1},p_{2})$ is a P-edge in $G(\mathcal{T},\mathcal{P})$, then there is no
path from $p_{2}$ to $p_{1}$, i.e. $p_{2}$ does not have any (direct or
indirect) implication on $p_{1}$.

######  Example 5.

The following ED aims to hide the hierarchical structure of an organization
unless it is public.

$\delta_{6}=\forall x,y($ |  $K\mathsf{hasPosition}(x,y)\rightarrow$
---|---
|  $K\,\exists z(\mathsf{worksIn}(x,z)\land\mathsf{PublicOffice}(z))))$

Moreover, we want to hide the fact that a person collaborates with a secret
service unless she holds an important position ($\mathsf{KeyPosition}$), for
example, she is the director. The following ED achieves this goal:

$\delta_{7}=\forall x($ |  $K\,\exists y(\mathsf{collaborate}(x,y)\land\mathsf{SecService}(y))\rightarrow$
---|---
|  $K\,\exists z(\mathsf{hasPosition}(x,z)\land\mathsf{KeyPosition}(z)))$

Let the policy $\mathcal{P}$ be $\mathcal{P}=\\{\delta_{6},\delta_{7}\\}$. For
the empty TBox $\mathcal{T}=\emptyset$, one can see that $\mathcal{P}$ is
acyclic for $\mathcal{T}$. Conversely, for the $\text{DL-Lite}_{\mathcal{R}}$
TBox $\mathcal{T}=\\{\mathsf{worksIn}\sqsubseteq\mathsf{collaborate}\\}$,
$\mathcal{P}$ is not acyclic for $\mathcal{T}$, since there is a cycle in
$G(\mathcal{T},\mathcal{P})$ constituted by the P-edges
$(\mathsf{collaborate},\mathsf{hasPosition})$ and
$(\mathsf{hasPosition},\mathsf{worksIn})$ and the T-edge
$(\mathsf{worksIn},\mathsf{collaborate})$.

With this notion in place, we can now describe the decision problem we are
going to study. Specifically, for $X\in\\{\text{SC},~{}\text{IC}\\}$, we
consider the recognition problem $X$-AREC[$\mathcal{L}_{q}$], which is
parametric w.r.t. a Boolean query language $\mathcal{L}_{q}$.
$X$-AREC[$\mathcal{L}_{q}$] is defined exactly as $X$-REC[$\mathcal{L}_{q}$]
except that the input $\text{DL-Lite}_{\mathcal{R}}$ CQE instances
$\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ are such that the policy
$\mathcal{P}$ is acyclic for $\mathcal{T}$.

From now on, given a set of CQs $\mathcal{Q}$,111W.l.o.g. we assume that the
sets of existentially quantified variable symbols used by the CQs in
$\mathcal{Q}$ are pairwise disjoint. we denote by $\textit{And}(\mathcal{Q})$
the CQ
$\exists\vec{y}\big{(}\bigwedge_{\exists\vec{z}\phi\in\mathcal{Q}}\phi\big{)}$,
where $\vec{y}$ is a sequence of all the existentially quantified variables
occurring in $\mathcal{Q}$.

Given a TBox $\mathcal{T}$, a policy $\mathcal{P}$ and a CQ $q(\vec{x})$, we
denote by $\phi_{\mathit{pc}}(\mathcal{T},\mathcal{P},q(\vec{x}))$ the CQ
(with free variables $\vec{x}$)
$\textit{And}(\textit{PolicyCons}(\mathcal{T},\mathcal{P},\\{q(\vec{x})\\})$,
where $\textit{PolicyCons}(\mathcal{T},\mathcal{P},\\{q(\vec{x})\\})$ is as in
Definition 7, considering the free variables in $\vec{x}$ as new constant
symbols.

######  Lemma 5.

Let $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ be a
$\text{DL-Lite}_{\mathcal{R}}$ CQE instance, let $\mathcal{P}$ be an acyclic
policy for $\mathcal{T}$, and let $q(\vec{x})$ be a CQ. For every ground
substitution $\vec{c}$ for $\vec{x}$, there exists an optimal CQ-censor of
$\mathcal{E}$ that contains the BCQ $q(\vec{c})$ if and only if
$\textit{eval}(q_{r}(\vec{c}),\mathcal{I}_{\mathcal{A}})$ is true, where
$q_{r}(\vec{x})=\textit{PerfectRef}(\phi_{\mathit{pc}}(\mathcal{T},\mathcal{P},q(\vec{x})),\mathcal{T})$.

Given a BCQ $q$, we say that a BCQ $q^{\prime}$ is a _clash for $q$ in
$\mathcal{E}$_ if there exists an optimal CQ-censor of $\mathcal{E}$
containing $q^{\prime}$ and there exists no optimal CQ-censor of $\mathcal{E}$
containing both $q$ and $q^{\prime}$. Given a BUCQ $q$, we say that a BCQ
$q^{\prime}$ is a clash for $q$ in $\mathcal{E}$ if for every
$q^{\prime\prime}\in q$, $q^{\prime}$ is a clash for $q^{\prime\prime}$ in
$\mathcal{E}$.

Now, let $q$ be a BUCQ and let $q^{\prime}(\vec{x})$ be a CQ. We denote by
$\textit{Clash}(q,q^{\prime}(\vec{x}),\mathcal{T},\mathcal{P})$ the following
FO formula (with free variables $\vec{x}$):

$\begin{array}[]{l}\textit{PerfectRef}(\phi_{\mathit{pc}}(\mathcal{T},\mathcal{P},q^{\prime}(\vec{x})),\mathcal{T})\>\wedge\\\
\displaystyle\big{(}\bigwedge_{q_{i}\in
q}\neg\textit{PerfectRef}(\phi_{\mathit{pc}}(\mathcal{T},\mathcal{P},\textit{And}(\\{q^{\prime}(\vec{x}),q_{i})\\}),\mathcal{T})\big{)}\end{array}$

Using Lemma 5, we are able to prove the following property.

######  Lemma 6.

Let $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ be a
$\text{DL-Lite}_{\mathcal{R}}$ CQE instance, let $q\in\textbf{BUCQ}$, let
$q^{\prime}(\vec{x})$ be a CQ, and let
$q_{i}\in\textit{{BCQ}}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$ for every
$q_{i}\in q$. Then, for every ground substitution $\vec{c}$ for $\vec{x}$,
$q^{\prime}(\vec{c})$ is a clash for $q$ in $\mathcal{E}$ iff
$\textit{eval}(q_{cl}(\vec{c}),\mathcal{I}_{\mathcal{A}})$ is true, where
$q_{cl}(\vec{x})=\textit{Clash}(q,q^{\prime}(\vec{x}),\mathcal{T},\mathcal{P})$.

It is now possible to show that, in the case of $\text{DL-Lite}_{\mathcal{R}}$
CQE instances in which $\mathcal{P}$ is an acyclic policy for $\mathcal{T}$,
if a clash for a BUCQ $q$ exists, then there exists a clash for $q$ whose
length depends only on the size of $\mathcal{P}\cup\mathcal{T}\cup\\{q\\}$.

######  Lemma 7.

Let $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ be a
$\text{DL-Lite}_{\mathcal{R}}$ CQE instance such that $\mathcal{P}$ is acyclic
for $\mathcal{T}$, and let $q$ be a BUCQ such that
$q_{i}\in\textit{{BCQ}}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$ for every
$q_{i}\in q$. Then, $\mathcal{E}\models_{\text{SC}}q$ iff there exists no BCQ
$q^{\prime}$ such that $q^{\prime}$ is a clash for $q$ in $\mathcal{E}$ and
$\textit{Len}(q^{\prime})\leq\ell$, where $\ell=m\cdot k^{h}$, $m$ is the
number of BCQs in $q$, $k=\textit{MaxLenCQ}(\mathcal{P})$, and $h$ is the
number of EDs in $\mathcal{P}$.

We can now define an FO sentence and then prove that it provides a first-order
rewriting of SC-entailment of BUCQs.

######  Definition 9.

Let $\mathcal{T}$ be a $\text{DL-Lite}_{\mathcal{R}}$ TBox, let $\mathcal{P}$
be an acyclic policy for $\mathcal{T}$, and let $q\in\textbf{BUCQ}$. We define
the FO sentence $\textit{\text{SC}-Entailed}(q,\mathcal{T},\mathcal{P})$ as
follows:

$\begin{array}[]{l}\displaystyle\bigvee_{q^{p}\in\wp^{-}(q)}\Big{(}\bigwedge_{q_{i}\in
q^{p}}\textit{PerfectRef}(q_{i},\mathcal{T})\>\wedge\bigwedge_{q_{i}\in
q\setminus
q^{p}}\neg\textit{PerfectRef}(q_{i},\mathcal{T})\>\wedge\\\\[2.84526pt]
\displaystyle\qquad\;\;\bigwedge_{q^{\prime}(\vec{x})\in\mathcal{Q}}\neg\big{(}\exists\vec{x}\,(\textit{Clash}(q^{p},q^{\prime}(\vec{x}),\mathcal{T},\mathcal{P})\wedge\bigwedge_{x\in\vec{x}}Ind(x))\big{)}\Big{)}\end{array}$

with $\wp^{-}(q)=\wp(q)\setminus\\{\emptyset\\}$, where $\wp(q)$ is the
powerset of $q$, $\mathcal{Q}$ is the set of CQs defined over the predicates
and constants occurring in $\\{q\\}\cup\mathcal{P}\cup\mathcal{T}$ and whose
maximum length is $m\cdot k^{h}$, $m$ is the number of BCQs in $q$, $h$ is the
number of EDs in $\mathcal{P}$, and $k=\textit{MaxLenCQ}(\mathcal{P})$.

Based on Lemma 6 and Lemma 7, we are able to prove the following crucial
property for $\textit{\text{SC}-Entailed}(q,\mathcal{T},\mathcal{P})$.

######  Lemma 8.

Let $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ be a
$\text{DL-Lite}_{\mathcal{R}}$ CQE instance such that $\mathcal{P}$ is an
acyclic policy for $\mathcal{T}$, and let $q\in\textbf{BUCQ}$. Then,
$\textit{\text{SC}-Entailed}(q,\mathcal{T},\mathcal{P})$ is a first-order
rewriting of SC-entailment of $q$ for $\mathcal{T}$ and $\mathcal{P}$.

The above first-order rewritability property of SC-entailment of BUCQs
immediately implies the next result.

######  Theorem 6.

SC-AREC[BUCQ] is in $\mathrm{AC}^{0}$ in data complexity.

Finally, given a BUCQ $q$, we define the sentence
$\textit{\text{IC}-Entailed}(q,\mathcal{T},\mathcal{P})$ as follows:

$\begin{array}[]{l}\bigvee_{q_{i}\in
q}\textit{\text{SC}-Entailed}(q_{i},\mathcal{T},\mathcal{P})\end{array}$

It is then easy to prove the analogous of Lemma 8 (and Theorem 6) for
$\textit{\text{IC}-Entailed}(q,\mathcal{T},\mathcal{P})$ and IC-entailment.

######  Lemma 9.

Let $\mathcal{E}=\langle\mathcal{T},\mathcal{A},\mathcal{P}\rangle$ be a
$\text{DL-Lite}_{\mathcal{R}}$ CQE instance such that $\mathcal{P}$ is an
acyclic policy for $\mathcal{T}$, and let $q\in\textbf{BUCQ}$. Then,
$\textit{\text{IC}-Entailed}(q,\mathcal{T},\mathcal{P})$ is a first-order
rewriting of IC-entailment of $q$ for $\mathcal{T}$ and $\mathcal{P}$.

###### Proof.

The result follows immediately from Lemma 8 and from the fact that
$\mathcal{E}\models_{\text{IC}}q$ iff there exists a BCQ $q_{i}\in q$ such
that $\mathcal{E}\models_{\text{SC}}q_{i}$ (the latter property easily follows
from Definition 5 and Theorem 1). ∎

######  Theorem 7.

IC-AREC[BUCQ] is in $\mathrm{AC}^{0}$ in data complexity.

##  6 Conclusions

The results given in this paper are summarized in Table 1. Beyond their
theoretical connotation, our results for acyclic dependencies are particularly
interesting for practical applications, since data complexity in these cases
is the same as that for standard query answering over databases, and this
paves the way for implementation through consolidated SQL technology.
Moreover, the table shows that confidentiality is preserved in most of the
cases that we have considered.

We posit that the epistemic nature of our framework makes it suited to being
extended to incorporate user background knowledge, which can be modeled
through appropriate epistemic formulas. The implications of this extension
remain a subject for future investigation. Further possible development may
explore ontology languages alternative to $\text{DL-Lite}_{\mathcal{R}}$, such
as $\mathcal{EL}$ Baader et al. (2005) or the OWL 2 profiles Motik et al.
(2012). Additionally, extending the framework to accommodate preferences on
data to be censored while ensuring compliance to the policy, as in Cima et al.
(2021), and examining a dynamic context where censors filter responses based
on previous answers, as explored in Bonatti et al. (2022), are paths for
further research.

## Acknowledgements

This work was partially supported by: projects FAIR (PE0000013) and SERICS
(PE00000014) under the MUR National Recovery and Resilience Plan funded by the
EU - NextGenerationEU; GLACIATION project funded by the EU (N. 101070141);
ANTHEM (AdvaNced Technologies for Human-centrEd Medicine) project (CUP
B53C22006700001) funded by the National Plan for NRRP Complementary
Investments; the MUR PRIN 2022LA8XBH project Polar (POLicy specificAtion and
enfoRcement for privacy-enhanced data management); and by the EU under the
H2020-EU.2.1.1 project TAILOR (grant id. 952215).

## References

  * Abiteboul et al. [1995] Serge Abiteboul, Richard Hull, and Victor Vianu.  Foundations of Databases.  Addison Wesley Publ. Co., 1995.
  * Baader et al. [2005] Franz Baader, Sebastian Brandt, and Carsten Lutz.  Pushing the $\mathcal{EL}$ envelope.  In Proc. of the 19th Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 364–369, 2005.
  * Baader et al. [2020] Franz Baader, Francesco Kriegel, Adrian Nuradiansyah, and Rafael Peñaloza.  Computing compliant anonymisations of quantified ABoxes w.r.t. $\mathcal{EL}$ policies.  In Proc. of the 19th Int. Semantic Web Conf. (ISWC), volume 12506 of Lecture Notes in Computer Science, pages 3–20. Springer, 2020.
  * Baget et al. [2011] Jean-François Baget, Michel Leclère, Marie-Laure Mugnier, and Eric Salvat.  On rules with existential variables: Walking the decidability line.  Artif. Intell., 175(9-10):1620–1654, 2011.
  * Biskup and Bonatti [2004] Joachim Biskup and Piero A. Bonatti.  Controlled query evaluation for enforcing confidentiality in complete information systems.  Int. J. Inf. Sec., 3(1):14–27, 2004.
  * Biskup and Weibert [2008] Joachim Biskup and Torben Weibert.  Keeping secrets in incomplete databases.  Int. J. Inf. Sec., 7(3):199–217, 2008.
  * Biskup [2000] Joachim Biskup.  For unknown secrecies refusal is better than lying.  Data and Knowledge Engineering, 33(1):1–23, 2000.
  * Bonatti and Sauro [2013] Piero A. Bonatti and Luigi Sauro.  A confidentiality model for ontologies.  In Proc. of the 12th Int. Semantic Web Conf. (ISWC), pages 17–32, 2013.
  * Bonatti et al. [2022] Piero Bonatti, Gianluca Cima, Domenico Lembo, Lorenzo Marconi, Riccardo Rosati, Luigi Sauro, and Domenico Fabio Savo.  Controlled query evaluation in OWL 2 QL: A ”longest honeymoon” approach.  In Proc. of the 21st Int. Semantic Web Conf. (ISWC), volume 12922 of Lecture Notes in Computer Science, pages 428–444. Springer, 2022.
  * Bonatti [2022] Piero A. Bonatti.  A false sense of security.  Artificial Intelligence, 310, 2022.
  * Calì et al. [2012] Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz.  A general datalog-based framework for tractable query answering over ontologies.  J. of Web Semantics, 14:57–83, 2012.
  * Calvanese et al. [2007a] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati.  EQL-Lite: Effective first-order query processing in description logics.  In Proc. of the 20th Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 274–279, 2007.
  * Calvanese et al. [2007b] 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.  J. of Automated Reasoning, 39(3):385–429, 2007.
  * Cima et al. [2021] Gianluca Cima, Domenico Lembo, Lorenzo Marconi, Riccardo Rosati, and Domenico Fabio Savo.  Controlled query evaluation over prioritized ontologies with expressive data protection policies.  In Proc. of the 20th Int. Semantic Web Conf. (ISWC), volume 12922 of Lecture Notes in Computer Science, pages 374–391. Springer, 2021.
  * Console and Lenzerini [2020] Marco Console and Maurizio Lenzerini.  Epistemic integrity constraints for ontology-based data management.  In Proc. of the 37th AAAI Conf. on Artificial Intelligence (AAAI), pages 2790–2797. AAAI Press, 2020.
  * Cuenca Grau et al. [2013] Bernardo Cuenca Grau, Evgeny Kharlamov, Egor V. Kostylev, and Dmitriy Zheleznyakov.  Controlled query evaluation over OWL 2 RL ontologies.  In Proc. of the 12th Int. Semantic Web Conf. (ISWC), pages 49–65, 2013.
  * Cuenca Grau et al. [2015] Bernardo Cuenca Grau, Evgeny Kharlamov, Egor V. Kostylev, and Dmitriy Zheleznyakov.  Controlled query evaluation for datalog and OWL 2 profile ontologies.  In Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 2883–2889, 2015.
  * European Union [2016] European Union.  Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016.  Official J. of the European Union, L 119:48, 2016.
  * König et al. [2015] Mélanie König, Michel Leclère, Marie-Laure Mugnier, and Michaël Thomazo.  Sound, complete and minimal UCQ-rewriting for existential rules.  Semantic Web, 6(5):451–475, 2015.
  * Lembo et al. [2019] Domenico Lembo, Riccardo Rosati, and Domenico Fabio Savo.  Revisiting controlled query evaluation in description logics.  In Proc. of the 28th Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 1786–1792, 2019.
  * Motik et al. [2012] Boris Motik, Bernardo Cuenca Grau, Ian Horrocks, Zhe Wu, Achille Fokoue, and Carsten Lutz.  OWL 2 Web Ontology Language profiles (second edition).  W3C Recommendation, World Wide Web Consortium, December 2012.  Available at http://www.w3.org/TR/owl2-profiles/.
  * Sicherman et al. [1983] George L. Sicherman, Wiebren de Jonge, and Reind P. van de Riet.  Answering queries without revealing secrets.  ACM Trans. on Database Systems, 8(1):41–59, 1983.
  * Vardi [1982] Moshe Y. Vardi.  The complexity of relational query languages.  In Proc. of the 14th ACM SIGACT Symp. on Theory of Computing (STOC), pages 137–146, 1982.

## Appendix

### Auxiliary notions and results

We recall the following property, which is a direct consequence of [Calvanese
et al., 2007a, Theorem 6].

######  Proposition 4.

Let $\Phi,\Phi^{\prime}$ be FO theories, and let $\phi$ be an ED. If, for
every subformula $Kq(\vec{x})$ occurring in $\phi$, and for every ground
substitution $\vec{t}$ for $\vec{x}$, $\Phi\models q(\vec{t})$ iff
$\Phi^{\prime}\models q(\vec{t})$, then $\Phi\models_{\mathsf{EQL}}\phi$ iff
$\Phi^{\prime}\models_{\mathsf{EQL}}\phi$.

We say that a set of BCQs $\mathcal{C}$ is _closed under subqueries_ if, for
every $q\in\mathcal{C}$ and for every subquery222Given a BCQ $q$ of the form
$\exists\vec{x}_{1}(\alpha_{1}\wedge\ldots\wedge\alpha_{n})$, a _subquery_ of
$q$ is a BCQ $q^{\prime}$ of the form
$\exists\vec{x}_{2}(\alpha_{i_{1}}\wedge\ldots\wedge\alpha_{i_{m}})$ such
that, for every $j\in\\{1,\ldots,m\\}$, $1\leq i_{j}\leq n$, and $\vec{x}_{2}$
are the variables of $\vec{x}_{1}$ that occur in some $\alpha_{i_{j}}$.
Informally, the subquery $q^{\prime}$ is obtained from $q$ deleting some of
its atoms. $q^{\prime}$ of $q$, we have $q^{\prime}\in\mathcal{C}$.

######  Proposition 5.

Let $\mathcal{T}$ be a $\text{DL-Lite}_{\mathcal{R}}$ TBox, and let
$\mathcal{C}$ be a set of BCQs closed under subqueries. For every BUCQ $q$,
$\mathcal{T}\cup\mathcal{C}\models q$ iff
$\mathcal{T}\cup\mathcal{C}_{k}\models q$, where $k=\textit{MaxLenCQ}(q)$ and
$\mathcal{C}_{k}=\mathcal{C}\cap\textbf{BCQ}_{k}$.

###### Proof.

We prove that, if $\mathcal{T}\cup\mathcal{C}\models q$ then
$\mathcal{T}\cup\mathcal{C}_{k}\models q$ (the only-if direction is trivial).
First, by Proposition 1, $\mathcal{T}\cup\mathcal{C}\models q$ iff
$\mathcal{C}\models q^{\prime}$, where
$q^{\prime}=\textit{PerfectRef}(q,\mathcal{T})$. As said, we also have that
$\textit{MaxLenCQ}(q)=\textit{MaxLenCQ}(q^{\prime})$. Moreover,
$\mathcal{C}\models q^{\prime}$ iff there exists a BCQ $q^{\prime\prime}$ in
$q^{\prime}$ and a homomorphism $h$ mapping $q^{\prime\prime}$ into
$\mathcal{C}$: now, since $\mathcal{C}$ is closed under subqueries, the
existence of $h$ implies the existence of a homomorphism that maps
$q^{\prime\prime}$ onto a subset of BCQs $\mathcal{C}^{\prime}$ of
$\mathcal{C}$ such that the length of each BCQ of $\mathcal{C}^{\prime}$ is
not greater than $\textit{Len}(q^{\prime\prime})$ (which of course is not
greater than $\textit{MaxLenCQ}(q^{\prime})$). This immediately implies that
$\mathcal{C}\models q^{\prime}$ iff $\mathcal{C}_{k}\models q^{\prime}$, which
in turn implies the thesis. ∎

### Proofs of theorems and lemmas

Proof of Proposition 2

Let $\mathcal{Q}$ be the finite set of BCQs
$\\{q\in\textbf{BCQ}_{h}\mid\mathcal{E}\models_{\text{SC}}q\\}$, where
$h=\max(k,\textit{MaxLenCQ}(\mathcal{P}))$. We observe that
$\mathcal{Q}\subseteq\bigcap_{\mathcal{C}\in\textit{OptCQCens}(\mathcal{E})}\mathcal{C}$.
Let also $\mathcal{A}^{\prime}$ be the ABox isomorphic to $\mathcal{Q}$, i.e.
the ABox obtained by $(i)$ creating, for each $q\in\mathcal{Q}$, a set
$\mathcal{A}_{q}$ collecting the atoms occurring in $q$; $(ii)$ replacing
distinct variables occurring in each $\mathcal{A}_{q}$ with distinct fresh
labeled nulls; $(iii)$ representing $\mathcal{A}^{\prime}$ as
$\bigcup_{q\in\mathcal{Q}}\mathcal{A}_{q}$.

We now prove by contradiction that
$\mathcal{T}\cup\mathcal{A}^{\prime}\models_{\mathsf{EQL}}\mathcal{P}$, so let
us suppose this does not hold. In this case, there would exist an ED
$\tau\in\mathcal{P}$ of the form
$\forall\vec{x}_{1},\vec{x}_{2}(Kq_{b}(\vec{x}_{1},\vec{x}_{2})\rightarrow
Kq_{h}(\vec{x}_{2}))$ and two ground substitutions $\vec{c_{1}}$ and
$\vec{c_{2}}$ for $\vec{x}_{1}$ and $\vec{x_{2}}$, respectively, such that
$\mathcal{T}\cup\mathcal{A}^{\prime}\models q_{b}(\vec{c}_{1},\vec{c}_{2})$
and $\mathcal{T}\cup\mathcal{A}^{\prime}\not\models q_{h}(\vec{c}_{2})$. By
construction of $\mathcal{A}^{\prime}$ this holds only if
$\mathcal{T}\cup\mathcal{Q}\models q_{b}(\vec{c}_{1},\vec{c}_{2})$ and
$\mathcal{T}\cup\mathcal{Q}\not\models q_{h}(\vec{c}_{2})$. Since, as noticed,
$\mathcal{Q}$ is contained in every CQ-censor for $\mathcal{E}$, then from
$\mathcal{T}\cup\mathcal{Q}\models q_{b}(\vec{c}_{1},\vec{c}_{2})$ it follows
by monotonicity that $\mathcal{T}\cup\mathcal{C}\models
q_{b}(\vec{c}_{1},\vec{c}_{2})$ holds for every CQ-censor $\mathcal{C}$ for
$\mathcal{E}$ (i.e.
$\mathcal{E}\models_{\text{SC}}q_{b}(\vec{c}_{1},\vec{c}_{2})$). Moreover,
from $\mathcal{T}\cup\mathcal{Q}\not\models q_{h}(\vec{c}_{2})$ and by
construction of $\mathcal{Q}$ it follows that
$\mathcal{E}\not\models_{\text{SC}}q_{h}(\vec{c}_{2})$ (indeed, from
$\mathcal{E}\models_{\text{SC}}q_{h}(\vec{c}_{2})$ we would have that
$q_{h}(\vec{c}_{2})\in\mathcal{Q}$, and so that
$\mathcal{T}\cup\mathcal{Q}\models_{\text{SC}}q_{h}(\vec{c}_{2})$).

Since $\mathcal{E}\models_{\text{SC}}q_{b}(\vec{c}_{1},\vec{c}_{2})$ and
$\mathcal{E}\not\models_{\text{SC}}q_{h}(\vec{c}_{2})$, then it holds
$\mathcal{T}\cup\mathcal{C}\not\models_{\mathsf{EQL}}\mathcal{P}$ for at least
one CQ-censor $\mathcal{C}$ for $\mathcal{E}$. This, however, contradicts
Definition 3, thus proving that
$\mathcal{T}\cup\mathcal{A}^{\prime}\models_{\mathsf{EQL}}\mathcal{P}$. Then,
it is immediate to verify that, given any $q\in\textbf{BCQ}_{k}$,
$\mathcal{E}\models_{\text{SC}}q$ iff
$\mathcal{E}^{\prime}\models_{\text{SC}}q$. ∎

Proof of Proposition 3

Let $\mathcal{A}^{\prime}$ be the ABox isomorphic to the finite set of BCQs
$\mathcal{Q}=\\{q\in\textbf{BCQ}_{h}\mid\mathcal{E}\models_{\text{SC}}q\\}$,
where $h=\max(k,\textit{MaxLenCQ}(\mathcal{P}))$. First, as shown in the proof
of Proposition 2, we have that
$\mathcal{T}\cup\mathcal{A}^{\prime}\models_{\mathsf{EQL}}\mathcal{P}$. Then,
since $\mathcal{T}\cup\mathcal{A}^{\prime}\models_{\mathsf{EQL}}\mathcal{P}$,
it is immediate to verify that, for every $q\in\textbf{BUCQ}_{k}$,
$\mathcal{E}\models_{\text{IC}}q$ iff
$\mathcal{E}^{\prime}\models_{\text{IC}}q$ (the key property is that a BUCQ is
IC-entailed iff at least one of the BCQs occurring in it is IC-entailed). ∎

Proof of Theorem 3

This property is an immediate consequence of Proposition 3 when we assume that
$k$ is the maximum length of a BCQ occurring in a BUCQ of $\mathcal{Q}$. ∎

Proof of Lemma 1

We show a reduction of 3-CNF, a well-known NP-hard problem, to the complement
of SC-REC[BCQ]. Let $\mathcal{T}$ be the empty TBox, and let $\mathcal{P}$
contain the following EDs:

$\begin{array}[]{r@{}l}\forall x,y,v,z\,\big{(}K(&C_{1}(x,y)\wedge
V_{1}(x,v)\wedge V(y,v)\wedge\\\ &\quad N(x,z)\wedge S(x))\rightarrow
KS(z)\big{)}\\\ \forall x,y,v,z\,\big{(}K(&C_{2}(x,y)\wedge V_{2}(x,v)\wedge
V(y,v)\wedge\\\ &\quad N(x,z)\wedge S(x))\rightarrow KS(z)\big{)}\\\ \forall
x,y,v,z\,\big{(}K(&C_{3}(x,y)\wedge V_{3}(x,v)\wedge V(y,v)\wedge\\\ &\quad
N(x,z)\wedge S(x))\rightarrow KS(z)\big{)}\\\ \forall
x\,\big{(}K(&V(x,f)\wedge V(x,t))\rightarrow K\bot\big{)}\end{array}$

Given a 3-CNF formula $\phi$ with $m$ clauses, we represent every clause of
$\phi$ in the ABox $\mathcal{A}$ through the roles
$C_{1},C_{2},C_{3},V_{1},V_{2},V_{3}$: e.g., if the $i$-th clause of $\phi$ is
$\neg a\vee b\vee\neg c$, we add to $\mathcal{A}$ the assertions
$C_{1}(i,a),C_{2}(i,b),C_{3}(i,c),V_{1}(i,f),V_{2}(i,t),V_{3}(i,f)$. Moreover,
$\mathcal{A}$ contains the assertions

$\begin{array}[]{l}\\{V(a,f),V(a,t)\mid a\in\textit{PV}(\phi)\\}\>\cup\\\
\\{S(i),N(i,i+1)\mid 1\leq i\leq m\\}\end{array}$

where $\textit{PV}(\phi)$ are the propositional variables of $\phi$.

We now show that $\phi$ is satisfiable iff
$\langle\emptyset,\mathcal{A},\mathcal{P}\rangle\not\models_{\text{SC}}S(1)$.

First, if $\phi$ is satisfiable, then let $P$ be the set of propositional
variables occurring in $\phi$, let $I$ be a propositional interpretation
(subset of $P$) satisfying $\phi$, and let $\mathcal{C}$ be the following
subset of $\textit{{BCQ}}\text{-}Cons(\mathcal{A})$:

$\begin{array}[]{r@{}l}\mathcal{C}=\mathcal{A}\setminus(&\\{V(p,f)\mid p\in
P\cap I\\}\;\cup\\\ &\\{V(p,t)\mid p\in P\setminus
I\\}\cup\\{S(1),\ldots,S(m)\\})\end{array}$

It is immediate to verify that $\mathcal{C}\models_{\mathsf{EQL}}\mathcal{P}$,
and thus there exists an optimal CQ-censor $\mathcal{C}^{\prime}$ of
$\mathcal{E}$ containing $\mathcal{C}$. Now suppose that
$S(1)\in\mathcal{C}^{\prime}$. Then, since $I$ satisfies $\phi$, there exists
an instantiation of $y$ and $v$ that, together with the instantiation $x=1$,
$z=2$ is such that the BCQ in the premise of one of the first three
dependencies of $\mathcal{P}$ is entailed by $\mathcal{C}^{\prime}$, which
implies (for $\mathcal{C}^{\prime}\models_{\mathsf{EQL}}\mathcal{P}$ to hold)
that $S(2)\in\mathcal{C}^{\prime}$. But now, the presence of $S(2)$ in
$\mathcal{C}^{\prime}$ implies (for the same argument as above) that
$S(3)\in\mathcal{C}^{\prime}$, Iterating the above argument, we conclude that
$S(m)\in\mathcal{C}^{\prime}$: this in turn would imply that
$S(m+1)\in\mathcal{C}^{\prime}$, but $S(m+1)$ does not belong to
$\textit{{BCQ}}\text{-}Cons(\mathcal{A})$, and since
$\mathcal{C}^{\prime}\subseteq\textit{{BCQ}}\text{-}Cons(\mathcal{A})$, we
have a contradiction. Consequently, $\mathcal{C}^{\prime}$ can not contain
$S(1)$, which implies that $\mathcal{E}\not\models_{\text{SC}}S(1)$.

On the other hand, given a guess of the atoms of the $V$ predicate in
$\mathcal{A}$ satisfying the fourth dependency and corresponding to an
interpretation of the propositional variables that does not satisfy $\phi$, it
is immediate to verify that the sequence of instantiations of the bodies of
the first three dependencies of $\Sigma$ mentioned above (which, as above
explained, leads to the need of adding $S(m+1)$ to the optimal CQ-censor when
the interpretation corresponding to such a guess of the atoms for $V$
satisfies $\phi$) is blocked by the absence of some ground atom for $V$ in the
optimal CQ-censor. More precisely: there exists a positive integer $k\geq 1$
such that the atoms $S(k),S(k-1),\ldots,S(1)$ can be added to all the optimal
CQ-censors corresponding to such a guess of the $V$ atoms. This implies that,
if $\phi$ is unsatisfiable, then $S(1)$ belongs to all the optimal CQ-censors
of $\mathcal{E}$, hence $\mathcal{E}\models_{\text{SC}}S(1)$. ∎

Proof of Lemma 3

Suppose the algorithm returns false. Then, there exists a set of BCQks
$\mathcal{C}$ satisfying conditions (i), (ii), and (iii) of the algorithm.
Now, by condition (i) it follows that there exists an optimal CQ-censor
$\mathcal{C}^{\prime}$ of $\mathcal{E}$ such that
$\mathcal{C}\subseteq\mathcal{C}^{\prime}$. Then, since condition (iii) of the
algorithm holds, by Lemma 2 it follows that
$\mathcal{C}=\mathcal{C}^{\prime}\cap\textbf{BCQ}_{k}$ (hence $\mathcal{C}$ is
closed under subqueries); consequently, by condition (ii) and Proposition 5 it
follows that $\mathcal{T}\cup\mathcal{C}^{\prime}\not\models q$, which implies
that $\mathcal{E}\not\models_{\text{SC}}q$.

Conversely, suppose $\mathcal{E}\not\models_{\text{SC}}q$. then, there exists
an optimal CQ-censor $\mathcal{C}^{\prime}$ of $\mathcal{E}$ such that
$\mathcal{T}\cup\mathcal{C}^{\prime}\not\models q$. Now let
$k=\max(\textit{MaxLenCQ}(q),\textit{MaxLenCQ}(\mathcal{P}))$ and let
$\mathcal{C}=\mathcal{C}^{\prime}\cap\textbf{BCQ}_{k}$. Since $\mathcal{C}$ is
closed under subqueries, by Proposition 5, for every subformula $Kq(\vec{x})$
occurring in $\mathcal{P}$ and for every ground substitution $\vec{t}$ for
$\vec{x}$, where $\vec{t}$ is a tuple of constants occurring in $\mathcal{A}$,
$\mathcal{T}\cup\mathcal{C}\models q(\vec{t})$ iff
$\mathcal{T}\cup\mathcal{C}^{\prime}\models q(\vec{t})$, hence by Proposition
4 it follows that
$\mathcal{T}\cup\mathcal{C}\models_{\mathsf{EQL}}\mathcal{P}$, therefore
condition (i) of the algorithm holds for $\mathcal{C}$. Moreover, by
Proposition 5 it follows that condition (ii) holds for $\mathcal{C}$. Finally,
suppose condition (iii) does not hold for $\mathcal{C}$, i.e. there exists
$q^{\prime}\in\textit{{BCQ}}_{k}\text{-}Cons(\mathcal{T}\cup\mathcal{A})\setminus\mathcal{C}$
such that
$\textit{PolicyCons}(\mathcal{T},\mathcal{P},\mathcal{C}\cup\\{q^{\prime}\\})\subseteq\textit{{BCQ}}_{k}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$.
Then, it is immediate to verify that
$\mathcal{T}\cup\textit{PolicyCons}(\mathcal{T},\mathcal{P},\mathcal{C}\cup\\{q^{\prime}\\})\models_{\mathsf{EQL}}\mathcal{P}$,
i.e.
$\textit{PolicyCons}(\mathcal{T},\mathcal{P},\mathcal{C}\cup\\{q^{\prime}\\})$
is a CQ-censor of $\mathcal{E}$. Now let $\mathcal{C}^{\prime\prime}$ be the
maximal subset of $\textit{{BCQ}}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$
such that
$\textit{PolicyCons}(\mathcal{T},\mathcal{P},\mathcal{C}\cup\\{q^{\prime}\\})=\mathcal{C}^{\prime\prime}\cap\textbf{BCQ}_{k}$
and
$\mathcal{C}^{\prime\prime}=\textit{{BCQ}}\text{-}Cons(\mathcal{T}\cup\mathcal{C}^{\prime\prime})$.
By Proposition 5 and Proposition 4 it follows that
$\mathcal{T}\cup\mathcal{C}^{\prime\prime}\models_{\mathsf{EQL}}\mathcal{P}$.
But now, $\mathcal{C}^{\prime}$ is the maximal subset of
$\textit{{BCQ}}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$ such that
$\mathcal{C}=\mathcal{C}^{\prime}\cap\textbf{BCQ}_{k}$, and since
$\mathcal{C}\subset\textit{PolicyCons}(\mathcal{T},\mathcal{P},\mathcal{C}\cup\\{q^{\prime}\\})$,
it follows that $\mathcal{C}^{\prime}\subset\mathcal{C}^{\prime\prime}$, thus
contradicting the hypothesis that $\mathcal{C}^{\prime}$ is an optimal CQ-
censor of $\mathcal{E}$. Consequently, condition (iii) holds for
$\mathcal{C}$, hence the algorithm returns false. ∎

Proof of Lemma 5

Suppose $\textit{eval}(q_{r}(\vec{c}),\mathcal{I}_{\mathcal{A}})$ is true.
Then, $\mathcal{A}\models q_{r}(\vec{c})$, hence by Proposition 1 it follows
that $\mathcal{T}\cup\mathcal{A}\models q_{r}^{\prime}(\vec{c})$, where
$q_{r}^{\prime}(\vec{x})=\phi_{\mathit{pc}}(\mathcal{T},\mathcal{P},q(\vec{x}))$,
which implies that
$\textit{PolicyCons}(\mathcal{T},\mathcal{P},\\{q(\vec{c})\\})\subseteq\textit{{BCQ}}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$,
thus by Lemma 2 there exists an optimal CQ-censor of $\mathcal{E}$ that
contains $q(\vec{c})$.

Conversely, suppose there exists an optimal CQ-censor of $\mathcal{E}$ that
contains $q(\vec{c})$. Then, by Lemma 2
$\textit{PolicyCons}(\mathcal{T},\mathcal{P},\\{q(\vec{c})\\})\subseteq\textit{{BCQ}}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$.
Thus, $\mathcal{T}\cup\mathcal{A}\models q^{\prime}$ for every BCQ
$q^{\prime}\in\textit{PolicyCons}(\mathcal{T},\mathcal{P},\\{q(\vec{c})\\})$,
which implies that $\mathcal{T}\cup\mathcal{A}\models
q_{r}^{\prime}(\vec{c})$. Hence, by Proposition 1 we derive
$\mathcal{A}\models\textit{PerfectRef}(q_{r}^{\prime}(\vec{c}),\mathcal{T})$.
Now, from the properties of PerfectRef it immediately follows that the BCQ
$\textit{PerfectRef}(q_{r}^{\prime}(\vec{c}),\mathcal{T})$ is equivalent to
$q_{r}(\vec{c})$, hence $\mathcal{A}\models q_{r}(\vec{c})$, and therefore
$\textit{eval}(q_{r}(\vec{c}),\mathcal{I}_{\mathcal{A}})$ is true. ∎

Proof of Lemma 6

Suppose $q^{\prime}(\vec{c})$ is a clash for $q$ in $\mathcal{E}$, Then, there
exists an optimal CQ-censor of $\mathcal{E}$ containing $q^{\prime}(\vec{c})$,
which by Lemma 5 implies that
$\textit{eval}(q_{r}(\vec{c}),\mathcal{I}_{\mathcal{A}})$ is true, where
$q_{r}(\vec{x})=\textit{PerfectRef}(\phi_{\mathit{pc}}(\mathcal{T},\mathcal{P},q^{\prime}(\vec{x})),\mathcal{T})$.
Moreover, for every $q_{i}\in q$, $q^{\prime}(\vec{c})$ is a clash for $q_{i}$
in $\mathcal{E}$, i.e. there exists no optimal CQ-censor of $\mathcal{E}$
containing $q^{\prime}(\vec{c})\wedge q_{i}$, which again by Lemma 5 implies
that $\textit{eval}(\bigwedge_{q_{i}\in q}\neg
q_{r}^{\prime}(\vec{c}),\mathcal{I}_{\mathcal{A}})$ is true, where
$q_{r}^{\prime}(\vec{x})=\textit{PerfectRef}(\phi_{\mathit{pc}}(\mathcal{T},\mathcal{P},q^{\prime}(\vec{x})\wedge
q_{i}),\mathcal{T})$. Consequently,
$\textit{eval}(q_{cl}(\vec{c}),\mathcal{I}_{\mathcal{A}})$ is true.

Conversely, suppose $\textit{eval}(q_{cl}(\vec{c}),\mathcal{I}_{\mathcal{A}})$
is true. This implies that
$\textit{eval}(q_{r}(\vec{c}),\mathcal{I}_{\mathcal{A}})$ is true, hence by
Lemma 5 it follows that there exists an optimal CQ-censor of $\mathcal{E}$
containing $q^{\prime}(\vec{c})$. Moreover, since
$\textit{eval}(q_{cl}(\vec{c}),\mathcal{I}_{\mathcal{A}})$ is true, then for
every $q_{i}\in q$, $\textit{eval}(\neg
q_{r}^{\prime}(\vec{c}),\mathcal{I}_{\mathcal{A}})$ is true, hence
$\textit{eval}(q_{r}^{\prime}(\vec{c}),\mathcal{I}_{\mathcal{A}})$ is false,
and thus by Lemma 5 it follows that there exists no optimal CQ-censor of
$\mathcal{E}$ containing $q^{\prime}(\vec{c})\wedge q_{i}$. Consequently,
$q^{\prime}(\vec{c})$ is a clash for $q$ in $\mathcal{E}$. ∎

Proof of Lemma 7

To prove the lemma, we need to introduce some auxiliary definitions and
properties.

Given an ED $\delta$ of the form $\forall\vec{x}\,(Kq_{b}\rightarrow Kq_{h})$,
we denote by $\textit{body}(\delta)$ the CQ $q_{b}$ and denote by
$\textit{head}(\delta)$ the CQ $q_{h}$. Also, we use the notation
$\delta(\vec{x})$ to indicate an ED with universally quantified variables
$\vec{x}$.

Given an ED $\delta$ of the form $\forall
x_{1},\ldots,x_{m}\,(Kq_{b}\rightarrow Kq_{h})$,we define
$\mathit{TGD}(\delta)$ as the following FO implication corresponding to a
_tuple-generating dependency_ (_TGD_), also known as _existential rule_ (see
e.g. Calì et al. [2012]; Baget et al. [2011]):

$\forall
x_{1},\ldots,x_{m}\,(q_{b}\wedge\bigwedge_{i=1}^{m}\textit{Ind}(x_{i})\rightarrow
q_{h})$

Moreover, given a policy $\mathcal{P}$, we define $\mathit{TGD}(\mathcal{P})$
as the set of TGDs $=\\{\mathit{TGD}(\delta)\mid\delta\in\mathcal{P}\\}$.

Then, given a $\text{DL-Lite}_{\mathcal{R}}$ positive TBox inclusion $\eta$,
we define $\mathit{TGD}(\eta)$ as the TGD corresponding to $\eta$, i.e.:

$\begin{array}[]{l@{\ =\ }l}\mathit{TGD}(A\sqsubseteq B)&\forall
x(A(x)\rightarrow B(x))\\\ \mathit{TGD}(A\sqsubseteq\exists s)&\forall
x(A(x)\rightarrow\exists z\,s(x,z))\\\ \mathit{TGD}(A\sqsubseteq\exists
s^{-})&\forall x(A(x)\rightarrow\exists z\,s(z,x))\\\ \mathit{TGD}(\exists
r\sqsubseteq A)&\forall x,y(r(x,y)\rightarrow A(x))\\\ \mathit{TGD}(\exists
r\sqsubseteq\exists s)&\forall x,y(r(x,y)\rightarrow\exists z\,s(x,z))\\\
\mathit{TGD}(\exists r\sqsubseteq\exists s^{-})&\forall
x,y(r(x,y)\rightarrow\exists z\,s(z,x))\\\ \mathit{TGD}(\exists
r^{-}\sqsubseteq A)&\forall x,y(r(y,x)\rightarrow A(x))\\\
\mathit{TGD}(\exists r^{-}\sqsubseteq\exists s)&\forall
x,y(r(y,x)\rightarrow\exists z\,s(x,z))\\\ \mathit{TGD}(\exists
r^{-}\sqsubseteq\exists s^{-})&\forall x,y(r(y,x)\rightarrow\exists
z\,s(z,x))\\\ \mathit{TGD}(r\sqsubseteq s)&\forall x,y(r(x,y)\rightarrow
s(x,y))\\\ \mathit{TGD}(r\sqsubseteq s^{-})&\forall x,y(r(x,y)\rightarrow
s(y,x))\\\ \mathit{TGD}(r^{-}\sqsubseteq s)&\forall x,y(r(y,x)\rightarrow
s(x,y))\\\ \mathit{TGD}(r^{-}\sqsubseteq s^{-})&\forall x,y(r(y,x)\rightarrow
s(y,x))\end{array}$

We also define
$\mathit{TGD}(\mathcal{T})=\\{\mathit{TGD}(\eta)\mid\eta\in\mathcal{T}\\}$ for
a $\text{DL-Lite}_{\mathcal{R}}$ TBox $\mathcal{T}$. Finally, we denote by
$\mathit{TGD}(\mathcal{P},\mathcal{T})$ the set
$\mathit{TGD}(\mathcal{P})\cup\mathit{TGD}(\mathcal{T})$.

In the following, given a CQ $q(\vec{x})$, we denote by
$\textit{No}\textit{Ind}(q(\vec{x}))$ the CQ obtained from the $q(\vec{x})$ by
eliminating the atoms with predicate Ind.

We now make use of an existing query rewriting algorithm for TGDs, in
particular the algorithm shown in König et al. [2015], which computes a UCQ
rewriting (i.e. a set of CQs) of a CQ with respect to a set of TGDs. More
precisely, we denote by $\textit{UCQRewrite}(q(\vec{x}),\Sigma)$ the set of
CQs returned by such an algorithm for the input CQ $q(\vec{x})$ and set of
TGDs $\Sigma$.

We first show the following property:

> (PR1): Let $\delta(\vec{x})\in\mathcal{P}$. Then, the algorithm UCQRewrite
> on input $\textit{body}(\delta(\vec{x}))$,
> $\mathit{TGD}(\mathcal{P},\mathcal{T})$ terminates and, for every
> $q^{\prime}(\vec{x}^{\prime})\in\textit{UCQRewrite}(\textit{body}(\delta(\vec{x})),\mathit{TGD}(\mathcal{P},\mathcal{T}))$,
> it holds
> $\textit{Len}(\textit{No}\textit{Ind}(q^{\prime}(\vec{x}^{\prime})))\leq
> k^{h}$.

Proof of (PR1): It is not hard to verify that, since $\mathcal{P}$ is an
acyclic policy and $\mathcal{T}$ is a $\text{DL-Lite}_{\mathcal{R}}$ TBox, the
algorithm $\textit{UCQRewrite}(q,\mathit{TGD}(\mathcal{P},\mathcal{T}))$
terminates on every CQ $q$ (and thus in particular on
$\textit{body}(\delta(\vec{x}))$. Indeed, every atom whose predicate is Ind
can not be rewritten at all (since the predicate Ind does not appear in the
right-hand side of any TGD in $\mathit{TGD}(\mathcal{P},\mathcal{T})$), while
every atom whose predicate is not Ind can be rewritten at most once by TGDs
from $\mathit{TGD}(\mathcal{P})$ (because $\mathcal{P}$ is acyclic for
$\mathcal{T}$). Moreover, the set $\mathit{TGD}(\mathcal{T})$ is linear, which
implies that only a finite number of consecutive applications of such TGDs can
be applied to the rewriting of any atom. Moreover, since the application of
the TGDs in $\mathit{TGD}(\mathcal{T})$ in the rewriting cannot increase the
size of the rewritten query, it follows that every atom of
$\textit{body}(\delta(\vec{x}))$ can be rewritten in no more than $k^{h-1}$
atoms: since the length of $\textit{body}(\delta(\vec{x}))$ is not greater
than $k$, it follows that every CQ returned by
$\textit{UCQRewrite}(\textit{body}(\delta(\vec{x})),\mathit{TGD}(\mathcal{P},\mathcal{T}))$
has a length not greater than $k^{h}$, thus property (PR1) holds.

We now make use of UCQRewrite to define $\textit{ED-
closure}(\mathcal{P},\mathcal{T})$ as the following set of EDs:

$\begin{array}[]{l}\\{\forall\vec{x}^{\prime}(K\textit{No}\textit{Ind}(q^{\prime}(\vec{x}^{\prime}))\rightarrow
K\textit{head}(\delta(\vec{x}^{\prime}))\mid\\\
\;\delta(\vec{x})\in\mathcal{P}\wedge
q^{\prime}(\vec{x}^{\prime})\in\textit{UCQRewrite}(\textit{body}(\delta(\vec{x})),\mathit{TGD}(\mathcal{P},\mathcal{T}))\\}\end{array}$

Then, we prove the following property:

> (PR2): Let $q$ be a BCQ such that $\mathcal{T}\cup\mathcal{A}\models q$.
> There exists an optimal CQ-censor of $\mathcal{E}$ containing $q$ iff, for
> every ED $\delta(\vec{x})\in\textit{ED-closure}(\mathcal{P},\mathcal{T})$,
> and for every ground substitution $\vec{c}$ of $\vec{x}$, if
> $q\models\textit{body}(\delta(\vec{c}))$, then
> $\mathcal{T}\cup\mathcal{A}\models\textit{head}(\delta(\vec{c}))$.

Proof of (PR2): Suppose that there exists an optimal CQ-censor $\mathcal{C}$
of $\mathcal{E}$ containing $q$. Now suppose there exists
$\delta(\vec{x})\in\textit{ED-closure}(\mathcal{P},\mathcal{T})$ and a ground
substitution $\vec{c}$ of $\vec{x}$ such that
$\\{q\\}\models\textit{body}(\delta(\vec{c}))$ and
$\mathcal{T}\cup\mathcal{A}\not\models\textit{head}(\delta(\vec{c}))$. Of
course, since $q\in\mathcal{C}$, it follows that
$\mathcal{T}\cup\mathcal{C}\models\textit{body}(\delta(\vec{c}))$. Now let
$\delta_{0}(\vec{x})$ be the ED in $\mathcal{P}$ that has been rewritten into
$\delta(\vec{x})$. Given the properties of UCQRewrite, it follows that, if
$\mathcal{T}\cup\mathcal{C}\models\textit{body}(\delta(\vec{c}))$, then
$\mathcal{T}\cup\mathcal{C}\models\textit{body}(\delta_{0}(\vec{c}))$.
Consequently, since $\mathcal{C}$ is an optimal CQ-censor of $\mathcal{E}$,
$\mathcal{T}\cup\mathcal{C}\models\textit{head}(\delta(\vec{c}))$, and since
$\mathcal{C}\subseteq\textit{{BCQ}}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$,
it follows that
$\mathcal{T}\cup\mathcal{A}\models\textit{head}(\delta(\vec{c}))$.

Conversely, suppose there exists no optimal CQ-censor of $\mathcal{E}$
containing $q$. Then, by Lemma 2,
$\textit{PolicyCons}(\mathcal{T},\mathcal{P},\\{q\\})\not\subseteq\textit{{BCQ}}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$.
By Definition 7, it follows that there exist $\delta(\vec{x})\in\mathcal{P}$
and a ground substitution $\vec{c}$ for $\vec{x}$ such that
$\mathcal{T}\cup\textit{PolicyCons}(\mathcal{T},\mathcal{P},\\{q\\})\models\textit{body}(\delta(\vec{c}))$
and $\mathcal{T}\cup\mathcal{A}\not\models\textit{head}(\delta(\vec{c}))$.

Now, it is easy to verify that
$\mathcal{T}\cup\textit{PolicyCons}(\mathcal{T},\mathcal{P},\\{q\\})\models\textit{body}(\delta(\vec{c}))$
iff
$\mathit{Chase}(q,\mathit{TGD}(\mathcal{P},\mathcal{T}))\models\textit{body}(\delta(\vec{c}))$,
where $\mathit{Chase}$ is a well-known algorithm Abiteboul et al. [1995] that,
given a set of atoms333As often done in previous work, here we apply the chase
to a BCQ rather than to a set of ground atoms: it suffices to consider the BCQ
as the set of its atoms, and its variables as a new and additional set of
constants. and a set of TGDs, returns a (possibly infinite) set of atoms that
contains the initial set and is isomorphic to a _canonical model_ (or minimal
model) of all the input formulas.

Moreover, the known properties of UCQRewrite imply that
$\mathit{Chase}(q,\mathit{TGD}(\mathcal{P},\mathcal{T}))\models\textit{body}(\delta(\vec{c}))$
iff there exists
$q^{\prime}(\vec{x}^{\prime})\in\textit{UCQRewrite}(\textit{body}(\delta(\vec{x}),\mathit{TGD}(\mathcal{P},\mathcal{T})))$
such that $\\{q\\}\models q^{\prime}(\vec{c})$.

Consequently, by the definition of ED-closure, there exists
$\delta^{\prime}(\vec{x}^{\prime})\in\textit{ED-
closure}(\mathcal{P},\mathcal{T})$ such that
$\\{q\\}\models\textit{body}(\delta^{\prime}(\vec{c}))$ and
$\textit{head}(\delta^{\prime}(\vec{c}))=\textit{head}(\delta(\vec{c}))$, and
thus
$\mathcal{T}\cup\mathcal{A}\not\models\textit{head}(\delta^{\prime}(\vec{c}))$,
which concludes the proof.

As a consequence of (PR2), we immediately obtain the following property:

> (PR3): $q^{\prime}$ is a clash for $q$ in $\mathcal{E}$ iff, for every
> $q_{i}\in q$, there exist an ED $\delta(\vec{x})\in\textit{ED-
> closure}(\mathcal{P},\mathcal{T})$ and a ground substitution $\vec{c}$ for
> $\vec{x}$ such that $\\{q^{\prime}\wedge
> q_{i}\\}\models\textit{body}(\delta(\vec{c}))$.

Finally, it is immediate to verify that $\mathcal{E}\models_{\text{SC}}q$ iff
there exists no BCQ $q^{\prime}$ such that $q^{\prime}$ is a clash for $q$ in
$\mathcal{E}$. This property, property (PR1), and property (PR3) immediately
imply the lemma. ∎

Proof of Lemma 8

First, let $\psi_{1}(q^{p})$ be the sentence

$\begin{array}[]{l}\displaystyle\bigwedge_{q_{i}\in
q^{p}}\textit{PerfectRef}(q_{i},\mathcal{T})\>\wedge\bigwedge_{q_{i}\in
q\setminus q^{p}}\neg\textit{PerfectRef}(q_{i},\mathcal{T})\end{array}$

and let $\psi_{2}(q^{p})$ be the sentence

$\begin{array}[]{l}\displaystyle\bigwedge_{q^{\prime}(\vec{x})\in\mathcal{Q}}\neg\big{(}\exists\vec{x}\,(\textit{Clash}(q^{p},q^{\prime}(\vec{x}),\mathcal{T},\mathcal{P})\wedge\bigwedge_{x\in\vec{x}}Ind(x))\end{array}$

Now, suppose
$\textit{eval}(\textit{\text{SC}-Entailed}(q,\mathcal{T},\mathcal{P}),\mathcal{I}_{\mathcal{A}})$
is true. Thus, there exists a non-empty subset $q^{p}$ of $q$ such that
$\textit{eval}(\psi_{1}(q^{p})\wedge\psi_{2}(q^{p}),\mathcal{I}_{\mathcal{A}})$
is true. Then, since
$\textit{eval}(\psi_{1}(q^{p}),\mathcal{I}_{\mathcal{A}})$ is true, it follows
that $q_{i}\in\textit{{BCQ}}\text{-}Cons(\mathcal{T}\cup\mathcal{A})$ for
every $q_{i}\in q$. Therefore, from Lemma 6 and from the fact that
$\textit{eval}(\psi_{2}(q^{p}),\mathcal{I}_{\mathcal{A}})$ is true, it follows
that there exists no BCQ $q^{\prime}$ such that
$q^{\prime}\in\mathcal{Q}^{\prime}$ and $q^{\prime}$ is a clash for $q^{p}$ in
$\mathcal{E}$, where $\mathcal{Q}^{\prime}$ is the set of BCQs defined over
the predicates and constants occurring in
$\\{q\\}\cup\mathcal{P}\cup\mathcal{T}$ and whose maximum length is $m\cdot
k^{h}$, with $m$ representing the number of BCQs in $q$, $h$ representing the
number of EDs in $\mathcal{P}$, and $k=\textit{MaxLenCQ}(\mathcal{P})$.
Consequently, by Lemma 7 we conclude that
$\mathcal{E}\models_{\text{SC}}q^{p}$, which immediately implies that
$\mathcal{E}\models_{\text{SC}}q$.

Conversely, suppose $\mathcal{E}\models_{\text{SC}}q$. Let $q^{p}$ be the non-
empty subset of BCQs $\\{q_{i}\in q\mid
q_{i}\in\textit{{BCQ}}\text{-}Cons(\mathcal{T}\cup\mathcal{A})\\}$. Then,
$\textit{eval}(\psi_{1}(q^{p}),\mathcal{I}_{\mathcal{A}})$ is true. Moreover,
since there exists no BCQ $q^{\prime}$ such that $q^{\prime}\in\textbf{BCQ}$
and $q^{\prime}$ is a clash for $q$ in $\mathcal{E}$, by Lemma 6 it follows
that $\textit{eval}(\psi_{2}(q^{p}),\mathcal{I}_{\mathcal{A}})$ is true.
Consequently,
$\textit{eval}(\textit{\text{SC}-Entailed}(q,\mathcal{T},\mathcal{P}),\mathcal{I}_{\mathcal{A}})$
is true. ∎