Updates in RDF stores have recently been standardised in the SPARQL 1.1 Update specification. However, computing answers entailed by ontologies in triple stores is usually treated orthogonally to updates. Even W3C's SPARQL 1.1 Update language and SPARQL 1.1 Entailment Regimes specifications explicitly exclude a standard behaviour for entailment regimes other than simple entailment in the context of updates. In this paper, we take a first step to close this gap. We define a fragment of SPARQL basic graph patterns corresponding to (the RDFS fragment of) DL-Lite and the corresponding SPARQL update language, dealing with updates both of ABox and of TBox statements. We discuss possible semantics along with potential strategies for implementing them. Particularly, we treat materialised RDF stores, which store all entailed triples explicitly, and preservation of materialisation upon ABox and TBox updates.
The availability of SPARQL as a standard for accessing structured Data on the Web
may well be called one of the key factors to the success and increasing adoption of
RDF and the Semantic Web. Still, in its first iteration the SPARQL [23] specification
has neither defined how to treat ontological entailments with respect to RDF Schema
(RDFS) and OWL ontologies, nor provided means how to update dynamic RDF data.
Both these gaps have been addressed within the recent SPARQL 1.1 specification, which
provides both means to define query answers under ontological entailments (SPARQL 1.1
Entailment Regimes [
For the sake of this paper, we address such questions with the focus on a deliberately
minimal ontology language, namely the minimal RDFS fragment of [
1 ′ ⊑ 2 ′ ⊑
′ sc . ′ sp . 3 4
∃ ⊑ ∃ − ⊑
dom . rng .
( )
a .
5
6 (, ) P .
impose non-trivial challenges; in particular, specific issues arise through the interplay of
INSERT, DELETE, and WHERE clauses within a single SPARQL update operation, which
—to the best of our knowledge— have not yet been considered in this combination in
previous literature on updates under entailment (such as for instance [
TBox: :joe :hasP :jack. :Father sc :Parent.
:joe :hasM :jane.
:Mother sc :Parent. :hasF sp :hasP.
:hasM sp :hasP.
:hasP rng :Parent; dom :Child. :hasF rng :Father; dom :Child. :hasM rng :Mother; dom :Child.
The following query should return :jack and :jane as (RDFS entailed) answers:
SPARQL engines supporting simple entailment would only return :jack, though.
The intended behaviour for the query in Ex. 1 is typically achieved either (i) by
query rewriting techniques computing entailed answers at query run-time, or (ii) by
materialising all implied triples in the store, normally at loading time. That is, on
the one hand, borrowing from query rewriting techniques for DL-Lite (such as, e.g.,
PerfectRef [
SELECT ?Y WHERE { {:joe :hasP ?Y} Indeed, this query returns both :jane and :jack.
On the other hand, an alternative5 is to materialise all inferences in the triple store,
such that the original query can be used ’as is’, for instance using the minimalistic
inference rules for RDFS from [
Example 3 (cont’d). The materialised version of
would contain the following triples—
for conciseness we only show assertional implied triples here, that is triples from the
four leftmost rules in Fig. 1.
5 This alternative is viable for RDFS, but not necessarily for more expressive DLs.
6 These rules correspond to rules 2), 3), 4) of [
? a ?. ? sp ?. ? ? ?.
? ? ?.
? dom ?. ? ? ?.
? a ?. ? rng ?. ? ? ?.
? a ?.
? sc ?. ? sc ?.
? sc ?. ? sp ?. ? sp ?.
? sp ?. Example 4 (cont’d). The following operation tries to delete an implied triple and at the same time to (re-)insert another implied triple.
Existing triple stores offer different solutions to these problems, ranging from
ignoring entailments in updates altogether, to keeping explicit and implicit (materialised)
triples separate and re-materialising upon updates. In the former case (ignoring
entailments) updates only refer to explicitly asserted triples, which may result in non-intuitive
behaviours, whereas the latter case (re-materialisation) may be very costly, while still
not eliminating all non-intuitive cases, as we will see. The problem is aggravated by
no systematic approach to which implied triples to store explicitly in a triple store and
which not. In this paper we try to argue for a more systematic approach for dealing with
updates in the context of RDFS entailments; we will focus on materialised RDF stores,
which store all entailed ABox triples explicitly. We propose alternative update semantics
and discuss possible implementation strategies, partially inspired by query rewriting
techniques from ontology-based data access (OBDA) [
In previous work [
We introduce some basic notions about RDF graphs, RDFS ontologies, and SPARQL queries. Since we will draw from ideas coming from OBDA and DL-Lite, we introduce these notions in a way that is compatible with DLs.
Definition 1 (RDFS ontology, ABox, TBox, triple store). We call a set of inclusion assertions of the forms 1–4 in Table 1 an (RDFS) TBox (or ontology), a set of assertions of the forms 5–6 in Table 1 an (RDF) ABox, and the union = ∪ an (RDFS) triple store.
In the context of RDF(S), the set of constants coincides with the set of IRIs. We assume the IRIs used for concepts, roles, and constants to be disjoint from IRIs of the RDFS and OWL vocabularies.7 In the following, we view RDF and DL notation interchangeably, i.e., we treat any RDF graph consisting of triples without non-standard RDFS vocabulary as a set of TBox and ABox assertions. To define the semantics of RDFS, we rely on the standard notions of (first-order logic) interpretation, satisfaction of assertions, and model.
As for queries, we again treat the cases of SPARQL and DLs interchangeably. Let be a countably infinite set of variables (written as ’?’ -prefixed alphanumeric strings). Definition 2 (BGP, CQ, UCQ). A conjunctive query (CQ) , or basic graph pattern (BGP), is a set of atoms of the forms 5–6 in Table 1, where now , ∈ ∪ . 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., ).
In this definition we are considering only CQs in which all variables are
distinguished (i.e., are answer variables), and such queries correspond to SPARQL basic graph
patterns (BGPs). Also, we allow only for restricted forms of general SPARQL BGPs
that correspond to standard CQs as formulated over a DL ontology; that is, we rule out
more complex patterns in SPARQL 1.1 [
From now on, let rewrite(, ) be the UCQ resulting from applying PerfectRef [
The next result follow immediately from, e.g., [
Various triple stores (e.g., BigOWLIM [
Finally, we introduce the notion of a SPARQL update operation.
7 That is, we assume no “non-standard use” [22] of these vocabularies. While we could assume
concept names, role names, and individual constants mutually disjoint, we rather distinguish
implicitly between them “per use” (in the sense of “punning” [
Definition 3 (SPARQL update operation). Let and be BGPs, and a BGP or UNION pattern. Then an update operation ( , , ) has the form DELETE
INSERT
WHERE
Intuitively, the semantics of executing ( , , ) on , denoted as ( , , ) is defined by interpreting both and as “templates” to be instantiated with the solutions of ans( , ), resulting in sets of ABox statements to be deleted from , and to be inserted into . A naïve update semantics follows straightforwardly. Definition 4 (Naïve update semantics). Let = ∪ be a triple store, and ( , , ) an update operation. Then, naive update of with ( , , ), denoted ( , , ), is defined as ( ∖ ) ∪ , where = ⋃︀ ∈ans( , ) gr ( ), = ⋃︀ ∈ans( , ) gr ( ), and gr ( ) denotes the set of ground triples in pattern . As easily seen, this naïve semantics does not preserve materialisation.9 3
We investigate now alternative semantics for updates that preserve a materialised ABox (or simply, mat-preserving semantics) and in how far these semantics can—similar to query answering—be implemented on top of off-the-shelf SPARQL 1.1 triple stores. Definition 5 (Mat-preserving semantics). Let and ( , , ) be as in Def. 4. An Sem Sem update semantics Sem is called mat-preserving, if ( , , ) = mat( ( , , )). Specifically, we consider the following variants, given an update ( , , ): Sem0mat : as a baseline for a mat-preserving semantics, we apply the naïve semantics, followed by (re-)materialisation of the whole triple store.
Sem1mat : an alternative approach for a mat-preserving semantics is to follow the
socalled “delete and rederive” algorithm [
Sem2mat : Another mat-preserving semantics could take a different viewpoint with respect to deletions, following the intention to: (i) delete the instantiations of plus all their causes; (ii) insert the instantiations of plus all their effects. Sem3mat : Finally, a mat-preserving semantics could combine Sem1mat and Sem2mat deleting both causes of instantiations of and (recursively) “dangling” effects.10 The definition of semantics Sem0mat is straightforward.
Definition 6 (Baseline mat-preserving update semantics). Let
Sem0mat be as in Def. 4. Then, ( , , ) = mat( ( , , )). and ( , , ) 9 Consider, e.g., the update from Ex. 4 on the materialised store from Ex. 3. 10 Note the difference to the basic “delete and rederive” approach. Sem1mat in combination with the intention of Sem2mat would also mean to recursively delete effects of causes, and so forth.
Let us proceed with a “reality-check” on this semantics using our running example. Example 5. Consider the update from Ex. 4. It is easy to see that under Sem0mat executed on the materialised triple store of Ex. 3, it would not have any effect.
As this behaviour is quite arguable, let us proceed with discussing the proposed alternative mat-preserving update semantics, and how they could be implemented.
As for Sem1mat , we rely on a well-known technique in the area of updates for
deductive databases called “delete and rederive” (DRed) [
The basic intuition behind DRed of deleting effects of deleted triples and then rematerialising can be expressed in our notation as follows; as we will consider a variant of this semantics later on, we refer to this semantics as Sem1m at . and its materialisation , plus Definition 7. Let S(e m 1m, at , ) = mat( ∪ , ( , , ), , and be defined as in Def. 4. Then mat( ∪
)) ∪ ).
As opposed to the classic DRed algorithm, where Datalog distinguishes between view predicates (IDB) and extensional knowledge in the Database (EDB), in our setting we do not make this distinction, i.e., we do not distinguish between implicitly and explicitly inserted triples. This means that Sem1m at would delete also those effects that had been inserted explicitly before. a distinction between explicitly and implicitly inserted triples.
We introduce now a different variant of this semantics, denoted Sem1m at , that makes Definition 8. Let ( , , ) be an update operation, and = ∪ ∪ a triple store, where
Sem1m at triples. Then ( , , ) = ∪ ′ and respectively denote the explicit and implicit ABox ∪ ′ , where and are defined as in Def. 4, ′ = ( ∖ ) ∪ , and ′ = mat( ′ ∪ ) ∖
Note that in Sem1m at , as opposed to Sem1m at , we do not explicitly delete effects of from the materialisation, since the definition just relies on re-materialisation from scratch from the explicit ABox
′ still be used for computing Sem1m at as shown by the following proposition.
. Nonetheless, the original DRed algorithm can
Proposition 2. Let us interpret the inference rules in Fig. 1 and triples in respectively
as rules and facts of a logic program ; accordingly, we interpret and from Def. 8
as facts to be deleted from and inserted into , respectively. Then, the materialisation
computed by DRed, as defined in [
.
None of Sem0mat , Sem1m at , and Sem1m at are equivalent, as shown in Ex. 6. Example 6. Given the triple store = {:C sc :D . :D sc :E}, on which we perform the operation INSERT{:x a :C, :D, :E.}, explicitly adding three triples, and subsequently perform DELETE{:x a :C, :E.}, we obtain, according to the three semantics discussed so far, the following ABoxes: Sem0mat : {:x a :D. :x a :E.}, Sem1m at : {:x a :D. :x a :E.}.
Sem1m at : {}, between these two is shown by the subsequent update DELETE{:x a :D.}:
While after this update Sem0mat and Sem1m at deliver the same result, the difference Sem0mat : {:x a :E.},
Sem1m at : {},
Sem1m at : {}.
As for the subtle difference between Sem1m at and Sem1m at , we point out that none
of [
Further, continuing with Ex. 5, the update from Ex. 4 still would not have any effect, neither using Sem1m at , nor Sem1m at . That is, it is not possible in any of these update semantics to remove implicit information (without explicitly removing all its causes).
Sem2mat aims at addressing this problem concerning the deletion of implicit information. As it turns out, while the intention of Sem2mat to delete causes of deletions cannot be captured just with the mat operator, it can be achieved fairly straightforwardly, building upon ideas similar to those used in query rewriting.
As we have seen, in the setting of RDFS we can use algorithm PerfectRef to expand a CQ to a UCQ that incorporates all its “causes”. A slight variation can be used to compute the set of all causes, that is, in the most naïve fashion by just “flattening” the set of sets returned by PerfectRef to a simple set; we denote this flattening on a set of sets as flatten ( ). Likewise, we can easily define a modified version of mat( ), applied to a BGP these considerations, we can thus define both rewritings that consider all causes, and using a TBox
11. Let us call the resulting algorithm matef (, )12. Using rewritings that consider all effects of a given (insert or delete) pattern : = matef (, ). of as ef Definition 9 (Cause/Effect rewriting). Given a BGP insert or delete template for an update operation over the triple store , we define the all-causes-rewriting as caus = flatten (rewrite(, )); likewise, we define the all-effects-rewriting of
This leads (almost) straightforwardly to a rewriting-based definition of Sem2mat . Definition 10. Let ( , , ) be an update operation. Then
Sem2mat ( , , ) = ( caus, ef ,{ }{ fvars}) where fvars = {? a rdfs:Resource. | for each ? ∈ Var ( caus) ∖ Var ( )}.
The only tricky part in this definition is the rewriting of the WHERE clause, where is joined13 with a new pattern fvars that binds “free” variables (i.e., the fresh variables 11 This could be viewed as simply applying the first four inference rules in Fig. 1 exhaustively to
∪ , and then removing .
feasibility of this rewriting.
12 Note that it is not our intention to provide optimised algorithms here, but just to convey the
13 A sequence of ’{}’-delimited patterns in SPARQL corresponds to a join, where such joins can
again be nested with UNIONs, with the obvious semantics, for details cf. [
Example 7. Getting back to the materialised version of the triple store from Ex. 3, the update from Ex. 4 would, according to Sem2mat, be rewritten to
DELETE {?X a :Child. ?X :hasF ?x1. ?X :hasM ?x2. ?X :hasP ?x3.}
?x2 a rdfs:Resource. ?x3 a rdfs:Resource.}} with Sem2mat containing :jane a :Mother, :Parent. :jack a :Parent.
It is easy to argue that Sem2mat is mat-preserving. However, this semantics might still result in potentially non-intuitive behaviours. For instance, subsequent calls of INSERTs and DELETEs might leave “traces”, as shown by the following example. Example 8. Assume = fam from Ex. 1 with an empty ABox. Under Sem2mat, the following sequence of updates would leave as a trace —among others— the resulting triples as in Ex. 7, which would not be the case under the naïve semantics.
Sem3mat tries to address the issue of such “traces”, but can no longer be formulated by a relatively straightforward rewriting. For the present, preliminary paper we leave out a detailed definition/implementation capturing the intention of Sem3mat; there are two possible starting points, namely combining Sem1m at +Sem2mat, or Sem1m at +Sem2mat, respectively. We emphasise though, that independently of this choice, a semantics that achieves the intention of Sem3mat would still potentially run into arguable cases, since it might run into removing seemingly “disconnected” implicit assertions, whenever removed assertions cause these, as shown by the following example.
Example 9. Assume a materialised triple store consisting only of the TBox triples :Father sc :Person, :Male . The behaviour of the following update sequence under a semantics implementing the intention of Sem3mat is arguable:
DELETE {} INSERT {:x a :Father.} WHERE {};
DELETE {:x a :Male.} INSERT {} WHERE {}; We leave it open for now whether “recursive deletion of dangling effects” is intuitive: in this case, should upon deletion of being Male, also be deleted that is a Person?
In a strict reading of Sem3mat’s intention, :x a :Person. would count as a dangling effect of the cause for :x a :Male., since it is an effect of the inserted triple with no other causes in the store, and thus should be removed upon the delete operation.
Lastly, we point out that while implementations of (materialised) triple stores may make a distinction between implicit and explicitly inserted triples (e.g., by storing explicit and implicit triples separately, as sketched in Sem1m at already), we consider the distinction between implicit triples and explicitly inserted ones non-trivial in the context of SPARQL 1.1 Update: for instance, is a triple inserted based upon implicit bindings in the WHERE clause of an INSERT statement to be considered “explicitly inserted” or not? We tend towards avoiding such distinction, but we have more in-depth discussions of such philosophical aspects of possible SPARQL update semantics on our agenda.
So far, we have considered the TBox as static. As already noted in [
In order to allow for TBox updates, we have to extend the update language: in the following, we will assume general BGPs, extending Def. 2.
Definition 11 (general BGP). A general BGP is a set of triples of any of the forms from Table 1, where , , , ′, , ′ ∈ ∪ .
We observe that with this relaxation for BGPs, updates as per Def. 3 can query TBox data, since they admit TBox triples in . In order to address this issue we need to also generalise the definition of query answers.14 Definition 12. Let be a union of general BGPs and [[ ]] the simple SPARQL semantics as per [21], i.e., essentially the set of query answers obtained as the union of answers from simple pattern matching of the general BGPs in over the graph . Then we define ansRDFS(, ) = [[ ]]mat( )
In fact, Def. 12 does not affect ABox inferences, that is, the following corollary follows immediately from Prop. 1 for non-general UCQs as per Def. 2. Corollary 1. Let Q be a UCQ as per Def. 2. Then ansRDFS(, ) = ansrdfs(, )
As opposed to the setting discussed so far, where the last two rules in Fig. 1 used for
TBox materialisation were ignored, we now focus on the discussion of terminological
updates under the standard “intensional” semantics (essentially defined by the inference
rules in Fig. 1) and attempt to define a reasonable (that means computable) semantics
under this setting. Note that upon terminological queries, the RDFS semantics and DL
semantics differ, since this“intensional” semantics does not cover all terminological
inferences derivable in DL, cf. [
Observation 1. TBox updates potentially affects materialisation of the ABox, that is, (i) upon TBox insertions a materialised ABox might need to be re-materialised in order to preserve materialisation. (ii) upon TBox deletions in a materialised setting, we have a similar issue to what we called “dangling” effects earlier.
Observation 2. Whereas deletions of implicit ABox triples can be achieved
deterministically by deleting all single causes, TBox deletions involving sc and sp chains
can be achieved in several distinct ways, as already observed by [
Example 10. Consider the graph = {:A sc :B. :B sc :C. :B sc :D. :C sc :E. :D sc :E. :E sc :F.} with the update DELETE{:A sc :F.}
Independent of whether we assume a materialised TBox, we would have various choices here to remove triples, to delete all the causes for :A sc :F. 14 As mentioned in Fn. 7, elements of may act as individuals, concept, or roles names in parallel.
In order to define a deterministic semantics for TBox updates, we need a canonical
way to delete implicit and explicit TBox triples. Minimal cuts are suggested in [
Here, we suggest two update semantics using rewritings to SPARQL 1.1 property
path patterns [
Definition 13. Let ( , , ) be an update operation where , , are general BGPs. Then S(e m om,uattcu,t ) = mat( ( ′ , , ′ )), where each triple { 1 2} ∈ such that scp ∈ {sc, sp} is replaced within ′ by { 1 ?. }, and we add to ′ the property path pattern { 1 ?. ? * 2}. Analogously, Semimnactut is defined by replacing {? 2} within ′ , and adding { 1 * ?. ? 2} within ′ instead.
Both Semomuattcut and Semimnactut may be viewed as straightforward extensions of Sem0mat, i.e., both are mat-preserving and equivalent to the baseline semantics for non-general BGPs (i.e., on ABox updates): Proposition 3. Let ( , , ) be an update operation, where , , are (nongeneral) BGPs. Then ( , , ) = S(e m im,nactut, ) = S(e m 0m, at , )
Semomuattcut
The intuition behind Semmat is to delete for every deleted . triple, all
directly outgoing edges from that lead into paths to , or, resp., in Semmat all
directly incoming edges to . This choice is motivated by the following proposition.
Proposition 4. Let = DELETE { }, and let be a triple store with
materialised TBox . Then, the TBox statements deleted by S(e m om,uattcu,t ) (or, S(e m im,nactut, ),
resp.) form a minimal cut [
The following example illustrates that the generalisation of Prop. 4 to updates involving the deletion of several TBox statements at once does not hold. Example 11. Assume the materialised triple store = {:A scp :B,:C,:D. :B scp :C, :D.} and = DELETE{:A scp :C. :A scp :D.}. Here, Semimnactut does not yield a minimal multicut in wrt disconnecting (:A,:C) and (:A,:D).15
As the example shows, the extension of the baseline ABox update semantics to TBox updates already yields new degrees of freedom. We leave a more in-depth discussion of TBox updates also extending the other semantics from Sec. 3 for future work. 5
Previous work on updates in the context of tractable ontology languages such as
RDFS [
In the area of database theory, there has been a lot of work on updating logical
databases: Winslett [26] distinguishes between model-based and formula-based updates;
our approach clearly falls in the latter category, more concretely, ABox updates could
be viewed as sets of propositional knowledge base updates [
We have discussed the semantics of SPARQL 1.1 Update in the context of RDFS. To the best of our knowledge, this is the first work to discuss how to combine RDFS with the new SPARQL 1.1 Update language. While in this paper we have been operating on a very restricted setting (only capturing minimal RDFS entailments, restricting BGPs to disallow non-standard-use of the RDFS vocabulary), we could demonstrate that even in this setting the definition of a SPARQL 1.1 Update semantics under entailments is a non-trivial task. We proposed several possible semantics, neither of which might seem intuitive for all possible use cases; this might well suggest that there is no “one-size-fitsall” update semantics. Further, while ontologies should be “ready for evolution” [20], we believe that more work into semantics for updates of ontologies alongside with data (TBox & ABox) is still needed to ground research in Ontology Evolution into standards (SPARQL, RDF, RDFS, OWL), particularly in the light of the increased importance that RDF and SPARQL are experiencing in dynamic domains where also data is continuously updated (dealing with dynamics in Linked Data, querying sensor data, or stream reasoning). We have taken a first step in the present paper. Acknowledgements. This work has been funded by the Vienna Science and Technology Fund (WWTF, project ICT12-015), by the Vienna PhD School of Informatics, and by EU Project Optique (grant n. FP7-318338). 20. Noy, N.F., Klein, M.C.A.: Ontology evolution: Not the same as schema evolution. Knowledge and Information Systems 6(4), 428–440 (2004) 21. Pérez, J., Arenas, M., Gutierrez, C.: Semantics and complexity of SPARQL. ACM Trans. on
Database Systems 34(3), 16:1–16:45 (2009) 22. 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) 23. Prud’hommeaux, E., Seaborne, A.: SPARQL query language for RDF. W3C Recommendation, World Wide Web Consortium (Jan 2008), available at http://www.w3.org/TR/ rdf-sparql-query 24. Ullman, J.D.: Principles of Database and Knowledge-Base Systems, vol. 1. Computer Science
Press (1988) 25. Urbani, J., Margara, A., Jacobs, C.J.H., van Harmelen, F., Bal, H.E.: DynamiTE: Parallel materialization of dynamic RDF data. In: Proc. of the 12th Int. Semantic Web Conf. (ISWC).
Lecture Notes in Computer Science, vol. 8218, pp. 657–672. Springer (2013) 26. Winslett, M.: Updating Logical Databases. Cambridge University Press (2005)