Controlled Query Evaluation in Description Logics Through Instance Indistinguishability

1 Introduction

We consider controlled query evaluation (CQE), a declarative framework for privacy-preserving query answering investigated in the literature on knowledge representation and database theory [Sicherman et al., 1983; Bonatti et al., 1995; Biskup, 2000]. The basic idea of CQE is defining a data protection policy through logical statements. Consider for instance an organization that wants to keep confidential the fact that it has suppliers involved in both Project A and Project B. This can be expressed over the information schema of the organization through a denial assertion of the form

In CQE, two different main approaches can be identified. The first one [Biskup and Bonatti, 2004b; Biskup and Bonatti, 2004a; Biskup and Weibert, 2008; Benedikt et al., 2018; Benedikt et al., 2019; Studer and Werner, 2014] models privacy preservation through the notion of indistinguishable data instances. In this approach, a system for CQE enforces data privacy if, for every data instance I, there exists a data instance I ′ that does not violate the data protection policy and is indistinguishable from I for the user, i.e., for every user query q, the system provides the same answers to q over I and over I ′ . We call this approach (instance) indistinguishabilitybased (IB). In continuation of the previous example, in the presence of an instance {Supplier(c), ProjA(c), ProjB(c)}, an IB system should answer user queries as if the instance were, e.g., {Supplier(c), ProjA(c)} (note that other instances not violating the policy can be considered as indistinguishable, e.g., {Supplier(c), ProjB(c)}).

The second approach [Bonatti and Sauro, 2013; Cuenca Grau et al., 2013; Cuenca Grau et al., 2015] models privacy preservation by considering the whole (possibly infinite) set of answers to queries that the system provides to the user. In this approach, a CQE system protects the data if, for every data instance I, the logical theory corresponding to the set of answers provided by the system to all queries over I does not entail any violation of the data protection policy. According to [Cuenca Grau et al., 2015], we call this approach confidentiality-preserving (CP). In our ongoing example, a CP system would entail, e.g., the queries Supplier(c) ∧ ProjA(c) and ∃x.Supplier(x) ∧ ProjB(x), but not also the query Supplier(c) ∧ ProjB(c) (notice that the choice is non-deterministic, and in our example the system could have decided to disclose that c participates in Project B and hide its participation in Project A).

In both approaches, the ultimate goal is to realize optimal CQE systems, i.e., systems maximizing the answers returned to user queries, still respecting the data protection policy. Traditionally, this aim has been pursued through the construction of a single optimal censor, i.e., a specific implementation of the adopted notion of privacy-preservation, either IB or CP. Since, however, in both approaches several optimal censors typically exist, this way of proceeding requires to make a choice on how to obfuscate data, which, in the absence of additional (preference) criteria, may result discretionary. To avoid this, query answering over all optimal censors has been recently studied (limited to the CP approach) [Cuenca Grau et al., 2013; Lembo et al., 2019].

Despite their similarities, the precise relationship between the IB and CP approaches is still not clear and has not been fully investigated yet. Also, query answering over all optimal IB censors has not been previously studied. Moreover, among the complexity results obtained and the techniques defined so far for CQE, we still miss the identification of cases that are promising towards its practical usage.

In this paper, we aim at filling some of the above mentioned gaps in the context of Description Logic (DL) ontologies. 1

1 Privacy-preserving query answering in DLs has been investi-

We focus on the approach to CQE based on instance indistinguishability (Section 3), and study its relationship with the CP approach (Section 4). Specifically, we prove that the IB approach to CQE in DLs corresponds to a particular instance of the CP approach to CQE [Lembo et al., 2019]. Based on such a correspondence, for ontologies specified in the wellknown DL DL-LiteR [Calvanese et al., 2007], we are able to transfer some complexity results for query answering over all optimal censors shown in [Lembo et al., 2019] to the case of CQE under IB censors (Section 5). Such results show that, even in the lightweight DL DL-LiteR, query answering in the IB approach is intractable with respect to data complexity, unless one relies on a single optimal censor chosen non-deterministically in the lack of further meta-information about the domain of the dataset.

