Looking for an RDF Patch Format

by Mr.Anderson

As we move towards “Linked Data Platform”[0] support, we need to provide a mechanism to modify selectively repository content which represents containers and collections. Yes, in principle, the SPARQL and Graph Store protocols provide such facilities, but there is a wide-spread reluctance to admit their suitability due to one common issue: the restrictions placed on blank node designators. Any sorts of models which involve blank nodes require special procssing in order to specify the statements to modify. We note, for this, there is no effective standard method and have considered whether the “Linked Data Patch Format” could serve this purpose.

Based on the information to hand, despite both the extensive analysis which has been devoted to the abstract issues, and the purposeful deliberation leading up to the LDPatch proposal itself, we conclude that the suggested mechanism is inappropriate for inclusion in an RDF data management service. First, it does not appear possible for it to fulfill its relative preformance guarantees, second, it requires additional state and process control management from the client and, finally, it encumbers the server implementation and access protocol with elements which, given the other factors, serve no useful purpose.

In order to decide how to proceed, we consider the deliberations which led to the proposal and whether alternatives exist. To begin, there are several perspectives:

  • the original essay from Tim Berners-Lee and Dan Connoly [1],
  • the notes from James Carroll [2], concerning graph matching and isomorphism,
  • a much longer exploration of the complexities introduced by blank nodes from Axel Polleres [3],
  • a talk by Patrick Hayes which includes alternative notions of blank node semantics and, in particular, handles the salient issue neglected by Polleres: scope.
  • a note about a “Linked Data Patch Format” from the Linked Data Platform Working Group to cover a proposal which failed to achieve recommendation status [4], and
  • a shorter note from one of that note’s authors, Alexandre Bertails, which seeks to justify the “Patch Format” approach [5].

Despite the repeated analyses, none yields a standard approach to the problem. All rely on a misapprehension of the nature of “blank nodes” in a “physical symbol system”, fabricate a problem for which they then fail to find a solution, where neither need exist.

  • The authors first set the restriction, a blank node identifier has “no global designation”[noGlobal].
  • Then the authors introduce the notion, each “document” necessarily represents an isolated graph.
  • They then combine these restrictions to conclude that the designation rules for blank node identifiers may permit just one scope: that of the immediate document.
  • As a consequence, any mechanism which intends to communicate a graph requires a means to merge two independent graphs, each with a distinct vocabulary and, as such is necessarily a manifestation of a graph isomorphism problem.

As expressed in the LDPatch note:

As IRIs and RDF Literals have global scopes, such nodes in an argument graph represent the same resource as in the target graph. Blank nodes, on the other hand, pose a problem, as they have no global identifiers. Indeed, since the scope of blank node identifiers is limited to the LD Patch document in which they appear, any blank node identifier appearing in an LD Patch document is understood to denote a fresh blank node, distinct from any node initially present in the target graph. Therefore blank node identifiers in LD Patch cannot interfere with pre-existing blank nodes in the target graph.

From this perspective several known deficiencies in SPARQL become significant:

  • The SPARQL path facility is inadequate to bind the state necessary to effect side-effects on list representations.
  • The SPARQL function library lacks collection access and modifcation operations.
  • The means to designate paths in SPARQL basic graph pattern notation is too cumbersome to express constraints on internal path nodes.

The consequences for a linked data service are:

  • The document restriction carries over to SPARQL queries, as the constraint, no expression can directly designate any blank node in a target dataset
  • Where an HTTP POST or PATCH request includes among its instructions to the modify a graph any concrete designators for that graph’s components, it itself becomes a representation of that target and the patch process reduces to the isomorphism problem.

The combination is then taken as grounds sufficient to conclude that SPARQL is unsuitable for directed update operations and to justify a new language to avoid the one limitation and to provide more convenient means to describe any desired constraints. From our perspective, we need to determine whether these issues are sufficient to devote resources to redundant protocols, implementation and processing or whether it could be sufficient to

  • extend the SPARQL function library with several functions to support list access,
  • extend the SPARQL list syntax to support splicing, and
  • extend the SPARQL protocol to add a specification for the scope of blank node designators.

If it suffices to extend the SPARQL language semantics and that introduces no additional implementation complexity that would suggest the approach as a favourable alternative to a task-specific replacement such as LDPatch. This would be the case if, in pratice,

  • it is possible to extend SPARQL sufficiently to permit direct SPARQL requests to implement all use cases which the LDPatch note describes,
  • the extension constitutes a simpler implementation then SPARQL + LDPATCH while affording equivalent performance.
  • the extension permits much simpler application request logic and state management.

