Towards SPARQL instance-level Update in the Presence of OWL-DL TBoxes

Abstract

Represented knowledge is subject to frequent changes. To meet these requirements for dynamics, SPARQL update, an update language for RDF graphs, was developed. Even though there is some research on semantics of SPARQL ABox update for RDFS ontologies and approaches addressing updates in interplay with rather restricted TBoxes languages, up till now there is no de nition of semantics for SPARQL updates for OWL knowledge bases. In this paper, we de ne a SPARQL update semantics for OWL-DL ABoxes and show how existing methods like justi cation-based explanation can be used to conduct SPARQL updates in the presence of OWL-DL TBoxes. We argue that the interplay of the deletion and the insertion task of SPARQL update queries renders it not advisable to consider these tasks separately. This is why we introduce query-driven semantics aiming at optimizing the e ect of the whole update operation.

Keywords

• SPARQL update OWL Justi cation

1. Introduction

OWL [ 16 ] is a family of languages which are broadly used for knowledge representation purposes. It is based on description logics (DL) [ 4 ] and o ers versatile means to model terminological knowledge as well as knowledge about data. For knowledge represented in RDF [ 21 ], SPARQL [ 22 ] provides possibilities to query this knowledge. Similarly, the SPARQL-DL [ 23 ] query language, a distinct subset of the SPARQL query language, renders it possible to query OWL knowledge bases. A SPARQL-DL interface is included in every OWL API 3 reasoner which allows these reasoners to answer SPARQL-DL queries.

Besides querying represented knowledge, the management of changes constitutes an interesting challenge. Nearly all represented knowledge is subject to frequent changes and even the construction of a knowledge base can be seen as an evolutionary development. To meet these requirements for dynamics, SPARQL update [ 9 ], an update language for RDF graphs, was developed. Even though 1Work supported by DFG EVOWIPE. there is some research on semantics of SPARQL update for RDFS ontologies [ 1,13 ] and approaches addressing updates in interplay with rather restricted TBoxes languages [ 2 ], up till now there is no de nition of semantics for SPARQL updates for OWL knowledge bases. We de ne SPARQL update semantics for OWL-DL ABoxes and show how existing methods like justi cation-based explanation can be used to conduct SPARQL updates in the presence of OWL-DL TBoxes.

2. Running Example

We consider the knowledge base K = (T ; A), given in description logic syntax, T = fSoftwareEngineer v Employee;

Secretary v Employee;

Student u Employee v StudentTrainee;

9attendsCourse:> v Student g

A = fSoftwareEngineer (john);

Employee(john);

StudentTrainee(john);

Student (john)g (1) (2) (3) (4) (5) (6) (7) (8) with a SPARQL update which removes the status of being a StudentTrainee from all students who are employees and assigns them to some special course c1.

INSERT f?X :attendsCourse :c1g DELETE f?X a :StudentTraineeg

WHERE f?X a :Student, ?X a :Employeeg The update is supposed to be incorporated into the ABox by removing and adding as few assertions as possible. According to [ 9 ], the overall processing model is to rst evaluate the pattern in the WHERE clause, then to perform the deletion and after that the insertion. In order to use a uniform notation, we stick to description logic syntax and represent the triples which are supposed to be deleted or inserted as ABox assertions. W.r.t. the query presented above, the task is to delete StudentTrainee(john) and to insert attendsCourse(john; c1). To accomplish the deletion, we have to nd a minimal set of ABox assertions whose deletion prevents StudentTrainee(john) from being entailed by the knowledge base. This can be done by removing one of the following two sets fStudentTrainee(john); Student (john)g fStudentTrainee(john); Employee(john); SoftwareEngineer (john)g from the ABox. Note that both these possibilities constitute a minimal way to delete StudentTrainee(john) since no proper subset implements the deletion. For example the knowledge base resulting from removing only StudentTrainee(john) from the ABox would still entail StudentTrainee(john) since Student (john), Employee(john) together with the TBox axiom (3) imply StudentTrainee(john). In general, when considering knowledge bases with expressive TBoxes, there are many possibilities to accomplish a deletion. Determining which assertions to delete leads to di erent semantics for SPARQL update delete. Sec. 6 introduces some possible choices. Considering the insertion part of the example SPARQL update query, the task is to insert attendCourse(john; c1) into the ABox. Taking a closer look at the knowledge base, the last axiom in the TBox reveals that inserting attendCourse(john; c1) implies Student (john) which directly contradicts the rst possibility to delete StudentTrainee(john) mentioned above. This illustrates, that it is not advisable to consider insertion and deletion separately as this might have undesired e ects. To remedy this situation, in Sec. 6 we introduce query-driven semantics taking into account the whole query.

