A Novel Approach to Controlled Query Evaluation in DL-Lite

Abstract

In Controlled Query Evaluation (CQE) confidential data are protected through a declarative policy and a (optimal) censor, which guarantees that answers to queries are maximized without disclosing secrets. In this paper we consider CQE over Description Logic ontologies and study query answering over all optimal censors. We establish data complexity of the problem for ontologies specified in DL-LiteR and for variants of the censor language, which is the language used by the censor to enforce the policy. In our investigation we also analyze the relationship between CQE and the problem of Consistent Query Answering.

1 Introduction

In Controlled Query Evaluation (CQE), a policy, i.e., a set of logical assertions, regulates the access to a database or knowledge base by specifying the information that must be kept secret, and a censor alters answers to queries so that confidential data cannot be inferred by the users on the basis of the queries they ask. The notion of censor traces back to [ 16 ], and since then it has been investigated for propositional closed databases [ 6 ], incomplete databases [ 7 ], and, more recently, Description Logic (DL) ontologies [ 10,11 ]. In this latter context, optimal censors are defined as those censors that modify query answers in a “minimal” way. Intuitively, such censors hide data to preserve confidentiality according to the policy, without restricting unnecessarily the ability of the system to return answers to users’ queries.

Previous work on CQE in DLs has mainly focused on the tasks of establishing the existence of an optimal censor and characterizing the complexity of computing it. However, considering only one such censor means making an arbitrary selection among several optimal censors. To avoid such a discretionary choice, in this paper we adopt a different approach and study query answering over all optimal censors. Intuitively, given a query q, this amounts to compute the answers to q that are returned by all optimal censors. This form of reasoning can also be considered as the application of a single Copyright c 2019 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. SEBD 2019, June 16-19, 2019, Castiglione della Pescaia, Italy. censor corresponding to an “intersection” of all the optimal censors, which is thus a semantically well-founded (i.e., sound) approximation of any optimal censor. This idea has been also previously discussed in [ 10 ].

Our approach has similarities with the work on Consistent Query Answering (CQA), a framework for inconsistency management based on the notion of repair [ 3,5 ]. Roughly speaking, in DL, a repair of a possibly inconsistent ontology O is any ABox for O (i.e., the extensional component of Q) that is consistent with the TBox (i.e., the intensional component of O), and that differs “minimally” from the original ABox. Then, computing query answers in CQA amounts to reasoning over all repairs and the TBox. The connection between CQE and CQA in DL is based on the intuition that the assertions in the policy in CQE seems to act as the class of assertions in T that may be violated by the data of the ABox.

Some connections between CQA and a declarative approach for privacy preservation had already been discussed in [ 4 ]. The framework in that paper is similar to ours, with so-called secrecy views playing essentially the role of the policy. However, the setting considered there is relational and without intensional knowledge (TBox), and secrecy views are enforced through suitable virtual modifications of database values with SQL NULLs, so that this approach is incomparable with ours. Nonetheless, in this paper we elaborate on the intuition of [ 4 ] and investigate in depth the relationship between our CQE framework and CQA in DLs. We provide some general conditions ensuring that the two problems are mutually reducible, and we show cases of practical interest for which such conditions are satisfied and cases for which they are not. This also allows us to highlight the differences between the two frameworks.

The ultimate goal of this paper is to investigate data complexity of answering conjunctive queries (CQs) in CQE. In our analysis we consider ontologies specified in DL-LiteR [ 9 ]. We also consider some variants of the censor language LC . Intuitively, LC is the language in which the censor expresses the sentences implied by the ontology that can be disclosed to the users without violating the policy. We provide data complexity results for the cases when: (i) LC is the ABox of the ontology; (ii) LC coincides with the set of ground atoms expressed over the signature of the ontology; and (iii) LC is the language of CQs expressed over the signature of the ontology. Some of the complexity results follow from the correspondence between CQA and CQE; we provide novel techniques for the cases in which the CQE problem does not have a CQA counterpart. The complexity results proved in this paper are shown in Figure 1.

This paper is an extended abstract of [ 15 ], where also complexity results for ontologies specified in E L? [ 1 ] are provided. 2

Preliminaries

We consider a signature of predicates and constants, and a countably infinite alphabet of variables V. To simplify the presentation, we consider only languages containing FO sentences, i.e., formulas without free variables (our results applies to open formulas as well, modulo standard encoding of open formulas into closed ones). We use FO to indicate the language of all function-free FO sentences over and V. Every language considered in this paper is a subset of FO.