We examine each issue, in turn.


List Operators

SPARQL permits extension functions. The nature of list processing is well defined and the requisite operator definitions are wlll known. The simplest approach is to adopt the accessors and functions in the Common Lisp language [6], with standard SPARQL function syntax:

  • lisp:first (?node) [7]
  • lisp:rest (?node) [8]
  • lisp:nth (?node, ?index) [9]
  • lisp:nthcdr (?node, ?index) [10]
  • lisp:last (?node, ?index) [11]
  • lisp:member (?node, ?element) [12]

A facility to locate list nodes by pattern constraint requires the operators FIND and MEMBER-IF, with syntax which draws on EXISTS, to permit a quoted pattern as an argument along with the list head node value.

  • lisp:find-if (?node, ?constraint) [13]
  • lisp:member-if (?node, ?constraint) [14]

The initial complement is readily implemented within any processor, as each has simple function application and single-value return semantics. The latter two operators are more implementation specific, as they require a means to bind an intermediate node and apply a pattern prosepectively to the target dataset to test for existence. The semantics is analogous to EXISTS, and SPARQL itself would permit the expression as a combination of a list path expression and an EXISTS filter.

With respect to the working group note, given the dataset from [4],

<http://example.org/example> <http://example.org/vocab#preferredLanguages> ( "lorem" "ipsum" "dolor" "sit" "amet" ) .

allowing for the following prefix definitions,

prefix : <http://example.org/>
prefix vocab: <http://example.org/vocab#>
prefix lisp: <http://dydra.com/list-processing#>

the respective modifications from the ldpatch note [5] would be effected, in principle, as follows:

EXAMPLE 5,6 (replace one element (here the second one) with a new one)

UpdateList <#> <http://example.org/vocab#preferredLanguages> 1..2 ( "fr" ) .  
Output graph:  
<#> <http://example.org/vocab#preferredLanguages> ( "lorem" "fr" "dolor" "sit" "amet" ) .

is

delete {
  ?nthCell rdf:first ?nth
}
insert {
  ?nthCell rdf:first 'fr'
}
where {
  :example vocab:preferredLanguages ?head .
  bind ( lisp:nthcdr(?head, 1) as ?nthCell )
  ?nthCell rdf:first ?nth .
}

EXAMPLE 7,8 (insert new elements at a specific index (here 2))

UpdateList <#> <http://example.org/vocab#preferredLanguages> 2..2 ( "en" "fr" ) .  
Output graph:  
<#> <http://example.org/vocab#preferredLanguages> ( "lorem" "ipsum" "en" "fr" "dolor" "sit" "amet" ) .

is

delete {
  ?nthCell rdf:rest ?nthRest
}
insert {
  ?nthCell rdf:rest _:i1 . 
   _:i1 rdf:first 'fr' .
   _:i1 rdf:rest _:i2 .
   _:i2 rdf:first 'en' .
   _:i2 rdf:rest ?nthRest .
}
where {
  :example vocab:preferredLanguages ?head .
  bind ( lisp:nthcdr(?head, 1) as ?nthCell )
  ?nthCell rdf:rest ?nthRest .
}

however, see below for an alternative notation.

EXAMPLE 9,10 (append elements at the end of a collection)

UpdateList <#> <http://example.org/vocab#preferredLanguages> .. ( "en" "fr" ) .  
Output graph:  
<#> <http://example.org/vocab#preferredLanguages> ( "lorem" "ipsum" "dolor" "sit" "amet" "en" "fr" ) .

is

delete {
  ?lastCell rdf:rest rdf:nil
}
insert {
  ?lastCell rdf:rest ('en' 'fr') 
}
where {
  :example vocab:preferredLanguages ?head .
  bind ( lisp:last(?head) as ?lastCell )
}

EXAMPLE 11,12 (how to replace all the elements after the index 2 with the provided collection)

UpdateList <#> <http://example.org/vocab#preferredLanguages> 2.. ( "en" "fr" ) .  
Output graph:  
<#> <http://example.org/vocab#preferredLanguages> ( "lorem" "ipsum" "en" "fr" ) .

is