Inserting new assertions into an ABox might introduce inconsistencies. In this case, debugging techniques can be used to remove the inconsistency. Choosing one of the possibly many ways to resolve an inconsistency can be done by choosing one of the semantics we introduce in Sec. 6.2.

3. Background and Related Work

3.1. Related Work

The problem of belief revision and updating knowledge bases has received much attention in research [ 3,12 ]. [ 11 ] introduces a kernel semi-revision operator for belief bases in OWL-DL. The basic idea of this operator is to add the new information to the knowledge base, then compute all justi cations for possible inconsistencies and remove one element from each of these justi cations. Since in the last step the previously introduced information might be removed, it is not guaranteed that the inserted information is contained in the result. In contrast to this, some of the semantics we introduce guarantee that the result contains the inserted information whenever this is possible.

In [ 5 ], the prioritized assertional-based revision of DL-Lite knowledge bases is addressed. In their setting, it is assumed that the data is associated with priority or credibility information, possibly originating from the combination of data from di erent sources where each source has a certain reliability level.

Instance-level insertion and deletion for DL-LiteF , a tractable extension of DL-Lite which is oriented towards data intensive applications, is investigated in [ 6 ]. Since all reasoning tasks in DL-LiteF are tractable, approaches developed for this logic cannot be expected to be suitable for OWL-DL.

With respect to SPARQL update, [ 1 ] discusses possible semantics for SPARQL update in the presence of DL-Lite TBoxes. Due to the low expressivity of DL-Lite, inconsistencies are not an issue. [ 2 ] addresses the problem of handling inconsistencies due to class disjointness introduced by SPARQL updates. The approach is restricted to a DL-Lite fragment called DL LiteRDF S: covering RDFS as well as concept disjointness axioms. Di erent semantics of SPARQL ABox updates are de ned similar to the notion of the inconsistency tolerant semantics introduced in [ 15 ]. [ 2 ] use skillful query-rewriting to determine and resolve inconsistencies. These rewritings exploit the fact that in DL LiteRDF S: inconsistencies are caused by at most two ABox assertions. In contrast to this, inconsistencies in OWL-DL can be caused by an arbitrary number of ABox assertions.

[ 18 ] presents an approach for interactive ontology revision. User interaction is used to decide if an axiom should be accepted or rejected. This is combined with automated reasoning to ensure consistency.

3.2. Further Background

We introduce syntax and semantics of the description logic SHOIN which corresponds to OWL-DL. Given a set of atomic roles NR, the set of roles is de ned as NR [ fR j R 2 NRg, where R denotes the inverse role corresponding to the atomic role R. A role inclusion axiom is an expression of the form R v S, where R and S are atomic or inverse roles. A transitivity axiom is of the form Trans(S) for S an atomic or inverse role. An RBox R is a nite set of role inclusion axioms and transitivity axioms. v denotes the re exive, transitive closure of v over fR v S; Inv(R) v Inv(S) j R v S 2 Rg. A role R is transitive in R if there exists a role S such that S v R, R v S, and either Trans(S) 2 R or Trans(Inv(S)) 2 R. If no transitive role S with S v R exists, R is called simple.

Let NC be the set of atomic concepts and NI a set of individuals. The set of concepts is inductively de ned using the following grammar:

C ! > j ? j A j :C j C1 u C2 j C1 t C2 j 9R:C j 8R:C j nS j nS j fag where A 2 NC , Ci SHOIN concepts, R 2 NR, S 2 NR a simple role and a 2 NI .

A general concept inclusion (GCI) is of the form C v D with C and D SHOIN concepts. A TBox T is a nite set of GCIs also called axioms. An ABox A is a nite set of assertions of the form A(a) and R(a; b), with A an atomic concept, R an atomic role and a, b are individuals from NI . Note that in our setting, the ABox is only allowed to contain assertions about the belonging of individuals to atomic concepts and roles.

A knowledge base K is a triple (R; T ; A) with signature = (NC ; NR; NI ). The tuple I = ( I ; I ) is an interpretation for K i I 6= ; and I assigns an element aI 2 I to each individual a, a set AI I to each atomic concept A, and a relation RI I I to each atomic role R. I then assigns values to more complex concepts and roles as described in Tab. 1. I is a model of K (I j= K) if it satis es all axioms and assertions in R, T and A as shown in Tab. 1. A TBox T is called consistent, if there is an interpretation satisfying all axioms in T . A concept C is called satis able w.r.t. R and T i there exists a model I of R and T with CI 6= ;. An assertion A of the form B(a) or R(a; b) is entailed by a knowledge base K, denoted by K j= A, i I j= A for all models I of K.

Since this paper only considers updates concerning the ABox, we restrict the following de nition to ABox assertions. For the task of deleting assertions from >I ?I (:C)I (C t D)I (C u D)I (R )I = = = = = = ;

I

InCI CI [ DI CI \ DI f(y; x) j (x; y) 2 RIg

TBox & RBox axioms C v D

R v S Trans(R) ) ) )