To overcome the above problems and provide a practical, semantically well-founded solution, we define a quasioptimal notion of IB censor, which corresponds to the best sound approximation of all the optimal IB censors (Section 6). We then prove that, in the case of DL-LiteR ontologies, query answering based on the quasi-optimal IB censor is tractable with respect to data complexity and is reducible to the evaluation of a first-order query over the data instance, i.e., it is first-order rewritable. We believe that this result has an important practical impact. Indeed, we have identified a setting in which privacy-preserving query answering formalized in a declarative logic-based framework as CQE, for a DL (i.e., DL-LiteR) specifically designed for data management, has the same data complexity as evaluating queries over a database (i.e., AC0 ). This opens the possibility of defining algorithms for CQE of practical usage, amenable to implementation on top of traditional (relational) data management systems, as in Ontology-based Data Access [Xiao et al., 2018].

For complete proofs of our results we refer the reader to an extended version of the present paper [Cima et al., 2020].

2 Preliminaries

We use standard notions of function-free first-order (FO) logic, and in particular we consider Description Logics (DLs), which are fragments of FO using only unary and binary predicates, called concepts and roles, respectively [Baader et al., 2007]. We assume to have the pairwise disjoint countably infinite sets ΣC, ΣR, ΣI and ΣV for atomic concepts, atomic roles, constants (a.k.a. individuals), and variables, respectively. A DL ontology O = T ∪ A is constituted by a TBox T and an ABox A, specifying intensional and extensional knowledge, respectively. The set of atomic concepts and roles occurring in O is the signature of O. The semantics of O is given in terms of FO models over the signature of O, in the standard way [Baader et al., 2007]. In particular, we say that O is consistent if it has at least one model, inconsistent otherwise. O entails an FO sentence φ specified over the signature of O, denoted O |= φ, if φ is true in every model of O. In this paper, we consider ontologies expressed in DL-LiteR, the member of the DL-Lite family [Calvanese et al., 2007] which underpins OWL 2 QL [Motik et al., 2012],

gated also in settings different from CQE: see, e.g., [Cuenca Grau and Horrocks, 2008; Calvanese et al., 2012; Tao et al., 2014].

i.e., the OWL 2 profile specifically designed for efficient query answering. A TBox T in DL-LiteR is a finite set of axioms of the form B1 ⊑ B2 (resp., R1 ⊑ R2), denoting concept (resp., role) inclusion, and B1 ⊑ ¬B2 (resp., R1 ⊑ ¬R2), denoting concept (resp., role) disjointness, where: R1,R2 are of the form P, with P ∈ ΣR, or its inverse P -, and B1,B2 are of the form A, with A ∈ ΣC, ∃P , or ∃P -, i.e., unqualified existential restrictions, which denote the set of objects occurring as first or second argument of P , respectively. An ABox A is a finite set of ground atoms, i.e., assertions of the formA(a), P(a, b), where A ∈ ΣC, P ∈ ΣR, and a, b ∈ ΣI . As usual in query answering over DL ontologies, we focus on the language of conjunctive queries. A Boolean conjunctive query (BCQ) q is an FO sentence of the form ∃⃗x.φ(⃗x), where ⃗x are variables in ΣV, and φ(⃗x) is a finite, non-empty conjunction of atoms of the form α(⃗t), where α ∈ ΣC ∪ ΣR, and each term in ⃗t is either a constant in ΣI or a variable in ⃗x. We denote by Eval(q,A) the evaluation of a query q over (the model isomorphic to) an ABox A.

A denial assertion (or simply a denial) is an FO sentence of the form ∀⃗x.φ(⃗x) → ⊥, such that ∃⃗x.φ(⃗x) is a BCQ. Given one such denial δ and an ontology O, we say that O ∪ {δ} is consistent if O ̸|= ∃⃗x.φ(⃗x), and is inconsistent otherwise.

In the following, with FO, CQ, and GA we denote the languages of function-free FO sentences, BCQs, and ground atoms, respectively, all specified over the alphabets ΣC,ΣR,ΣI, and ΣV. Given an ontology O and a language L, with L(O) we refer to the subset of L whose sentences are built over the signature of O and the variables in ΣV. For a TBox T and a language L, we denote by clTL (·) the function that, for an ABox A, returns all the sentences φ ∈ L(T ∪A) such that T ∪A |= φ.

For the sake of presentation, we will limit our technical treatment to languages containing only closed formulas, but our results hold also for open formulas. In particular, the results on entailment of BCQs (see Sections 5 and 6) can be extended to arbitrary (i.e., non-Boolean) CQs in the standard way 2 . Our complexity results are for data complexity, i.e., are w.r.t. the size of the ABox only.

