Recent research has shown that labeling ontologies can be useful for restricting the access to some of the axioms and their implicit consequences. However, the labeling of the axioms is an error-prone and highly sensible task. In previous work we have shown how to correct the access restrictions if the security administrator knows the precise access level that a consequence must receive, and axioms are relabeled to that same access level. In this paper, we look at a more general situation in which access rights can be granted or denied to some speci c users, without having to fully specify the precise access level. We also allow a more exible labeling function, where the new access level of the relabeled axioms may di er from the level of the restriction. We provide black-box algorithms for computing suggestions of axioms to be relabeled.
Description Logics (DL) [
In some application domains it is desirable to restrict users to access only
portions of the ontology. For instance, in a security scenario [
However, the task of labeling axioms according to their access level is errorprone and highly sensitive to noise. Indeed, a set of seemingly innocuous axioms ? This work was developed while the author worked for SAP Research Dresden. may allow a user to derive some unwanted consequence. Dually, a too restrictive access level may hide a consequence from relevant users. This problem becomes more pronounced if neither the security administrator nor the knowledge engineer is an expert in logic. We thus want to develop a system that can automatically suggest changes in the labeling function that correct the access to a given consequence.
In previous work [
We develop black-box algorithms for nding the minimal sets of axioms that
need to be relabeled to the target label in order for the access of the consequence
to satisfy the restriction imposed. Additionally, we show that our methods can be
improved if one is only interested in nding one such set of minimal cardinality.
All our methods are based on results and ideas from axiom-pinpointing [
To keep our presentation and results as general as possible, we impose only minimal restrictions to our ontology language. We just assume that an ontology is a nite set, whose elements are called axioms. An ontology language speci es which sets of axioms are admitted as ontologies, with the only restriction that every subset of an ontology is itself an ontology. If O0 O and O is an ontology, then O0 is called a sub-ontology of O. A monotone consequence relation j= is a binary relation between ontologies O and consequences c such that if O j= c, then for every ontology O0 O it holds that O0 j= c. If O j= c, we say that c follows from O or that O entails c. Consider, for instance, a description logic L. Then, an ontology is a nite set of general concept inclusion axioms (GCIs) of the form C v D, with C; D L-concept descriptions and assertion axioms of the form C(b), with C an L-concept description and b an individual name. An example of a consequence is the subsumption relation A v B between concept names A; B.
If O j= c, we may be interested in nding the axioms responsible for this fact. A sub-ontology S O is called a MinA for O,c if S j= c and for every S0 S; S0 6j= c. The dual notion of a MinA is that of a diagnosis. A diagnosis for O,c is a sub-ontology S O such that O n S 6j= c and O n S0 j= c for all S0 S.
For a lattice (L; ) and a set K L, we denote as L`2K ` and N`2K ` the join (least upper bound) and meet (greatest lower bound) of K, respectively. We consider that ontologies are labeled with elements of the lattice. More formally, for an ontology O there is a labeling function lab that assigns a label lab(a) 2 L to every element a of O. We will often use the notation Llab := flab(a) j a 2 Og.
For a user labeled with the access level ` 2 L, we denote as O ` the subontology O ` := fa 2 O j lab(a) `g visible for him. The sub-ontologies O `; O=`; O6=`; O6 `, and O6 ` are de ned analogously. Conversely, for a subontology S O, we de ne
S := Na2S lab(a) and
S := La2S lab(a).
An element ` 2 L is join prime relative to Llab if for every K1; : : : ; Kn Llab, it holds that ` Lin=1 Ki implies that there is i; 1 i n such that ` Ki . For instance, in the lattice from Figure 1, `1 and `4 are the only elements that are not join prime relative to Llab = f`1; : : : ; `5g, since `1 `2 `4 but neither `1 `2 nor `1 `4 and similarly `4 `5 `3 but neither `4 `5 nor `4 `3. Join prime elements relative to Llab are called user labels. The set of all user labels is denoted as U . When dealing with labeled ontologies, the reasoning problem of interest consists on the computation of a boundary for a consequence c. Intuitively, the boundary divides the user labels ` of U according to whether O ` entails c or not.
Given a user label `u, we will say that the user sees a consequence c if `u
for some boundary . The following lemma relating MinAs and boundaries was
shown in [
i=1 Si is a boundary for O,c.
A dual result relating the boundary with the set of diagnoses, also holds.
i=1 Si is a boundary for O,c.
Example 4. Let (Ld; d) be the lattice shown in Figure 1, and O a labeled ontology from a marketplace in the Semantic Web with the following axioms a1 : EUecoService u HighperformanceService(ecoCalculatorV1 ) a2 : HighperformanceService
v ServiceWithLowCustomerNr u LowPro tService a3 : ServiceWithLowCustomerNr v ServiceWithComingPriceIncrease a4 : EUecoService v ServiceWithLowCustomerNr u LowPro tService a5 : LowPro tService v ServiceWithComingPriceIncrease where the function lab assigns to each axiom ai the label `i as shown in Figure 1. This ontology entails ServiceWithComingPriceIncrease(ecoCalculatorV1 ). The MinAs for O,c are fa1; a2; a3g; fa1; a2; a5g; fa1; a3; a4g; fa1; a4; a5g; and its diagnoses are fa1g; fa2; a4g; fa3; a5g. Using Lemma 3, we can compute the boundary as fa1g fa2;a4g fa3;a5g = `1 `1 `4 = `4: The join prime elements relative to Llab, which de ne valid user labels, are `0; `2; `3; `5. These labels represent the user roles as illustrated. Thus, the consequence c is only visible for the user roles `0; `5 and `3, i.e. for customer service employees, customers, and development engineers. 3
An e cient implementation of a black-box algorithm for computing the
boundary of DL consequences already exists [
We have previously shown [
De nition 5 (Boundary Constraint, Change Set). A boundary constraint is a tuple = (c; / `g; `t), where c is a consequence, / `g, with /2 f ; ; 6 ; 6 g, `g 2 L is a condition and `t is the target label with `t / `g.
the modi ed labeling function labS;` as labS;`(a) = (` if a 2 S; lab(a) otherwise.
For the rest of this paper, we assume, w.l.o.g. that the boundary for O; c; lab does not satisfy the condition / `g since otherwise, the empty set is already a CS and nothing needs to be changed in the labeling function.
Notice that, since `t / `g, the whole ontology O is always a change set.
However, using the whole ontology as a change set would set `t as the boundary
of every consequence of O. In general, we want to make the least possible changes
when correcting the boundary of a given consequence. For that reason, we will
focus on nding all those change sets that are minimal w.r.t. set inclusion. These
sets are useful if the knowledge engineer wants to obtain several suggestions
of correction, and then choose the adequate one by some external criterion.
However, due to the huge number (possibly exponentially many [
We divide this section in two parts. First we look at the case where the boundary restriction is of the form or . We show that previously known techniques can be used also in this setting. We then look at the negative restrictions, which require new methods to be developed. 3.1
Positive Conditions
We now focus on the case where the condition of the boundary constraint is of
the form `g. Due to the duality of MinAs and diagnoses, the case for `g can
be treated in an analogous way (see e.g. [
Let = (c; `g; `t) be a boundary constraint and `t `g. Recall (Lemma 2) that the boundary can be computed as the supremum of all Si , where Si is a MinA for O; c. Thus, if we relabel all the axioms in a MinA S to `t, then the boundary for O; c; labS;`t is `t `g; that is, every MinA is a change set. Yet, this change set may not be minimal. In fact, we only need that the in mum of the labels of all the axioms in this MinA is `g. This can be achieved by only relabeling the axioms in S that are not already `g.
Example 6. Continuing Example 4, recall that we have computed the label `4 as the boundary of the consequence c. Suppose now that we want to change this boundary to be `2, using `2 also as the relabeling target. As described above, every MinA is also a change set for this consequence. If we consider the MinA S = fa1; a2; a3g, then under the new labeling labS;`2 we obtain the new boundary fa1;a2;a3g fa1;a2;a5g fa1;a3;a4g fa1;a4;a5g = `2 `0 `3 `0 = `2: However, it is easy to see through a simple computation, that the set fa3g is also a change set, which is strictly included in the previous MinA. This set is obtained from the MinA by removing all axioms whose label is greater or equal `2, namely a1 and a2.
Intuitively, we simply consider every axiom a 2 O with lab(a) `g as xed in the sense that its label cannot be changed, as changing it will be super uous for any CS. We thus consider a generalization of MinAs, called IAS. De nition 7 (IAS). A minimal inserted axiom set (IAS) for ` is a subset I O such that O ` [ I j= c and O ` [ I0 6j= c for all I0 I.
The known algorithms for computing all MinAs [
In [
Negative Conditions We now consider the case in which the boundary constraint has a condition of the form 6 `g. As in the previous section, the case for 6 `g can be solved dually by simply interchanging MinAs and diagnoses.
Given an ontology O, a labeling function lab and a consequence c, if the boundary for O; c; lab is greater or equal to `g, then we know that for every diagnosis S for O; c it holds that S `g (see Lemma 3). Hence, if we relabel all the axioms in any diagnosis S to `t 6 `g, it follows that the boundary is then changed to a new value 6 `g; that is, S is a CS. However, just as in the previous section, this CS may not be minimal. One idea to try to nd a minimal CS is to follow the same intuition as in the previous section, and x all axioms whose labels already satisfy the condition 6 `g. Unfortunately, this idea is not correct, as shown by the following example.
Example 9. Returning to Example 4, suppose now that we want to change the boundary from `4 to some value 6 `4, using `5 as a target label. Recall that fa2; a4g and fa3; a5g are diagnoses for the consequence. If we consider the axioms having a label 6 `4 as xed, then none of these diagnoses produces a change set. In the rst one, the axiom a2 would be xed, but then, under the relabeling labfa4g;`5 we will obtain the boundary fa1g fa2;a4g fa3;a5g = `1 (`2 which does not satisfy the restriction 6 `4; hence, fa4g is not a change set.
In the case of the second diagnosis, the problem is even greater, since both axioms will be considered as xed. Thus, the approach would deduce that no axiom needs to be relabeled to obtain a boundary 6 `4, which is obviously not true.
Despite this, it is still possible to use diagnoses as a basis for computing the minimal CS. Suppose that we have a diagnosis S containing an axiom a0 such that `t lab(a0) 6 `g. Then, S0 = S n fa0g is also a CS, since
M labS0;`t (a) = `t lab(a0) 6 `g: a2S Obviously, this result holds not only for a single axiom a0 but for any subset T of S such that `t La2T lab(a) 6 `g.
Lemma 10. Let S be a diagnosis for O; c and = (c; 6 `g; `t) a boundary constraint. If T is a subset of S such that `t La2T lab(a) 6 `g, then S n T is a CS for .
Proof. For every axiom a 2 S n T , labSnT ;`t (a) = `t. Additionally, we know that La2S lab(a) `g, and hence T 6= S. Thus, under the new labeling, we have that
M labSnT ;`t (a) = `t
M lab(a) 6 `g a2S a2T Since S is a diagnosis, Lemma 3 implies that the new boundary satis es the condition, and hence S n T is a CS. tu
A simple consequence of this lemma is that, given a maximal subset T of S satisfying `t La2T lab(a) 6 `g, S n T is a minimal change set for contained in S. Algorithm 1 describes how to compute one such minimal change set from a diagnosis. This, however, might not be a \globally" minimal change set; that is, there might still exist other change sets strictly contained in it, as shown in the following example.
Example 11. Consider the lattice in Figure 1, an ontology O having four axioms fa1; a2; a3; a4g, and a consequence c such that the diagnoses for O; c are the sets fa1; a2; a3g and fa1; a4g. Assume that the labeling function lab is given by the mapping lab(a1) = `4; lab(a2) = `5; lab(a3) = lab(a4) = `2. It is easy to see that the boundary for this consequence is `1. If we apply Algorithm 1 to the diagnosis fa1; a2; a3g and the boundary constraint = (c; 6 `1; `3), where at Line 5, we rst choose a3, then ` is changed to `2 at Line 8, and hence the test ` lab(a) 6 `1 fails for axioms a1 and a2. Thus, the algorithm returns the change set fa1; a2g. However, fa1g is also a change set, since if a1 is relabeled to `3, then fa1;a4g = `2,and thus the boundary is 6 `1.
Although Algorithm 1 does not always output a globally minimal change set, one can still use it for computing all the minimal change sets for . The idea is based on the following lemma, which is a simple consequence of the de nition of diagnoses and change sets.
a set T such that (i) `t La2T lab(a) 6 `g and (ii) S [ T is a diagnosis for O; c.
For instance, in Example 11 we found the minimal change set fa1g. The set T = fa4g satis es the two conditions stated in Lemma 12.
To compute all minimal change sets, one then needs to compute all diagnoses, and from each of these diagnoses compute all the minimal change sets that are contained in it. This is possible through a nesting of two hitting set tree (HST) algorithms: the external one produces all di erent diagnoses for O; c, while the internal generates, for any given diagnosis, all the maximal subsets of axioms that can be removed to obtain a CS. Algorithm 2 shows how this internal HST algorithm works.
The idea behind all HST-like algorithms is the following. One rst computes a set of axioms T satisfying some property; in the case of Algorithm 2, the set is a minimal CS for contained in S. This set is then used to label the root of the tree. The algorithm then branches as follows. For each axiom a in T , a new branch is created and a is removed from the search space. A new set T 0 satisfying the property is then computed, and used to label the successor node. The removal of the axiom a 2 T from the search space ensures that T 6 T 0. This process is then iterated until the property is not satis ed by the search space; that is, Algorithm 1 returns the empty set. This process stops after at most exponentially many iterations, on the size of S, and the labels of the tree contain all the minimal sets of axioms satisfying the property; in our case, all minimal change sets contained in the diagnosis.
There are two common optimizations for HST algorithms, which are also used in Algorithm 2. The rst one is called early path termination. The idea behind this optimization is that if one can distinguish parts of the tree that will yield no new minimal sets of axioms, then one can stop exploring those branches. The two conditions for early path termination described in Line 1 of expand-hst test for a path where the search space is contained in a search space already explored in a Algorithm 2 HST to compute all minimal CS contained in a diagnosis previous branch. The second optimization is the reuse of sets. When expanding a tree, we only ask for a set of axioms satisfying the property that is contained in the current search space. If these conditions hold in a previously computed label, then we can reuse it, avoiding this way a possibly expensive call to Algorithm 1.
To nd all \global" minimal change sets, we use an additional HST algorithm that computes all diagnoses, and for each of these, calls Algorithm 2. This algorithm uses the same kind of optimizations. However, to improve the functionality of the reuse of solutions, the set of all change sets computed so far is kept in a global variable, accessible from every call to compute-all-CS. Thus, a change set that has been previously computed from a diagnosis S, can be reused in a call with a di erent diagnosis S0.
It is worth noticing that in some cases, a diagnosis may contain several axioms labeled with the same lattice element. Moreover, the condition for obtaining a minimal CS from Lemma 10 depends only on the labeling, and not in the axiom itself. Thus, it is sometimes possible to optimize the search for the minimal CS by considering only the labels and not the individual axioms, as described in Algorithm 3. The correctness of this algorithm is justi ed by the following lemma, whose proof is analogous to the one of Lemma 10. (early path termination) (CS reuse) Algorithm 3 Compute one minimal CS contained in a diagnosis (optimized) Procedure compute-one-CS(S; ) Input: S: diagnosis; = (c; 6 `g; `t): boundary constraint; Output: T S: minimal CS for
straint, and LS = flab(a) j a 2 Sg. If M then S n fa j lab(a) 2 Mg is a CS for . = (c; 6 `g; `t) a boundary con
As in the case for positive conditions, these algorithms can be further
optimized if one is only interested in a change set of minimal cardinality. Notice
simply that in Algorithms 1 and 3, whenever the condition in the for loop is
violated, then at least an axiom is ensured to belong to the output change set.
Thus, it is easy to adapt these algorithms to include a cardinality bound,
returning a partial CS once it has reached a given size. Since our method uses an HST
approach, the proofs of correctness of the variant of HST capable of exploiting
cardinality restrictions [
We have presented algorithms for correcting the boundary of a consequence in a more exible manner than previous approaches. Our framework allows the knowledge engineer to set bounds on what the new boundary should be, and specify a label as the target of the relabeling. This exibility is useful if, for instance, she wants to grant access to a consequence to some user, but is not willing to specify the exact set of users that should access it.
We developed algorithms that output all the minimal change sets. Additionally, we show how these algorithms can be optimized if one is only interested in an arbitrary change set of minimal cardinality.
As future work, we will rst implement and test the performance of our methods on large-scale real-world ontologies and applications. We also plan to generalize our framework to allow axioms to be relabeled to di erent elements of the lattice, according to an adequate minimality criterion.