We make a first step towards adapting the approach of Cuenca Grau and Kostylev for privacy-preserving publishing of linked data to Description Logic ontologies. We consider the case where both the knowledge about individuals and the privacy policies are expressed using EL concepts. We introduce the notions of compliance of a concept with a policy and of safety of a concept for a policy, and show how optimal compliant (safe) generalizations of a given EL concept can be computed.
When publishing information about individuals, one needs to ensure that
certain privacy constraints are fulfilled. These constraints are encoded as privacy
policies, and before publishing the information one needs to check whether the
information is compliant with these policies [
In [
In the present paper, we make a first step towards handling ontologies in
this context, but consider a quite restricted setting, where information about an
individual is given by a concept of the inexpressive Description Logic (DL) E L.
Basically, this is the setting where the ontology consists of an ABox containing
only concept assertions of the form C(a) for possibly complex concepts C, but
no role assertion. In [
D = Patient u 9seen_by :(Doctor u 9works_in:Oncology ); which says that one should not be able to find out who are the patients that are seen by a doctor that works for the oncology department. The concept
C = Patient u Male u 9seen_by :(Doctor u Female u 9works_in:Oncology ) is not compliant with the policy D since C v D. The concept
C0 = Male u 9seen_by :(Doctor u Female u 9works_in:Oncology ) is a compliant generalization of C, i.e., C v C0 and C0 6v D. However, it is not safe since C0 u Patient v D, i.e., if the attacker already knows that a is a patient then together with C0(a) the hidden information D is revealed. In contrast,
C00 = Male u 9seen_by :(Doctor u Female u 9works_in:>); is a safe generalization of C, though it is less obvious to see this. This concept is, however, not optimal since more information than necessary is removed. In fact, the concept
C000 = Male u 9seen_by :(Doctor u Female u 9works_in:>)
9seen_by :(Female u 9works_in:Oncology ) is a safe generalization of C that is more specific than C00, i.e. C v C000 @ C00.
In this paper, we will show how to compute optimal compliant and optimal safe generalizations of E L concepts C with E L policies, but instead of only one policy concept we allow for a finite set of E L concepts as policy, where a concept C0 is compliant with the policy fD1; : : : ; Dpg iff it is compliant with each element of this set, i.e., C 6v Di holds for all i = 1; : : : ; p. But first, we need to introduce the DL E L and the notions of compliance, safety, etc. in a more formal way. 1 Since EL concepts are closed under conjunction, we can assume that the ABox contains only one assertion for a.
A wide range of DLs of different expressive power haven been investigated in
the literature [
The semantics of E L is defined through interpretations I = ( I ; I ), where I is a non-empty set, called the domain, and I is the interpretation function, which maps every A 2 NC to a set AI I and every r 2 NR to a binary relation rI I I . This function I is extended to arbitrary E L concepts by setting >I := I , (C u D)I := CI \ DI , and (9r:C)I := f 2 I j 9 2 CI :( ; ) 2 rI g.
The E L concept C is subsumed by the E L concept D (written C v D) if
CI DI holds for all interpretations I. Strict subsumption (written C @ D)
holds if C v D and D 6v C, and we say that C is equivalent to D (written
C D) if C v D and D v C. Subsumption between E L concepts can be decided
in polynomial time [
Proposition 1. Let
C = A1 u : : : u Ak u 9r1:C1 u : : : u 9rm:Cm; and
D = B1 u : : : u B` u 9s1:D1 u : : : u 9sn:Dn; where A1; : : : ; Ak; B1; : : : ; B` 2 NC and r1; : : : ; rm; s1; : : : ; sn 2 NR. Then we have C v D iff – fB1; : : : ; B`g fA1; : : : ; Akg, and – for all i 2 f1; : : : ; ng there is j 2 f1; : : : ; mg such that si = rj and Cj v Di.
We are now ready to define the important notions regarding privacy-preserving publishing of ontological information that will be investigated in this paper. As mentioned in the introduction, policies are finite sets of E L concepts. We assume in the following, that the concepts occurring in the policy are not equivalent to top since otherwise there would not be compliant concepts.
Definition 1. A policy is a finite set P = fD1; : : : ; Dpg of E L concepts such that > 6 Di for i = 1; : : : ; p. Given an E L concept C and a policy P = fD1; : : : ; Dpg, the E L concept C0 is – compliant with P if C0 6v Di holds for all i = 1; : : : ; p; – safe for P if C0 u C00 is compliant with P for all E L concepts C00 that are compliant with P; – a P-compliant generalization of C if C v C0 and C0 is compliant with P; – an optimal P-compliant generalization of C if it is a P-compliant generalization of C and there is no P-compliant generalization C00 of C such that C00 @ C0; – a P-safe generalization of C if C v C0 and C0 is safe for P; – an optimal P-safe generalization of C if it is a P-safe generalization of C and there is no P-safe generalization C00 of C such that C00 @ C0. It is easy to see that safety implies compliance since the top concept is always compliant: if C0 is safe for P, then > u C0 C0 is compliant. 3
In this section, we characterize the concepts that are compliant with a given policy P, and use this to develop an algorithm that computes all optimal Pcompliant generalizations of a given E L concept C.
But first, we need to introduce some more notations. We call an E L concept an atom if it is a concept name or an existential restriction. Given an E L concept C, we denote the set of atoms occurring in its top-level conjunction with con(C). For example, if C = A u 9r:(B u 9s:A), then con(C) = fA; 9r:(B u 9s:A)g. As a special case of Proposition 1, subsumption between atoms can be characterized as follows. If E; F are atoms, then E v F iff – E = F 2 NC or – E; F are existential restrictions of the form E = 9r:E0; F = 9r:F 0 such that
E0 v F 0.
Definition 2. Let S; T be sets of atoms. Then we say that S covers T if for every F 2 T there is E 2 S such that E v F .
With this notation, Proposition 1 can be reformulated as follows: C v D iff con(C) covers con(D). The following (polynomial-time decidable) characterization of compliance is thus an immediate consequence of Proposition 1. Proposition 2. The E L concept C0 is compliant with the policy P = fD1; : : : ; Dpg iff con(C0) does not cover con(Di) for any i = 1; : : : ; p, i.e., for every i = 1; : : : ; p, at least one of the following two properties holds: – there is a concept name A 2 con(Di) such that A 62 con(C0); or – there is an existential restriction 9r:D 2 con(Di) such that C 6v D for all existential restrictions of the form 9r:C 2 con(C0).
Now assume that we are given an E L concept C and a policy P = fD1; : : : ; Dpg, and we want to construct a P-compliant generalization C0 of C. For C0 to satisfy the condition of Proposition 2, there needs to exist for every i = 1; : : : ; p an element of con(Di) that is not covered by any element of con(C0). In case con(C) contains elements covering such an atom, we need to remove or generalize them appropriately.
Definition 3. We say that H con(D1) [ : : : [ con(Dp) is a hitting set of con(D1); : : : ; con(Dp) if H \ con(Di) 6= ; for every i = 1; : : : ; p. This hitting set is minimal if there is no other hitting set strictly contained in it.
Basically, the idea is now to choose a hitting set H of con(D1); : : : ; con(Dp) and use H to guide the construction of a compliant generalization of C. In order to make this generalization as specific as possible, we use minimal hitting sets. In case the policy contains concepts Di with which C is already compliant (i.e., C 6v Di holds), nothing needs to be done w.r.t. these concepts. This is why, in the following definition, con(Di) does not take part in the construction of the hitting set if C 6v Di.
Definition 4. Let C be an E L-concept and P = fD1; : : : ; Dpg a policy. The set SCG(C; P) of specific compliant generalizations of C w.r.t. P consists of the concepts that can be constructed from C as follows: – If C is compliant with P, then SCG(C; P) = fCg. – Otherwise, choose a minimal hitting set H of con(Di1 ); : : : ; con(Diq ) where i1; : : : ; iq are exactly the indices for which C v Di. Note that q 1 since we are in the case where C is not compliant with P. In addition, according to our definition of a policy, none of the concepts Di is equivalent to >, and thus the sets con(Dij ) are non-empty. Consequently, at least one minimal hitting set exists. Each minimal hitting set yields a concept in SCG(C; P) by removing or modifying atoms in the top-level conjunction of C in the following way:
For every concept name A 2 con(C), remove A from the top-level conjunction of C if A 2 H; For every existential restriction 9ri:Ci 2 con(C), consider the set
Pi := fG j there is 9ri:G 2 H such that Ci v Gg: If Pi = ; then leave 9ri:Ci as it is.
If > 2 Pi, then remove 9ri:Ci.
Otherwise, replace 9ri:Ci with dF 2SCG(Ci;Pi) 9ri:F:
We will show below that every element of SCG(C; P) is a compliant generalization of C, and that all optimal compliant generalizations of C belong to SCG(C; P). However, SCG(C; P) may also contain compliant generalizations of C that are not optimal, as illustrated by the following example. Example 1. Let C = 9r:(A1 u A2 u A3 u A4) and P = fD1; D2g, where
D1 = 9r:A1 u 9r:(A2 u A3) and D2 = 9r:A2 u 9r:A4: We have C v D1 and C v D2, and thus C is not compliant with P. Consequently, the elements of SCG(C; P) are obtained by considering the minimal hitting sets of f9r:A1; 9r:(A2 u A3)g and f9r:A2; 9r:A4g.
If we take the minimal hitting set H = f9r:(A2 u A3); 9r:A2g and consider the only existential restriction in con(C), the corresponding set Pi consists of A2 uA3 and A2. It is easy to see that SCG(A1 uA2 uA3 uA4; Pi) = fA1 uA3 uA4g since the only minimal hitting set of fA1; A2g and fA2g is fA2g. Thus, we obtain C0 := 9r:(A1 u A3 u A4) as an element of SCG(C; P).
However, if we take the minimal hitting set H0 = f9r:A1; 9r:A2g instead, then the set Pi0 corresponding to the only existential restriction in con(C) is fA1; A2g. Consequently, in this case SCG(A1 u A2 u A3 u A4; Pi0) = fA3 u A4g since the only minimal hitting set of fA1g and fA2g is fA1; A2g. This yields C00 := 9r:(A3 u A4) as another element of SCG(C; P). Since C0 @ C00, the element C00 cannot be optimal.
Next, we show that the elements of SCG(C; P) are compliant generalizations of C.
Proposition 3. Let C be an EL-concept and P = fD1; : : : ; Dpg a policy. If C0 2 SCG(C; P), then C0 is a P-compliant generalization of C.
Proof. In case C is already compliant with P, then C = C0 and we are done. Thus, assume that C is not compliant with P. We show that C0 is a compliant generalization of C by induction on the role depth of C.
First, we show that C0 is a generalization of C, i.e., C v C0. This is an easy consequence of the fact that, when constructing C0 from C, atoms from the top-level conjunction of C are left unchanged, are removed, or are replaced by a conjunction of more general atoms. The only non-trivial case is where we replace an existential restriction 9ri:Ci with the conjunction dF 2SCG(Ci;Pi) 9ri:F . By induction, we know that Ci v F for all F 2 SCG(Ci; Pi), and thus 9ri:Ci v d
F 2SCG(Ci;Pi) 9ri:F .
Second, we show that C0 is compliant with P, i.e., C0 6v Di holds for i = 1; : : : ; p. For the indices i with C 6v Di, we clearly also have C0 6v Di since C v C0. Now, consider one of the remaining indices ij 2 fi1; : : : ; iqg, where i1; : : : ; iq are exactly the indices for which C v Di. The concept C0 was constructed by taking some minimal hitting set H of con(Di1 ); : : : ; con(Diq ). If the element in H hitting con(Dij ) is a concept name, then this concept name does not occur in con(C0), and thus C0 6v Dij . Thus, assume that it is an existential restriction 9ri:G. But then each existential restriction 9ri:Ci in con(C) with Ci v G is either removed or replaced by a conjunction of existential restrictions 9ri:F such that (by induction) F 6v G. In addition, other existential restrictions are either removed or generalized. This clearly implies C0 6v Dij since 9ri:G in con(Dij ) is not covered by any element of con(C0). tu
The next lemma states that every compliant generalization of C subsumes some element of SCG(C; P).
Lemma 1. Let C be an EL-concept and P = fD1; : : : ; Dpg a policy. If C00 is a P-compliant generalization of C, then there is C0 2 SCG(C; P) such that C0 v C00.
Proof. If C is compliant with P, then we have C 2 SCG(C; P) and C v C00 since C00 is a generalization of C. Thus, assume that C is not compliant with P, and let i1; : : : ; iq be exactly the indices for which C v Di.
Now, let ij be such an index. We have C v C00 6v Dij and C v Dij . Since C00 6v Dij , there is an element Ej 2 con(Dij ) that is not covered by any element of con(C00). Obviously, H00 := fE1; : : : ; Eqg is a hitting set of con(Di1 ); : : : ; con(Diq ). Thus, there is a minimal hitting set H of con(Di1 ); : : : ; con(Diq ) such that H H00. Let C0 be the element of SCG(C; P) that was constructed using this hitting set H. We claim that C0 v C00. For this, it is sufficient to show that con(C0) covers con(C00).
First, consider a concept name A 2 con(C00). Since C v C00, we also have A 2 con(C). If A 62 H00, then A 62 H, and thus A is not removed in the construction of C0. Consequently, A 2 con(C0) covers A 2 con(C00). If A 2 H00, then A is not covered by any element of con(C00) according to our definition of H00, which contradicts our assumption that A 2 con(C00).
Second, consider an existential restriction 9ri:E 2 con(C00). Since C v C00, there is an existential restriction 9ri:Ci in con(C) such that Ci v E. If this restriction is not removed or generalized when constructing C0, then we are done since this restriction then belongs to con(C0) and covers 9ri:E. Otherwise, Pi = fG j there is 9ri:G 2 H such that Ci v Gg is non-empty.
If > 2 Pi, then 9ri:> 2 H H00. However, then 9ri:E 2 con(C00) covers an element of H00, which is a contradiction.
Consequently, > 62 Pi, and thus 9ri:Ci is replaced with dF 2SCG(Ci;Pi) 9ri:F when constructing C0 from C. According to our definition of H00 and the fact that H H00, none of the existential restrictions 9ri:G considered in the definition of Pi is covered by 9ri:E 2 con(C00). This implies that E is a Pi-compliant generalization of Ci. By induction (on the role depth) we can thus assume that there is an F 2 SCG(Ci; Pi) such that F v E. This shows that 9ri:E 2 con(C00) is covered by 9ri:F 2 con(C0). tu
As an easy consequence of this lemma, we obtain that all optimal compliant generalizations of C must belong to SCG(C; P).
Proposition 4. Let C be an EL-concept and P = fD1; : : : ; Dpg a policy. If C00 is an optimal P-compliant generalization of C, then C00 2 SCG(C; P) (up to equivalence of concepts).
Proof. Let C00 be an optimal P-compliant generalization of C. By Lemma 1, there is an element C0 2 SCG(C; P) such that C0 v C00. In addition, by Proposition 3, C0 is a P-compliant generalization of C. Thus, optimality of C00 implies C00 C0. tu
We are now ready to formulate and prove the main result of this section. Theorem 1. Let C be an EL-concept and P = fD1; : : : ; Dpg a policy. Then the set of all optimal P-compliant generalizations of C can be computed in time exponential in the size of C and D1; : : : ; Dp.
Proof. It is sufficient to show that the set SCG(C; P) can be computed in exponential time. In fact, given SCG(C; P), we can compute the set of all optimal P-compliant generalizations of C by removing elements that are not minimal w.r.t. subsumption, which requires at most exponentially many subsumption tests. Each subsumption test takes at most exponential time since subsumption in E L is in P , and the elements of SCG(C; P) have at most exponential size, as shown below.
We show by induction on the role depth that SCG(C; P) consists of at most exponentially many elements of at most exponential size. The at most exponential cardinality of SCG(C; P) is an immediate consequence of the fact that there are at most exponentially many hitting sets of con(Di1 ); : : : ; con(Diq ), and each yields exactly one element of SCG(C; P) (see Definition 4). Regarding the size of these elements, note that we may assume by induction that an existential restriction may be replaced by a conjunction of at most exponentially many existential restrictions, where each is of at most exponential size. The overall size of the concept description obtained this way is thus also of at most exponential size. Given this, it is easy to see that the computation of these elements also takes at most exponential time. tu
The following example shows that the exponential upper bounds can indeed by reached.
Example 2. Let C = P1 u Q1 u : : : u Pn u Qn and P = fPi u Qi j 1 i ng. Then SCG(C; P) contains 2n elements since the sets fP1; Q1g; : : : ; fPn; Qng obviously have exponentially many hitting sets. To be more precise,
SCG(C; P) = fX1 u : : : u Xn j Xi 2 fPi; Qig for i = 1; : : : ; ng: This example can easily be modified to enforce an element of exponential size. Consider Cb = 9r:C and Pb = f9r:(Pi u Qi) j 1 i ng. Then SCG(Cb; Pb) = fdF 2SCG(C;P) 9r:F g: We leave it to the reader to further modify the example in order to obtain exponentially many elements of exponential size. 4
Before we can characterize safety, we need to remove redundant elements from P. We say that Di 2 P is redundant if there is a different element Dj 2 P such that Di v Dj . The following lemma is easy to prove.
Lemma 2. Let P be a policy and assume that Di 2 P is redundant. Then the following holds for all E L concepts C; C0: – C0 is compliant with P iff C0 is compliant with P n fDig; – C is safe for P iff C is safe for P n fDig.
This lemma shows that we can assume without loss of generality that our policies do not contain redundant concepts. However, elements of Di of P may also contain redundant atoms. In fact, if E; F are different atoms in con(Di) such that E v F , then the concept obtained from Di by removing F from its top-level conjunction is equivalent to Di. By iteratively removing such redundant atoms from the top-level conjunction of Di we obtain (in polynomial time) a concept Di0 equivalent to Di such that the elements of con(Di0) are incomparable w.r.t. subsumption. We call a policy redundancy-free if it does not contain redundant elements and every element is normalized in this sense.
Proposition 5. Let P = fD1; : : : ; Dpg be a redundancy-free policy. The EL concept C0 is safe for P iff there is no pair of atoms (E; F ) such that E 2 con(C0), F 2 con(D1) [ : : : [ con(Dp), and E v F .
Proof. First, assume that C0 is not safe for P, i.e., there is an EL concept C00 that is compliant with P, but for which C0 u C00 is not compliant with P. The latter implies that there is Di 2 P such that C0 u C00 v Di, which is equivalent to saying that con(C0) [ con(C00) covers con(Di). On the other hand, we know that con(C00) does not cover con(Di) since C00 is compliant with P. Thus, there is an element F 2 con(Di) that is covered by an element E of con(C0). This yields (E; F ) such that E 2 con(C0), F 2 con(D1) [ : : : [ con(Dp), and E v F .
Conversely, assume that there is a pair of atoms (E; F ) such that E 2 con(C0), F 2 con(Di), and E v F . Let C00 be the concept obtained from Di by removing F from the top-level conjunction of Di. Then we clearly have Di v C00. In addition, since Di is normalized, we also have C00 6v Di. Consider Dj 2 P different from Di, and assume that C00 v Dj. But then Di v C00 v Dj contradicts our assumption that P does not contain redundant elements. Thus, we have shown that C00 is compliant with P. In addition, con(C0) [ con(C00) covers con(Di). In fact, the elements of con(Di) n fF g belong to con(C00), and thus cover themselves. In addition, F is covered by E 2 con(C0). Thus C0 u C00 v Di, which shows that C0 is not safe for P. tu
Clearly, the necessary and sufficient condition for safety stated in this proposition can be decided in polynomial time. If needed, the policy can first be made redundancy-free, which can also be done in polynomial time.
We now consider the problem of computing optimal P-safe generalizations of a given EL concept C. First note that, up to equivalence, there can be only one optimal P-safe generalization of C. This is an immediate consequence of the fact that the conjunction of safe concepts is again safe, which in turn is an easy consequence of Proposition 5.
Lemma 3. Let C10; C20 be two EL concepts that are P-safe generalizations of C, where P is redundancy-free. Then C10 u C20 is also a P-safe generalization of C.
Thus there cannot be non-equivalent optimal P-safe generalizations of a given EL concept C since their conjunction would then be more specific, contradicting their optimality. This property is independent of whether the policy is redundancy-free or not since turning a policy into one that is redundancy-free preserves the set of concepts that are compliant with (safe for) the policy. Proposition 6. If C10; C20 are optimal P-safe generalizations of the EL concept C, then C10 C20.
The following theorem shows how an optimal safe generalization of C can be constructed.
Theorem 2. Let C be an EL concept and P = fD1; : : : ; Dpg a redundancy-free policy. We construct the concept C0 from C by removing or modifying atoms in the top-level conjunction of C in the following way: – For every concept name A 2 con(C), remove A from the top-level conjunction of C if A 2 con(D1) [ : : : [ con(Dp); – For every existential restriction 9ri:Ci 2 con(C), consider the set of concepts Pi := fG j there is 9ri:G 2 con(D1) [ : : : [ con(Dp) such that Ci v Gg: If Pi = ; then leave 9ri:Ci as it is.
If > 2 Pi, then remove 9ri:Ci.
Otherwise, replace 9ri:Ci with dF 2OCG(Ci;Pi) 9ri:F; where OCG(Ci; Pi) is the set of all optimal Pi-compliant generalizations of Ci.
Proof. Obviously C v C0 since, when constructing C0 from C, atoms from the top-level conjunction of C are left unchanged, are removed, or are replaced by a conjunction of more general atoms.
To show that C0 is safe for P, we must show that the condition of Proposition 5 holds. Thus assume that it is violated, i.e., there is a pair of atoms (E; F ) such that E 2 con(C0), F 2 con(D1) [ : : : [ con(Dp), and E v F . – First, we consider the case where E = A is a concept name. Then E v F implies that F = A, and thus A is a concept name occurring in con(D1) [ : : : [ con(Dp). However, all such concept names have been removed from the top-level conjunction of C when constructing C0. This contradicts our assumption that E = A belongs to con(C0). – Second, assume that E is an existential restriction E = 9ri:E0. Then F is of the form F = 9ri:G0 and E0 v G0. In addition, there is an existential restriction 9ri:Ci 2 con(C) from which E = 9ri:E0 was derived. By construction, Ci v E0. In the construction of C0, we consider the set Pi := fG j there is 9ri:G 2 con(D1) [ : : : [ con(Dp) such that Ci v Gg: Since Ci v E0 v G0, this set is non-empty, and since 9ri:E0 is derived from 9ri:Ci, it does not contain >. Consequently, we have E0 2 OCG(Ci; Pi). However, G0 2 Pi then implies that E0 6v G0, which yields the desired contradiction.
It remains to show that C0 is optimal. Thus assume that C00 is a P-safe generalization of C. It is sufficient to show that C0 v C00, i.e., that con(C0) covers con(C00).
– Assume that A 2 con(C00) is a concept name. Then C v C00 implies that A 2 con(C). In addition, since C00 is safe for P, Proposition 5 implies that A 62 con(D1) [ : : : [ con(Dp). Thus, A is not removed in the construction of C0, which yields A 2 con(C0). – Second, consider an existential restriction 9ri:E 2 con(C00). Since C v C00, there is an existential restriction 9ri:Ci in con(C) such that Ci v E. If this restriction is not removed or generalized when constructing C0, then we are done since this restriction then belongs to con(C0) and covers 9ri:E. Otherwise, Pi = fG j there is 9ri:G 2 con(D1) [ : : : [ con(Dp) such that Ci v Gg is non-empty.
If > 2 Pi, then 9ri:> 2 con(D1) [ : : : [ con(Dp). However, then 9ri:E 2 con(C00) covers an element of con(D1) [ : : : [ con(Dp), which is a contradiction to our assumption that C00 is safe for P.
Consequently, > 62 Pi, and thus 9ri:Ci is replaced with dF 2OCG(Ci;Pi) 9ri:F when constructing C0 from C. Since C00 is safe for P, none of the existential restrictions 9ri:G considered in the definition of Pi is covered by 9ri:E 2 con(C00). This implies that E is a Pi-compliant generalization of Ci. Consequently, there is an F 2 OCG(Ci; Pi) such that F v E. This shows that 9ri:E 2 con(C00) is covered by 9ri:F 2 con(C0). tu Since, by Theorem 1, OCG(Ci; Pi) can be computed in exponential time, the construction described in Theorem 2 can also be performed in exponential time. Corollary 2. Let C be an EL concept and P = fD1; : : : ; Dpg a redundancyfree policy. Then an optimal P-safe generalization of C can be computed in exponential time.
Example 2 can easily be modified to provide an example that shows that this exponential bound can actually not be improved since there are cases where the safe generalization is of exponential size. 5
We have introduced the notions of compliance with and safety for a policy in the simple setting where both the knowledge about individuals and the policy are given by EL concepts. In this setting, we were able to characterize compliant (safe) generalization of a given concept w.r.t. a policy, and have used these characterizations to obtain algorithms for computing these generalizations. These algorithms need exponential time, which is optimal since the generalizations may be of exponential size.
In the future, we intend to extend this work in two directions. On the one hand, we will consider EL concepts w.r.t. a background ontology. On the other hand, we will consider a setting where the ABox contains not just concept assertions, but also role assertions. In the latter case, one can use not just generalization of concepts, but also renaming of individuals as operations for achieving compliance (safety). Finally, of course, these two extensions should be combined.