3 CQE through Instance Indistinguishability

A CQE framework consists of a TBox T and a policy P over T , i.e., a finite set of denial assertions over the signature of T . An ABox A for T is such that A and T have the same signature. In the following, when a TBox T is given, we always assume that the coupled policy is specified over T , that each considered ABox A is for T , and that, unless otherwise specified, T ∪A and T ∪P are consistent. A censor is a function that taken an ABox for T as input alters standard query answering over T ∪A so that on the basis of the answers (even a possibly infinite set thereof) and the TBox, a user can never infer a BCQ ∃⃗x.φ(⃗x) such that ∀⃗x.φ(⃗x) → ⊥ belongs to P.

We here propose a notion of censor which is the natural application to our framework of the analogous definitions given in [Biskup and Bonatti, 2004b; Biskup and Weibert, 2008;

2 We also notice that, since DL-LiteR is insensitive to the adoption of the unique name assumption (UNA) for CQ answering [Artale et al., 2009], our results hold both with and without UNA.

Benedikt et al., 2018; Benedikt et al., 2019]. The basic idea of this approach is that for every underlying instance (an ABox in our framework) and every query, a censor returns to the user the same answers it would return on another (possibly identical) instance that does not contain confidential data, so that she cannot understand which of the two instances she is querying. This is formalized as follows.

Definition 1 [Indistinguishability-based censor] Let T be a DL TBox and P be a policy. An indistinguishability-based (IB) censor for T and P is a function cens(·) that, for each ABox A, returns a set cens(A) ⊆ clTCQ(A) such that there exists an ABox A′ for which (i) cens(A) = cens(A′ ) (in this case we say that A and A′ are indistinguishable w.r.t. cens) and (ii) T ∪P ∪A′ is a consistent FO theory.

Example 1 Let us now formalize more precisely the scenario we have used for the examples in the introduction, by instantiating our CQE framework. The TBox signature consists of the atomic concepts Supplier, ProjA, and ProjB, denoting the set of suppliers of the company, suppliers involved in Project A and those involved in Project B, respectively, and contains the axioms ProjA ⊑ Supplier and ProjB ⊑ Supplier, stating that each individual instance of ProjA or ProjB is also instance of Supplier. Data protection is specified through the policy P = {∀x.ProjA(x) ∧ ProjB(x) → ⊥}. The following functions are IB censors for T and P:

• cens1: given an ABox A, cens1(A) returns the set clTCQ(APA ) of BCQs, where APA is obtained from A by removing the assertion ProjA(c), for each individual c such that both ProjA(c) and ProjB(c) are in A (note that for every ABox A, A and APA are indistinguishable w.r.t. cens1. Similarly in the following censors).
• cens2: given an ABox A, cens2(A) returns the set clTCQ(APB ) of BCQs, where APB is obtained from A by removing the assertion ProjB(c), for each individual c such that both ProjA(c) and ProjB(c) are in A.
• cens3: given an ABox A, cens3(A) returns the set clTCQ(Asup) of BCQs, where Asup is obtained from A by adding the assertion Supplier(c) and removing ProjA(c) and ProjB(c), for each individual c such that both ProjA(c) and ProjB(c) are in A.

It is easy to see that an IB censor always exists, but, as Example 1 shows, there may be many IB censors for T and P, and so it is reasonable to look for censors preserving as much information as possible. Formally, given two IB censors cens and cens′ for T and P, we say that cens′ is more informative than cens if: (i) for every ABox A, cens(A) ⊆ cens′ (A), and (ii) there exists an ABox A′ such that cens(A′ ) ⊂ cens′ (A′ ). Optimal censors are then defined as follows.

Definition 2 Let T be a DL TBox and P be a policy. An IB censor cens for T and P is optimal if there does not exist any other IB censor for T and P that is more informative than cens. The set of all the optimal IB censors for T and P is denoted with OptIBCensT ,P .

Example 2 Among the censors of Example 1, cens3 ̸∈ OptIBCensT ,P, since both cens1 and cens2 are more informative than cens3. It can be then verified that cens1 and cens2 are the only optimal IB censors for T and P.

4 IB Censors vs. CP Censors

