PatchRequirements
This is for discussion among public-ldp-patch@w3.org folks. No decisions have been made. Don't rely on the numbers -- they'll change when people edit this page.
If you care, please add vote and comment lines. Votes: +1 this should be a requirement, +0 this should be considered desirable but not required, -0 this isn't even desirable, -1 this would make the system not usable for me. Syntax like:
sandro: +1 in product foo we've been using this, and need it
Proposed Requirements:
Syntax
Human Readable
Patches need to be fairly humanly readable, like Turtle or SPARQL, more than N-Quads or RDF/XML.
SPARQL Syntax
Patch syntax is a subset of SPARQL Update syntax.
Example:
PREFIX foaf <http://xmlns.com/foaf/0.1/> DELETE DATA { <http://www.w3.org/People/Berners-Lee/card#i> foaf:mbox <mailto:timbl@w3.org> } INSERT DATA { <http://www.w3.org/People/Berners-Lee/card#i> foaf:mbox <mailto:timbl@hushmail.com> }
Probably only makes sense if the semantics are the same as SPARQL's, for the given expressions. Unclear how to provide metadata.
Dataset Syntax
Patches are expressed in RDF Datasets (quads). As such, they can be transmitted in TriG and stored in quad stores (perhaps with a little munging of graph names).
In TriG it might be serialized like:
PREFIX : <http://www.w3.org/ns/ldppatch#> [ a :BasicPatch; :startETag "fa65e4c5ad0e5f7a94337910847bd10f7af10c74"; :delete _:d1; :insert _:i1 ].
GRAPH _:d1 { <http://www.w3.org/People/Berners-Lee/card#i> foaf:mbox <mailto:timbl@w3.org > } GRAPH _:i1 { <http://www.w3.org/People/Berners-Lee/card#i> foaf:mbox <mailto:timbl@hushmail.com> }
Streaming
Patches can be processed in a single pass, using much less memory than it takes to store large patches.
Metadata
Syntax includes a way to include arbitrary metadata about patches.
End-State ID
Sender can say what the ending state ID is.
For example, Alice and Bob both know the exact graph which is the state of resource R, with etag "v1". Alice sense Bob a patch to change it to a new state. Does Alice get to tell Bob, as part of that patch, what she wants the new etag to be?
Packaging
A single patch document may contain multiple patches, which can fail or succeed independently, and are processed as separate transactions, if ACID properties are being provided.
Compact
Patches are smaller than just sending the triples to be deleted and the triples to be added (in some normal RDF syntax).
General
Universality
Given any two RDF Graphs, G1 and G2, it is possible construct a patch from G1 to G2
Tractability
All operations are tractable (that is, can be done in polynomial time and space with respect to the inputs).
This is not easy with RDF, because subgraph matching involves the NP Graph Isomorphism Problem. More intuitively for some people, a database WHERE clause can easily have a combinatorial explosion in the number of matches, so a patch involving WHERE matching might take a very long time to process.
Can be broken into:
- It is possible to construct a tractable patch, for any pair of graphs
- It is tractable to construct a tractable patch, for any pair of graphs
- All patches are tractable, for any pair of graphs
Atomicity
Patches are "all or nothing". If the patch fails in some way, then no change is done.
Either all patches are atomic, or a patch can be flagged as requiring atomic processing.
Isolation
Patches appear to other systems to be applied all at once.
Either all patches are processes in isolation, or the client can ask that they are.
Durability
Once a patch has been confirmed as processed, the client can assume it will not be lost, eg due to power failure or software crash.
Rigidity
Patches may be expressed as working only against a given start graph.
If a rigid patch says some triples are to be deleted, and any of them are not present, the patch is rejected.
Blindness
Patches may be expressed as working against any graph, where the patch constructor doesn't exactly know the content of the graph. Might just be adding triples, regardless of the graph. Might use wildcards or variables.
If a blind patch says some triples are to be deleted, and they are not present, the patch process continues anyway.
Concurrency
Systems are allowed to handle multiple rigid patches to the same start graph via some kind of safe merging. For example, two patches that each add triples can both be handled.
(Concurrent blind patches are not an issue, since they don't specify the start graph.)
Turing Complete
Patches need to be able to make arbitrary, smart, blind changes by including code which runs on the server, using the state of the resource at the time of processing.
Functionality
Wildcards
Patches may include wildcard terms, like "delete { * :p * }" to delete all triples using predicate :p. Weaker/simpler than full variables.
Variables
Patches can be written with variables. Relates to All-Matches and Wildcards, but different. Tends to create combinatoric explosion, making processing intractable.
Variables might be explicit, or blank nodes might be treated as variables, or both.
Variables which occur only in inserted triples (not in delete or where) are probably to be interpreted as fresh blank nodes.
Repeated Matching
Patches can be written which operate against all matching triples, possibly with combinatoric explosion. Alternatively, patches might only process one match and then stop.
(This only matters if there are some kind of variables.)
Node Renaming
Patches may express that some node is to be replaced, wherever it occurs, with some other node.
List Operations
Well-formed RDF lists can be manipulated (insert & delete) by simple instructions in a patch.
String Operations
If there's a triple like { :s :p "This is a very, very long string." }, the string can be modified in a patch without sending all the new text of the string.
Something like replace_substring(:s, :p, 1, 3, "hat") would change the above triple to { :s :p "That is a very, very long string." } (assuming there were no other { :s :p ?x } triples in the store.
Node Renumbering
See http://lists.w3.org/Archives/Public/public-ldp-patch/2013Sep/0009.html near the word "range".
__NUMBEREDHEADINGS__