# trustsensitive_evolution_of_dllite_knowledge_bases__76da4edb.pdf

Trust-Sensitive Evolution of DL-Lite Knowledge Bases

Dmitriy Zheleznyakov, Evgeny Kharlamov, Ian Horrocks Department of Computer Science, University of Oxford, UK {f_name.l_name}@cs.ox.ac.uk

Evolution of Knowledge Bases (KBs) consists of incorporating new information in an existing KB. Previous studies assume that the new information should be fully trusted and thus completely incorporated in the old knowledge. We suggest a setting where the new knowledge can be partially trusted and develop model-based approaches (MBAs) to KB evolution that rely on this assumption. Under MBAs the result of evolution is a set of interpretations and thus two core problems for MBAs are closure, i.e., whether evolution result can be axiomatised with a KB, and approximation, i.e., whether it can be (maximally) approximated with a KB. We show that DL-Lite is not closed under a wide range of trust-sensitive MBAs. We introduce a notion of s-approximation that improves the previously proposed approximations and show how to compute it for various trust-sensitive MBAs.

Introduction

Recent years have witnessed a strong and increasing interest in Description Logic (DL) knowledge bases (KBs) (Baader et al. 2003) as a mechanism for representing structured knowledge; in particular, DLs became the foundation for OWL 2, the standard ontology language of the Semantic Web. A DL KB K consists of a TBox T that models at the intensional level the static and structural aspects of an application domain, and an ABox A that models at the extensional level the current state of affairs or data about individuals. In many applications KBs are subject to changes, for instance, when they are constructed from evolving Web pages (Suchanek and Weikum 2013) or databases (Furche et al. 2012), or created collaboratively (Bollacker et al. 2008; Stearns et al. 2001). A typical scenario for such applications is to incorporate in a given KB K an acquired KB N that expresses new information. In the case where N interacts with K in an undesirable way, e.g., by causing the KB or relevant parts of it to become unsatisfiable, N cannot simply be added to K. Different ways to address this problem are possible, corresponding to different approaches for KB evolution.

This research has been partially supported by the EU project Optique (FP7-IP-318338), the Royal Society, the EPSRC grants ED3, DBonto, and Ma SI3. Copyright c 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Knowledge evolution in the context of DL KBs has recently attracted a lot of attention from both practical and foundational perspectives, see e.g. (Fridman Noy et al. 2004; Haase and Stojanovic 2005; Flouris et al. 2008; Konev, Walther, and Wolter 2008; Cuenca Grau et al. 2012; Wu and Lécué 2014). Model-based approaches (MBAs) are the most commonly studied. Under MBAs, the result of evolution is the set of first-order interpretations M that are models of N, minimally distant from the models of K. The latter condition corresponds to a widely accepted principle of minimal change (Eiter and Gottlob 1992). Depending on how minimality and distance are defined, one can obtain various evolution semantics and a number of them have been introduced and studied (Qi and Du 2009; Calvanese et al. 2010; Wang, Wang, and Topor 2010; Kharlamov and Zheleznyakov 2011; Liu et al. 2011; Kharlamov, Zheleznyakov, and Calvanese 2013; Zhuang et al. 2014; Qi et al. 2015; Wang et al. 2015; Zhuang et al. 2016). To the best of our knowledge, all previous studies of KB evolution assume that the new knowledge N should be fully trusted and thus completely taken on board (see Related Work section). However, this assumption does not hold in a wide range of important applications (Suchanek and Weikum 2013) where N comes from a partially trusted source, e.g., from the Web or from a source with a limited expertise. In this work we address this issue for MBAs and study how an external notion of trust could be used in order to determine how new knowledge should be integrated with existing knowledge. Following Hunter and Booth (2015), who studied trust in the context of propositional belief revision, we assume that the knowledge provider has expertise that is restricted to a particular area and thus cannot distinguish between certain states of the application domain first-order interpretations in our case. We formalise such a notion of trust as an equivalence relation on first-order interpretations and introduce four natural classes of trust. Then we use trust as an external mechanism to relativise arbitrary interpretations (not necessarily models of N) to models of N by considering equivalence classes of the latter s models. This allows us to define the result of evolution as a set of minimally distinct interpretations M selected from these equivalence classes instead of just models of N as in classical MBAs. Our trustsensitive evolution is generic in the sense that it is applicable to KBs of any DL, and is backwards-compatible with classi-

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