In [Cuenca Grau et al., 2015], a different notion of censor, named confidentiality-preserving (CP) censor, has been proposed. Intuitively, a CP censor establishes which are the BCQs entailed by a TBox and a given ABox that can be disclosed without violating the policy. We report below the definition given in [Lembo et al., 2019], which generalizes CP censors to any language L ⊆ FO, called the censor language.

Definition 3 [Confidentiality-preserving censor] Let T be a DL TBox, P be a policy, and L ⊆ FO be a language. A confidentiality-preserving (CP) censor in L for T and P is a function cens(·) that, for each ABox A, returns a set cens(A) ⊆ clTL (A) such that T ∪P ∪ cens(A) is a consistent FO theory.

The notion of more informative censor previously given for IB censors can be naturally extended to CP censors, and we can thus define optimal censors also in this case.

Definition 4 Let T be a DL TBox, P be a policy, and L ⊆ FO be a language. A CP censor cens in L for T and P is optimal if there does not exist any other CP censor in L for T and P that is more informative than cens. The set of all the optimal CP censors in L for T and P is denoted with L-OptCPCensT ,P.

Example 3 Consider T and P as defined in Example 1. An optimal CP censor cens4 in CQ for T and P is defined as follows: given an ABox A, cens4(A) returns the set of BCQs obtained by removing from clTCQ(A) every query containing the atom ProjA(c), for each individual c such that both ProjA(c) and ProjB(c) are in A.

We soon notice that the CP censor cens4 is instead not an IB censor. Indeed, consider the ABox A = {ProjA(c), ProjB(c)}. We have that cens4(A) = {φ | φ ∈ CQ and T ∪ S |= φ}, where S = {∃x.ProjA(x), ProjB(c)}. It is not hard to see that there exists no ABox A′ such that A′ and A are indistinguishable w.r.t. cens4 and T ∪ P ∪ A′ is consistent.

Let A be an ABox and cens be either an IB or a CP censor, the set cens(A) is called theory of the censor cens for A.

The following theorem explains the relation between IB censors and CP censors.

Theorem 1 Let T be a DL TBox and P be a policy. If cens is an IB censor for T and P, then it is a CP censor in CQ for T and P. The converse does not necessarily hold.

Proof. Let cens be an IB censor for T and P. Consider an arbitrary ABox A. According to Definition 1, there exists an ABox A′ such that cens(A) = cens(A′ ) and T ∪ P ∪ A′ is consistent. Since by definition cens(A′ ) contains only sentences φ ∈ CQ logically implied by T ∪ A′ (i.e., BCQs φ such that φ ∈ clTCQ(A′ )) and T ∪ P ∪ A′ is consistent, we have that T ∪ P ∪ cens(A′ ) is consistent as well. Due to the equivalence cens(A′ ) = cens(A), we derive that T ∪ P ∪ cens(A) is consistent. To conclude the implication part observe that, by definition, cens(A) ⊆ clTCQ(A).

As for the converse, Example 3 shows that the CP censor cens4 in CQ for T and P is not an IB censor for T and P.

We also notice that optimal IB censors are not necessarily optimal CP censors in CQ. Indeed, consider Examples 1 and 3. We have that cens1 ∈ OptIBCensT ,P but, even if, as shown by Theorem 1, it is a CP censor in CQ for T and P, cens1 ̸∈ CQ-OptCPCensT ,P (it is easy to see that cens4 is more informative than cens1). We also know from Example 3 that the optimal CP censor cens4 in CQ for T and P is not an IB censor, and thus cens4 ̸∈ OptIBCensT ,P. However, from Theorem 1 it easily follows that if an optimal CP censor in CQ for T and P is also an IB censor then it is an optimal IB censor for T and P, as stated below.

Proposition 1 Let T be a DL TBox and P be a policy. If cens ∈ CQ-OptCPCensT ,P and cens is an IB censor for T and P, then cens ∈ OptIBCensT ,P. The converse does not necessarily hold.

Actually, the relation between the two optimality notions of censor depends on the censor language adopted for the CP censors. In particular, for GA, the set of the theories of the optimal IB censors for a TBox T and a policy P coincides with the set of the deductive closures clTCQ(·) of the theories of the optimal CP censors in GA for T and P. This property is formalized by the following theorem, which is crucial to establish the complexity results of the next section.