delete {
  ?nthCell rdf:rest ?nthRest
}
insert {
  ?nthCell rdf:rest ('en' 'fr') 
}
where {
  :example vocab:preferredLanguages ?head .
  bind ( lisp:nthcdr(?head, 1) as ?nthCell )
  ?nthCell rdf:rest ?nthRest .
}

EXAMPLE 13,14 (how to replace the n last elements)

UpdateList <#> <http://example.org/vocab#preferredLanguages> -3.. ( "en" "fr" ) .  
Output graph:  
<#> <http://example.org/vocab#preferredLanguages> ( "lorem" "ipsum" "en" "fr" ) .


delete {
  ?nthCell rdf:rest ?nthRest
}
insert {
  ?nthCell rdf:rest ('en' 'fr') 
}
where {
  :example vocab:preferredLanguages ?head .
  bind ( lisp:last(?head, 4) as ?nthCell )
  ?nthCell rdf:rest ?nthRest .
}

EXAMPLE 15,16 (remove elements (here the second and the third) from a collection)

UpdateList <#> <http://example.org/vocab#preferredLanguages> 1..3 ( ) .  
Output graph:  
<#> <http://example.org/vocab#preferredLanguages> ( "lorem" "sit" "amet" ) .

is

delete {
  ?nthCell rdf:rest ?nthRest
}
insert {
  ?nthCell rdf:rest ?nthCellNthCell 
}
where {
  :example vocab:preferredLanguages ?head .
  bind ( lisp:nthcdr(?head, 0) as ?nthCell )
  bind ( lisp:nthcdr(?nthCell, 2) as ?nthCellNthCell)
  ?nthCell rdf:rest ?nthRest .
}

EXAMPLE 17,18 (how to empty a collection)

UpdateList <#> <http://example.org/vocab#preferredLanguages> 0.. ( ) .

is

delete {
  :example vocab:preferredLanguages ?head .
}
insert {
  :example vocab:preferredLanguages rdf:nil .
}
where {
  :example vocab:preferredLanguages ?head .
}

That is, a trivial function library is sufficient to enable a SPARQL processor to perform all of the access-related list operations which indicate LDPatch conformance. Were LDPatch to introduce abstraction, that might sustain an additional argument, that its expressions are more powerful, but, as it also composes just literal formula, its expressive compactness offers no obvious advantage.

The remaining examples are, by the blog author’s own assertion, to be accomplished with a subset of SPARQL update and the only objections are, that mechanism is too computationally intensive and the result semantics are not clear. In which case, if the data to be modified is subject to complex constraints, there would need to be an argument that something else is necessarily more efficient than BGP projection.


Why LDPatch?

If arguments to prefer LDPatch based on greater sufficiency face counter demonstrations and those from expressiveness fail to address whether the characteristics of requiring fewer formula is a necessary advantage or a subject of idiomatic preferences, that leaves the third possible direction for LDPatch argument: that of efficiency and for an imperative in its approach due to the inherent complexity of BGP processing.

The W3C LDPatch note stakes a broad claim to “simplicity, ease of implementation, and run-time performance”. A third-party, concise paraphrase of the argument, traces the benefit to the simple tree semantics of LDPatch path expression:

Navigation operations take a node set, initially a single node, and each “step” replaces it through a simple property function. The only other operation is the filter, which shares the characteristic, that it operates on the immediate node set only. By constract, this is not the case for SPARQL, which must support more complex graph patterns, and therefore merge joins on potentially large sets. One could reduce the BGPs to the paths and optimize the queries for navigation (which requires extra complexity of SPARQL implementations in practice), but even still, it would place extra resource demands on a service intended to ssupport atomic PATCH requests if it is expected to run for many minutes on a preliminary query, just to decide that there’s one triple to update.

The argument attracts. It proposes, the path notation describes a process which can be realized more efficiently as it is inherently simpler. Two issues relate to performance:

  • the graph isomorphism problem which follows from the requirement that graphs be merged, which follows from the restriction on the scope of blank node ifentifiers
  • the node designation problem, which follows from SPARQL’s limitations to statement patterns with property paths.

Unfortunately, where the “Why LDPatch” essay[5] raises these issues, the claims elude substantiation in both regards. It argues, on one hand, from deficiencies in its notion of blank node designator scope to claim that the tailored LDPatch approach is necessary, and, on the other from the characteristics of its restricted expressions to claim that LDPatch promotes a processing model which is necessarily more effective than that of a SPARQL processor. As conducted, the arguments do not convince.

