We study con dentiality enforcement in ontologies under the Controlled Query Evaluation (CQE) framework. In a CQE system, a policy speci es the sensitive information, and a censor ensures that answers to user's queries that could violate the policy are not returned. Our goal is the design of optimal CQE algorithms, which ensure con dentiality while maximising access to information. We study two natural classes of censors that can be realised using existing infrastructure for query answering and propose optimal CQE algorithms for the standardised pro les of the ontology language OWL 2.
is a pressing need to devise mechanisms for ensuring that data is only made accessible to authorised users [1, 7{12, 20, 21].
Controlled Query Evaluation (CQE) is a prominent formal framework for con dentiality enforcement. In CQE, sensitive information is declaratively speci ed by means of a policy and con dentiality is enforced by a censor : when given a user query, a censor checks whether returning the answer might lead to a policy violation, in which case it returns a distorted answer. CQE was introduced in [18], and studied in [3, 4, 6] for propositional databases with complete information. It was extended to (propositional) incomplete databases in [5]. Beyond propositional logic, CQE remains largely unexplored [2].
In this paper we study CQE in the context of ontologies. Our basic framework is described in Section 3. We assume data to be hidden and that users interact with the system by means of a query interface. An ontology, which we assume to be known to all users, provides the vocabulary and background knowledge needed for users to formulate accurate queries, as well as to enrich query answers with implicit information. Policies are given as a set of ground atoms that follow from the ontology and data. When given a (conjunctive) query, the system returns the subset of certain answers determined by the censor; in this way, the role of the censor is to preserve con dentiality by ltering out those answers that could lead to a violation of the policy. Formally, we model the information that users could gather by querying the system as an (in nite) rst-order theory; ? This paper recapitulates and extends our previous work [11]. It comes with a technical report available at http://tinyurl.com/DL14paper55. con dentiality preservation then amounts to ensuring that such theory together with the ontology does not entail any atom in the policy. In this setting, there is a danger that con dentiality enforcement may over-restrict users' access. Thus, we focus on optimal censors, which maximise answers to queries while ensuring con dentiality of the policy. Furthermore, we are interested in censors that can be implemented by reusing o -the-shelf query answering infrastructure. To ful l this requirement, we introduce in Section 4 two classes of censors, which we call view and obstruction censors, respectively.
View censors return only those answers that follow from the ontology and a materialised dataset (a view ). In this way, a view encodes the information that users are authorised to access: the censor answers faithfully all queries against the view, and any information not captured by the view is inaccessible by default. View censors require the ability to materialise implicit data, and hence are especially well-suited for RDF-based applications in which reasoning is performed by a triple store. Obstruction censors are dual to view censors in the sense that they explicitly specify information which users are denied access to (with all other information being accessible by default). Obstruction censors are speci ed by a nite set of \forbidden query patterns" (obstructions ), and all query answers that instantiate such patterns are ltered out. In contrast to view censors, obstruction censors do not require modi cation of the data and hence are well-suited for OBDA applications, where data is typically managed by an
that it is not always possible to \simulate" one with another.
In Section 5 we focus on view censors. First, we investigate their intrinsic limitations, and then show how these limitations can be circumvented. We propose algorithms for computing optimal view censors for knowledge bases with OWL
however, rely on views that can be of exponential size in the worst case. So, we identify natural conditions on ontologies that guarantee polynomial size of optimal views. In particular, all OWL 2 QL ontologies satisfy these conditions.
cient and necessary conditions for an optimal such censor to exist. Then, we propose algorithms for computing optimal obstruction censors for knowledge bases with OWL 2 QL as well as restricted OWL 2 RL ontologies, which are based on obstructions of polynomial size. 2
We treat equality as an ordinary predicate, but assume that any set of formulae
contains all the axioms of equality for . A fact is a ground, equality-free
atom, and a dataset is a nite set of facts. A structure I is a pair ( I ; I ) of a
domain and interpretation function for the symbols in the signature. We de ne
homomorphisms between structures I and J in the standard way and I ,! J
denotes the fact that such a homomorphism from I to J exists.
(
A rule is a sentence of the form 8x:8z:['(x; z) ! 9y: (x; y)], where x, z, and y are pairwise disjoint vectors of variables, the body '(x; z) is an equalityfree conjunction of atoms with variables x [ z, and the head (x; y) is a conjunction of atoms with variables x [ y. For simplicity universal quanti ers in rules are usually omitted. A rule is (i) Datalog if its head consists of a single atom and y is empty; (ii) guarded if it has a body atom (a guard ) mentioning all universally quanti ed variables; (iii) linear if it has a single body atom; and (iv) multi-linear if the body contains only guards. An ontology is a nite set of rules. We assume that both rule heads and bodies are non-empty and they do not contain the nullary atoms > and ?. Thus, O [ D is satis able for each ontology O and dataset D, and O 6j= for each fact , which ensures a separation between schema and data.
the normalised axioms of this DL in the form of rules. To capture the semantics
of >, usually allowed in DLs, we treat it as a unary predicate and assume that
each ontology O contains the rule P (x1; : : : ; xn) ! >(xi) for each predicate P
and 1 i n. A Horn-SROIF ontology is in (i) RL if it has no rules of
Type (
'(x; y) a conjunction of atoms. A union of CQs (UCQ ) is a formula Wi Qi(x), with each Qi(x) a CQ. A CQ is Boolean (BCQ ) if x is empty. A tuple of constants t is a (certain) answer to Q(x) over ontology O and dataset D if O [ D j= Q(t).
3
to users, who can formulate arbitrary CQs via a query interface. A policy, which is unknown to users, is given as a set of facts entailed by O[D. It is assumed that system administrators are in charge of specifying policies, and that each policy is assigned to a speci c (group of) users by means of standard mechanisms such as role-based access control techniques [17].
De nition 1. A policy P for O and D is a dataset such that O [ D j= P. A CQE-instance I is a triple (O; D; P), with P a policy for O and D.
Oex = fFOf (x; y) !FOf (y; x); Susp(x)^Cr (x) !Thr (x);
Likes(x; y) ^ Thr (y) ! ThrFan(x)g; Dex = fFOf (John; Bob); FOf (Bob; Mary ); Likes(John; Seven);
Likes(Bob; Seven); Susp(Seven); Cr (Seven)g:
crime are thrillers; and everyone who likes a thriller is a thriller fan. Assume that John wants to hide his friend list. Then, Pex = f exg with ex = FOf (John; Bob), and Iex = (Oex; Dex; Pex).
De nition 2. A censor for a CQE-instance I = (O; D; P) is a function cens that maps each CQ Q to a subset of cert(Q; O; D). The characteristic theory Thcens of cens is the (possibly in nite) set of sentences
fQ(t) j t 2 cens(Q) and Q(x) is a CQg: Censor cens is con dentiality preserving if O [ Thcens 6j= for each 2 P. It is optimal if (i) it is con dentiality preserving and (ii) no con dentiality preserving censor cens0 6= cens exists such that cens(Q) cens0(Q) for every Q.
by asking an unbounded number of queries to the system. If the censor is con dentiality preserving, then no information can be obtained about P, regardless of the CQs asked. Finally, optimal censors maximise information accessibility without compromisig the policy. 4
called a view. Intuitively, a view encodes the information that a user is allowed to see. The user gets only those query answers that follow from O and this view.
certain answers, which can be fully delegated to the query answering engine.1 1 We assume that all the de nitions in this section are parameterised by a ( xed) instance I = (O; D; P).
De nition 3. The view censor vcensIV for I based on a dataset V (a view), is the function mapping each CQ Q(x) to the set cert(Q; O; D) \ cert(Q; O; V).
encode as much information from the hidden dataset as possible.
with a fresh constant anb. Intuitively, Vex is the result of \anonymising" the constant Bob, while keeping the structure of the data intact. Since Vex contains no information about Bob, we have Oex [ Vex 6j= ex, that is the censor based on Vex is con dentiality preserving. View Vex, however, is not optimal: Oex [ Vex does not entail the fact Likes(Bob; Seven), which is harmless for con dentiality. Indeed, Oex [Ve0x 6j= ex holds for the extension Ve0x of Vex with Likes(Bob; Seven).
pecially well-suited for RDF-based applications, in which reasoning is performed by a triple store. In OBDA scenarios, however, data is typically managed by an
the form of a Boolean UCQ U , such that given a query Q(x) and an answer t over O and D, the censor returns t only if no CQ in U follows from Q(t). Thus, the obstruction can be seen as a collection of \forbidden query patterns", which should not be disclosed.
De nition 4. The obstruction censor ocensIU for I based on a Boolean UCQ U (called an obstruction) is the function mapping each CQ Q(x) to the set ft j t 2 cert(Q; O; D) and A[Q(t)] 6j= U g:
rithms: checking A[Q(t)] j= U can be delegated to an RDBMS. Also, obstructions can be maintained virtually without the need of data materialisation.
following obstruction Uex:
9x:FOf (x; Bob) _ 9x:FOf (Bob; x) _ 9x:Likes(Bob; x) _ ThrFan(Bob):
the same as over Oex [ Dex.
and an obstruction. View and obstruction censors, however, behave rather differently: a view explicitly encodes the information accessible to users, whereas obstructions specify information which users are denied access to. Thus, obstructions are dual to views. Unsurprisingly, even in simple cases it is not obvious whether (and how) a view can be realised by an obstruction, or vice-versa.
and obstruction U yield the same censor. Each Datalog ontology O and dataset
is es t 2 cert(Q; O; D) i A[Q(t)] ,! HO;D and hence captures the information relevant to query answering. We can then formalise the duality between views and obstructions in a natural way: U and V implement the same censor i U captures the structures not homomorphically embeddable into HO;V . To formalise this statement, we recall the notion of (non-uniform) constraint satisfaction [13]. De nition 5. Let J be a nite structure and C a class of nite structures. The CSP of J relative to C (denoted CSP[C](J )) is the set fI 2 C j I ,! J g.
De nition 6. Let C be a class of nite structures and let C0 C. First-order sentence de nes C0 if I 2 C0 is equivalent to I j= for every structure I 2 C.
Theorem 1. Let I = (O; D; P) be a CQE-instance with O Datalog ontology, and C the class of nite structures I with I ,! HO;D. Then, vcensIV = ocensIU i U de nes :CSP[C](HO;V ), for any view V and obstruction U .
Theorem 2. There is a CQE-instance for which there exists a view censor, but no obstruction censor. There is a CQE-instance for which there exists an obstruction censor, but no view censor. 5
studied independently. In this section, we focus on view censors.
Theorem 3. There are CQE-instances I1 and I2 such that
- the ontology of I1 uses rules of Types (
optimal views; in turn, the construction of I2 shows that equality is not needed to preclude optimality in the presence of recursion, transitivity axioms, and Self restrictions.
MovFan anj ThrFan
John anb2 anb1 Bob
De nition 7. Let I = (O; D; P) be a CQE-instance with O a guarded RL ontology. A view V consisting of unary atoms Vc1 on constants from I, unary atoms V91 on new constants (anonymised copies), and binary atoms V2, is exhaustive on I if it satis es all of the following. 1. The part Vc1 is a maximal set of unary atoms from HO;D such that O[Vc1 6j= for each 2 P. 2. For each constant a from I, and each set A of unary predicates, such that - A(a) 2 HO;D for every A 2 A, - if A; B 2 A, and O j= A(x) ^ B(x) ! C(x), then C 2 A, - if A 2 A, then O 6j= A(x) ! x a for each a, - O [ Vc1 [ fA(a0)jA 2 Ag 6j= for each 2 P and a fresh constant a0, the view V uses a fresh constant aA, and the part V91 contains all unary atoms A(aA) such that A 2 A. 3. For each constant a from I, let a be the set of constants consisting of a itself and all the constants aA. The binary part V2 of the view V contains the atom R(a1; a2) for constants a1; a2 i - R(a1; a2) 2 HO;D, where a1 2 a1 and a2 2 a2 , - O [ fR(a1; a2)g 6j= for any 2 P, and
1 1 1 1 - O [ Vc [ V9 [ fR(a1; a2)g j= A(a ) implies that A(a ) 2 Vc [ V9.
O = fThrFan(x) ! MovieFan(x); ThrFan(y) ^ FOf (x; y) ! MovieFan(x)g; D = fFOf (John; Bob); ThrFan(John); ThrFan(Bob)g;
P = fMovieFan(Bob); MovieFan(John)g:
ure 1, where Vc1 = ;, V91 contains unary atoms over the anonymised copies anb1, anb2 of Bob, and anj of John, and V2 contains the depicted binary atoms. Two anonymised copies of Bob are necessary in any optimal view for I to answer correctly \harmless" queries like 9x; y; z:ThrFan(z) ^ MovieFan(z) ^ FOf (y; z) ^ ThrFan(y) ^
MovieFan(y) ^ FOf (y; x) ^ MovieFan(x) ^ FOf (John; x):
Theorem 4. Let I = (O; D; P) be a CQE-instance with O a guarded RL ontology, and V an exhaustive view on I. Then V is optimal. Furthermore, if O is linear, then vcensIV is the only optimal censor for I.
HAlOso;V, p=ropVerftoiersaonfyVec1x, hVa91u,stainvde Vvi2ewguVar,anthteaet tihs,atnoV rduoleess naoret eanptpaliilcaabnlye ptoolicVy. atom. Optimality follows from the fact that for any a in I, each combination of its unary atoms that satis es the relevant axioms in O is \witnessed" by a new constant from a, and all possible binary atoms which are compatible with those combinations are added to the view. Then, no essentially new atom can be \added" to the view V without disclosing a policy. The uniqueness of the optimal censor for linear ontologies follows from the lack of choices in the construction of V. An exhaustive view may use exponentially many constants. However, for multi-linear ontologies, optimal views are of polynomial size.
Proposition 1. Let I = (O; D; P) be a CQE-instance with O a multi-linear RL ontology. There is an optimal censor for I based on a view of polynomial size. 5.2
View Censors for EL and QL
quanti ed knowledge. To bridge this gap, we show that, under some mild conditions, we can transform an ontology O into a Datalog ontology O0 such that an optimal view for (O; D; P) can be directly obtained from such a view for (O0; D; P). Thus, devising an optimal view censor for an instance is reduced to devising one for an instance with a Datalog ontology.
De nition 8. Let be a set of constants. A Datalog ontology O0 is a ( Datalog) -rewriting of an ontology O if for each fact and dataset D over constants from we have that O [ D j= i O0 [ D j= .
Proposition 2. Let I = (O; D; P) be a CQE-instance with D using set of constants , O0 a -rewriting of O such that O0 j= O, and V0 an optimal view for (O0; D; P). Then HO0;V0 is an optimal view for I.
Now, we just need to transform a QL (or guarded EL) ontology into a stronger
guarded RL ontology, which, however, entails the same facts for any dataset. We
exploit techniques developed for the combined approach to query answering [14{
16, 19]. The idea is to transform rules of Type (
Propositions 2 and 3 ensure that H (O);V is optimal for I = (O; D; P) with
is a guarded RL ontology, and the results of Section 5.1 are applicable. Theorem 5. A CQE-instance with a QL or guarded EL ontology has an optimal view censor. For QL, it is unique and can be based on a polynomial size view. 6
De nition 10. A goal is a conjunction of atoms. The SLD resolution step takes a goal 1 ^ : : : ^ m and a Datalog rule Vik=0 i ! and produces a new goal (Vik=0 i ) ^ 2 ^ : : : ^ m , where is a most general uni er (MGU) of 1 and . A proof of a goal G0 in a Datalog ontology O and dataset D is a sequence G0 r1; !1 G1 r2; !2 : : : rn; !n Gn; where Gn = > and the goal Gi is obtained from the goal Gi 1 and sentence ri 2 O [D by an SLD resolution step with MGU i.
a proof of G exists in O [ D i O [ D j= 9 G, with 9 G the existential closure of G. We next provide a characterisation of optimality based on proofs. Consider a policy atom 2 P and some proof of in O [ D. If a censor answers positively su ciently many BCQs 9 G for goals G in , then a user could \reconstruct" (a part of) and compromise the policy. Also, there can be many proofs of , and a user can compromise the policy by reconstructing any of them. Thus, to ensure that a censor is con dentiality preserving, we must guarantee that the obstruction contains enough CQs to prevent reconstruction of any . If we want the censor to be optimal, the obstruction should not \block" too many queries.
in nite \obstruction". To formalise this intuition we need an auxiliary notion.
Q 2 Q there exists Q0 2 C with Q j= Q0.
2 To correctly deal with Self restrictions (rules (
Theorem 6. Let I = (O; D; P) be a CQE-instance with O a Datalog ontology. 1. If is a nite pseudo-obstruction for I, then U = WQ2 Q is an optimal obstruction for I. 2. If each pseudo-obstruction for I is in nite, then no optimal obstruction censor for I exists.
Theorem 7. There is a CQE-instance with ontology in both RL and EL (respectively, RL) for which an optimal view (respectively, obstruction) censor exists, but no optimal obstruction (respectively, view) censor exists.
mal obstructions for instances with linear RL ontologies. These results are then adapted to the case of QL. The algorithm for linear RL is based on the computation of the set Q(I). To do this computation e cient, we need the following auxiliary structure.
De nition 12. Let O be a linear RL ontology, D a dataset, x and y fresh variables, and A the set of all equality-free atoms over the signature of O[D extended with x and y. The proof graph of O [ D is the directed graph with the set of nodes A [ f>g, and edges ( ; ) such that can be derived from by means of a single SLD resolution step with a rule from O [ D.
Example 5. Consider a CQE-instance Ie1x with ontology Oe1x = fLikes(x; y) ! Movie(y); Likes(x; y) ! MovieFan(x)g, dataset De1x = fLikes(John; Seven)g, and the policy of single atom e1x = MovieFan(John). A fragment of the proof graph is given in Figure 2.
Theorem 8. Let I = (O; D; P) be a CQE-instance with O a linear RL ontology. For each 2 P, let S be the set of nodes in the proof graph of O [ D in a path from to >. Finally, let U be the Boolean UCQ _
_ 2P
G2S nf>g 9 G: Then, ocensIU is the unique optimal censor for I, and U can be computed in polynomial time in the size of I.
↵ e1x = MovieFan(John)
Movie(Seven)
MovieFan(x) Likes(John, y)
Likes(x, Seven) Likes(John, Seven) >
Movie(y)
Likes(x, y) 1 1
Fig. 2. Fragment of proof graph for Oex [ Dex
from e1x to > and S e1xn f>g = fMovieFan(John); likes(John; y)g. Thus, U = MovieFan(John) _ 9y:Likes(John; y) is optimal.
(O) given in De nition 9, preserves linearity of rules. Hence, Proposition 3 and Theorem 8 yield the following result.
Theorem 9. For every CQE-instance with a QL ontology there exists a unique optimal obstruction censor. 7
for system designers to ensure selective access to data and provide insights on the fundamental tradeo between accessibility and con dentiality of information.
be implemented using o -the-shelf query answering infrastructure. Thus, our algorithms provide a starting point to the development of CQE systems.
questions. From a theoretic point of view, we plan to consider policies beyond sets of facts (e.g., given as CQs). We also plan to study weaker notions of optimality that can ensure polynomiality of views and obstructions for more expressive languages. From a practical perspective, we will implement our algorithms and test their scalability using state-of-the art Datalog engines such as RDFox.3
work in [9]. In this setting, policies are represented as authorisation views : CQs that de ne the only information accessible to the user; since queries are answered faithfully against the views, there is no explicit notion of policy violation. In contrast, in our setting policies express inaccessible information, and our goal is to maximally answer queries without violating the policy.
3 http://www.cs.ox.ac.uk/isg/tools/RDFox/