Dealing with Inconsistencies due to Class Disjointness in SPARQL Update

Abstract

The problem of updating ontologies has received increased attention in recent years. In the approaches proposed so far, either the update language is restricted to (sets of) atomic updates, or, where the full SPARQL Update language is allowed, the TBox language is restricted to RDFS where no inconsistencies can arise. In this paper we discuss directions to overcome these limitations. Starting from a DL-Lite fragment covering RDFS and concept/class disjointness axioms, we define two semantics for SPARQL Update: under cautious semantics, inconsistencies are resolved by rejecting all updates potentially introducing conflicts; under brave semantics, instead, conflicts are overridden in favor of new information where possible. The latter approach builds upon existing work on the evolution of DL-Lite knowledge bases, setting it in the context of generic SPARQL updates.

Keywords

• Update

Introduction

This paper initiates the study of SPARQL updates in the context of potential inconsistencies: as a minimalistic ontology language allowing for inconsistencies, we consider ¬ RDFS , an extension of RDFS [ 8 ] with class disjointness axioms of the form { disjointWith } from OWL [ 10 ], sometimes referred to as negative inclusions or NIs [ 4 ], as the corresponding description logic encoding of this statement is As a running example, we assume a triple store with an RDFS

encoding an educational domain, asserting a range restriction plus mutual disjointness of the concepts like professor and student (we use Turtle syntax [ 2 ], in which dw abbreviates OWL’s disjointWith keyword, and dom and rng respectively stand for the domain and range keywords of RDFS). ⊑ ¬

. ¬ ontology (TBox) :Professor dw :Student. }