On the first count, it proposes “skolemization” as a necessary means to provide a shared context for designation between the client and server, but then dismisses it with the claim, the processing load would be excessive. Skolemization is applied to graphs to limit an identifier’s designation by circumscribing it to some scope where the designation is assured unique. In the case of RDF, when representations of graphs are combined, it ensures that no designator for any concrete anonymous node from a given constituent graph can be misconstrued to designate a different anonymous node in some other constituent graph. This is required in situations where nodes are distinct, but for some reason, the lexical forms of their designators cannot be distinguished. In cases where a process merges two graphs, the skolem function can be non-invertible. Where it generates designators which are guaranteed universally unique – for example, uuid values, the scope is then, trivially, the computing universe and encodings which include such designators can be trivially merged.

In this context the “Turtle Patch” method[16] is considered. That method suggests to “skolemize” the identifiers when they are externalized, and to provide means to interpret new identifiers as designating the respective original nodes when presented back to the server as request content. If the encoding were to follow the practice, to employ a skolem function with non-invertible results then the mechanism introduces unwarranted complexity and contributes to the LDPatch argument, that skolemization is not feasible. It need not.

As the Turtle patch document implies, an invertible function is to be preferred. For an endpoint which is based on a collection of identified datasets, such identifiers are readily generated. In some cases the ideal function, the identity function, is also the most suitable. That is, within some defined contexts, among them a client-server interaction with a SPARQL or Graph Store endpoint, there may be no reason to skolemize existing content. If the client and server simply specify that the node designators are stable, no skolem function is required to achieve that: the labels retain validity as designators for both client and server. To follow the suggestion from the Turtle patch document, one could specify

Prefer: return=representation; blank-nodes=use-identity

or something similar. There need be no problem.


If the issues related to blank node designation fail to exhibit benefits for LDPatch, perhaps its performance would still demonstrate an advantage. This would be the case, were the abstract model for the target data operations or the existing LDPatch implementations to substantiate the argument for inherent efficiency advantages according to the results of investigations on SPARQL processing complexity.

LDPatch discussions attach some primacy to a “node” beyond that which inheres in RDF’s notion of “resource”. The concept appears in discourse, as if such entities exist in some concrete form apart from the abstract entities designated by resource identifiers and represented in an RDF store. They are treated is if they exhibit special characteristics which permit more efficient property function computation, that is, of the other nodes which satisfy a path expression involving an originating “node” and a “predicate”. Bertails' post echos this sentiment. It describes that the abstract semantics for SPARQL evaluation necessarily entail a particular implementation and distinguishes LDPatch, as benefiting from the effect of the LDPatch bind form,