Theorem 2 Let T be a DL TBox and P be a policy. Then, ib cens ∈ OptIBCensT ,P iff there exists a CP censor cp cens ∈ GA-OptCPCensT ,P such that, for each ABox A, clTCQ(cp cens(A)) = ib cens(A).

Proof (sketch). (⇐). Since cp cens ∈ GA-OptCPCensT ,P, it is easy to see that cp cens(A) = clTGA(A) for each ABox A such that T ∪ P ∪ A is consistent. Thus, for each ABox A, since T ∪ P ∪ cp cens(A) is consistent and clTCQ(cp cens(A)) = ib cens(A) holds by assumption, we derive that ib cens(A) = ib cens(cp cens(A)), i.e., all pairs of ABoxes A and cp cens(A) are indistinguishable w.r.t. ib cens, and so ib cens is an IB censor for T and P.

We now prove its optimality by contradiction. Suppose there is an IB censor ib cens′ more informative than ib cens. So ib cens(A′ ) ⊂ ib cens′ (A′ ) = ib cens′ (A′i ) ⊆ clTCQ(A′i ), where A′ is the ABox such that ib cens(A′ ) ⊂ ib cens′ (A′ ) and A′i is the ABox such that A′ and A′i are indistinguishable w.r.t. ib cens′ (one of such pairs A′ ,A′i must exist). But then, the function cp cens′ such that cp cens′ (A) = cp cens(A) for each ABox A ̸= A′ and cp cens′ (A′ ) = clTGA(A′i ) can be shown to be a CP censor in GA for T and P more informative than cp cens, which leads to a contradiction.

(⇒). Since ib cens ∈ OptIBCensT ,P, it can be shown that, for each ABox A, ib cens(A) = clTCQ(A) if T ∪P ∪A is consistent, and ib cens(A) = clTCQ(A′ ) otherwise, where A′ is the ABox such that A and A′ are indistinguishable w.r.t. ib cens. Let cp cens be the function such that, for each ABox A, cp cens(A) returns all and only the ground atoms of ib cens(A), i.e., cp cens(A) = GA∩ ib cens(A). From the above considerations, it is not hard to derive that cp cens is a CP censor in GA for T and P such that clTCQ(cp cens(A)) = ib cens(A) for each ABox A. Moreover, it can be shown by contradiction that cp cens ∈ GA-OptCPCensT ,P.

Algorithm 1: OptGACensor

input: a DL-LiteR TBox T , a policy P, an ABox A; output: an ABox;

1. AT ← clTGA(A);
2. Th ← ∅;
3. while AT is not empty do:
4. let α be the lexicographically first assertion in AT ;
5. AT ←AT \ {α};
6. if T ∪ Th ∪ {α} ∪P is consistent then
7. Th ← Th ∪ {α};
8. return Th;

5 Query Answering under Optimal IB Censors

In this section we study query answering under IB censors over DL-LiteR ontologies. In particular, we consider entailment of BCQs specified over the signature of the ontology.

A possible strategy for addressing this problem is to choose only one IB censor among the optimal ones, and use it to alter the answers to user queries. In the absence of a criterion for determining which censor is the best for our purposes, the choice of the optimal censor is made in an arbitrary way (like in [Biskup and Bonatti, 2007; Cuenca Grau et al., 2013]). Towards the realization of an optimal IB censor, we first provide the algorithm OptGACensor (Algorithm 1), which implements a function that, for every DL-LiteR TBox T and every policy P, corresponds to an optimal CP censor in GA for T and P. Then we explain how to use OptGACensor to establish BCQs entailment under an optimal IB censor by exploiting Theorem 2. The algorithm first computes the set AT of ground atoms entailed by T ∪A. Then, it iteratively picks a ground atom α fromAT following the lexicographic order, and adds α to the ABox Th if T ∪ Th ∪ α does not violate the policy P. The following theorem establishes the correctness and complexity of the algorithm.

Theorem 3 Let T be a DL-LiteR TBox and P be a policy. There exists a censor cens ∈ GA-OptCPCensT ,P such that, for each ABox A, OptGACensor(T ,P,A) (i) returns cens(A) and (ii) runs in polynomial time in the size of A.

Proof (sketch). The proof of correctness is straightforward. Tractability in the size of A follows from the fact that clTGA(A) can be computed in polynomial time, and the consistency check of step 6 can be done in AC0 in the size of A [Lembo et al., 2015].