= {:studentOf dom :Student. :studentOf rng :Professor. Consider the following SPARQL update [ 6 ] request in the context of the TBox :

INSERT {?X :studentOf ?Y} WHERE {?X :attendsClassOf ?Y}

Consider an ABox with data on student tutors that happen to attend each other’s classes: = 1 :jimmy}. Here, {:jimmy :attendsClassOf :ann. :ann :attendsClassOf would create two assertions :jimmy :studentOf :ann and :ann :studentOf :jimmy. Due to the range and domain constraints in , these assertions result in clashes both for Jimmy and for Ann. Note that all inconsistencies

assertions vs. RDF(S), where , ′ denote concept (or, class) names, , ′ denote role (or, property) names, is the set of IRI constants (excl. the OWL/RDF(S) vocabulary) and ,

∈ . For RDF(S), we use abbreviations (rsc, sp, dom, rng, a) as introduced in [ 11 ]. TBox

RDFS¬ 1. ′ ⊑ 2. ′ ⊑ ′ sc .

3. ′ sp . 4. ∃ − ⊑

TBox ∃ ⊑

RDFS¬

TBox

RDFS¬ ABox RDFS¬

rng . dom . 5. ′ ⊑ ¬ ′ dw . 6. ( ) a .

7. (, ) P . keep those that cause no clashes. are in the new data, and thus we say that is intrinsically inconsistent for the particular ABox 1. Our solution for such updates will be to discard problematic assignments but

Now, let 2 be the ABox {:jimmy :attendsClassOf :ann. :jimmy a :Professor}. It is clear that after the update , the ABox will become inconsistent, due to the property assertion :jimmy :studentOf :ann, implying that Jimmy is both a professor and a student which contradicts the TBox disjointness axiom. In contrast to the previous case, the clash now is between the prior knowledge and the new data. We propose two update semantics, extending our previous work [ 1 ] for dealing with such inconsistencies and provide rewriting algorithms for implementing them using the basic constructs of the SPARQL language (e.g., making use of the UNION, MINUS, FILTER, and OPTIONAL operators).

In the remainder of the paper, after some short preliminaries (Sec. 2) we discuss checking of intrinsic inconsistencies in Sec. 3, and then in Sec. 4 we present two semantics for dealing with general inconsistencies in the context of materialized triple stores. An overview of related work and concluding remarks can be found in Sec. 5. 2

Preliminaries

We introduce basic notions about RDF graphs, RDFS¬ ontologies, and SPARQL queries. In this paper we use RDF and DL notation interchangeably, treating RDF graphs that do not use non-standard RDFS

¬ vocabulary [ 12 ] as sets of TBox and ABox assertions.

Definition 1 (RDFS

¬ ABox, TBox, triple store). We call a set 6–7 in Table 1 an (RDF) ABox, and the union tions of the forms 1–5 in Table 1 an (RDFS¬) TBox, a set of inclusion asserof assertions of the forms = ∪ an (RDFS¬) triple store.

– each atomic concept to a subset ℐ of ℐ , Definition 2 (Interpretation, satisfaction, model, consistency). An interpretation ⟨ ℐ , ·ℐ ⟩ consists of a non-empty set ℐ and an interpretation function ·ℐ , which maps ? sc ?.

? a ?.

? a ?. ? sp ?.

? ? ?. ? ? ?.

? dom ?.

? ? ?. ? a ?.

? a ?. ? rng ?.

? ? ?.

? a ?, ?.

? dW ?. ⊥ Fig. 1. Minimal RDFS rules from [ 11 ] plus class disjointness “clash” rule from OWL2 RL [ 10 ]. – each negation of atomic concept to (¬ ℐ ) = ℐ ∖ ℐ , – each atomic role to a binary relation ℐ over ℐ , and – each element of to an element of ℐ .

For expressions ∃ and ∃ −, the interpretation function is defined as (∃ )ℐ = { ∈ ℐ | ∃. (, ) ∈ ℐ } resp. (∃ −)ℐ = { ∈ ℐ | ∃. (, ) ∈ ℐ }. An interpretation ℐ satisfies an inclusion assertion 1 ⊑ 2 (of one of the forms 1–5 in Table 1), if 1ℐ ⊆ 2ℐ . Analogously, ℐ satisfies ABox assertions of the form ( ), if ℐ ∈ ℐ , and of the form (, ), if ( ℐ , ℐ ) ∈ ℐ . An interpretation ℐ is called a model of a triple store (resp., a TBox , an ABox ), denoted ℐ | = (resp., ℐ | = , ℐ | = ), if ℐ satisfies all assertions in (resp., , ). Finally, is called consistent, if it does not entail both ( ) and ¬ ( ) for any concept and constant ∈ , where entailment is defined as usual.

As in [ 1 ], we treat only restricted SPARQL queries corresponding to (unions of) conjunctive queries without non-distinguished variables over DL ontologies: Definition 3 (BGP, CQ, UCQ, query answer). A conjunctive query (CQ) , or basic graph pattern (BGP), is a set of atoms of the form 6–7 from Table 1, where now , ∈ ∪ .4 A union of conjunctive queries (UCQ) , or UNION pattern, is a set of CQs. We denote with ( ) (or ( )) the set of variables from occurring in (resp., ). An answer (under RDFS¬ Entailment) to a CQ over a triple store is a substitution of the variables in ( ) with constants in such that every model of satisfies all facts in . We denote the set of all such answers with ansrdfs(, ) (or simply ans(, )). The set of answers to a UCQ is ⋃︀ ∈ ans(, ).

We also recall from [ 1 ], that query answering in the presence of ontologies can be done either by rule-based pre-materialization of the ABox or by query rewriting. Let rewrite(, ) be the UCQ resulting from applying PerfectRef [ 3 ] (or, equivalently, the stripped-down version from [1, Alg.1]) to a query and let = ∪ be a triple store. Furthermore, let mat( ) be the triple store obtained from exhaustive application of the inference rules in Fig. 1 on a consistent triple store , and—analogously—let chase(, ) refer to “materialization” w.r.t. applied to a CQ . The next result transfers from [ 1 ] to consistent RDFS¬ stores.

Proposition 1. Let = ∪ be a consistent triple store, and a CQ. Then, ans(, ) = ans(rewrite(, ), ) = ans(, mat( )).

We have used this previously to define the semantics of SPARQL update operations. Definition 4 (SPARQL update operation, simple update of a triple store). Let and be BGPs, and a BGP or UNION pattern. Then an update operation ( , , ) has the form

DELETE

INSERT

WHERE Let = ∪ be a triple store. Then the simple update of w.r.t. ( , , ) is defined as ( , , ) = ( ∖ ) ∪ , where = ⋃︀ ∈ans( , ) gr ( ), = ⋃︀ ∈ans( , ) gr ( ), and gr ( ) denotes the set of ground triples in pattern . 4 is a countably infinite set of variables (written as ’?’-prefixed alphanumeric strings).

For the sake of readability of the algorithms, we assume that all update operations ( , , ) in this paper contain no constants in the BGPs and , and that all property assertions (? p ? ) in have distinct variables ? and ? . Enhancing our results to updates with constants and variable equalities in and is not difficult, but requires distinguishing special cases: e.g., instead of replacing the variable in a pattern by , the expression FILTER( = ) can be used in the case when is a constant; instead of ( ) MINUS for a variable , FILTER NOT EXISTS should be used for ground .

We call a triple store or (ABox) materialized if in each state it always guarantees ∖ = mat( )∖ mat( ). In the present paper, we will always focus on “materialization preserving” semantics for SPARQL update operations, which we dubbed Sem2mat in [ 1 ] and which preserves a materialized triple store. We recall the intuition behind Sem2mat, given an update = ( , , ): (i) delete the instantiations of plus all their causes; (ii) insert the instantiations of plus all their effects.

Definition 5 (Sem2mat [ 1 ]). Let ( , , ) be an update operation. Then S(e m 2m, at , ) = ( caus, ef ,{ }{ fvars}) Here, given a pattern , caus = flatten (rewrite(, )); ef = chase(, ) and fvars = {? a rdfs:Resource |? ∈ ( caus) ∖ ( )}, where flatten (·) computes the set of all triples occurring in the UCQ (, ), which in our case allows us to obtain all possible “causes” of each atom in , and “?v a rdfs:Resource” is a shortcut for a pattern that binds ? to any ∈ occurring in .

We refer to [ 1 ] for further details, but stress that as such, Sem2mat is not able to detect or deal with inconsistencies arising from and . In what follows, we will discuss how this can be remedied. 3

Checking Consistency of a SPARQL Update

Within previous work on the evolution of DL-Lite knowledge bases [ 4 ], updates given in the form of pairs of ABoxes , have been studied. However, whereas such update might be viewed to fit straightforwardly to the corresponding , in Def. 4, in [ 4 ] it is assumed that is consistent with the TBox, and thus one only needs to consider how to deal with inconsistencies between the update and the old state of the knowledge base. This a priori assumption may be insufficient for SPARQL updates though, where concrete values for inserted triples are obtained from variable bindings in the WHERE clause, and depending on the bindings, the update can be either consistent or not. This is demonstrated by the update from Sec. 1 which, when applied to the ABox 4, results in an inconsistent set of insertions . We call this intrinsic inconsistency of an update relative to a triple store = ∪ .

Definition 6. Let be a triple store. The update is said to be intrinsically consistent w.r.t. if the set of new assertions from Def. 4 generated by applying to , taken in isolation from the ABox of , does not contradict the TBox of . Otherwise, the update is said to be intrinsically inconsistent w.r.t. .

Algorithm 1: constructing a SPARQL ASK query to check intrinsic inconsistency (for the definition of

ef , cf. Def. 5) Output: A SPARQL ASK query returning // contains clashes in itself, i.e., is inconsistent for any triple store

UNION {{ 1[? ↦→? ]} . { 2[? ↦→? ]}} for a fresh ? 2 3 else old state of the knowledge base, illustrated by the ABox 2 from Sec. 1. This latter case can be addressed by adopting an update policy that prefers newer assertions in case of conflicts, as studied in the context of DL-Lite KB evolutions [ 4 ], which we will discuss in Sec. 4 below. Intrinsic inconsistencies however are harder to deal with, since there is no cue which assertion should be discarded in order to avoid the inconsistency. Our proposal here is thus to discard all mutually inconsistent pairs of insertions.

We first present an algorithm for checking intrinsic inconsistency by means of SPARQL ASK queries and then a safe rewriting algorithm. This rewriting is based on an observation that clashing triples can be introduced by a combination of two bindings of variables in the WHERE clause, as the example in the Sec. 1 (the ABox 1) illustrates. To handle such cases, two copies of the WHERE clause are created by the rewriting in Algorithms 1 and 2, for each pair of disjoint concepts according to the TBox of the triple store. These algorithms use notation described in Rem. 1 below. just a substitution of ? by ? in . Finally, Remark 1. Our rewriting algorithms rely on producing fresh copies of the WHERE clause. Assume , 1, 2, . . . to be substitutions replacing each variable in a given formula with a distinct fresh one. For a substitution , we also define [ ] resp. [ ] to be an extension of , renaming each variable at positions not affected by with a distinct fresh one. For instance, let be a triple (? :studentOf ? ). Now, makes a variable disjoint copy of : ? 1 :studentOf ? 1 for fresh ? 1, ? 1. [? ↦→? ] is [? ↦→? ] results in ? :studentOf ? 2 for fresh ? 2. We assume that all occurrences of [ ] stand for syntactically the same query, but that in

( 1) ∩ by the parameterizing substitution .

[ 1] and

[ 2], for distinct 1 and 2, can only have variables ( 2) in common. That is, the choice of fresh variables is defined variable renamings as in Rem. 1 and ? is a fresh variable.

Now, the possibility of unifying two variables ? and ? in on a given triple store can be tested with the query { 1[?

↦→? ]}{ 2[? ↦→? ]} where 1 and 2 are

In order to check the intrinsic consistency of an update, this condition should be evaluated for every pair of variables of , the unification of which leads to a clash. A SPARQL ASK query based on this idea is produced by Alg. 1. Note that it suffices to 2 5 6 7 Algorithm 2: Safe rewriting safe( )

Output: SPARQL update safe( ) all those which are implied by . check only triples of the form {?

a ? } at line 5 of Alg. 1, since disjointness conditions can only be formulated for concepts, according to the syntax in Table 1. Furthermore, since we are taking the facts in

ef extended by all facts implied by , at line 6 of Alg. 1 it suffices to check the disjointness conditions explicitly mentioned in and not Example 1. Consider the update from Sec. 1, in which the INSERT clause can create clashing triples. To identify potential clashes, Alg. 1 first applies the inference rule for the range constraint, and computes a :Professor}. Now both variables ?, ? ef = {?

a :Student . ? occur in the triples of type (6) from the safe rewriting safe(·) in Alg. 2, removing all variable bindings that participate in a clash between different triples of . Let be a WHERE clause, in which the variables ? and ?

should not be unified to avoid clashes. With 1, 2 being “fresh” variable to eliminate unsafe bindings that send ?

and ? to a same value. renamings as in Rem. 1, Alg. 2 uses the union of 1[? ↦→? ] and 2[? ↦→? ] Example 2. Alg. 2 extends the WHERE clause of the update from Sec. 1 as follows: INSERT{?X :studentOf ?Y} WHERE{?X :attendsClassOf ?Y

MINUS{{?X1 :attendsClassOf ?X} UNION {?Y :attendsClassOf ?Y2}}} Note that the safe rewriting can make the update void. For instance, safe( ) has no effect on the ABox 1 from Sec. 1, since there is no cue, which of :jimmy :attendsClassOf :ann, :ann :attendsClassOf :jimmy needs to be dismissed to avoid the clash. However, if we extend this ABox with assertions both satisfying the WHERE clause of and not causing undesirable variable unifications, safe( ) as a result of safe( ). would make insertions based on such bindings. For instance, adding the fact :bob :attendsClassOf :alice to 1 would assert :bob :studentOf :alice

A rationale for using MINUS rather than FILTER NOT EXISTS in Alg. 2 (and also in a rewriting in forthcoming Sec. 4) can be illustrated by an update in which variables in the INSERT and DELETE clauses are bound in different branches of a UNION: DELETE {?V a :Professor} INSERT {?X :studentOf ?Y}

WHERE {{?X :attendsClassOf ?Y} UNION {?V :attendsClassOf ?W}} A safe rewriting of this update (abbreviating :attendsClassOf as :aCo) is DELETE {?V a :Professor} INSERT {?X :studentOf ?Y} WHERE { {{?X :aCo ?Y} UNION {?V :aCo ?W}}

MINUS{ {{?X1 :aCo ?X} UNION {?V1 :aCo ?W1}}

UNION {{?Y :aCo ?Y2} UNION {?V2 :aCo ?W2}} } } It can be verified that with FILTER NOT EXISTS in place of MINUS this update makes no insertions on all triple stores: the branches {?V1 :aCo ?W1} and {?V2 :aCo ?W2} are satisfied whenever {?X :aCo ?Y} is, making FILTER NOT EXISTS evaluate to False whenever {?X :aCo ?Y} holds.

We conclude this section by formalizing the intuition of update safety. For a triple store and an update = ( , , ), let J K ings computed by the query “ SELECT ? 1, . . . , ? WHERE ” over , where ? 1, . . . , ? are the variables occurring in or in . denote the set of variable bindThen, the following properties hold for an arbitrary RDFS¬ triple store Theorem 1. Let be a TBox, let be a SPARQL update ( , , ), and let query and update safe( ) = ( , , ′ ) result from applying Alg. 1 resp. Alg. 2 to and . = ∪ : (1) ( ) = True iff ∃, ′ ∈ J K (2) J K ∖ J ′ = { ∈ J K | ∃ ′ ∈ J K

K s.t. ( ) ∧ ′( ) ∧ | = ⊥

; s.t. ( ) ∧ ′( ) ∧ | = ⊥}. 4

Materialization Preserving Update Semantics

In this section we discuss resolution of inconsistencies between triples already in the triple store and newly inserted triples. Our baseline requirement for each update semantics is formulated as the following property. triple store.

Definition 7 (Consistency-preserving). Let be a triple store and ( , , ) an update. A materialization preserving update semantics Sem is called consistency preSem serving in RDFS¬ if the evaluation of update , i.e., ( , , ), results in a consistent

Our two consistency preserving semantics are respectively called brave and cautious. The brave semantics always gives priority to newly inserted triples by discarding all pre-existing information that contradicts the update. The cautious semantics is exactly the opposite, discarding inserts that are inconsistent with facts already present in the triple store; i.e., the cautious semantics never deletes facts unless explicitly required by the DELETE clause of the SPARQL update.

Algorithm 3: Brave semantics Sembmraavte 1 ′ := caus;

Input: Materialized triple store Output: ( , , )

Sembmraavte 2 foreach triple pattern (? a ) in ef do 3 4 5 6 return ( ′ , ef ,{ }

fvars) if (?

a ′) ∈/ ′ then ′ := ′ . {?

a ′}caus foreach ′ s.t. ⊑ ¬ ′ ∈ or ′ ⊑ ¬

∈ do

, SPARQL update ( , , )

Both semantics rely upon incremental update semantics Sem2mat , introduced in Sec. 2, which we aim to extend to take into account class disjointness. Note that for the present section we assume updates to be intrinsically consistent, which can be checked or enforced beforehand in a preprocessing step by the safe rewriting discussed in Sec. 3. In this section, we lift our definition of update operation to include also updates ( , , ) with produced by the safe rewriting Alg. 2 from some update satisfying Def. 4. What remains to be defined is the handling of clashes between newly inserted triples and triples already present in the triple store.

The intuitions of our semantics for a SPARQL update ( , , ) in the context of an RDFS

¬ TBox are as follows: – brave semantics Sembmraavte: (i) delete all instantiations of and their causes, plus all the non-deleted triples in

clashing with instantiations of triples in to be inserted, again also including the causes of these triples; (ii) insert the instantiations of plus all their effects. – cautious semantics Semcmauatt : (i) delete all instantiations of and their causes; (ii) insert all instantiations of plus all their effects, unless they clash with some non-deleted triples in : in this latter case, perform neither deletions nor insertions. For a SPARQL update , we will define rewritings of implementing the above semantics, which can be shown to be materialization preserving and consistency preserving. 4.1

Brave Semantics The rewriting in Alg. 3 implements the brave update semantics Sembmraavte; it can be viewed as combining the idea of FastEvol [ 4 ] with Sem2mat to handle inconsistencies by giving priority to triples that ought to be inserted, and deleting all those triples from the store that clash with the new ones.

The DELETE clause ′ of the rewritten update is initialized with the set of triples from the input update . Rewriting ensures that also all “causes” of deleted facts are removed from the store, since otherwise deleted triples will be re-inserted by materialization. To this end, line 1 of Alg. 3 adds to ′ all facts from which can be derived. Then, for each triple implied by (that is, for each triple in computes clashing patterns and adds them to the DELETE clause ef ) the algorithm ′ , along with their causes. Note that it suffices to only consider disjointness assertions that are syntactically contained in is materialized.

(and not all that are implied by ), since we assume that the triple store Finally, the WHERE clause of the rewritten update is extended to satisfy the syntactic triple store, computing its new materialized and consistent state. by the part restriction that all variables in ′ must have matches in the WHERE clause: bindings of “fresh” variables introduced to ′ by eventual domain or range constraints are provided fvars, cf. Def. 5 and Ex. 3 below. The rewritten update is evaluated over the Example 3. Ex. 2 in Sec. 3 provided a safe rewriting safe( ) of the update from Sec. 1. According to Alg. 3, this safe update is rewritten to: DELETE {?X a :Professor . ?X1 :studentOf ?X .

?Y a :Student . ?Y :studentOf ?Y1} property assertions implying clashes need to be deleted, and the respective triples in ′ contain fresh variables ?

1 and ? 1. These variables have to be bound in the WHERE clause, and therefore fvars adds two optional clauses to

computationally reasonable implementation of the concept fvars from Def. 5. of safe( ), which is a Theorem 2. Alg. 3, given a SPARQL update and a consistent materialized triple store , computes a new consistent and materialized state w.r.t. brave semantics. Unlike Sembmraavte, its cautious version Semcmauatt always gives priority to triples that are already present in the triple store, and dismisses any inserts that are inconsistent with it. We implement this semantics as follows: (i) the DELETE command does not generate inconsistencies and thus is assumed to be always possible; (ii) the update is actually executed only if the triples introduced by the INSERT clause do not clash with state of the triple graph after all deletions have been applied.

Cautious semantics thus treats insertions and deletions asymmetrically: the former depend on the latter but not the other way round. The rationale is that deletions never cause inconsistencies and can remove clashes between the old and the new data.

As in the case of brave semantics, cautious semantics is implemented using rewriting, presented in Alg. 4. First, the algorithm issues an ASK query to check that no clashes will be generated by the INSERT clause, provided that the DELETE part of the update is executed. If no clashes are expected, in which case the ASK query returns False, the brave update from the previous section is applied. concepts ′ that are explicitly mentioned as disjoint with

For a safe update each triple pattern {? = ( , , ), the ASK query is generated as follows. For a } among the effects of , at line 3 Alg. 4 enumerates all in . As in the case of brave semantics, this syntactic check is sufficient due to the assumption that the update is applied to a materialized store; by the same reason also no property assertions need to be taken into account.

Algorithm 4: Cautious semantics Semcmauatt

Input: Materialized triple store = ∪ , SPARQL update ( , , )

Semcmauatt

Output: ( , , ) 1 := { FILTER(False)} // neutral element w.r.t. union 2 foreach (? a ) ∈ ef do 3 foreach ′ s.t. ⊑ ¬ ′ ∈ or ′ ⊑ ¬ ∈ do 4 −′ := { FILTER(False)} 5 foreach (? a ′) ∈ caus do 6 −′ := −′ UNION { [? ↦→? ]} :=

UNION {{? a ′} MINUS { −′ }} 7 12 8 := ASK WHERE {{ }.{ }}; 9 if ( ) then 10 return 11 else

Sembmraavte return ( , , )

For each concept ′ disjoint from , we need to check that a triple matching the pattern {? a ′} is in the store and will not be deleted by . Deletion happens if there is a pattern {? a ′} ∈ caus such that the variable ? can be bound to the same value as ? in the WHERE clause . Line 6 of Alg. 4 produces such a check, using a copy of , in which the variable ? is replaced by ? and all other variables are replaced with distinct fresh ones. Since there can be several such triple patterns in caus, testing for clash elimination via the DELETE clause requires a disjunctive graph pattern −′ constructed at line 6 and combined with {? a ′} using MINUS at line 7.

Finally, the resulting pattern is appended to the list of clash checks using UNION . As a result, { }.{ } queries for triples that are not deleted by and clash with an instantiation of some class membership assertion {? a } ∈ ef .

Theorem 3. Alg. 4, given a SPARQL update and a consistent materialized triple store = ∪ , computes a new consistent and materialized state w.r.t. cautious semantics. Example 4. Alg. 4 rewrites the safe update safe( ) from Ex. 2 as follows: ASK WHERE{{?X :attendsClassOf ?Y

MINUS{{?X1 :attendsClassOf ?X} UNION {?Y :attendsClassOf ?Y2}}} .{{?Y a :Student} UNION {?X a :Professor}}} Now, consider an update ′ having both INSERT and DELETE clauses: DELETE {?Y a :Professor} INSERT{?X a :Student} WHERE {?X :attendsClassOf ?Y} The update ′ inserts a single class membership fact and thus is always intrinsically consistent. The ASK query in Alg. 4 takes the DELETE clause of ′ into account:

ASK WHERE {{?X :attendsClassOf ?Y} .{{?X a :Professor} MINUS {?Z :attendsClassOf ?X }}}

Discussion and Conclusions

In this paper, we have taken a step further from our previous work, in combining SPARQL Update and RDFS entailment by also adding class/concept disjointness as a first step towards dealing with inconsistencies in the context of SPARQL Update. As discussed throughout the paper, previous approaches to handle inconsistencies in DL KB evolution (e.g., [ 4, 5, 9 ]) have assumed that the set of ABox assertions to be inserted is intrinsically consistent w.r.t. the TBox, and thus inconsistencies are treated only w.r.t. the old state of the knowledge base. As we have shown, this assumption is not trivially verifiable in the context of SPARQL updates, where DELETE/INSERT atoms are instantiated by a WHERE clause, and clashing triples could be instantiated within the same INSERT operation. We have addressed this problem by providing means to check whether a SPARQL update is intrinsically consistent and defining a safe rewriting that removes intrinsic clashes during inserts on-the-fly.

Next, taken that the problem of intrinsic consistency is solved, we have demonstrated how to extend the approach of [ 4 ] to SPARQL updates. We have defined a materialization and consistency preserving rewriting for SPARQL updates that essentially combines the ideas of [ 4 ] and our previous work on SPARQL updates under RDFS for materialized triple stores [ 1 ], dealing with clashes due to class disjointness axioms in a brave manner. That is, we overwrite inconsistent information in the triple store in favor of information being inserted. Alternatively, we have also defined a dual consistency-preserving update semantics that on the contrary discards insertions that would lead to inconsistencies.

Besides practical evaluation of the proposed algorithms, we plan to further extend our work towards increasing coverage of more expressive logics and OWL profiles, namely additional axioms from OWL 2 RL or OWL 2 QL [ 10 ]. Also, it could be useful to investigate further semantics, allowing for compromises between fully discarding the inconsistent old data and refusing the entire update due to clashes, and lift our methods to work with stores that are not fully materialized.

The consideration of negative information is an important issue also in other related works on knowledge base updates: for instance, the seminal work on database view maintenance by Gupta et al. [ 7 ] is also used in the context of materialized views using Datalog rules with stratified negation. Likewise, let us mention the work of Winslett [ 13 ] on formula-based semantics to updates, where negation is also considered. Acknowledgements. This work was supported by the Vienna Science and Technology Fund (WWTF), project ICT12-SEE, and EU IP project Optique (Scalable End-user Access to Big Data), grant agreement n. FP7-318338.

References

1. Ahmeti , A. , Calvanese , D. , Polleres , A. : Updating RDFS aboxes and tboxes in SPARQL . In: Proc. of the 13th Int. Semantic Web Conf. (ISWC). Lecture Notes in Computer Science , vol. 8796 , pp. 441 - 456 . Springer ( 2014 )

2. Beckett , D. , Berners-Lee , T. , Prud 'hommeaux, E., Carothers , G.: RDF 1.1 Turtle - Terse RDF Triple Language . W3C Recommendation, World Wide Web Consortium (Feb 2014 ), available at http://www.w3.org/TR/turtle/

3. Calvanese , D. , De Giacomo , G. , Lembo , D. , Lenzerini , M. , Rosati , R. : Tractable reasoning and efficient query answering in description logics: The DL-Lite family . J. of Automated Reasoning 39 ( 3 ), 385 - 429 ( 2007 )

4. Calvanese , D. , Kharlamov , E. , Nutt , W. , Zheleznyakov , D. : Evolution of DL-Lite knowledge bases . In: Proc. of the 9th Int. Semantic Web Conf. (ISWC). Lecture Notes in Computer Science , vol. 6496 , pp. 112 - 128 . Springer ( 2010 )

5. De Giacomo, G. , Lenzerini , M. , Poggi , A. , Rosati , R.: On instance-level update and erasure in description logic ontologies . J. of Logic and Computation 19 ( 5 ), 745 - 770 ( 2009 )

6. Gearon , P. , Passant , A. , Polleres , A. : SPARQL 1.1 update. W3C Recommendation, World Wide Web Consortium (Mar 2013 ), available at http://www.w3.org/TR/ sparql11-update/

7. Gupta , A. , Mumick , I.S. , Subrahmanian , V.S.: Maintaining views incrementally . In: Proc. of the ACM SIGMOD Int. Conf. on Management of Data . pp. 157 - 166 ( 1993 )

8. Hayes , P. , Patel-Schneider , P. : RDF 1.1 semantics. W3C Recommendation, World Wide Web Consortium (Feb 2014 ), available at http://www.w3.org/TR/rdf11-mt/

9. Liu , H. , Lutz , C. , Milicic , M. , Wolter , F. : Updating description logic ABoxes . In: Doherty, P. , Mylopoulos , J. , Welty , C.A . (eds.) Proc. of the 10th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR) . pp. 46 - 56 . AAAI Press ( 2006 )

10. Motik , B. , Grau , B.C. , Horrocks , I. , Wu , Z. , Fokoue , A. , Lutz , C. : OWL 2 Web Ontology Language profiles (second edition) . W3C Recommendation, World Wide Web Consortium (Dec 2012 ), available at http://www.w3.org/TR/owl2-profiles/

11. Muñoz , S. , Pérez , J. , Gutiérrez , C. : Minimal deductive systems for RDF . In: Proc. of the 4th European Semantic Web Conf. (ESWC). Lecture Notes in Computer Science , vol. 4519 , pp. 53 - 67 . Springer ( 2007 )

12. Polleres , A. , Hogan , A. , Delbru , R. , Umbrich , J.: RDFS & OWL reasoning for linked data . In: Reasoning Web. Semantic Technologies for Intelligent Data Access - 9th Int. Summer School Tutorial Lectures (RW), Lecture Notes in Computer Science , vol. 8067 , pp. 91 - 149 . Springer ( 2013 )

13. Winslett , M. : Updating Logical Databases. Cambridge University Press ( 2005 )