=Paper=
{{Paper
|id=Vol-1350/paper-05
|storemode=property
|title=Dealing
with Inconsistencies due to Class Disjointness in SPARQL Update
|pdfUrl=https://ceur-ws.org/Vol-1350/paper-05.pdf
|volume=Vol-1350
|dblpUrl=https://dblp.org/rec/conf/dlog/AhmetiCPS15
}}
==Dealing
with Inconsistencies due to Class Disjointness in SPARQL Update==
https://ceur-ws.org/Vol-1350/paper-05.pdf
Dealing with Inconsistencies due to Class Disjointness in
SPARQL Update
Albin Ahmeti1,3 , Diego Calvanese2 , Axel Polleres3 , and Vadim Savenkov3
1
Vienna University of Technology, FavoritenstraΓe 9, 1040 Vienna, Austria
2
Faculty of Computer Science, Free University of Bozen-Bolzano, Bolzano, Italy
3
Vienna University of Economics and Business, Welthandelsplatz 1, 1020 Vienna, Austria
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, incon-
sistencies are resolved by rejecting all updates potentially introducing conflicts;
under brave semantics, instead, conflicts are overridden in favor of new informa-
tion 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.
1 Introduction
This paper initiates the study of SPARQL updates in the context of potential inconsis-
tencies: 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Β¬ ontology (TBox)
π― 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).
π― = {:studentOf dom :Student. :studentOf rng :Professor.
:Professor dw :Student. }
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 :attendsClassOf :ann. :ann :attendsClassOf
:jimmy}. Here, π’ 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
Table 1. DL-LiteRDFSΒ¬ 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¬ TBox RDFS¬ TBox RDFS¬ ABox RDFS¬
β² β² β² β²
1. π΄ β π΄ π΄ sc π΄. 3. βπ β π΄ π dom π΄. 5. π΄ β Β¬π΄ π΄ dw π΄. 6. π΄(π₯) π₯ a π΄.
2. π β² β π π β² sp π . 4. βπ β β π΄ π rng π΄. 7. π (π₯, π¦) π₯ P π¦.
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
keep those that cause no clashes.
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 π― of inclusion asser-
tions of the forms 1β5 in Table 1 an (RDFSΒ¬ ) TBox, a set π of assertions of the forms
6β7 in Table 1 an (RDF) ABox, and the union πΊ = π― βͺ π an (RDFSΒ¬ ) triple store.
Definition 2 (Interpretation, satisfaction, model, consistency). An interpretation
β¨π₯β , Β·β β© consists of a non-empty set π₯β and an interpretation function Β·β , which maps
β each atomic concept π΄ to a subset π΄β of π₯β ,
?πΆ sc ?π·. ?π a ?πΆ. ?π dom ?πΆ. ?π ?π ?π.
?π a ?π·. ?π a ?πΆ.
?π sp ?π. ?π ?π ?π. ?π rng ?πΆ. ?π ?π ?π. ?π a ?πΆ,?π·. ?πΆ dW ?π·.
?π ?π ?π. ?π a ?πΆ. β₯
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 ans rdfs (π, πΊ) (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 Semmat 2 in [1]
and which preserves a materialized triple store. We recall the intuition behind Semmat 2 ,
given an update π’ = (ππ , ππ , ππ€ ): (i) delete the instantiations of ππ plus all their
causes; (ii) insert the instantiations of ππ plus all their effects.
Definition 5 (Semmat
2 [1]). Let π’(ππ , ππ , ππ€ ) be an update operation. Then
Semmat
πΊπ’(ππ2,ππ ,ππ€ ) = πΊπ’(π caus ,π eff ,{ππ€ }{π fvars })
π π π
caus
Here, given a pattern π , π = flatten(rewrite(π, π― )); π eff = chase(π, π― ) and
π = {?π£ a rdfs:Resource |?π£ β π±(π caus ) β π±(π )}, where flatten(Β·) computes the
fvars
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, Semmat
2 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 ππeff , cf. Def. 5)
Input: RDFSΒ¬ TBox π― , SPARQL update π’(ππ , ππ , ππ€ )
Output: A SPARQL ASK query returning π ππ’π if π’ is intrinsically inconsistent
eff
1 if β₯ β ππ then
2 return ASK {} //π’ contains clashes in itself, i.e., is inconsistent for any triple store
3 else
4 π := { FILTER(False)}; //neutral element w.r.t. union
5 foreach pair of triple patterns (?π a π ), (?π a π
) in ππeff do
6 if π β Β¬π
β π― then
7 π := π UNION {{ππ€ π1 [?π β¦β?π]} . {ππ€ π2 [?π β¦β?π]}} for a fresh ?π
8 return ASK WHERE {π }
Intrinsic inconsistency of the update differs crucially from the inconsistency w.r.t. the
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.
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
just a substitution of ?π by ?π in πΉ . Finally, πΉ π[?π β¦β?π] results in ?π :studentOf
?π2 for fresh ?π2 . We assume that all occurrences of πΉ π[π] stand for syntactically the
same query, but that πΉ π[π1 ] and πΉ π[π2 ], for distinct π1 and π2 , can only have variables
in πππππ(π1 ) β© πππππ(π2 ) in common. That is, the choice of fresh variables is defined
by the parameterizing substitution π.
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
variable renamings as in Rem. 1 and ?π is a fresh variable.
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
Algorithm 2: Safe rewriting safe(π’)
Input: RDFSΒ¬ TBox π― , SPARQL update π’(ππ , ππ , ππ€ )
Output: SPARQL update safe(π’)
eff
1 if β₯ β ππ then
2 return π’(ππ , ππ , FILTER(False))
3 π := { FILTER(False)}; //neutral element w.r.t. union
4 foreach pair of triple patterns (?π a π ), (?π a π
) in ππeff do
5 if π β Β¬π
β π― then
6 //cf. Rem. 1 for notation π[. . .]
7 π := π UNION {ππ€ π1 [?π β¦β?π ]} UNION {ππ€ π2 [?π β¦β?π]}}
8 return π’(ππ , ππ , ππ€ MINUS {π })
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 ππeff extended by all facts implied by π― , at line 6 of
Alg. 1 it suffices to check the disjointness conditions explicitly mentioned in π― and not
all those which are implied by π― .
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 infer-
ence rule for the range constraint, and computes ππeff = {?π a :Student . ?π
a :Professor}. Now both variables ?π, ?π occur in the triples of type (6) from
Table 1 with clashing concept names. The following ASK query is produced by Alg. 1.
ASK WHERE { ?X :attendsClassOf ?Y . ?Y :attendsClassOf ?X1 }
(In this and subsequent examples we omit the trivial FILTER(False) union branch used
in rewritings to initialize variables with disjunctive conditions, such as π in Alg. 1)
Suppose that an insert is not intrinsically consistent for a given triple store. One solution
would be to discard it completely, should the above ASK query return True. Another
option which we consider here is to only discard those variable bindings from the
WHERE clause, which make the INSERT clause ππ inconsistent. This is the task of
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
renamings as in Rem. 1, Alg. 2 uses the union of ππ€ π1 [?π β¦β?π ] and ππ€ π2 [?π β¦β?π]
to eliminate unsafe bindings that send ?π and ?π to a same value.
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 dis-
missed to avoid the clash. However, if we extend this ABox with assertions both satisfy-
ing the WHERE clause of π’ and not causing undesirable variable unifications, safe(π’)
would make insertions based on such bindings. For instance, adding the fact :bob
:attendsClassOf :alice to π1 would assert :bob :studentOf :alice
as a result of safe(π’).
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 eval-
uate 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π’πΊ denote the set of variable bind-
ings computed by the query β SELECT ?π1 , . . . , ?ππ WHERE ππ€ β over πΊ, where
?π1 , . . . , ?ππ are the variables occurring in ππ or in ππ .
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 π― .
Then, the following properties hold for an arbitrary RDFSΒ¬ triple store πΊ = π― βͺ π:
(1) ππ’ (πΊ) = True iff βπ, πβ² β Jππ€ Kπ’πΊ s.t. π(ππ ) β§ πβ² (ππ ) β§ π― |= β₯;
(2) Jππ€ Kπ’πΊ β Jππ€β² Kπ’πΊ = {π β Jππ€ Kπ’πΊ | βπβ² β Jππ€ Kπ’πΊ 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 seman-
tics is formulated as the following property.
Definition 7 (Consistency-preserving). Let πΊ be a triple store and π’(ππ , ππ , ππ€ ) an
update. A materialization preserving update semantics Sem is called consistency pre-
serving in RDFSΒ¬ if the evaluation of update π’, i.e., πΊSem
π’(ππ ,ππ ,ππ€ ) , results in a consistent
triple store.
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 Semmat
brave
Input: Materialized triple store πΊ = π― βͺ π, SPARQL update π’(ππ , ππ , ππ€ )
Semmat
Output: πΊπ’(ππbrave,ππ ,ππ€ )
β² caus
1 ππ := ππ ;
eff
2 foreach triple pattern (?π a πΆ) in ππ do
3 foreach πΆ β² s.t. πΆ β Β¬πΆ β² β π― or πΆ β² β Β¬πΆ β π― do
4 if (?π a πΆ β² ) β / ππβ² then
5 ππ := ππ . {?π a πΆ β² }caus
β² β²
6 return πΊπ’(π β² ,π eff ,{π }π fvars )
π π π€ π
Both semantics rely upon incremental update semantics Semmat 2 , 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 Semmat brave : (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 Semmat caut : (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 seman-
tics, 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 Semmat brave ; it can be viewed
as combining the idea of FastEvol [4] with Semmat 2 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 ππeff ) the algorithm
computes clashing patterns and adds them to the DELETE clause ππβ² , along with their
causes. Note that it suffices to only consider disjointness assertions that are syntactically
contained in π― (and not all that are implied by π― ), since we assume that the triple store
is materialized.
Finally, the WHERE clause of the rewritten update is extended to satisfy the syntactic
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
by the part ππfvars , cf. Def. 5 and Ex. 3 below. The rewritten update is evaluated over the
triple store, computing its new materialized and consistent state.
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}
INSERT {?X :studentOf ?Y . ?X a :Student . ?Y a :Professor}
WHERE {{?X :attendsClassOf ?Y
MINUS{{?X2 :attendsClassOf ?X} UNION {?Y :attendsClassOf ?Y2}}}
OPTIONAL {?X1 :studentOf ?X} OPTIONAL {?Y :studentOf ?Y1} }
The DELETE clause removes potential clashes for the inserted triples. Note that also
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 ππ€ of safe(π’), which is a
computationally reasonable implementation of the concept π fvars from Def. 5.
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.
4.2 Cautious Semantics
Unlike Semmat mat
brave , its cautious version Semcaut 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.
For a safe update π’ = (ππ , ππ , ππ€ ), the ASK query is generated as follows. For
each triple pattern {?π a πΆ} among the effects of ππ , at line 3 Alg. 4 enumerates all
concepts πΆ β² that are explicitly mentioned as disjoint with πΆ 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 Semmat
caut
Input: Materialized triple store πΊ = π― βͺ π, SPARQL update π’(ππ , ππ , ππ€ )
Semmat
Output: πΊπ’(ππcaut
,ππ ,ππ€ )
1 π := { FILTER(False)} // neutral element w.r.t. union
eff
2 foreach (?π a πΆ) β ππ do
3 foreach πΆ β² s.t. πΆ β Β¬πΆ β² β π― or πΆ β² β Β¬πΆ β π― do
β
4 π©πΆ β² := { FILTER(False)}
5 foreach (?π a πΆ β² ) β ππcaus do
β β
6 π©πΆ β² := π©πΆ β² UNION {ππ€ π[?π β¦β?π]}
β
7 π := π UNION {{?π a πΆ β² } MINUS {π©πΆ β² }}
8 π := ASK WHERE {{ππ€ }.{π }};
9 if π(πΊ) then
10 return πΊ
11 else
Semmat
12 return πΊπ’(ππbrave
,ππ ,ππ€ )
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 πΆ} β ππeff .
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 }}}
5 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)