This extended abstract summarizes our recent work [1] in which we study a dynamic Controlled Query Evaluation method over Description Logic ontologies. Semantic Web technologies are increasingly used to represent and link together diferent sources of information coming from public organizations as well as private citizens. This information may include sensitive knowledge, e.g., medical records or social network activities, whose disclosure may afect the privacy of individuals if not adequately protected [2, 3]. One goal of confidentiality-preserving data publishing is to prevent the disclosure of sensitive information to unauthorized users while being as cooperative as possible, that is, answering queries honestly whenever this does not harm confidentiality. Specifically, in Controlled Query Evaluation (CQE) [4, 5] the data protection policy is declaratively specified through logical formulas and is enforced by altering query answers through so-called censors, which either refuse to answer some queries or lie when this is needed in order to protect some secrets. In general, there exist multiple, mutually incomparable ways of concealing answers, i.e., mutually incomparable censors. Diferent works proposed static CQE methods, where a censor is constructed (or approximated) beforehand, establishing once and for all which queries should be answered truthfully [2, 6, 7, 8, 9]. In several cases, such approaches are not fully cooperative, because the secure view of the data is chosen without taking the users' interests into account. Conversely, following the work of Biskup and Bonatti [10], in this paper we introduce a dynamic CQE (dynCQE) method that progressively decides whether to be truthful or to lie, based on the specific stream of queries. Roughly speaking, the dynamic CQE approach selects, at each step, as many censors as possible, coherently with the previous answers. By doing so, it
maximizes the possibility of answering the next query honestly by choosing from the current pool of censors those that allow answering the query truthfully (if any).
We consider Description Logic (DL) ontologies = ∪ , where is a TBox and is an ABox. We assume that an ABox is a finite set of ground atoms, i.e., assertions of the form () and (, ), where and are an atomic concept and an atomic role, respectively, occurring in the signature of , and and are constants. In what follows, we denote by cl () the set of ground atoms entailed by an ontology ∪ , i.e., cl () = { | is a ground atom and ∪ |= }. We also consider data protection policies (for short, policies) that are finite sets of denials, i.e., sentences of the form → ⊥ such that is a Boolean conjunctive query (BCQ). As for user queries, we focus on Boolean Union of Conjunctive Queries (BUCQs).
A CQE specification is a pair ⟨ , ⟩, where is a TBox and is a policy such that ∪ is a consistent first-order (FO) theory. A CQE instance is a triple ℰ = ⟨ , , ⟩, where ⟨ , ⟩ is a CQE specification, and is an ABox such that ∪ is consistent. In this paper, we assume that a user is aware of both the TBox and the policy, but not the ABox.
Censors specify which consequences of an ontology can be disclosed without violating the policy. The following definition is adapted from [9, Definition 1].
Definition 1 (Censor). Let ℰ = ⟨ , , ⟩ be a CQE instance. A censor for ℰ is an ABox ⊆ cl () such that ∪ ∪ is consistent.
Given a CQE instance ℰ and a censor for ℰ , we say that is optimal if there exists no censor ′ for ℰ such that ⊂ ′. We denote by OptCens(ℰ ) the set of all the optimal censors for ℰ . We observe that a censor for a CQE instance ℰ always exists,1 and thus OptCens(ℰ ) ̸= ∅. Given a BUCQ , we denote by OptCens(ℰ , ) the set of optimal censors that, together with , entail :
OptCens(ℰ , ) = { ∈ OptCens(ℰ ) | ∪ |= }
We are interested in dynamic CQE systems, which a user interacts with by evaluating one query after another. The following notion of state captures the history of such queries. Definition 2 (State). Let ℰ = ⟨ , , ⟩ be a CQE instance. A state of ℰ is a pair = ⟨ℰ , ⟩, where = ⟨1, . . . , ⟩ (with ≥ 0) is a sequence of BUCQs.
The evaluation of each query provides the user with new information. The query answering
semantics adopted by the CQE system must ensure that, even by collecting such information, it
is impossible for the user to discover data protected by the policy. At the same time, we aim
to get a semantics that returns the longest possible sequence of honest answers before lying
(the so-called “longest honeymoon” approach [
Definition 3 (Dynamic CQE – dynCQE). Let ℰ = ⟨ , , ⟩ be a CQE instance, and let = ⟨1, . . . , ⟩ (with ≥ 0) be a sequence of BUCQs. The set StCens() of censors of is inductively defined as follows: 1Trivially, the empty set is a censor for any CQE instance ℰ.
• StCens(0) = OptCens(ℰ ); • StCens(+1) =
StCens() ∩ OptCens(ℰ , +1) otherwise, for every 0 ≤ ≤ − 1.
{︃StCens() if StCens() ∩ OptCens(ℰ , +1) = ∅, For each BUCQ occurring in , we say that is entailed by , denoted by |= , if ∪ |= for every ∈ StCens(). We denote by EntQ () the set of queries of entailed by , i.e., EntQ () = { ∈ | |= }.
One can see that, for any = 1, . . . , , the set of censors of a state is always non-empty and consists of a subset of the set of censors of its predecessor state − 1, i.e., StCens(− 1) ⊇ StCens() ⊃ ∅ . This also implies that EntQ (− 1) ⊆ EntQ () holds for any = 1, . . . , .
Informally speaking, each set StCens() (with 1 ≤ ≤ ) in the above definition progressively selects the optimal censors of ℰ that agree with EntQ (). If none of the surviving optimal censors in StCens() entails (together with ) a query +1, then +1 ̸|= +1, so we have that StCens(+1) = StCens(). Conversely, if at least one of the censors in StCens(), together with the TBox, entails +1, then, according to dynCQE, we have a positive answer, and StCens(+1) keeps only the censors in StCens() that agree with such answer. Example 1. Some pharmaceutical products may reveal with high accuracy which kind of disease is afecting a person. For instance, drugs that contain phenytoin, or that are classified as anti-seizure medications, indicate some form of epilepsy.
Let ℰ = ⟨ , , ⟩ be a CQE instance, where: = {Abc ⊑ Antiseizure}; = {∃, (buy(, ) ∧ Antiseizure()) → ⊥,
∃, (buy(, ) ∧ contain(, phenytoin)) → ⊥}; = {buy(john, m), Abc(m), buy(alice, m), contain(m, phenytoin)}.
In words, the TBox states that Abc is an anti-seizure medication, while the policy conceals the presence of patients sufering from epilepsy.
Let us start by considering the empty sequence of BUCQs. By definition, we have that StCens(⟨ℰ , ⟨⟩⟩) coincides with the set of optimal censors for ℰ : • 1 = {buy(john, m), buy(alice, m)}; • 2 = {buy(john, m), contain(m, phenytoin)}; • 3 = {Abc(m), Antiseizure(m), buy(alice, m)}; • 4 = {Abc(m), Antiseizure(m), contain(m, phenytoin)}.
Let 1 = buy(john, m) be the first query. The censors 1 and 2 agree with answering true to this query. All the censors that disagree with such an answer are then removed, obtaining StCens(⟨ℰ , ⟨1⟩⟩) = StCens(⟨ℰ , ⟨⟩⟩) ∩ OptCens(ℰ , 1) = {1, 2}. Then, let 2 = Abc(m) be a new query in the sequence. Since neither ∪ 1 nor ∪ 2 entail 2, then StCens(⟨ℰ , ⟨1, 2⟩⟩) = StCens(⟨ℰ , ⟨1⟩⟩). Now, consider adding 3 = ∃buy(, m) to the sequence. Since ∪ 1 |= 3 while ∪ 2 ̸|= 3, we have StCens() = {1}, where = ⟨ℰ , ⟩ with = ⟨1, 2, 3⟩. Clearly, |= 1 and |= 3, but ̸|= 2.
Note that the stream of queries is processed greedily, answering the truth as long as some of the censors in StCens() allow to do it. In fact, we will show that dynCQE satisfies the maximally cooperative property, which implies and strengthens the longest honeymoon approach. Definition 4 (Cooperativity). Let ℰ = ⟨ , , ⟩ be a CQE instance, = ⟨1, . . . , ⟩ (with ≥ 0) a sequence of BUCQs, and and ′ two censors for ℰ . We say that is more cooperative than ′ with respect to if there exists a non-negative integer < such that • ∪ |= ⇐⇒ ∪ ′ |= for every 1 ≤ ≤ , and • ∪ |= +1 and ∪ ̸|
′ = +1.
We also say that is maximally cooperative with respect to if there does not exist any censor ′′ for ℰ that is more cooperative than .
We are now ready to prove that, for each state = ⟨ℰ , ⟩ of a CQE instance, the set StCens() coincides with the set of all censors that are maximally cooperative with respect to . Theorem 1. Let ℰ = ⟨ , , ⟩ be a CQE instance, and = ⟨1, . . . , ⟩ be a sequence of BUCQs. A censor for ℰ is maximally cooperative with respect to if ∈ StCens(⟨ℰ , ⟩).
The next technical results focus on DL-Liteℛ CQE specifications and instances, i.e., when
TBox and ABox are expressed in DL-Liteℛ [
We first show that the behavior of dynCQE can not be simulated by static CQE, for which
algorithms are already known [
Theorem 2. There exists a DL-Liteℛ CQE specification ⟨ , ⟩ and a BUCQ such that there exists no DL-Liteℛ CQE specification ⟨ ′, ′⟩ such that, for every ABox , OptCens(⟨ ′, ′, ⟩) = StCens(), where = ⟨⟨ , , ⟩, ⟨⟩⟩.
On the other hand, we show that dynCQE query processing is first-order rewritable by
providing a tailored query rewriting algorithm. This implies that the associated decision
problem is in AC0 in data complexity [
The present work can be extended in several interesting directions. First, while the presented results indicate the possibility of a query rewriting approach to dynamic CQE, more work is still needed to define a practical query answering technique. Moreover, we are currently working on extending our dynamic CQE approach also to non-Boolean UCQs.
Acknowledgments This work was partially supported by: projects FAIR (PE0000013) and SERICS (PE00000014) under the MUR National Recovery and Resilience Plan funded by the European Union - NextGenerationEU; Glaciation project funded from the European Union’s HE research and innovation programme (grant agreement No 101070141); ANTHEM project funded by the National Plan for NRRP Complementary Investments (CUP: B53C22006700001).