From Theorem 2 and Theorem 3 it follows that, to establish if a BCQ q is entailed by T ∪ A under an optimal IB censor for T and P, it is sufficient to verify whether T ∪ OptGACensor(T ,P,A) |= q, which can be done in polynomial time in the size of A.

We note also that it is possible to implement different optimal IB censors (actually, every optimal IB censor) by modifying the order in which the ABox assertions from the set clTGA(A) are selected by the algorithm.

Depending on the application at hand, the approach of randomly choosing a censor may not always be considered appropriate [Cuenca Grau et al., 2013]. For this reason, in [Lembo et al., 2019] the authors suggest to use a form of skeptical entailment over (the theories of) all the optimal censors, i.e., they propose a CQE framework in which a query has a positive answer if it is entailed by each optimal censor. In the same spirit, we define the following decision problem.

Definition 5 Let T be a DL TBox, P be a policy, A be an ABox, and q be a BCQ. IB-Entailment(T ,P,A, q) is the problem of deciding whether q ∈ cens(A) for every cens in OptIBCensT ,P.

By exploiting Theorem 2 and the results given in [Lembo et al., 2019], we can provide the following theorem.

Theorem 4 Let T be a DL-LiteR TBox, P be a policy, A be an ABox, and q be a BCQ. Then, IB-Entailment(T , P, A, q) is coNP-complete in data complexity.

Proof. The result immediately follows from Theorem 2 and from [Lembo et al., 2019, Theorem 6], which states that deciding if T ∪ cp cens(A) |= q for every cp cens in GAOptCPCensT ,P is coNP-complete in data complexity.

6 Approximating Optimal IB Censors

As stated in Theorem 4, IB-Entailment is in general intractable in data complexity. Towards a practical approach to CQE, in this section we consider a different entailment problem that approximates IB-Entailment, and we show that its data complexity is in AC0 (i.e., the same complexity of evaluating FO queries over a database). The approximation we propose consists in considering a non-necessarily optimal IB censor whose theory, for every ABox, is as close as possible to the theories of all the optimal IB censors.

Definition 6 [AIB censor and QIB censor] Let T be a DL TBox, P be a policy, and cens be an IB censor for T and P. We say that:

• (i) cens is an approximation of the optimal IB censors (AIB censor) for T and P if, for every cens′ ∈ OptIBCensT ,P and for every ABox A, cens(A) ⊆ cens′ (A);
• (ii) cens is a quasi-optimal IB censor (QIB censor) for T and P if cens is an AIB censor for T and P and there exists no AIB censor cens′ for T and P that is more informative than cens.

Example 4 The IB censor cens3 of Example 1 is a QIB censor for T and P (but cens3 ̸∈ OptIBCensT ,P).

For QIB censors the following notable property holds.

Theorem 5 Let T be a DL TBox and P be a policy. A QIB censor for T and P always exists and it is unique.

Proof (sketch). First, observe that the censor cens0 such that cens0(A) = ∅ for every ABox A, satisfies condition (i) of Definition 6. So, either cens0 is a QIB censor, or there exists a more informative AIB censor. This implies the existence of a QIB censor. Then, it is possible to show that if two distinct QIB censors censa, censb exist (i.e., such that censa(A) ̸= censb(A) for at least one ABox A), it is possible to construct another AIB censor cens′a that is more informative than censa (or, more informative than censb), such that cens′a (A′ ) = censa(A′ ) for all A′ ̸= A, and cens′a (A) = clTCQ(A1 ∪A2), where A1 and A2 are two ABoxes indistinguishable with A w.r.t. censa and censb, respectively. This leads to a contradiction.

Hereinafter, we denote with qib censT ,P the QIB censor for T and P. Entailment of BCQs over QIB censors is then naturally defined as follows.

Definition 7 Let T be a DL TBox, P be a policy, A be an ABox, and q be a BCQ. QIB-Entailment(T ,P,A, q) is the problem of deciding whether q ∈ qib censT ,P(A).

We now focus on the case of DL-LiteR TBoxes and prove that, in this case, entailment of BCQs under QIB censors is FO-rewritable. Formally, we say that QIB-entailment in a DL L is FO-rewritable, if for every TBox T expressed in L, every policy P and every BCQ q, one can effectively compute an FO query qr such that for every ABox A, QIB-Entailment(T ,P,A, q) is true iff A |= qr. We call qr the QIB-perfect reformulation of q w.r.t. T and P.