Given a set K FO, Mod (K) indicates the set of models of K, i.e., the FO interpretations I such that I (i.e., the interpretation of in I) evaluates to true, for each sentence 2 K. If I is a model of K, we say that I satisfies K and write I j= K. K is consistent if it has at least one model, i.e., if Mod (K) 6= ;, inconsistent otherwise. K entails a FO sentence , denoted K j= , if I is true in every I 2 Mod (K).

A Boolean conjunctive query (BCQ) q is a FO sentence of the form 9x:conj(x), where conj(x) = 1(x) ^ : : : ^ n(x), x is a sequence of variables, and each i(x) is an atom (possibly with constants) with predicate i and variables in x. The length of a BCQ q is the number of its atoms, denoted by length(q).

In the following, CQ denotes the language of BCQs over and V, CQk the language of BCQs from CQ whose maximum length is k, and GA the language of ground atoms. Obviously, for every integer k, GA CQk CQ. Verifying whether K j= for K FO and 2 GA is also called instance checking.

A DL ontology O is specified as T [ A, where T is the TBox and A is the ABox [ 2 ]. Throughout the paper an ABox is always a set of ground atoms. We are interested in DL-LiteR DL ontologies [ 9 ]. A DL-LiteR TBox is a finite set of assertions of the form: B1 v B2, B1 v :B2, R1 v R2, R1 v :R2, where: each Ri, with i 2 f1; 2g, is an atomic role Q 2 , or its inverse Q ; each Bi, with i 2 f1; 2g, is an atomic concept A 2 , or a concept of the form 9Q (resp. 9Q ), i.e., unqualified existential restriction, which denotes the set of objects occurring as first (resp. second) argument of Q.

We also consider denial assertions (or simply denials) over concepts and roles, i.e., sentences of the form: 8x.conj(x) ! ? where conj(x) is such that 9x.conj(x) is a BCQ whose atoms use only unary and binary predicates. The length of the denial is the length of such query. A denial is satisfied by an ontology O if O 6j= 9x.conj(x).

In the following, given an ontology O and a language L FO, we denote with L(O) the subset of formulas of L over the predicates and constants occurring in O.

All the complexity results we provide refer to data complexity, that in our framework is the complexity computed only with respect to the size of the ontology ABox. 3

CQE Framework

Our CQE framework is adapted from [ 11 ]. An L CQE instance E is a quadruple hT ; A; P; LCi, where T is a TBox in the DL L, A is an ABox such that T [ A is consistent, P is the policy, i.e., a set of denial assertions over the signature of T [ A, such that T [ P is consistent, and LC FO(T [ A) is the censor language. Intuitively: T is the schema a user interacts with to pose her queries; A is the dataset underlying the schema; P specifies the knowledge that cannot be disclosed for confidentiality reasons, in the sense that the user will never get, through query answers, sufficient knowledge to violate the denials in P; and LC is the language with respect to which the censor is specified, that is, the censor establishes which are the sentences in LC implied by T [ A that can be divulged to the user while preserving the policy (cf. Definition 1). To simplify the notation, we will sometimes omit to specify that a certain censor language is limited to the signature of T [ A (e.g., we will use GA instead of GA(T [ A)).

We then define a censor in terms of its underlying theory.

Definition 1. The theory Thcens of a censor cens for a CQE instance hT ; A; P; LCi is a subset of LC such that: (i) T [ A j= , for each 2 Thcens, and (ii) T [ P [ Thcens is consistent.

A censor c is optimal if there is no censor c0 such that Thc Thc0 LC. The set of theories of all the optimal censors of a CQE instance E is denoted by Thoc-Set(E ). Example 1. A CQE instance E = (T ; A; P; CQ) is used by an international humanitarian organization for regulating the access to the information about its volunteer staff. In E , T is an empty TBox, A = fworkedIn(v1; cA); workedIn(v1; cB); workedIn(v2; cA)g, and P = f8x.workedIn(x; cA) ^ workedIn(x; cB) ! ?g: In words, the policy specifies as confidential the fact that a volunteer worked in both country A and country B, given that these countries are currently at war with each other.

Below we provide the definition of entailment in CQE1.

Definition 2. (CQE-entailment) Given a CQE instance E and a FO sentence , decide whether Th j= for every Th 2 Thoc-Set(E ). If this is the case, we write E j=CQE .

As usual, when the language of is restricted to ground atoms (i.e., ABox assertions), CQE-entailment is called (CQE-)instance checking.

Example 2. For the CQE instance E of Example 1, we have, for instance, that E j=CQE 9x.workedIn(v1; x) and E j=CQE 9x.workedIn(x; cB), but E 6j=CQE workedIn(v1; cB). 4

Relationship between CQE and CQA

In this section we discuss the relationship between the CQE framework we have just defined and CQA. To this aim, we first provide a general definition for CQA.

A L CQA instance J is a triple hT ; A; LRi where T is a consistent TBox in the DL L, A is an ABox, and LR FO(T [ A) is the repair language. The consistent entailment set in a language L of a (possibly inconsistent) theory T [ A, denoted by CES (T ; A; L), is the set f j 2 L and there exists a A0 A such that T [ A0 is consistent and T [ A0 j= g. A repair for a CQA instance is defined as follows. Definition 3. A repair R for a CQA instance J = hT ; A; LRi is a subset of LR such that: (i) R CES (T ; A; LR) and; (ii) T [ R is consistent and; (iii) there does not exist any R0 such that R R0 CES (T ; A; LR) and T [ R0 is consistent. We denote by RepSet(J ) the set of repairs of J .

Definition 3 captures some notions of repair proposed in the literature, such as the repair at the basis of the prototypical AR-semantics, or the repair adopted by the CARsemantics [ 13,14 ]. Indeed, given an ontology O = T [ A, repairs in the AR-semantics aim to preserve as many facts as possible of those in A. This means that, in a CQA instance adopting the AR-semantics, the language LR has to be set to A. Differently, the CAR-semantics aims to preserve as many facts as possible of those implied by T and 1 Due to space limits, we give a simplified definition and refer to [ 15 ] for other formal details. each subset of A consistent with T . Thus, to encode such semantics LR has to coincide with the set GA(O) of ground atoms over the predicates and constants in O.

We now provide some conditions on CQE and CQA instances that allow to establish correspondences between (theories of) censors and repairs.

Definition 4. A CQE instance hT ; A; P; LCi is CQA-reducible if: (i) for every 2 LC such that T [ A j= and f g [ T [ P is consistent, there exists A0 A such that T [ A0 [ P is consistent and T [ A0 j= ; (ii) for every 2 LC and every A0 A such that T [ A0 [ P is consistent, if

T [ A0 [ P j= then T [ A0 j= .

In words, condition (i) imposes that every logical consequence of T [ A that is consistent with the policy and the TBox belongs to CES (T [ P; A; LC). Condition (ii) instead says that in a CQA-reducible instance the sentences in the policy act as constraints on top of T [ A, since they never contribute to infer new formulas from LC if added to T [ A.

Example 3. The instance E = hT ; A; P; LCi with T = fA v Bg, A = fA(d)g, P = f8x.A(x) ! ?g, and LC = GA is not CQA-reducible, since it does not respect condition (i), even though it satisfies condition (ii) (in a trivial way). Instead, E = hT ; A0; P0; LCi with A0 = fA(d); B(d)g, P = f8x.A(x) ^ B(x) ! ?g, and T and LC as before is CQA-reducible.

Theorem 1. Let E = hT ; A; P; LCi be a CQE instance, such that E is a CQA-reducible. Then Thoc-Set(hT ; A; P; LCi) = RepSet(hT [ P; A; LCi):

Below we consider reducibility of CQA instances into CQE ones.

Definition 5. A CQA instance hT ; A; LRi is CQE-reducible if there exists a partition TP [ TN of T such that TP [ A is consistent, TN is equivalent to a set of denials, and: (i) for every 2 LR, such that TP [ A j= and f g [ T is consistent, there exists

A0 A such that T [ A0 is consistent and T [ A0 j= ; (ii) for every 2 LR and every A0 A such that T [ A0 is consistent, if T [ A0 j= then TP [ A j

0 = .

Intuitively, the above definition says that in a CQE-reducible instance we can identify a portion TN of T such that its assertions act as constraints on the ontology TP [ A (cond. (ii)), thus TN behaves as a policy in a CQE instance. At the same time, each logical consequence of TP [ A consistent with T must belong to CES (T ; A; LR) (cond. (i)). CQE-reducible instances have the following property.

Theorem 2. Let J = hT ; A; LRi be a CQA instance, such that J is CQE-reducible with T = TP [ TN . Then RepSet(hTP [ TN ; A; LRi) = Thoc-Set(hTP ; A; TN ; LRi).

We now rephrase entailment in CQA [ 14 ]: given a CQA instance J = hT ; A; LRi and a FO sentence , decide whether T [ R j= for every R 2 RepSet(J ). This is denoted by J j=CQA . The following results follow from Theorem 1 and Theorem 2. Corollary 1. Let E = hT ; A; P; LCi be a CQA-reducible CQE instance and a FO sentence. Then, E j=CQE iff J j=CQA , where J = hT [ P; A; LCi. Furthermore, Let J = hT ; A; LRi be a CQE-reducible CQA instance with T = TP [ TN , and a FO sentence. Then, J j=CQA iff E j=CQE , where E = hTP ; A; TN ; LRi .

CQE under Restricted Censor Languages

In this section we establish data complexity of instance checking and CQ entailment for DL-LiteR CQE instances, when the censor language LC coincides with the ABox A, and with the set of ground atoms GA. For the former case, we establish our complexity results by exploiting a mutual reduction between entailment in CQE and CQA. For the latter case, the two frameworks behave in a slightly different way, and thus we also need to use techniques tailored to the CQE setting.

We start with LC = A, and show that CQE instances are CQA-reducible, but also that CQA-instances are CQE-reducible when the repair language coincides with A. Theorem 3. Each DL-LiteR CQE instance hT ; A; P; Ai is CQA-reducible, and each DL-LiteR CQA instance hT ; A; Ai is CQE-reducible.

The following result follows from Theorem 3 and the fact that CQ entailment in DL-LiteR;den CQA instances under AR-semantics is coNP-complete, already for instance checking [ 14 ].

Theorem 4. Both instance checking and CQ entailment are coNP-complete in data complexity for DL-LiteR CQE instances hT ; A; P; Ai.

We now consider LC = GA. In this case, DL-LiteR CQE instances are not always CQA-reducible, as shown in Example 3. Reducibility in the other way round is also not always possible. However, we can show some weaker, but useful, properties. Proposition 1. Each DL-LiteR CQE instance hT ; A; P; GAi, such that T [ P [ f g is satisfiable for each 2 A, is CQA-reducible. Also, each DL-LiteR CQA instance hT ; A; GAi, such that T [ f g is satisfiable for each 2 A, is CQE-reducible.

For DL-LiteR CQE instances satisfying the conditions mentioned in Proposition 1 we can establish computational complexity of query answering by mutual reduction between CQE and CQA under CAR-semantics, similarly to what we have done to prove Theorem 4. In fact, we are able to exactly characterize the complexity for general DL-LiteR CQE instances by using tailored proofs, which are inspired to those used in CQA to establish both upper and lower complexity bounds.

Theorem 5. Instance checking and CQ entailment are respectively in AC0 and coNPcomplete in data complexity, for DL-LiteR CQE instances hT ; A; P; GAi. 6

CQE under Full Censor Language

In this section we study CQE-entailment when the censor language LC is CQ. We start with the following property that is central for our analysis.

Theorem 6. Let T be a DL-LiteR TBox, let A be an ABox such that T [ A is consistent, let P be a policy, let q be a BCQ, and let k = max(h; length(q)), where h is the maximum length of a denial assertion in P. Then, hT ; A; P; CQi j=CQE q iff hT ; A; P; CQki j=CQE q.

LC = A LC = GA LC = CQ Instance Checking coNP-complete in AC0 in PTIME

CQ Entailment coNP-complete coNP-complete in PTIME In the rest of the section, without loss of generality, we assume that, in every CQE instance of the form hT ; A; P; CQki, all formulas of the language CQk (as well as the query q of the CQE-entailment problem) use the set of 2k variables fx1; : : : ; x2kg.

We now define the CQE-Ent-DL-LiteR algorithm for deciding CQE-entailment of BCQs for DL-LiteR KBs.

Algorithm CQE-Ent-DL-LiteR(T ; A; P; q)

Input: DL-LiteR TBox T , ABox A s. t. T [ A is consistent, policy P, BCQ q Output: true if hT ; A; P; CQi j=CQE q, false otherwise let h be the maximum length of a denial in P; let k = max(h; length(q));

= CQEntailedSubset(T ; A; k); for i = 1 to k do remove from every subset 0 such that j 0j = i and T [ P [ 0 is inconsistent; if q 2 then return true else return false

In the algorithm, CQEntailedSubset(T ; A; k) is the function returning the set of BCQs from CQk that are entailed by T [ A.

Informally, the algorithm first computes an integer k, based on the length of q and of the denials in P; then, it computes the set that represents the intersection of the theories of the optimal censors for the CQE instance hT ; A; P; CQki: this is done by eliminating from all formulas that belong to minimal subsets of that are inconsistent with T [ P; finally, it checks the presence of q among the queries in the above set . Theorem 7. Let E = hT ; A; P; CQi be a DL-LiteR CQE instance, and q a BCQ. Then, E j=CQE q iff CQE-Ent-DL-LiteR(T ; A; P; q) returns true.

Algorithm CQE-Ent-DL-LiteR(T ; A; P; q) runs in PTIME in the size of the ABox, since CQEntailedSubset(T ; A; k) can be computed in polynomial time in the size of A and checking the consistency of T [ P [ 0 can be reduced to checking the consistency of a DL-LiteR;den ontology, which is polynomial in data complexity [ 14 ]. Theorem 8. Entailment of CQs is in PTIME in data complexity for DL-LiteR CQE instances hT ; A; P; CQi. 7

Conclusions

Our results (cf. Figure 1) show a surprising aspect: the complexity of CQ entailment for restricted censor languages is harder than when LC = CQ. Indeed, in this latter case, CQ entailment can be established through the computation of the intersection of (a finite and polynomial representation of) all the theories of optimal censors, which can be done in polynomial time. This does not hold for LC equal to A or GA.

Our research work can be extended in many directions. First, the PTIME upper bound for CQE over DL-LiteR TBoxes and CQ censor language should be refined. We believe that an AC0 bound can be shown in this case. Then, the complexity analysis of CQE could be extended to other DLs, as well as to other policy and censor languages. Also, based on the complexity analysis presented in this paper, it would be important to look for practical techniques allowing for the implementation of CQE extensions of current DL reasoners and Ontology-based Data Access systems [ 8,12 ].

References

1. F. Baader , S. Brandt , and C. Lutz . Pushing the E L envelope . In Proc. of IJCAI , pages 364 - 369 , 2005 .

2. F. Baader , D. Calvanese , D. McGuinness , D. Nardi , and P. F. Patel- Schneider, editors. The Description Logic Handbook: Theory, Implementation and Applications . Cambridge University Press, 2nd edition, 2007 .

3. L. E. Bertossi . Database Repairing and Consistent Query Answering. Synthesis Lectures on Data Management . Morgan & Claypool Publishers, 2011 .

4. L. E. Bertossi and L. Li . Achieving data privacy through secrecy views and null-based virtual updates . IEEE Trans. Knowl . Data Eng., 25 ( 5 ): 987 - 1000 , 2013 .

5. M. Bienvenu and C. Bourgaux . Inconsistency-tolerant querying of description logic knowledge bases . In RW Tutorial Lectures , pages 156 - 202 , 2016 .

6. J. Biskup and P. A. Bonatti . Controlled query evaluation for enforcing confidentiality in complete information systems . Int. J. Inf. Sec. , 3 ( 1 ): 14 - 27 , 2004 .

7. J. Biskup and T. Weibert . Keeping secrets in incomplete databases . Int. J. Inf. Sec. , 7 ( 3 ): 199 - 217 , 2008 .

8. D. Calvanese , B. Cogrel , S. Komla-Ebri , R. Kontchakov , D. Lanti , M. Rezk , M. RodriguezMuro, and G. Xiao. Ontop: Answering SPARQL queries over relational databases . Semantic Web J. , 8 ( 3 ): 471 - 487 , 2017 .

9. D. Calvanese , G. De Giacomo, D. Lembo , M. Lenzerini , and R. Rosati . Tractable reasoning and efficient query answering in description logics: The DL-Lite family . J. of Automated Reasoning , 39 ( 3 ): 385 - 429 , 2007 .

10. B. Cuenca Grau , E. Kharlamov , E. V. Kostylev , and D. Zheleznyakov . Controlled query evaluation over OWL 2 RL ontologies . In Proc. of ISWC , pages 49 - 65 , 2013 .

11. B. Cuenca Grau , E. Kharlamov , E. V. Kostylev , and D. Zheleznyakov . Controlled query evaluation for Datalog and OWL 2 profile ontologies . In Proc. of IJCAI , pages 2883 - 2889 , 2015 .

12. G. De Giacomo , D. Lembo , M. Lenzerini , A. Poggi , R. Rosati , M. Ruzzi , and D. F. Savo . MASTRO: A reasoner for effective Ontology-Based Data Access . In Proc. of ORE , 2012 .

13. D. Lembo , M. Lenzerini , R. Rosati , M. Ruzzi , and D. F. Savo . Inconsistency-tolerant semantics for description logics . In Proc. of RR , pages 103 - 117 , 2010 .

14. D. Lembo , M. Lenzerini , R. Rosati , M. Ruzzi , and D. F. Savo . Inconsistency-tolerant query answering in ontology-based data access . J. of Web Semantics , 33 : 3 - 29 , 2015 .

15. D. Lembo , R. Rosati , and D. F. Savo . Revisiting controlled query evaluation in Description Logics . In Proc. of IJCAI , 2019 . To appear.

16. G. L. Sicherman , W. de Jonge, and R. P. van de Riet. Answering queries without revealing secrets . ACM Trans. Database Syst ., 8 ( 1 ): 41 - 59 , 1983 .