The runtime complexity for matching nodes in a graph is known to be extremely bad in some cases. While SparqlPatch is better that SPARQL Update in that regard, there are still some issues, which become apparent only when you start implementing and thinking about the runtime semantics. The main data structure in the SPARQL semantics is the Solution Mapping, which keeps track of which concrete nodes from the graph can be mapped to which variables, applying to each clause in the WHERE statement. So the semantics of the Basic Graph Pattern (ie. all the clauses in the SparqlPatch’s WHERE) involves a lot of costly Cartesian products. Also, it would be nice to change the evaluation semantics of the Basic Graph Pattern such that the evaluation order of the clauses is exactly the one from the query. It makes a lot of sense to let the client have some control over the evaluation order in the context of a PATCH. Unlike SparqlPatch, the Bind statement does not operate on triples. Instead, an LD Path expression ( / ^schema:url ) is evaluated against a concrete starting node ( <http://conferences.ted.com/TED2009/> ). The result node gets bound to a variable ( ?ted ) which can then be used in the following statements. That is the main difference when compared to SparqlPatch semantics.[5]

As attractive as this argument may be, it never explains, why this should, in itself, necessarily change the evaluation complexity. Were it to be true, that the LDPatch path language in combination with its protocol necessarily change something the manner in which path expressions are to be computed, the argument might convince, but that claim remains to be demonstrated. To express the question in another way, is there some qualitiative consequence which follows from Cartesian products of low cardinality and when, under what circumstance.

Several authors have reported their investigations into SPARQL path evaluation complexity. I recall one report to have included both a complexity analysis and performance results for a path evaluation algorithm which implemented the regular path semantics which was adopted for SPARQL in the aftermath of the Arenas et.al “yottabyte” paper[17]. I have not located it, which I regret, as, by my recollection it was the most concrete of the available essays. As an alternative, however, the Losemann&Maartens paper[18], which appeared at roughly the same time as Arenas' and includes a bit more discussion about the consequences of alternative path semantics than its more well-known counterpart. Its section 3.1 describes the algorithm and arrives at a complexity result of O(|r| x m log Rmax) where “r” is the path expression size and “m log Rmax” reflects the graph size in terms of the number of solutions for isolated path segment matches. They conclude, that the corresponding algorithms will run in polynomial time. This sets a lower bounds on the complexity for path evaluation for an abstract representation which involves triples and operates on the basis of arrays or fields of term designators. The alternative paper, as yet unlocated, described how to implement this in concrete terms for the most complex case – that of unbounded paths, in terms of paired intermediate fields arranged in opposing sort orders.

Given this result, to continue the argument in favor of LDPatch, above, the case could be made, that something about LDPatch reduces path evaluation complexity, perhaps in terms of path length, in terms of intermediate path set cardinality, or in terms of the factors which led to Losemann’s m log Rmax bounds. That is certainly conceivable.

The LDPatch presentation suggest two ways in which this could be true:

  • guarantee a match time with a very small constant or
  • quarantee singleton match result sets

The match latency requirement could be met, if the implementation were based on a graph store which relied on an attributed node model, such as neo4j. In this case, the goal is to provide relative resource designators with identifiers and locations as predictible as possible in order that the match factor reduce to a small constant. If, however, one follows the indications of the Python implementation which LDPatch duscussions cite[19], the mechanism devolves, in the manifestation of its graph_value operator, to a triple match with two constant terms. That is, it promotes no imperative for a node-centric concrete storage model and gives no indication of the hoped-for designation/location conflation. On the other hand, several in memory rdf store implementations do reduce match latency to a constant time operation in that their concrete storage model involves hash tables as relation indices. Memory suggests that to be the case for Sesame’s in-memory implementation and even for one of the very first RDF store implementation, Wilbur.[22] Yet, with respect to the question regarding optimization above, while one would most likely not “reduce the BGPs to the paths and optimize the queries” [as such], the work on rdf store implementations such as RDF-3x[20] and HEXASTORE[21] demonstrate methods to reduce the cost of a triple match to a minimum by means of index arrangements, which suggests, it might be feasible to reduce BGP processing to path-like iteration given the appropriate result set cardinality.[23]

On the question of match result set cardinality, the first line in the LDPatch example in Betrails' post reiterates the premise for the argument in unambiguous terms:

an LD Path expression is evaluated against a concrete starting node:
Bind ?ted ted:TED2009/ / ^schema:url .

In other words, the use case is intended to limit match result sets to cardinality one. In which case the complexity result, above, indicates that performance results from [7] are to be expected and the variations will follow from how well the index implementation performs matches.


Contingencies

In addition to these reservations, a number of additional contingent issues occur, which the LDPatch discussion never adresses, but which affect client application complexity:

  • What is the consequence when the designators to which the patch is to be applied are the result of some on-going process? That is, what happens when there does turn out to be more than one? In that case, then the governing factor will no longer be the match time, but the overhead entailed by iteration. In that case, the client application must manage that ongoing state in a way which permits it to synchronize a sequence of requests to an LDPatch server for resources which are, in fact, constituents of a single logical application operation.

  • What is the consequence, when the match time is dominated by secondary storage latency? Despite the benefits of agressive indexing demonstrated by implementations RDF-3x, there will always be cases where numbers dictate non-uniform storage. In those cases, a trade-off will appear at the point where the costs of set processing are lower than those for singleton processing, at which point, it would be preferable to permit the store to rearrange the process, rather than to shift the implementation to another language.


So far as we can tell, in summary, the argument for LDPatch does not bear out. Until some development can convince otherwise, we will deploy the list operators, continue to improveme property path processing, implement protocol support for blank node scope declarations, and retrench to consider whether, once realizes the unappreciated potential of blank node designators, something as simple as the diff patch format is all there needs to be?

Appendix: Dotted List Notation

In order to provide the ‘dot notation’ for lists[15], the SPARQL grammar requires to change one production:

[[102]]  Collection ::= '(' GraphNode+ ( '.' DottedNode )? ')'
[[102a]] DottedNode ::= GraphNode

With that addition to the language syntax, example 7,8 is accomplished as

delete {
  ?nthCell rdf:rest ?nthRest
}
insert {
  ?nthCell rdf:rest ('en' 'fr' . ?nthRest)
}
where {
  :example vocab:preferredLanguages ?head .
  bind ( lisp:nthcdr(?head, 1) as ?nthCell )
  ?nthCell rdf:rest ?nthRest .
}

Appendix: Definitions

Here, modulo the details which concern runtime representation and state, are schematic definitions for the above functions based on a single statement pattern match operator:

(defun lisp:first (resource)
  (if (eql resource rdf:nil)
    rdf:nil
    (match-object :s resource :p rdf:first)))

(defun lisp:rest (resource)
  (if (eql resource rdf:nil)
    rdf:nil
    (match-object :s resource :p rdf:rest)))

(defun lisp:nthcdr (index resource)
  (if (or (<= index 0)
          (eql resource rdf:nil)
          (eql resource nil))
    resource
    (lisp:nthcdr (1- index) (match-object :s resource :p rdf:rest))))

(defun lisp:nth (resource index)
  (lisp:first (lisp:nthcdr index resource)))

(defun lisp:last (resource &optional (index 1))
  (loop with cells = (list resource)
    do (setf resource (match-object :s resource :p rdf:rest)
             cells (cons resource cells)
    until (or (eql resource rdf:nil)
              (eql resource nil))
    finally (return (or (nth index cells) rdf:nil)))))

(defun lisp:member (resource element)
  (loop for member = resource
    then (match-object :s member :p rdf:rest)
    when (or (eql member rdf:nil)
             (eql member nil))
    return rdf:nil
    when (eql element (match-object :s member :p rdf:first))
    return member))

[noGlobal] The “no global identity” constraint conflates a restriction on the nature of an abstract model with the contingencies of operations in a physical symbol system. Whlie there may be cases, where it should not be permitted to designate some given node in a concrete graph in order that ambiguous references not yield unintended contradiction, to satisfy this restriction does not require that the constraint apply universally. That is, even if, to be clear in terms, there may be situations where no global identifier is permitted, in order to communicate representations, some identifier must be permitted in some context and the question reduces to: – what is that context, – how is the context defined and identified, and – what are its designation semantics?

As the various rules which govern the scope of blank node labels in SPARQL already demonstrate, the matter devolves to a question of context and It simply requires, that one be able to control the scope of a reference. Even the customary “[]” form serves as a designator, for which the concrete syntax of the respective encoding defines its relation to syntactic forms and the decoding semantics defined from that relation a respective scope.

As Seaborne seeks to clarify[https://lists.w3.org/Archives/Public/public-rdf-dawg/2011AprJun/0054.html] during correspondence on SPARQL,

to put it another way, bNodes have global identity but that identity is not the same as label or document identifier.

That is, while the identity of a blank node will contribute to mechanisms to determine the identity of a node which a blank node label designates, the node identitiy remains independent from any restrictions which the mechanism may define and may contribute to any numer of variations in designation, with inherent restriction. [24, 25]

As expressed in RDF 1.1 Semantics,

RDF graphs can be viewed as conjunctions of simple atomic sentences in first-order logic, where blank nodes are free variables which are understood to be existential. Taking the union of two graphs is then analogous to syntactic conjunction in this syntax. RDF syntax has no explicit variable-binding quantifiers, so the truth conditions for any RDF graph treat the free variables in that graph as existentially quantified in that graph. Taking the union of graphs which share a blank node changes the implied quantifier scopes.

That said, noted, with no restriction as to the result scope, which leaves open the obvious question, how to effect the change when the terms are those of a concrete graph, that is the terms of a quad field in a store, rather than an abstract graph? One must recognize that notions such as “Naming/Identifying Unnamed Elements”[26] is a contradiction in terms and one the discussion concludes, the consequence is that all entities are identified, which means thay are all named in some context and the only matter is, how to define and manage contexts. That is, in order to be effective, it is to be framed as a context definition problem rather than as a context equivalence problem.


[0] ; “Linked Data Platform 1.0”
[1] : “Delta: an ontology for the distribution of differences between RDF graphs”, Tim Berners-Lee and Dan Connolly (www.w3.org/DesignIssues/lncs04/Diff.pdf)
[2] : “Signing RDF Graphs”, Jeremy J. Carroll (http://www.hpl.hp.com/techreports/2003/HPL-2003-142.pdf), “Matching RDF Graphs” (http://www.hpl.hp.com/techreports/2001/HPL-2001-293.pdf)
[3] : “On Blank Nodes”, Mallea, Arenas, Hogan, Polleres, (http://web.ing.puc.cl/~marenas/publications/iswc11.pdf), “Everything You Always Wanted to Know About Blank Nodes” (http://www.websemanticsjournal.org/index.php/ps/article/viewFile/365/387)
[4] : “Linked Data Patch Format”, Bertails, Cahmpin and Sambra, (http://www.w3.org/TR/2015/NOTE-ldpatch-20150728/)
[5] : “Why LD PAtch”, Alexandre Bertails (http://bertails.org/2014/09/20/why-ldpatch/)
[6] : http://naggum.no/ANSI-CL/
[7] : http://www.lispworks.com/documentation/HyperSpec/Body/f_firstc.htm
[8] : http://www.lispworks.com/documentation/HyperSpec/Body/f_rest.htm
[9] : http://www.lispworks.com/documentation/HyperSpec/Body/f_nth.htm
[10] : http://www.lispworks.com/documentation/HyperSpec/Body/f_nthcdr.htm
[11] : http://www.lispworks.com/documentation/HyperSpec/Body/f_last.htm
[12] : http://www.lispworks.com/documentation/HyperSpec/Body/f_mem_m.htm
[13] : http://www.lispworks.com/documentation/HyperSpec/Body/f_find_.htm
[14] : http://www.lispworks.com/documentation/HyperSpec/Body/f_mem_m.htm
[15] : http://www.lispworks.com/documentation/HyperSpec/Body/26_glo_d.htm#dotted_list
[16] : http://www.w3.org/2001/sw/wiki/TurtlePatch#Handling_Blank_Nodes
[17] : Arenas, Marcelo, Sebastian Conca, and Jorge Perez. “Counting beyond a Yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard.” In Proceedings of the 21st international conference on World Wide Web, pp. 629-638. ACM, 2012. http://www.dcc.uchile.cl/~jperez/papers/www2012.pdf
[18] : Losemann, Katja, and Wim Martens. “The complexity of regular expressions and property paths in SPARQL.” ACM Transactions on Database Systems (TODS) 38, no. 4 (2013): 24. http://www.theoinf.uni-bayreuth.de/download/tods13.pdf
[19] : https://github.com/pchampin/ld-patch-py/blob/master/ldpatch/processor.py
[20] : Neumann, Thomas, and Gerhard Weikum. “The RDF-3X engine for scalable management of RDF data.” The VLDB Journal 19, no. 1 (2010): 91-113. https://cs.uwaterloo.ca/~gweddell/cs848/papers/RDF-3X.pdf
[21] : Weiss, Cathrin, Panagiotis Karras, and Abraham Bernstein. “Hexastore: sextuple indexing for semantic web data management.” Proceedings of the VLDB Endowment 1, no. 1 (2008): 1008-1019.http://people.csail.mit.edu/tdanford/6830papers/weiss-hexastore.pdf
[22] : Lassila, Ora. “Taking the RDF model theory out for a spin.” In The Semantic Web – ISWC 2002, pp. 307-317. Springer Berlin Heidelberg, 2002. http://lambda.csail.mit.edu/~chet/papers/others/l/lassila/lassila-iswc2002.pdf
[23] : De Abreu, Domingo, Alejandro Flores, Guillermo Palma, Valeria Pestana, Jose Pinero, Jonathan Queipo, Jose Sanchez, and Maria-Esther Vidal. “Choosing Between Graph Databases and RDF Engines for Consuming and Mining Linked Data.” In COLD. 2013. http://ceur-ws.org/Vol-1034/DeAbreuEtAl_COLD2013.pdf
[24] : Hellman http://go-to-hellman.blogspot.de/2009/11/blank-node-bother-and-rdf-copymess.html
[25] : Apache Jena Elephas https://jena.apache.org/documentation/hadoop/io.html#global-blank-node-identity
[26] : Lantzaki, Christina, and Yannis Tzitzikas. “Tasks that Require, or can Benefit from, Matching Blank Nodes.” arXiv preprint arXiv:1410.8536 (2014).http://arxiv.org/pdf/1410.8536.pdf

blog comments powered by Disqus