cal MBAs in the sense that it coincides with them whenever the model of trust assumes that the knowledge provider is an expert in everything. Since evolution under MBAs is defined as a set of interpretations M, in practice one would want to efficiently axiomatise this M as a KB or, whenever this is impossible, to efficiently closely approximate it with a KB. Thus, the two core KB evolution problems for a given DL L and MBA semantics are closure of L under the semantics, i.e., whether and how for every K and N in L, the corresponding M under the semantics can be axiomatised in L, and approximation of the semantics in L whenever L is not closed. We study the closure and approximation problems for DL-Lite a tractable DL behind the QL profile of OWL 2 under trust-sensitive MBAs for various models of trust. Firstly, we show that DL-Lite is not closed under any trust-sensitive semantics. It was known that DL-Lite is not closed under many classical MBAs (Calvanese et al. 2010; Kharlamov, Zheleznyakov, and Calvanese 2013; Qi et al. 2015) and our results in particular imply the non-closure of DL-Lite under those classical MBAs for which this problem remained open. We next turn our attention to the approximation problem for DL-Lite and an important practical setting of ABox evolution where the TBox is static and only the ABox evolves. A widely studied approach for this setting is sound approximation, where M is approximated with a KB whose set of models contains M. For classical MBAs De Giacomo et al. (2009), Kharlamov, Zheleznyakov, and Calvanese (2013), and Qi et al. (2015) proposed algorithms to compute maximal sound approximations for various semantics. Here we propose the notion of s-approximation a KB that may use special predicates and constants and show that in general it improves sound approximations by better capturing M for both classical and trust-sensitive MBAs. Moreover, we show that s-approximations are also better in preserving Boolean queries satisfied by M and we determine an important class of such queries. Finally, we develop polynomial time algorithms to compute maximal sound s-approximations for several trust-sensitive and classical evolution semantics.

Preliminaries Description Logics. We assume standard definitions of first-order logic signature, sentences, interpretations, satisfiability, and entailment. We further assume a fixed signature with disjoint countable sets of unary and binary predicates and constants, and that all interpretations are over this signature and the same countable domain Δ. Let PW (Possible Worlds) denote the class of all such interpretations. Whenever convenient we treat interpretations as sets of atoms. In DLs (Baader et al. 2003), the doman of interest is modelled by means of concepts, that are formulae with one free variable, denoting sets of objects, roles, that are formulae with two free variables, denoting binary relations between objects, and constants, denoting objects. In order to support such modelling, DLs provide a specialised variable-free syntax and operators for constructing concepts and roles from unary predicates (called atomic concepts) and binary predicates (called atomic roles). A DL KB K = (T , A) consists

of a TBox T that is a finite set of sentences (called TBox assertions) over concepts and roles, and an ABox A that is a finite set of sentences (called ABox or membership assertions) of the form C(a) and R(a, b), where C is a concept, R is a role and a, b are constants. A DL L is a recursive set of KBs closed under renaming of constants and the subset relation. All the logics of the DL-Lite family have the following constructs for complex concepts and roles (Calvanese et al. 2007): (i) B ::= A | R, (ii) C ::= B | B, and (iii) R ::= P | P , where A and P are an atomic concept and role, B and C are basic and general concepts, and R is a basic role. A DL-Litecore TBox consists of concept inclusions assertions B C. DL-Lite extends DL-Litecore by allowing in a TBox role inclusion assertions R1 R2 and functionality assertions (funct R) in a way that if R1 R2 appears in a TBox, then neither (funct R2) nor (funct R 2 ) appears in the TBox.1 This syntactic restriction ensures the tractability of the logic. ABoxes in DL-Litecore and DL-Lite consist of membership assertions of the form C(a) and P(a, b). The semantics for concepts and roles is defined in the standard way under an assumption that a I = a for each constant a. That is, AI Δ, P I Δ Δ, (P )I = {(b, a) | (a, b) P I}, ( B)I = Δ\BI, and ( R)I = {a | there exists b s.t (a, b) RI}. The semantics of assertions is also defined in the standard way: I |= D1 D2 if DI 1 DI 2 , I |= (funct R) if the relation RI is a function, I |= C(a) if a I CI, and I |= P(a, b) if (a I, b I) P I. For ξ a concept, role, (set of) assertions(s), or (set of) interpretation(s), pred(ξ) denotes the set of atomic concepts and roles in ξ. Mod(K) denotes the set of all interpretations I that are models of K, i.e., I |= ϕ for each assertion ϕ in K.

Classical Model-Based Evolution. A classical evolution setting consists of an old KB K and a new KB N. Under classical MBAs, the evolution result is the subset of Mod(N) that is minimally distant from Mod(K). We now formally introduce classical MBAs (Calvanese et al. 2010). Let I and J be interpretations. Recall that I J denotes the symmetric difference (I \ J ) (J \ I). A distance function dist between I and J can be defined in one of the following ways. Distances based on atoms are defined as (i) a set I J , denoted dista {}(I, J ), or (ii) a number |I J |, denoted dista #(I, J ). Distances based on predicates are defined as (i) a set {α | α is a predicate and αI = αJ }, denoted distp {}(I, J ), or (ii) a number |distp {}(I, J )| denoted distp #(I, J ). Distances returned by distx {}, where x {a, p} are sets and thus can be compared via set inclusion: distx {}(I1, J1) distx {}(I2, J2) if distx {}(I1, J1) distx {}(I2, J2). Distances returned by distx # are natural numbers and thus can be compared numerically.2 Let S and S be sets of interpretations and dist a distance function. The subset mindist,S(S ) of S that consists of interpretations minimally distant from S is defined as follows:

1In (Calvanese et al. 2010) this DL is referred to as DL-Lite FR. 2Note that for infinite distx {}(I, J ), we assume that: for any I and J if distx {}(I , J ) is (i) finite, then distx {}(I , J ) < distx {}(I, J ), or (ii) infinite, then distx {}(I , J ) = distx {}(I, J ).

{J S | there is I S s.t. for each I S, and for each J S it holds dist(I , J ) < dist(I, J )}. We now define selectors that choose those interpretations of S that are minimally distant from S. Definition 1. A selector, denoted S, is a function that maps each pair (S, S ) of sets of models into 2S . We consider the following selectors, where x {a, p}, and y {{}, #}: a global selector induced by distx y, denoted Gx y, is defined as mindistx y,S(S ); a local selector induced by distx y, denoted Lx y, is defined as I Smindistx y,{I}(S ).

Finally, classical evolution semantics for K and N is defined as S(Mod(K), Mod(N)). Note that, in terms of Katsuno and Mendelzon (1991), semantics based on local selectors correspond to knowledge update, and semantics based on global selectors correspond to knowledge revision.

Trust-Sensitive Model-Based Evolution In this section we introduce four models of trust and define how they can be incorporated in MBAs.

Models of Trust. Our models of trust reflect the assumption that the knowledge provider has a restricted area of expertise, and thus we do not trust facts that are outside this area. In terms of interpretations this means that if two interpretations disagree only on such facts, then the provider cannot distinguish between them. Definition 2. A model of trust is an equivalence relation on models. We consider four classes of models of trust: total trust, denoted TT, consists of one equivalence relation TT defined as I1 TT I2 iff I1 = I2; total distrust, denoted TD, consists of one equivalence relation TD defined as I1 TD I2 for each I1 and I2; assertion trust, denoted AT, consists of one equivalence relation Φ for each finite set of assertions Φ which is defined as I1 Φ I2 iff either I1 |= ϕ and I2 |= ϕ or I1 |= ϕ and I2 |= ϕ for each ϕ Φ. predicate trust, denoted PT, consists of one equivalence relation P for each finite set of predicates P which is defined as I1 P I2 iff p I1 = p I2 for each p P. Example 3. Consider a scenario about places where famous researchers Einstein (Ein) and Mendeleev (Men) live (lives In). Consider the two following models of trust: Pex PT and Φex AT, where Φex = {lives In(Ein, us), lives In(Men)} and Pex = {lives In}. In Pex we trust that the knowledge provider is an expert in places of residence in general, while in Φex we trust that they can tell whether or not Einstein lives in the USA and Mendeleev lives somewhere. Consider two interpretations I1 ex = {lives In(Ein, us)} and I2 ex = {lives In(Ein, us), lives In(Ein, ru)}. It is easy to see that I1 ex Pex I2 ex, while I1 ex Φex I2 ex.

We will use models of trust to relativise interpretations to a given one using the following extender function.

Definition 4. An extender, denoted E, is a function that maps each pair ( , I) where is a model of trust and I is an interpretation, into 2PW in the following way:

E( , I) = {J PW | J I}.

For a set of interpretations S, E( , S) =

I S E( , I).

Clearly, for each S it holds that S E( , S), while E( , S) S does not hold in general.

Example 5. E( Pex, I1 ex) and E( Φex, I1 ex) are, resp.:

{I PW | {(Ein, us)} = lives In I} and {I PW | I |= lives In(Ein, us), and I |= lives In(Men)}.

Trust-Sensitive Evolution Settings and Semantics. We distinguish between KB and ABox evolution. In the former case the whole KB changes, while in the latter case the TBox is fixed and only the ABox evolves. The following definition of evolution settings reflects this distinction. Definition 6. Let L be a DL and C a class of models of trust. An (L, C)-setting E for KB evolution is a quadruple (T , A, N, ), where (T , A) and N are satisfiable L-KBs and is a model of trust in C. An (L, C)-setting E for ABox evolution is a quadruple (T , A, N, ), where N is an L-ABox, (T , A) and (T , N) are satisfiable L-KBs, is a model of trust in C. We will refer to E as just a C-setting (resp., setting) when L is (resp., L and C are) clear or not important. Example 7. Consider Eex = (Tex, Aex, Nex, Φex), a (DL-Lite, AT)-setting for ABox evolution, where the TBox is Tex = , ABox is Aex = {lives In(Men, ru)}, and the new ABox is Nex = {lives In(Ein, us), lives In(Men, us)}.

We are now ready to show how models of trust can provide an external mechanism to guide evolution semantics. Intuitively, models of trust work like filters that are applied to the (models of the) new knowledge N before performing the evolution. Recall that the classical MBAs pick interpretations J from Mod(N) that comes from the knowledge provider. In our case, however, we know that the knowledge provider cannot distinguish between any two -equivalent interpretations, i.e., any J that is -equivalent to J is as good as J , and therefore, trust-sensitive evolution picks interpretations from E( , Mod(N)) that extends Mod(N) with all such J s. This approach corresponds to how Hunter and Booth (2015) introduced trust in the evolution of propositional theories. Definition 8. Let S be a selector. Then a trust-sensitive evolution semantics sem S maps each setting E = (T , A, N, ) to a set of interpretations S Mod(T , A), E( , M ) , where M is equal to Mod(N) if E is for KB evolution and to Mod(T , N) if E is for ABox evolution. Example 9. Consider two sets of interpretations: Mex = Mod(Tex, Aex), M ex = Mod(Tex, Nex). Then, the evolution result sem Ga {}(Eex) = Ga {}(Mex, E( Φex, M ex)) is equal to

{J PW | {lives In(Ein, us), lives In(Men, ru)} J }.

For classical MBAs the evolution result for Eex under Ga {} is:

{J PW | {lives In(Ein, us), lives In(Men, ru), lives In(Men, us)} J }. In practice one would expect the result of evolution to be a KB. Thus, a natural problem to study for MBAs is how evolution results can be axiomatised. Observe that the result of trust-sensitive evolution from Example 9 can be axiomatised respectively as

( , {lives In(Ein, us), lives In(Men, ru)}),

while the evolution result from Example 9 under the classical MBA Ga {} can be axiomatised as

( , {lives In(Ein, de), lives In(Men, ru), lives In(Men, us)}).

In the classical case, the resulting KB is the union of the old Aex and the new knowledge Nex. In the trust-sensitive case, the semantics rejects the new knowledge about Mendeleev since there is no trust in the fact that he is a US born.

Closure of DL-Lite Under Evolution We now turn our attention to DL-Lite and show that evolution results in general cannot be axiomatised as DL-Lite KBs. We start with a definition of the closure problem.

Definition 10. Let L be a DL, C a class of models of trust, and sem a trust-sensitive evolution semantics. Then, L is closed under sem for C if for every (L, C)-setting E there is an L-KB K such that Mod(K) = sem(E).

Total Trust and Total Distrust. The main reason why we introduce TT and TD is to verify on these extreme cases whether trust-sensitive evolution semantics behave in an intuitive way. In particular, we expect backward compatibility of trust-sensitive MBAs with the classical ones, that is, sem S should coincide with the corresponding classical semantics S in the case of TT. The following proposition confirms that this is indeed the case.

Proposition 11. Let E=(T , A, N, TT) be a (L, TT)-setting for some DL L. Then for any selector S, it holds that sem S(E) = S(Mod(T , A), M ), where M is equal to Mod(N) if E is for KB and Mod(T , N) if E is for ABox evolution.

The proposition implies that all non-closure results for DL-Lite under classical MBAs are inherited by trustsensitive MBAs for TT. In particular, it is known that for ABox evolution DL-Lite is not closed under six out of eight MBAs: Calvanese et al. (2010) showed the non-closure under La {} and La #, Kharlamov, Zheleznyakov, and Calvanese (2013) under Lp {} and Lp #, and finally Qi et al. (2015) under Ga {} and Ga #. For KB evolution Calvanese et al. (2010) showed the non-closure under all eight MBAs. Thus, the remaining open problem for trust-sensitive MBAs for TT is the closure under Gp {} and Gp # for ABox evolution. The following theorem closes this gap.

Theorem 12. For ABox evolution, DL-Lite is not closed under sem S for TT, where S {Gp {}, Gp #}.

Proof (Sketch).. Regarding Gp {}, one can check that for the TT-setting with A = { R (a)}, N = { R (a)}, and T = {A R, R A}, the set of interpretations obtained by evolution satisfies x.R(x, a) y.(y = a R(x, y)). One can show that this set is not axiomatisable in DL-Lite. The non-closure for the case of Gp # can be shown similarly.

In the case of TD, regardless of the DL L, selector S, and (L, TD)-setting E = (T , A, N, TD), it is easy to see that sem S(E) = Mod(T , A) for both KB and ABox evolution. Thus, sem S satisfies our intuition: it rejects the new information N as it is distrusted.

Assertion and Predicate Trust. We denote with S the set of all introduced semantics: S =

x,y,Z{sem Zx y}, where x {a, p}, y {{}, #}, and Z {L, G}. Observe that for each (L, TT)-setting ETT=(T , A, N, TT) one can construct an (L, PT)-setting EPT = (T , A, N, P), where P = pred(T A N), such that for each sem S we have sem(ETT) = sem(EPT). Therefore, all the non-closure results for TT are inherited by PT. Finally, we turn our attention to AT and show the nonclosure of DL-Lite under various trust-sensitive semantics.

Theorem 13. For AT it holds that: For KB evolution and each sem S, DL-Lite is not closed under sem; this holds already in the case when the new information consists of one TBox assertion. For ABox evolution and each sem S DL-Lite is not closed under sem.

In order to prove these results one can show that for each semantics sem considered in the theorem, there is a setting E, such that sem(E) is a set of models that satisfies a so-called genuine disjunction. That is, sem(E) satisfies ϕ ψ, for some ABox assertions ϕ and ψ, but does not satisfy either ϕ or ψ. By Lemma 1 from (Calvanese et al. 2010) such a set of interpretations is not axiomatisable in DL-Lite.

Approximation of Evolution in DL-Lite Since DL-Lite is not closed under the trust-sensitive MBAs, we turn our attention to approximation of evolution results. In this section we focus on ABox evolution and thus all settings are for ABox evolution. A sound approximation of sem(E) is a KB K such that sem(E) Mod(K), and it is maximal if no other sound approximation K exists s.t. Mod(K ) Mod(K). Sound approximation of evolution in the context of DLs has been studied for classical MBAs by De Giacomo et al. (2009), Kharlamov, Zheleznyakov, and Calvanese (2013), and Qi et al. (2015). We extend the notion of sound approximation by considering s-approximations which we introduce next. In order to define them, we use the following notation. Let Σ be a signature, then I|Σ is a sub-interpretation of I consisting of all atoms of I whose predicates are in Σ, and for a set

of models S, we define S|Σ as {I|Σ | I S}. Finally, S Σ S , if S|Σ S |Σ.

Definition 14. Let S be a set of interpretations, and K a knowledge base. Then, K is a sound s-approximation of S if S pred(S) Mod(K). Moreover, K is a maximal sound s-approximation of S if no other sound s-approximation K of S exists such that Mod(K ) pred(S) Mod(K). Finally, K is an s-axiomatisation of S if S = Mod(K)|pred(S).

Note that s-approximations coincide with sound approximations when pred(S) = pred(K).

Total Trust

In this section we will study sem S evolution in case of TT and S {Ga {}, Ga #} and use the following notations: cl T (A) is the set of membership assertions ϕ s.t. A T |= ϕ and cl(T ) is the set of TBox assertions ϕ s.t. T |= ϕ. It is known (Calvanese et al. 2007) that in DL-Lite cl T (A) and cl(T ) are finite and can be computed in polynomial time. Let E = (T , A, N, TT) be a TT-setting. Qi et al. (2015) showed that the algorithm At Alg, introduced by Kharlamov and Zheleznyakov (2011), computes a maximal sound approximation K of S(Mod(T , A), Mod(T , N)), where S {Ga {}, Ga #}. Given E, At Alg returns an ABox N A , where A is the maximal subset of cl T (A) such that (T , N A ) is satisfiable. By Proposition 11, K is also a maximal sound approximation of sem S(E). However, K is not necessarily their maximal sound s-approximation, as illustrated next.

Example 15. Consider a TT-setting E2 ex = (T 2 ex, A2 ex, N 2 ex, TT) over the signature Σex = {lives In, place}, where T 2 ex = { lives In place}, A2 ex = { lives In(Men)}, and N 2 ex = { lives In(Men)}. The maximal sound approximation obtained with At Alg is (T 2 ex, N 2 ex). However, any model J from Mod(T 2 ex, N 2 ex) with place J = is not in M = sem Ga {}(E2 ex). We can rule out such models by introducing a fresh role P that would enforce the existence of an element from Δ in the interpretation of place. Indeed, consider a KB Ks = (T s, As), where T s = T 2 ex { P place} and As = { P(a )} with P and a a fresh role and constant, respectively. Note also that Ks is a sound s-approximation of M and Mod(Ks) Σex Mod(K) holds as no model J of Ks is such that place J = .

In contrast to At Alg, for a given TT-setting E, Algorithm 1 (TT-SApprox) provides a maximal sound s-approximation for sem S(E), where S {Ga {}, Ga #}. One can follow the steps of the algorithm in Example 15. TT-SApprox first computes the maximal sound approximation using At Alg (Line 1). Then, in the spirit of Example 15, the algorithm finds general concepts C whose interpretations should not be empty in the resulting set of models (Line 8) and ensures that this will not happen via introducing new TBox and ABox assertions with fresh roles and constants (Lines 6 and 9) as in the example. Finally, if an interpretation of C should contain at least n constants, then the algorithm ensures that by making disjoint the non-empty ranges of the introduce properties that are pointing to C (Lines 10-11).

Algorithm 1: TT-SApprox

INPUT : a (DL-Litecore, TT)-setting E = (T , A, N, TT) OUTPUT: a DL-Litecore KB (T , A )

1 set T = T and A = At Alg(E)

2 introduce a fresh constant a not occurring in T , A, nor N

3 for each basic role R over pred(A, T ) do

4 introduce a fresh atomic role PR / pred(E)

5 if R(a) cl T (A) for some a then

6 set A = A { PR(a )}

7 for each R C cl(T ) for some general concept C do

8 if R(a) cl T (A) for some a and either R(a) / cl T (N) or there is no constant b s.t. C(b) cl T (A) and C(b) cl T (N) then

9 set T = T { P R C}

10 for each pair of introduced roles PR and PS do

11 if R S is in cl(T ) then set T = T { P R P S }

12 return (T , A N)

The following theorem shows that TT-SApprox efficiently computes maximal sound s-approximations. Theorem 16. Let E = (T , A, N, TT) be a (DL-Litecore, TT)-setting. Then, TT-SApprox(E) is a maximal sound s-approximation of sem S, where S {Ga {}, Ga #}. Moreover, TT-SApprox runs in time polynomial in |T A N|. A practical benefit of sound s-approximations is that they preserve important queries that may be lost by sound approximations. We will now introduce a class of such queries. An example query from this class is: Is it true that a university has at least five (distinct) researchers r1, . . . , r5 such that r1, r2, r3 work on the first project, r2, r3, r4 on the second one, and r1, r5 on the third one? Let Θ(x) be a formula recursively defined as follows:

Ψ(x) ::= A(x) | x R(x, x ) | x R(x , x), Θ(x) ::= Ψ(x) | Ψ(x).

Then, Q is the class of queries of the following form:

x1, . . . , xn

i =j (xi = xj)

i Xk Xk {1,...,n}

Theorem 17. Let q Q and sem = sem Ga y be an evolution semantics, where y {{}, #}. Then, there exists a TT-setting Eq such that sem(Eq) |= q and TT-SApprox(Eq) |= q, but At Alg(Eq) |= q.

Predicate Trust Let (T , A) be a DL-Lite KB and P PT for some P. A natural approach to this case would be to capture E( P, Mod(T , A)) with some theory, thus reducing the problem to the TT case. On the first glance, it would be sufficient just to remove assertions that are over the wrong signature from cl T (A). This, however, is not enough as shown in the following example.

Algorithm 2: PT-Extend SAx

INPUT : a DL-Litecore KB (T , A), a finite set of predicates P OUTPUT: a DL-Litecore KB (T , A )

1 set T = T and A =

2 introduce a fresh constant a not occurring in T nor A

3 for each α cl T (A) do

4 if the predicate of α is in P then set A = A {α}

5 for each basic role R over pred(T , A) do

6 introduce a fresh atomic role PR / pred(T , A)

7 if R(a) cl T (A) for some constant a then

8 set A = A { PR(a )}

9 for each R C in cl(T ) with C P do

10 set T = T { P R C}

11 for each pair of fresh atomic roles PR and PS do

12 if R S is in cl(T ) then set T = T { P R P S }

13 return (T , A )

Example 18. Consider P3 ex PT, where P3 ex = {person} and (T 3 ex, A3 ex), where T 3 ex = { lives In person}, A3 ex = {person(Men), lives In(Men)}. Consider also A = {person(Men)}, a subset of cl T (A3 ex) consisting of all the membership assertions over P3 ex. One can see that I = {person(x) | x Δ} is a model of (T 3 ex, A ), while I / E( P3 ex, Mod(T 3 ex, A3 ex)). However, we can still capture E( P3 ex, Mod(T 3 ex, A3 ex)) with (T s, As), where T s = T 3 ex { P person} and As = A { P(a )} for a fresh role P and constant a . Indeed, one can check that E( P3 ex, Mod(T 3 ex, A3 ex)) = Mod(T s, As)|pred(T 3 ex,A3 ex).

E( P, Mod(K)) can still be captured using saxiomatisation. Consider Algorithm 2 (PT-Extend SAx) that, for a given (T , A) and P, returns a maximal sound s-approximation of E( P, Mod(T , A)). One can follow the steps of the algorithm in Example 18: it finds concepts C whose interpretation should not be empty in each I of E( P, Mod(T , A)) (Line 10) and ensures their non-emptiness (Lines 8 and 9). Finally, as in Algorithm 1, PT-Extend SAx guarantees that the minimal number of constants in C is as required (Lines 11-12).

Theorem 19. Let (T , A) be a DL-Litecore KB and let P PT for some finite set of predicates P. Then PT-Extend SAx(T , A, P) is an s-axiomatisation of E( P, Mod(T , A)). Moreover, PT-Extend SAx runs in time polynomial in |T A P|.

Finally, we will show that PT-Extend SAx can be used to compute maximal sound s-approximations of sem S for S = La {}, that corresponds to a widely accepted Winslett s evolution semantics (De Giacomo et al. 2006; Winslett 1990).

Theorem 20. Let P be a finite set of predicates and EP = (T , A, N, P) a (DL-Litecore, PT)-setting. Let also (T , N ) = PT-Extend SAx((T , N), P) and ETT = (T , A, N , TT) be (DL-Litecore, TT)-setting. Then, if K is a maximal sound s-approximation (resp., s-axiomatisation) of sem La {}(ETT), then K is also a maximal sound s-approximation (resp., s-axiomatisation) of sem La {}(EP).

Algorithm 3: AT-Extend Ax

INPUT : a DL-Lite KB K = (T , A), a finite set of membership assertions Φ OUTPUT: a DL-Lite KB (T , A )

2 for each α cl T (A) do

3 if either α or α is in Φ then set A = A {α}

4 return (T , A )

Assertion Trust Let (T , A) be a DL-Lite KB and Φ AT for some finite set of membership assertions Φ. Firstly, observe that the set of models E( Φ, Mod(T , A)) can be axiomatised and Algorithm 3 (AT-Extend Ax), where α = B(a) if α = B(a) and α = B(a) if α = B(a) for some basic concept B, provides this axiomatisation. The algorithm keeps assertions of cl T (A) such that they or their negations are in Φ. The following theorem shows the correctness of AT-Extend Ax. Theorem 21. Let (T , A) be a DL-Lite KB and Φ AT for some finite set of membership assertions Φ. Then, E( Φ, Mod(T , A)) = Mod(AT-Extend Ax(T , A, Φ)), and AT-Extend Ax runs in time polynomial in |T A Φ|. An immediate consequence of the theorem is that each AT-setting E can be transformed into a TT setting ETT with the same evolution result under sem S with any selector S. Corollary 22. Let S be a selector and Φ a finite set of membership assertions. Let EΦ = (T , A, N, Φ) and ETT = (T , A, NTT, TT) be (DL-Lite, AT) and (DL-Lite, TT)-settings, respectively, where (T , NTT) = AT-Extend Ax(T , N, Φ). Then, sem S(EΦ) = sem S(ETT).

Related Work and Discussions Related Work. To the best of our knowledge, this is the first work that combines trust and evolution in the context of DLs. The closest research to ours is knowledge management with preferences where either logical formulae or predicates are ordered and thus less preferred elements can be seen as less trusted. However, this rather corresponds to defining levels of importance than trust. Bienvenu, Bourgaux, and Goasdoué (2014) studied inconsistency-tolerant semantics for querying inconsistent KBs. They rely on KB repairs which are subsets of the ABox that are consistent with the TBox, and use various models of preferences to determine the most important repairs. Since they do not select repairs that are of low importance, this can be seen as a trust-based KB repairing. However, their approach is based on formulae and thus closer to so-called formula-based evolution (Eiter and Gottlob 1992) rather than to the model-based approach that we study in this paper. Qi and Du (2009) studied evolution under a modified version of Gp # selector that relies on predicate-based preferences in selecting models of Mod(N). The crucial difference between their and our work is that their evolution result M is a subset of Mod(N) that consists of the most important models, while in our case we construct M by first extending Mod(N) according with the model of trust and then choosing

minimally distant elements from this extended set regardless their importance. Note that our approach can be combined with the selector of (Qi and Du 2009), but this requires further investigation.

Conclusion. We have formalised the notion of trust and evolution semantics as operators E and S and have shown how they can be composed to obtain trust-sensitive evolution semantics. This approach can be generalised to any notions of trust and evolution semantics that can be captured via operators. We have applied trust-sensitive MBAs to DL-Lite and have shown that under all of them DL-Lite is not closed. On the one hand, this is expected since DL-Lite has a limited expressive power, and already in the case of classical MBAs can return sets of models M whose axiomatisation requires syntactic constructs beyond DL-Lite. On the other hand, this is not selfevident since trust-sensitive MBAs in general return sets of models that are very different from the ones of classical MBAs. Thus, for both classical and trust-sensitive MBAs the main challenge is to find a good notion of evolution approximation and to develop (efficient) algorithms to compute optimal approximations. We have proposed a novel notion of sound s-approximation that captures evolution results better than sound approximations previously considered in the evolution context (i.e., s-approximations always capture as many and in some cases even more models, recall Example 15), and that preserve queries that may be lost by regular approximations. We have provided polynomial-time algorithms that compute maximal sound s-approximations for classical and several trust-sensitive MBAs. Our algorithms work either directly on trust-sensitive evolution settings or they can be utilised as subroutines to reduce evolution from trust-sensitive to classical settings. We see these algorithms as a starting point for developing efficient procedures for automated knowledge update and revision. We also believe this work is a timely contribution for the Semantic Web, where applications may depend on third-party information that is only partly trusted.

Baader, F.; Calvanese, D.; Mc Guinness, D. L.; Nardi, D.; and Patel Schneider, P. F. 2003. The Description Logic Handbook: Theory, Implementation, and Applications. DL Handbook. Bienvenu, M.; Bourgaux, C.; and Goasdoué, F. 2014. Querying inconsistent description logic knowledge bases under preferred repair semantics. In AAAI, 996 1002.

Bollacker, K.; Evans, C.; Paritosh, P.; Sturge, T.; and Taylor, J. 2008. Freebase: A Collaboratively Created Graph Database for Structuring Human Knowledge. In SIGMOD, 1247 1250. Calvanese, D.; De Giacomo, G.; Lembo, D.; Lenzerini, M.; and Rosati, R. 2007. Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family. J. Autom. Reasoning 39(3):385 429.

Calvanese, D.; Kharlamov, E.; Nutt, W.; and Zheleznyakov, D. 2010. Evolution of DL-Lite Knowledge Bases. In ISWC. Cuenca Grau, B.; Jiménez-Ruiz, E.; Kharlamov, E.; and Zheleznyakov, D. 2012. Ontology Evolution Under Semantic Constraints. In KR.

De Giacomo, G.; Lenzerini, M.; Poggi, A.; and Rosati, R. 2006. On the Update of Description Logic Ontologies at the Instance Level. In AAAI, 1271 1276. De Giacomo, G.; Lenzerini, M.; Poggi, A.; and Rosati, R. 2009. On Instance-level Update and Erasure in Description Logic Ontologies. JLC 19(5):745 770. Eiter, T., and Gottlob, G. 1992. On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals. In PODS, 261 273. Flouris, G.; Manakanatas, D.; Kondylakis, H.; Plexousakis, D.; and Antoniou, G. 2008. Ontology Change: Classification and Survey. Knowledge Eng. Review 23(2):117 152. Fridman Noy, N.; Kunnatur, S.; Klein, M.; and Musen, M. 2004. Tracking Changes During Ontology Evolution. In ISWC, 259 273. Furche, T.; Gottlob, G.; Grasso, G.; Gunes, O.; Guo, X.; Kravchenko, A.; Orsi, G.; Schallhart, C.; Sellers, A.; and Wang, C. 2012. DIADEM: Domain-Centric, Intelligent, Automated Data Extraction Methodology. In WWW Demo, 267 270. Haase, P., and Stojanovic, L. 2005. Consistent Evolution of OWL Ontologies. In ESWC, 182 197. Hunter, A., and Booth, R. 2015. Trust-Sensitive Belief Revision. In IJCAI, 3062 3068. Katsuno, H., and Mendelzon, A. 1991. On the Difference between Updating a Knowledge Base and Revising It. In KR, 387 394. Kharlamov, E., and Zheleznyakov, D. 2011. Capturing Instance Level Ontology Evolution for DL-lite. In ISWC, 321 337. Kharlamov, E.; Zheleznyakov, D.; and Calvanese, D. 2013. Capturing Model-Based Ontology Evolution at the Instance Level: The Case of DL-Lite. J. Comput. Syst. Sci. 79(6):835 872. Konev, B.; Walther, D.; and Wolter, F. 2008. The Logical Difference Problem for Description Logic Terminologies. In IJCAR, 259 274. Liu, H.; Lutz, C.; Miliˇci c, M.; and Wolter, F. 2011. Foundations of Instance Level Updates in Expressive Description Logics. Artif. Intell. 175(18):2170 2197. Qi, G., and Du, J. 2009. Model-based Revision Operators for Terminologies in Description Logics. In IJCAI, 891 897. Qi, G.; Wang, Z.; Wang, K.; Fu, X.; and Zhuang, Z. 2015. Approximating Model-Based ABox Revision in DL-Lite: Theory and Practice. In AAAI, 254 260. Stearns, M. Q.; Price, C.; Spackman, K. A.; and Wang, A. Y. 2001. SNOMED Clinical Terms: Overview of the Development Process and Project Status. In AMIA, 662 666. Suchanek, F. M., and Weikum, G. 2013. Knowledge Harvesting from Text and Web Sources. ICDE 1250 1253. Wang, Z.; Wang, K.; Zhuang, Z.; and Qi, G. 2015. Instance-Driven Ontology Evolution in DL-Lite. In AAAI, 1656 1662. Wang, Z.; Wang, K.; and Topor, R. 2010. A New Approach to Knowledge Base Revision in DL-Lite. In AAAI. Winslett, M. 1990. Updating Logical Databases. Cambridge University Press. Wu, J., and Lécué, F. 2014. Towards Consistency Checking over Evolving Ontologies. In CIKM, 909 918. Zhuang, Z.; Wang, Z.; Wang, K.; and Qi, G. 2014. Contraction and Revision Over DL-Lite TBoxes. In AAAI, 1149 1156. Zhuang, Z.; Wang, Z.; Wang, K.; and Qi, G. 2016. DL-Lite Contraction and Revision. JAIR 56:329 378.