CI RI (RI)+

DI SI

RI

fagI (8R:C)I (9R:C)I ( n S)I ( n S)I = = = = = faIg fx j 8y : (x; y) 2 RI ) y 2 CI fx j 9y : (x; y) 2 RI ^ y 2 CIg fx j jfy j (x; y) 2 SIgj ng fx j jfy j (x; y) 2 SIgj ng

ABox assertion

A(a) R(a; b) ) ) aI 2 AI (aI; bI) 2 RI a knowledge base or the task of debugging an ABox which is unsatis able w.r.t. the TBox and RBox, the notion of justi cations is very helpful. Given an ABox assertion and a knowledge base K = (R; T ; A), a justi cation of in K is a minimal subset of A which together with T and R implies .

De nition 1 (Justi cation [ 14 ]) Let K = (R; T ; A) be a knowledge base and be an ABox assertion. J A is a justi cation for in K if (R; T ; J ) j= and for all J 0 J , (R; T ; J 0) 6j= . The set of all justi cations for in K is denoted by Just ( ; K).

An Internationalized Resource Identi er (IRI) is a character string used to iden

tify a resource. Blank nodes identify anonymous resources which are not directly identi able from an RDF statement. A literal is a character string which possibly can be interpreted by means of a certain datatype.

De nition 2 (RDF Triple, RDF Graph) Let I, B and L be disjoints sets of IRIs,