We prove FO-rewritability of entailment of BCQs under QIB censors in DL-LiteR by exploiting a correspondence between this problem and entailment of BCQs under IARsemantics for DL ontologies, which is indeed FO-rewritable for DL-LiteR,den, i.e., DL-LiteR enriched with denial assertions [Lembo et al., 2015]. We recall that the IAR-semantics is an inconsistency-tolerant semantics that allows for meaningful entailment also when the ABox contradicts the TBox of an ontology (for instance, when A = {A(d), B(d), C(d)} and T = {A ⊑ ¬B}). The IAR-semantics is based on the notion of ABox repair (A-repair), which is a maximal subset of the ABox that is consistent with the TBox (in our example there are two A-repairs, R1 = {A(d), C(d)} and R2 = {B(d),C(d)}). Then, entailment under IAR-semantics is defined as follows: let T be a DL-LiteR,den TBox, A be an ABox, and q be a BCQ, IAR-Entailment(T ,A, q) is the problem of verifying whether T ∪Riar |= q, where Riar is the intersection of all A-repairs of O = T ∪ A, called the IAR-repair of O (in our example, Riar = {C(d)}).

To establish the relationship between QIB-entailment and IAR-entailment, we give the notion of secret, which in our framework is the counterpart of minimal inconsistent set in inconsistency-tolerant query answering [Lembo et al., 2015].

Let T be a TBox, let P be a policy, and let A be an ABox. We say that a set of ABox assertions S ⊆ clTGA(A) is a secret in T ∪P∪A, if T ∪P∪S is inconsistent and for each assertion σ ∈ S we have that T ∪P ∪S \ {σ} is consistent. We denote by secrets(T ,P,A) the set of all the secrets in T ∪P ∪A. We now provide the following key property.

Lemma 1 Let T be a DL TBox, P be a policy, A be an ABox, and q be a BCQ. QIB-Entailment(T , P, A, q) is true iff there exists an ABox A′ ⊆ clTGA(A) such that (i) T ∪A′ |= q, and (ii) A′ ∩ S = ∅, for each secret S ∈ secrets(T , P, A).

Proof (sketch). (⇐). It is not difficult to show that given an ABox assertion α ∈ clTGA(A), there exists an optimal IB censor cens ∈ OptIBCensT ,P such that α ̸∈ cens(A) only if there exists a secret S in secrets(T ,P,A) such that α ∈ S.

Now, from the above property, conditions (i) and (ii) we have that A′ ⊆ cens(A) for every cens ∈ OptIBCensT ,P. This means that A′ ⊆ qib censT ,P(A). Moreover, since T ∪A′ |= q, we have that T ∪ qib censT ,P(A) |= q.

(⇒). It is not hard to see that there exists an ABox A′ satisfying condition (i) (A′ is the ABox indistinguishable from A w.r.t. qib cens). As for condition (ii), suppose that there exists an ABox assertion α ∈ A′ and a secret S ∈ secrets(T ,P,A) such that α ∈ S. From Definition 6, we have that α ∈ cens′ (A) for every cens′ ∈ OptIBCensT ,P. Since S \{α} is consistent with T ∪P, it is possible to define an optimal IB censor whose theory contains S \ {α}, which is a contradiction.

The following theorem establishes the relationship between QIB-entailment and IAR-entailment.

Theorem 6 Let T be a DL-LiteR TBox, let P be a policy, let A be an ABox, and let q be a BCQ. QIB-Entailment(T , P, A, q) is true iff IAR-Entailment(T ∪ P, clTGA(A), q) is true.

Proof. Since T ∪A is consistent, then the secrets in T ∪P ∪ clTGA(A) coincide with the minimal subsets of clTGA(A) that are inconsistent with T ∪P. Therefore, the IAR-Repair R of 〈T ∪ P, clTGA(A)〉 is the set of ground atoms from clTGA(A) that do not belong to any secret in T ∪ P ∪ clTGA(A). Thus, from Lemma 1 the thesis follows.