blank nodes and literals. An RDF triple is of the form (s; p; o) 2 (I [ B) I (I [ B [ L). A set of RDF triples is called RDF graph.

A triple without blank node is called ground triple. Every SHOIN knowledge base can be mapped to an RDF graph and vice versa. See Tab. 2 for the mapping of ABox assertions and [ 19 ] for further details on the mapping. Therefore, we consider a knowledge base K = (R; T ; A) to be equivalent to the RDF graph produced by this mapping. Furthermore, for the sake of uniform notation, in most cases we will stick to DL syntax.

De nition 3 (BGP, CQ, UCQ, Query Answer [ 2 ]) A conjunctive query (CQ) q, or basic graph pattern (BGP), is a set of atoms of the form given in Tab. 2 where x; y 2 [ V with V a countable in nite set of variables (written as '?-' pre xed alphanumeric strings) and a set of IRIs. A union of conjunctive queries (UCQ) or UNION pattern Q, is a set of CGs. V(q) (V(Q)) denotes the set of variables, occurring in q (Q). An answer to a CQ q over a knowledge base K is a substitution of the variables in V(q) with constants in such that every model of

K satis es all facts in q . The set of all such answers is denoted with ans(q; K).

The set of answers to a UCQ Q is [q2Qans(q; K).

Please note, that our de nition of a BGP disallows blank nodes. Next, we introduce the notion of a SPARQL update operation and simple update semantics.

De nition 4 (SPARQL Update Operation[2]) Let Pd and Pi be BGPs and Pw a

BGP or UNION pattern. An update operation u(Pd; Pi; Pw) has the form

DELETE Pd INSERT Pi WHERE Pw De nition 5 (Simple Update Semantics [ 2 ]) Let K = (R; T ; A) be a knowledge base then the simple update of K w.r.t. an SPARQL update operation u(Pd; Pi; Pw) is de ned as Ku(Pd;Pi;Pw) = (R; T ; ((A n Ad) [ Ai) where Ad = [ 2ans(Pw;K)gr(Pd ) and Ai = [ 2ans(Pw;K)gr(Pi ) with gr a selection function which selects all ground triples from a BGP.

The simple update of a knowledge base w.r.t. u(Pd; Pi; Pw) results in removing the set of ABox assertions corresponding to Pd and adding the set of ABox assertions corresponding to Pi. Note that in case of using simple update semantics, it is not guaranteed that the assertions in Pd are not entailed anymore. Furthermore, it is possible that the resulting knowledge base is inconsistent. Since this outcome is not always acceptable for an update, in Sec. 6 we suggest di erent semantics for SPARQL update operations which behave di erently.

4. Overall Architecture

According to [ 9 ], the overall processing model for performing a SPARQL update query is to rst evaluate the pattern in the WHERE clause, then perform the deletion and after that the insertion. This is why we suggest the work ow given in Algorithm 1.

In Line 1 a CONSTRUCT query for the DELETE and WHERE clause is used to create a graph GD consisting of the triples which are supposed to be deleted. These triples correspond to a set of ABox assertions denoted by Ad. Similar to this, Line 2 constructs the set Ai of ABox assertions which are supposed to be inserted. Next, the task of deleting the set of assertions given in Ad is addressed. For this, in Line 3 function compDeletion is called which, given a knowledge base, a set of ABox assertions which should be deleted and a keyword indicating the desired semantics, determines a subset of A which accomplishes the deletion. The pseudo code for this procedure is given in Algorithm 2. Line 4 checks the satis ability of Algorithm 1 Perform a SPARQL update query to a knowledge base. Input: K = (R; T ; A), SPARQL update query u(Pd; Pi; Pw), DeleteSem the desired sematics for deletion and InsertSem the desired semantics for insertion. Output: Revised knowledge base K = (R; T ; ARevised) 1: Ad = set of ABox ass. for the result of asking CONSTRUCT Pd WHERE Pw to K 2: Ai = set of ABox ass. for the result asking CONSTRUCT Pi WHERE Pw to K 3: Deletion = compDeletion(K; Ad; DeleteSem) 4: if K = (R; T ; (A n Deletion) [ Ai) consistent then 5: return K = (R; T ; (A n Deletion) [ Ai) 6: else 7: Debug = compDeletion(K = (R; T ; (A n Deletion) [ Ai); f?g; InsertSem) 8: return K = (R; T ; ((A n Deletion) [ Ai) n Debug ) 9: end if the knowledge base resulting from rst deleting the ABox assertions determined by the compDeletion function and then adding the assertions in Ai. If the resulting knowledge base is satis able, then Line 5 returns the resulting knowledge base. If however the resulting knowledge base is unsatis able, the compDeletion procedure is used to debug the knowledge base. For this purpose, the compDeletion procedure is called with f?g as the set of assertions which are supposed to be deleted together with the desired insert semantics InsertSem. compDelete computes a set of ABox assertions which should be deleted in order to debug the knowledge base. This approach exploits the fact that debugging a knowledge base can be accomplished by deleting false from the knowledge base. Line 8 returns the knowledge base resulting from removing the computed set Debug , resulting in the knowledge base K = (R; T ; ((A n Deletion) [ Ai) n Debug ).

5. Deletion

For a knowledge base K = (R; T ; A) and Ad a set of ABox assertions which are supposed to be deleted, we now describe how to determine a minimal subset of A whose deletion prevents the assertions in Ad from being entailed by K. De nition 6 (Deletion) Let K = (R; T ; A) be a knowledge base and Ad a set of

ABox assertions. A deletion D of Ad in K is a minimal subset of the ABox A such that no element in Ad is entailed by (R; T ; A n D).

As demonstrated by the example provided in Sec. 2, it is not su cient to only remove all elements contained in Ad from the ABox since even after their removal they might still be entailed by the knowledge base. Furthermore, there might be more than one possible way to accomplish the deletion of Ad. The latter aspects will be addressed in Sec. 6. To determine a deletion of Ad in a knowledge base K, we suggest to use justi cations.

5.1. Justi cation based Deletion

Justi cations can be used to compute a deletion for an assertion from a knowledge base K = (R; T ; A). Please note that according to Def. 1, we restrict justi cations to be subsets of the ABox. Since the set of all justi cations for in K = (R; T ; A) corresponds to the set of all minimal subsets of A which together with R and T imply , it is su cient to delete exactly one element from each justi cation in order to prevent from being entailed. This corresponds to the construction of a minimal hitting set of the set of all justi cations for in K. De nition 7 (Hitting Set) Let S = fS1; : : : Sng be a set of sets. A hitting set for S is a set H [in=1Si with H \ Si 6= ;; 81 i n. If further no proper subset of

H is a hitting set for S, H is called a minimal hitting set. The set of all minimal hitting sets for S is denoted by HS (S).

Each minimal hitting set in HS (Just ( ; K)) constitutes a deletion of f g in K.

Example 1 The set of all justi cations for StudentTrainee (john) in the knowledge

base K given in Sec. 2 is:

Just (StudentTrainee(john); K) = ffStudentTrainee(john)g; fStudent (john); Employee(john)g; fStudent (john); SoftwareEngineer (john)gg

The two minimal hitting sets for Just (StudentTrainee(john); K), which both provide a deletion for StudentTrainee(john) in K, are: H1 =fStudentTrainee(john); Employee(john); SoftwareEngineer (john)g H2 =fStudentTrainee(john); Student (john)g

Potentially every subset of the ABox can be a justi cation for , resulting in justi cations with arbitrary cardinalities. Hence, there can be more than one hitting set for the set of all justi cations of and di erent ways to perform a deletion. When dealing with SPARQL update queries, it is reasonable to assume that more than one ABox assertion is supposed to be deleted. The rst idea to compute all possible deletions for a set of assertions Ad would be to compute all justi cations for all assertions in Ad separately and then compute all minimal hitting sets for these justi cations. However this approach considers an unnecessarily high number of justi cations because the union of all justi cations might contain non-minimal sets.

Example 2 Consider the knowledge base presented in the Sec. 2 together with Ad = fStudentTrainee(john); Student (john)g the set of assertions which are supposed to be deleted. The task is to nd a minimal set A0 A such that (T ; A n A0) 6j= StudentTrainee(john) and (T ; A n A0) 6j= Student (a). We construct the set of justi cations for both assertions:

Just (StudentTrainee(john); K) = ffStudentTrainee(john)g; fEmployee(john); Student (john)g; fSoftwareEngineer (john); Student (john)gg

Just (Student (john); K) = ffStudent (john)gg:

The only hitting for Just (StudentTrainee(john); K) [ Just (Student (john); K) is

HS(Just (StudentTrainee(john); K) [ Just (Student (john); K)) = ffStudentTrainee(john); Student (john)gg:

Only the justi cations fStudentTrainee(john)g and fStudent (john)g have to be

considered for the construction of the hitting set, since the other justi cations are supersets of fStudent (john)g. This leads to the notion of root justi cations. De nition 8 (Root Justi cation [ 17 ]) Let K = (R; T ; A) be a knowledge base, U = f 1; : : : ; ng a set of ABox assertions and Just ( i; K) the set of all justi cations of i in K. A set J 2 [in=1Just ( i; K) is a root justi cation for U in K i there is no J 0 2 [in=1Just ( i; K) with J 0 J . All justi cations in [in=1Just ( i; K) which are not a root justi cation are called derived justi cation.

Example 3 Only fStudentTrainee(john)g and fStudent (john)g are root justi ca

tions in Ex. 2.

As shown in [ 17 ], for a set of assertions Ad which are supposed to be deleted from a knowledge base K it is su cient to consider only root justi cations in order to determine what to delete.

Next we present Algorithm 2 which uses the notion of root justi cations to compute a deletion for a set of ABox assertions from a knowledge base. We use a black box for the computation of root justi cations. One way to compute all root justi cations for a given set of assertions Ad is to use an o the shelf reasoner like Pellet [ 24 ] to compute rst all justi cations for the di erent elements of Ad and then to remove all derived justi cations. Another way is to use the algorithm introduced in [ 17 ] which directly computes the root justi cations. For a knowledge

Algorithm 2 (compDeletion)

Given K = (R; T ; A) and a set of ABox assertions Ad which should be deleted, construct a minimal set A0 with A0 A and (R; T ; A n A0) 6j= A for all A 2 Ad. Input: K = (R; T ; A), a set of ABox assertions Ad which should be deleted and the desired semantics.

Output: A deletion for Ad in K.

1: RJ ust = set of all root justi cations for Ad in K 2: HS = set of all minimal hitting sets for RJ ust 3: Deletion = chooseDeletion(K; u(Pd; Pi; Pw); HS ; Semantics) 4: return Deletion base K and a set of ABox assertions Ad which are supposed to be deleted, line 1 computes all root justi cations for Ad in K. Next, line 2 constructs all minimal hitting sets for the set of root justi cations. Line 3 uses these minimal hitting sets together with a speci ed semantic to choose a subset of the ABox which should be deleted. The next Section presents possible choices for these semantics.

6. Semantics

In the previous section, we learnt that there can be more than one possible way to delete a set of assertions from a knowledge base. Furthermore, there might be more than one possible way to debug a knowledge base resulting from an insertion. To handle this problem, di erent semantics are suggested to choose among the possibilities.

6.1. Semantics for Deletion

Maxichoice Semantics [ 8 ]: In maxichoice semantics, the deletion with minimal cardinality is chosen. This corresponds to maximizing the number of ABox assertions which are preserved. Thus the resulting ABox implements the deletion while possessing maximal cardinality.

In cases, where there is more than one deletion with minimal cardinality, the maxichoice semantics does not specify which of these deletions to choose. We refrain from choosing an arbitrary one just for the sake of determinism. One way to solve this issue would be to o er the di erent possibilities to the user and let the user choose. Another possibility would be to use additional information associated with the ABox assertions like suggested in the priority/credibility based semantics introduced at the end of this section.

Meet Semantics [ 8 ]: This semantics is rather pessimistic since it removes all assertions occurring in a deletion. Thus the resulting ABox implements the deletion while possessing minimal cardinality.

Priority/Credibility based Semantics [ 8 ]: In some cases, additional information associated to the assertions in the ABox is available. Examples for this kind of information are credibility or time stamps and are summarized by the term provenance information. This provenance information can be used to decide which assertions to delete by for example preferably deleting those assertions associated with a low credibility or an old time stamp [ 20 ].

6.2. Semantics for Insertion

Insertion of a set of ABox assertions Ai can be accomplished by adding it to the knowledge base and then checking if the resulting knowledge base is satis able. If it is satis able, the resulting knowledge base corresponds to the result of the update operation. If it is unsatis able, the methods for deletion can be used to remove the inconsistencies from the knowledge base by deleting f?g from the knowledge base. As soon as a debugging step is used during an insertion, there might be several possibilities to perform the insertion. Di erent semantics can be used to pick one of these possibilities. Please note that it is possible that some (or even all) possibilities to debug the knowledge base remove the inserted assertions.

In addition to the semantics introduced in the previous section, semantics for insertion can take into account the fact that one can distinguish between old information, which was present in the ABox before the insertion and new information which was introduced by the insertion. The semantics presented below build on this distinction and were rst introduced in [ 2 ] for DL LiteRDF S: .

Brave Semantics: This semantics gives priority to new assertions which are inserted by the query meaning that the possibility to debug is selected which contains the highest number of assertions in Ai.

Note that there are cases, where there is is more than one possible way for debugging which contains the highest number of assertions in Ai. Similar to the maxichoice semantics we are facing non-determinism here and refrain from choosing an arbitrary possibility to debug just for the sake of determinism. One way to solve this issue would be to leave the decision to the user by o ering the di erent debugging possibilities to the user. Another possibility would be to use additional provenance information associated with the ABox assertions.

Cautious Semantics: In contrast to brave semantics, the cautious semantics gives priority to assertions which were already present before the insertion. This means that the possibility to debug is selected, which preserves as many of the already present assertions as possible. In the worst case, the debugging step removes the inserted assertion, making the insertion a semi-revision operator as corresponding to the one introduced in [ 11 ].

Fainthearted Semantics: This semantics is rather overcautious since it totally discards an insertion as soon as there is a con ict between the inserted assertions and the already present assertions.

6.3. Update Semantics taking into account the Interplay of Deletion and

Insertion

Next, we introduce another semantics, which aims at optimizing the overall result of an update. When considering the deletion and the insertion part of an update separately, it is possible that the insertion cancels the deletion. More precisely, it is possible that inserting assertions causes other assertions to be entailed which were deleted by the very same update.

Example 4 We consider an update operation deleting StudentTrainee (john) and

inserting Secretary (john) into the knowledge base introduced in Sect 2. As shown in Ex. 1, there are two possibilities to delete StudentTrainee (john) from the knowledge base, which we here denote by Del 1 and Del 2:

Del 1 = fStudentTrainee(john); Employee(john); SoftwareEngineer (john)g Del 2 = fStudentTrainee(john); Student (john)g

We choose Del 1 to perform the deletion of StudentTrainee (john) leaving only

the assertion Student (john) in the ABox. Next we address the insertion: Adding

Secretary (john) to the ABox together with the TBox assertions (2) and (3) from

Sec. 2 causes the deleted assertion StudentTrainee (john) to be entailed which clearly is not intended.

Ex. 4 illustrates that, in order to optimize the overall result of an update operation, it might be worthwhile not to consider the deletion and the insertion separately but to take their interplay into account. Before presenting semantics implementing this idea, we introduce the notion of an implementation of an update operation to a knowledge base, which corresponds to one possibility to perform an update operation to this knowledge base.

De nition 9 (Implementation of an Update Operation) Let K = (R; T ; A) be a knowledge base, u(Pd; Pi; Pw) an update operation, Ad the set of ABox assertions for the result of asking CONSTRUCT Pd WHERE Pw, Ai set of ABox assertions for the result of asking CONSTRUCT Pi WHERE Pw to K. Then (Del ; Dbg ) is called an implementation of update operation u(Pd; Pi; Pw) w.r.t. K, if Del is a deletion for

Ad in K and Dbg is a deletion for f?g in (R; T ; (AnDel )[Ai). The knowlege base

(Del;Dbg) resulting from (Del ; Dbg ) is de ned as Ku(Pd;Pi;Pw) = (R; T ; ((AnDel )[Ai)nDbg ): We omit the knowledge base if it is clear from the context and simply say that (Del ; Dbg ) is an implementation of update operation u(Pd; Pi; Pw). Next we present query-driven semantics which, can be used to choose one of the possible implementations of an update operation u(Pd; Pi; Pw).

Query-driven Semantics: Given knowledge base K = (R; T ; A), an update operation u(Pd; Pi; Pw), Ad, Ai de ned as in Def. 9 and an implementation (Del ; Dbg ) (Del;Dbg) of u(Pd; Pi; Pw). All assertions in Ad which are not entailed by Ku(Pd;Pi;Pw) can be seen as successful deletions (w.r.t. this implementation (Del ; Dbg )). Similarly, (Del;Dbg) all assertions in Ai which are entailed by Ku(Pd;Pi;Pw) can be seen as successful insertions (w.r.t. this implementation (Del ; Dbg )). The aim of query-driven semantics is to maximize the number of successful deletions and insertions. De nition 10 (Query-driven Update Semantics) Let K = (R; T ; A) be a knowledge base, u(Pd; Pi; Pw) an update operation, Ad the set of ABox assertions for the result of asking CONSTRUCT Pd WHERE Pw and Ai the set of ABox assertions for the result of asking CONSTRUCT Pi WHERE Pw to K. The query-driven update

Semqd of K w.r.t. u(Pd; Pi; Pw) is Ku(Pd;Pi;Pw) = (R; T ; ((A n Del ) [ Ai) n Dbg) where (Del ; Dbg ) is the implementation of u(Pd; Pi; Pw) maximizing jf

(Del;Dbg) 2 Ad j Ku(Pd;Pi;Pw) 6j= (Del;Dbg) gj + jf 2 Ai j Ku(Pd;Pi;Pw) j= gj (9)

If the SPARQL update query does not contain a DELETE clause, Del is empty and the query-driven update semantics behaves like the brave semantics. If the SPARQL update query does not contain an INSERT clause, Equation 9 does not choose a deletion. For these cases, query-driven semantics should be combined with one of the semantics for deletion presented in Sec. 6.1.

Note that there are other cases where query-driven semantics still leaves some choices: there could be more than one combination of deletion and debugging maximizing Eq. (9). This non-determinism could be avoided by presenting the set of successful deletions and insertions for these combinations to the user and let the user decide which of the possibilities is closest to the desired result. Another possibility would be to enhance the query mechanism such that the user is able to give priorities to certain parts of the query. Considering for example the query presented in Sec. 2 the user could specify that the deletion of the StudentTrainee status is more important than the assignment of those students to course c1.

Example 5 Let us reconsider the update operation introduced in Ex. 4. Please

recall that Ad = fStudentTrainee(john)g and Ai = fSecretary (john)g and that two di erent deletions Del 1 and Del 2 were presented.

(A n Del 1) [ Ai = fStudent (john); Secretary (john)g (A n Del 2) [ Ai = fSoftwareEngineer (john); Employee(john);

Secretary (john)g

Both (A n Del 1) [ Ai and (A n Del 2) [ Ai are satis able w.r.t. the TBox, hence no

debugging step is necessary. The two possible results of the update operation are: K1 = (T ; (A n Del 1) [ Ai)

K2 = (T ; (A n Del 2) [ Ai) Secretary (john) constitutes a successful insertion in both K1 and K2. Since K1 j= StudentTrainee(john) and K2 6j= StudentTrainee(john), StudentTrainee(john) is a successful deletion in K2 but not in K1. Query-driven semantics results in K2 since it maximizes the number of successful insertions and deletions. Query-driven semantics aims at the optimization of the overall result of the query. In extreme cases, where the sizes of Ad and Ai di er dramatically, it could happen that the smaller set is neglected. For example if jAdj = 5 and jAij = 1000, Eq. (9) is dominated by the set of successful insertions. This could be remedied by introducing a weight indicating the importance of the desired deletion or insertion.

7. Conclusion and Future Work

In this paper, we presented an approach to compute SPARQL ABox update in the presence of OWL-DL TBoxes. We address the fact that there might be more than one way to perform a deletion with di erent semantics according to which one of the possibilities is chosen. To master the interplay of the deletion and the insertion task of a SPARQL update query, we introduce query-driven semantics which aim at maximizing the overall e ect of an update operation.

An implementation of our approach is on the way. We are using SPARQL-DL to evaluate the CONSTRUCT query and Pellet to compute all possible justi cations.

Besides evaluating the approach, future work addresses the use of summarization techniques to e ciently compute justi cations. Since the set of ABox assertions which are supposed to be deleted are created by a basic graph pattern, this set is likely to contain many similar assertions. We want to exploit these similarities by rst aggregating similar individuals into one individual and then computing the justi cation for a bunch of assertions in one single step. Possible summarization techniques we are looking into are [ 7 ] and [ 10 ].

Acknowledgements We would like to thank Albin Ahmeti, Diego Calvanese, Axel Polleres and Vadim Savenkov for being so kind to share the implementation of their approach for SPARQL instance-level update in the presence of DL LiteRDF S: TBoxes which will serve as a basis for our implementation.

References

[1] A. Ahmeti , D. Calvanese , and A. Polleres . Updating RDFS aboxes and tboxes in SPARQL . In Semantic Web Conference (1) , volume 8796 of LNCS . Springer, 2014 .

[2] A. Ahmeti , D. Calvanese , A. Polleres , and V. Savenkov . Handling inconsistencies due to class disjointness in SPARQL updates . In ESWC , volume 9678 of LNCS . Springer, 2016 .

[3] C. E. Alchourron , P. Gardenfors, and D. Makinson . On the logic of theory change: Partial meet contraction and revision functions . J. Symb. Log. , 50 ( 2 ): 510 { 530 , 1985 .

[4] F. Baader and W. Nutt . Basic description logics . In Description Logic Handbook , pages 43 { 95 . Cambridge University Press, 2003 .

[5] S. Benferhat , Z. Bouraoui , O. Papini , and E. Wu rbel. A prioritized assertional-based revision for dl-lite knowledge bases . In JELIA , volume 8761 of LNCS . Springer, 2014 .

[6] G. De Giacomo , M. Lenzerini , A. Poggi , and R. Rosati . On instance-level update and erasure in description logic ontologies . J. Log. Comput. , 19 ( 5 ): 745 { 770 , 2009 .

[7] A. Fokoue , A. Kershenbaum , L. Ma , E. Schonberg, and K. Srinivas . The summary abox: Cutting ontologies down to size . In ISWC , volume 4273 of LNCS . Springer, 2006 .

[8] P. Ga rdenfors and H. Rott . Belief revision . In D. M. Gabbay , C. J. Hogger , and J. A . Robinson, editors, Handbook of Logic in Arti cial Intelligence and Logic Programming (Vol. 4 ). Oxford University Press, Oxford, UK, 1995 .

[9] P. Gearon , A. Polleres , and A. Passant . SPARQL 1.1 update. W3C recommendation, W3C , Mar. 2013 . http://www.w3.org/TR/2013/REC-sparql11 -update-20130321/.

[10] B. Glimm , Y. Kazakov , and T. Tran . Ontology materialization by abstraction re nement in horn SHOIF . In AAAI , pages 1114 { 1120 . AAAI Press, 2017 .

[11] C. Halaschek-Wiener and Y. Katz . Belief base revision for expressive description logics . In OWLED , volume 216 of CEUR Workshop Proceedings. CEUR-WS.org , 2006 .

[12] S. O. Hansson . A Textbook of Belief Dynamics , volume 11 of Applied Logic Series. Kluwer Academic Publishers, 1999 .

[13] R. Horne , V. Sassone , and N. Gibbins . Operational semantics for SPARQL update . In JIST , volume 7185 of LNCS . Springer, 2011 .

[14] M. Horridge . Justi cation based explanation in ontologies . PhD thesis , University of Manchester, UK, 2011 .

[15] D. Lembo , M. Lenzerini , R. Rosati , M. Ruzzi , and D. F. Savo . Inconsistency-tolerant semantics for description logics . In RR , volume 6333 of LNCS . Springer, 2010 .

[16] D. McGuinness , E. Kendall , J. Bao , and P. Patel-Schneider . OWL 2 web ontology language quick reference guide (second edition) . Technical report, W3C , Dec. 2012 . http://www.w3.org/TR/2012/REC-owl2 - quick-reference- 20121211 /.

[17] K. Moodley . Debugging and repair of description logic ontologies . Master's thesis , University of KwaZulo-Natal, Durban, South Africa, 2010 .

[18] N. Nikitina , S. Rudolph , and B. Glimm . Interactive ontology revision . J. Web Sem ., 12 : 118 { 130 , 2012 .

[19] P. Patel-Schneider and B. Motik. OWL 2 web ontology language mapping to RDF graphs (second edition) . W3C recommendation, W3C , Dec. 2012 . http://www.w3.org/TR/2012/REC-owl2 - mapping - to-rdf- 20121211 /.

[20] S. Schenk , R. Q. Dividino , and S. Staab . Using provenance to debug changing ontologies . J. Web Sem ., 9 ( 3 ): 284 { 298 , 2011 .

[21] G. Schreiber and Y. Raimond . RDF 1 . 1 primer . W3C note, W3C , June 2014 . http://www.w3.org/TR/2014/NOTE-rdf11 - primer-20140624/.

[22] A. Seaborne and S. Harris . SPARQL 1 . 1 query language . W3C recommendation, W3C , Mar. 2013 . http://www.w3.org/TR/2013/REC-sparql11 - query-20130321/.

[23] E. Sirin and B. Parsia . SPARQL-DL: SPARQL query for OWL-DL . In OWLED , volume 258 of CEUR Workshop Proceedings. CEUR-WS.org , 2007 .

[24] E. Sirin , B. Parsia , B. C. Grau , A. Kalyanpur , and Y. Katz. Pellet : A practical OWL-DL reasoner . J. Web Sem., 5 ( 2 ): 51 { 53 , 2007 .