Theorem 6 actually states that, to solve QIB-entailment, we can resort to the query rewriting techniques used to establish IAR-entailment given in [Lembo et al., 2015], provided that we compute clTGA(A). We recall that query entailment under IAR-semantics in a DL L is FO-rewritable if for every TBox T expressed in L and every BCQ q, one can effectively compute an FO query qr such that for every ABox A, IAR-Entailment(T ,A, q) is true iff A |= qr. The query qr is called the IAR-perfect reformulation of q w.r.t. T .

To establish FO-rewritability of QIB-entailment in DL-LiteR, however, we still need to address the above mentioned computation of clTGA(A), and turn it into an additional query reformulation step. To this aim, we can exploit the fact that, for a DL-LiteR,den ontology T ∪ A, an FO query q evaluates to true over clTGA(A) iff q′ evaluates to true over A, where q′ is obtained by suitably rewriting each atom of q according to the positive inclusions of T . Intuitively, in this way we cast into the query all the possible causes of the facts that are contained in the closure of the ABox w.r.t. the TBox (similarly to what is done in query rewriting algorithms for DL-Lite [Calvanese et al., 2007]).

To compute such a query q′ , we use the function atomRewr(q, T ), which substitutes each atom α of q with the formula φ(α) defined as follows (where A, B are atomic concepts and R, S are atomic roles):

The following lemma, whose proof can be immediately obtained from the definitions of clTGA(·) and atomRewr(·, ·), states the property we are looking for.

Lemma 2 Let T be a DL-LiteR,den TBox, A be an ABox, and q be an FO sentence. Then Eval(q, clTGA(A)) = Eval(atomRewr(q, T ), A).

We are now able to extablish FO-rewritability of QIBentailment.

Theorem 7 Let T be a DL-LiteR TBox, P be a policy, q be a BCQ, and qr be an FO sentence that is a IAR-perfect reformulation of q w.r.t. the DL-LiteR,den TBox T ∪P. Then, the FO sentence atomRewr(qr, T ) is a QIB-perfect reformulation of q w.r.t. T and P.

Proof. Let the FO sentence qr be an IAR-perfect reformulation of q w.r.t. the DL-LiteR,den TBox T ∪ P. Then, for every ABox A, IAR-Entailment(T ∪ P, clTGA(A), q) is true iff Eval(qr, clTGA(A)) is true. Now, from Lemma 2, it follows that, for every ABox A, Eval(qr, clTGA(A)) = Eval(atomRewr(qr, T ),A). Since by Theorem 6, for every ABox A such that T ∪A is consistent, IAR-Entailment(T ∪ P, clTGA(A), q) is true iff QIB-Entailment(T ,P,A, q) is true, it follows that the FO sentence atomRewr(qr, T ) is a QIB-perfect reformulation of q w.r.t. T and P.

Since IAR-entailment is actually FO rewritable, as shown in [Lembo et al., 2015], the above theorem proves the FO rewritability of QIB-entailment for DL-LiteR TBoxes. Moreover, the above theorem identifies a technique for obtaining the QIB-perfect reformulation of a CQ, based on a simple combination of the IAR-perfect reformulation algorithm of [Lembo et al., 2015] and the atomRewr reformulation defined above. Therefore:

Corollary 1 Let T be a DL-LiteR TBox, P be a policy, A be an ABox, and q be a BCQ. The problem QIB-Entailment(T , P, A, q) is in AC0 in data complexity.

7 Conclusions

In this paper, we have studied the approach to CQE based on instance indistinguishability and identified a semantically well-founded notion of CQE that enjoys first-order rewritability in the case of DL-LiteR ontologies. We believe that this result opens the way towards practical implementations of CQE engines for DL ontologies and Ontology-based Data Access. We are currently working to achieve this goal.

Another important future direction is a deeper study of the user model. Our framework inherits from its predecessors a relatively simple model, which assumes that the user knows (at most) the TBox and all the query answers returned by the system, and considers only the deductive abilities of the user over such knowledge. This user model might need to be enriched to capture more realistic data protection scenarios.

Acknowledgements

This work was partly supported by the EU within the H2020 Programme under the grant agreement 834228 (ERC Advanced Grant WhiteMec) and the grant agreement 825333 (MOSAICrOWN), by Regione Lombardia within the Call Hub Ricerca e Innovazione under the grant agreement 1175328 (WATCHMAN), and by Sapienza Universit`a di Roma (2019 project CQEinOBDM).