Re: the state of ldp-patch, and a procedural proposal

On 10/18/2013 08:13 AM, Pierre-Antoine Champin wrote:
> Alexandre, all,
>
> first thanks for this nice review.
>
> It seems that my own proposal [1] has gone completely unnoticed.
> I'm not taking this personnally, but I would like to hear the feedback
> of the group on this idea, especially the handling of RDF lists, which I
> think are not covered by any of the proposals mentionned by Alexandre.
>

Effectively, nothing personal, but my apologies for missing yours. I've 
created a wiki page with my summary and have already added yours [2].

Generally, I like this approach. I do like the handling of rdf:list
(despite what the SPARQL crowd says, rdf:list are awesome!) but I
still need to think more about it. It is not a subset of SPARQL Update
but having property paths is already a good way to access some bnodes
without referring to them. I would prefer to avoid relying on
skolemization. The B (Bind) idea looks simple. I believe this can
easily be combined with the simple BGP + nailed nodes approach.

I see emerging several trends:

* 2 kind of syntaxes: SPARQL Update subset or RDF PATCH derivatives

* skolemizing bnodes VS matching bnodes

* expressive power, ie. how powerful and complex the BGP can be

* support of specific features, eg. rdf:list

Maybe we can have polls to make progress? I believe that the very
first question to answer is about skolemization.

Alexandre.

[2] 
http://www.w3.org/2012/ldp/wiki/LDP_PATCH_Proposals#Pierre-Antoine_Champin.27s_RDF-PATCH



>    pa
>
> [1] http://lists.w3.org/Archives/Public/public-ldp-patch/2013Sep/0022.html
>
>
> On Fri, Oct 18, 2013 at 4:57 AM, Alexandre Bertails <bertails@w3.org
> <mailto:bertails@w3.org>> wrote:
>
>     Hi guys,
>
>     I've been playing with different approaches around LDP PATCH. I wanted
>     to provide some feedback, both from the user's perspective and from
>     the implementer's perspective.
>
>     As a user, I'm among the people interested in implementing a
>     Decentralized Social Web using a vanilla/generic LDP server, with
>     WebID and WebACL. I've mainly focused my own experiments with being
>     able to patch WebID profiles. So far in the read-write-web server,
>     we've been using full SPARQL but we are interested in a lighter PATCH
>     format which would not rely on external libraries.
>
>     On 09/14/2013 09:40 PM, Sandro Hawke wrote:
>      > There have been some good emails on public-ldp-patch, and there
>     was some
>      > good discussion at F2F4.   Here's where I think we are.   I don't
>     know
>      > of anything in this email that anyone would disagree with (that
>     is, I'm
>      > trying to summarize consensus), and I end with a suggested path
>     forward.
>      >
>      > I think the biggest challenge we face -- and the challenge that
>     divided
>      > me and Eric at the meeting -- is how to patch triples that
>     involve blank
>      > nodes.   There seem to be two approaches:
>      >
>      > 1.  Require the client to create a graph pattern (a "where clause")
>      > which unambiguously identifies the blank nodes involved in the
>     triples
>      > to be updated, and require the server to use that graph pattern
>     to find
>      > those blank nodes in the graph being patched.
>      >
>      > 2.  Require that during the conversation that ends up involving
>      > patching, both parties use the same mapping from blank node labels to
>      > blank nodes.
>      >
>      > Option 1 is a good fit for SPARQL.   SPARQL servers naturally do that
>      > graph matching.  In contract, standard SPARQL servers don't have
>     any way
>      > to share blank node scope as required for option 2. That kind of
>      > exposure of blank node labels has traditionally been avoided in the
>      > design of RDF systems.
>
>     General remark: Linked Data (in LDP) is different from general RDF:
>     the data lives in "small" HTTP documents, not in "big" RDF store. I
>     believe that the problem that SPARQL Update addresses is quite
>     different from what we want to achieve with LDP PATCH. Because of
>     that, I was against considering a subset of SPARQL Update at first,
>     but Eric and my experiments made me change my mind.
>
>      >
>      > However, the worst-case performance with option 1 is exponential.
>     If a
>      > triple to be updated is in the middle of a large cloud of blank
>     nodes,
>      > then matching the where-clause might not be possible before we
>     all die
>      > of old age.  (It's an extremely well studied problem in computer
>      > science; I'm not an expert, but I think I'm reading the results
>     correctly.)
>
>     Following Eric's lead, I've actually started with the BGP approach:
>     DELETE + INSERT + WHERE-with-simple-BGP. To address the complexity
>     issue, I think we can always add some restriction on the BGP. In
>     practice, it depends on the expressive power the people are expecting
>     for a PATCH.
>
>      >
>      > No one has offered data about how often this worst-case behavior
>     might
>      > be a problem in practice.  Arguably we're still in the early days, so
>      > it's too soon to know how painful this restriction might turn out
>     to be.
>      >
>      > Some people said that the server can just set a time limit and reject
>      > patches that end up taking too long.   Other people (me) replied that
>      > makes the overall system too unpredictable, that systems should
>     be able
>      > to send patches with confidence, especially one server to
>     another.  As I
>      > said at the meeting, I don't know if this worst-case performance will
>      > turn out to be a problem, but I'm concerned enough about it that
>     I can't
>      > +1 option 1, and don't want my name on a spec based on it.  David
>      > reported at the meeting that Google's internal culture generally
>     forbids
>      > using exponential algorithms, so we might expect if they were in the
>      > group they would formally object to option 1 (or just decide to never
>      > use it, which amounts to the same thing).  Our anecdotal reports that
>      > they don't use SPARQL support this hearsay, but as long is it remains
>      > hearsay, we probably shouldn't take it too seriously.
>      >
>      > Which brings me to the proposal.
>      >
>      > Let's move forward with both Option 1 *and* Option 2, marking
>     them both
>      > "at risk" in the spec.   That gives us the whole Last Call and
>     Candidate
>      > Recommendation periods to gather input on how bad the exponential
>      > performance issue is for Option 1 and how bad the implementation
>      > challenge is for Option 2 (how hard it is to get RDF systems to share
>      > scope in blank node labels).
>      >
>      > Then at the end of CR, we can decide if either of them is good
>     enough to
>      > normatively reference as the basic LDP patch format.   If they
>     both end
>      > up implemented and with people liking them, then we just pick one, so
>      > the folks don't have to implement both going forward.    If
>     neither of
>      > them is implemented and liked, then we're back to where we are today,
>      > with no standard patch format for LDP, but some more data on why
>     it's hard.
>      >
>      > How's that sound?
>      >
>      > I imagine Option 1 would end up as some subset of SPARQL Update, like
>      > TurtlePatch  [1] plus variables or like Eric presented at the
>     meeting. I
>      > imagine for Option 2 we'd have something like Andy and Rob's RDFPatch
>      > [2] or my old GRUF [3] (which I'd forgotten about until reading
>     RDFPatch).
>
>     Here is my reviews on [1] and [2] and some other proposals. Take into
>     account that I didn't participate in the conversations on LDP PATCH
>     and that there is to knowledge no page gathering all the proposals.
>
>     TurtlePatch
>     -----------
>
>     Champion: Sandro
>
>     Summary: subset of SPARQL Update with INSERT and DELETE clauses.
>
>     Example:
>
>     [[
>        PREFIX foaf <http://xmlns.com/foaf/0.1/>
>        PREFIX s <http://www.w3.org/2000/01/rdf-schema#>
>        DELETE DATA {
>          <http://www.w3.org/People/Berners-Lee/card#i> foaf:mbox
>     <mailto:timbl@w3.org <mailto:timbl@w3.org>>
>        }
>        INSERT DATA {
>          <http://www.w3.org/People/Berners-Lee/card#i> foaf:mbox
>     <mailto:timbl@hushmail.com <mailto:timbl@hushmail.com>>
>          <http://www.w3.org/People/Berners-Lee/card> s:comment "This is my
>     general description of myself.\n\nI try to keep data here up to date and
>     it should be considered authoritative."
>        }
>     ]]
>
>     Pros:
>     * can be implemented using full SPARQL implementation
>     * easy to implement from scratch (parser + runtime)
>
>     Cons:
>     * no support for bnodes
>
>     Status:
>     * I implemented this approach in Banana-RDF
>
>     Remark: Sandro talked about "TurtlePatch plus variables" but I'm not
>     sure what that means exactly by reading his spec. Until I see a
>     solution properly considering bnodes, it will be a -1 for me.
>
>     RDF Patch
>     ---------
>
>     Champion: Andy Seaborne
>
>     Summary: diffs for RDF dataset
>
>     Example: (A is for Add and D for Delete)
>
>     [[
>        A <http://example.org/alice> <http://xmlns.com/foaf/0.1/name>
>     "Robert" .
>        A <http://example.org/bob> <http://xmlns.com/foaf/0.1/knows>
>     <http://example/alice> .
>        A <http://example.org/alice> <http://xmlns.com/foaf/0.1/name>
>     "Alice" .
>        D <http://example.org/bob> <http://xmlns.com/foaf/0.1/name>
>     "Robert" .
>        A <http://example.org/bob> <http://xmlns.com/foaf/0.1/name> "Bob" .
>     ]]
>
>     Pros:
>     * easy to implement from scratch (parser + runtime)
>
>     Cons:
>     * specified for an RDF dataset, not an LDPR
>     * blank nodes are system dependant, so not well specified in the case
>         of LDP
>
>     Remark: actually pretty much the same than TurtlePatch, but it feels
>     like it was written for a different use-case. I don't understand how
>     LDP is supposed to communicate stable bnodes label for that solution
>     to work. So -1 again for me.
>
>     EricP's proposal (sorry, don't have a better name)
>     ----------------
>
>     Champion: EricP
>
>     Summary: SPARQL subset with DELETE, INSERT and WHERE clause. The WHERE
>     clause is restricted to a simple BGP with no var-predicates.
>
>     Example:
>     [[
>     PREFIX foaf: <http://xmlns.com/foaf/0.1/>
>     DELETE { ?s foaf:name "Alex" }
>     INSERT { ?s foaf:name "Alexandre" }
>     WHERE { ?s foaf:name "Alex" }
>     ]]
>
>     Pros:
>     * can be implemented using full SPARQL implementation
>     * in practice, still easy enough to implement from scratch (parser +
>     runtime)
>     * can be used to reach some bnodes
>
>     Cons:
>     * some queries can be NP-complete (would be good to document one
>         example)
>
>     Status:
>     * I implemented this approach in Banana-RDF
>
>     Remark: one could argue that in practice, LDPRs are not supposed to be
>     crazy big, and that most queries won't end up with the worst-case
>     complexity. But I do share the concerns. So it's a +1 for me if the
>     group wants to go with it, with some reservations about the
>     complexity.
>
>     EricP's proposal + pinned nodes
>     -------------------------------
>
>     Champion: TimBL
>
>     *note: TimBL used another term that "pinned node" but I cannot
>        remember it right now :-/ Please someone (Tim?) help me.
>
>     Summary: same as previous one, but the BGP returns a single matching
>     node. Some additional constraints are put on the query. TimBL wrote
>     the algorithm on the whiteboard for me and it made sense.
>
>     Pros:
>     * can be implemented using full SPARQL implementation
>     * in practice, still easy enough to implement from scratch (parser +
>     runtime)
>     * can be used to reach some bnodes
>     * expected not to be NP-complete
>
>     Cons:
>     * we further restrain the number of bnodes that can be
>         matched. Shouldn't be an issue in practice.
>
>     Status:
>     * I implemented a similar restriction in Banana-RDF when the BGP is a
>         tree pattern.
>     * TimBL told me that Tabulator already implements that approach.
>
>     Remark: it's a refinement of EricP's proposal. The specifics still
>     have to be worked on but I like the general idea about constraining
>     the BGP. Another +1 for me, but I obviously prefer this one on
>     EricP's.
>
>     Joe Presbrey's PATCH
>     --------------------
>
>     Champion: Joe Presbrey
>
>     Summary: format is Turtle. For each triple { s p o }, { s p ANY } is
>     deleted and { s p o } is added. His implementation forbids the use of
>     blank nodes.
>
>     Pros:
>     * super easy
>
>     Cons:
>     * can't have { s p o1; o2 } anymore
>     * no bnodes
>
>     Status:
>     * Joe implemented this approach in one of his projects (I guess either
>     data.fm <http://data.fm> or ldpy)
>
>     Remarks: it's too destructive and doesn't handle bnodes, so -1.
>
>
>
>     In summary, it looks like people are ok to consider a subset of
>     SPARQL. Also, I believe that we cannot ignore the bnodes out there and
>     LDP PATCH must provide an acceptable solution for them. I personally
>     found EricP's proposal easy to implement, so that's a clear
>     candidate. Like others, I'm sensitive to the complexity issue and I
>     believe that some additional constraint on the BGP should avoid the
>     pitfall, so I'm interested in TimBL's idea from Tabulator.
>
>     At that point, I believe that the most compelling proposal is EricP's
>     with TimBL's constraint. If the group shows interest, I'd be
>     interested in writing a first draft of the spec.
>
>     What do you guys think?
>
>     Alexandre.
>
>      >
>      >      -- Sandro
>      >
>      > [1] http://www.w3.org/2001/sw/wiki/TurtlePatch
>      > [2] http://afs.github.io/rdf-patch
>      > [3] http://websub.org/wiki/GRUF (from Apr 2010)
>      >
>      >
>      >
>      >
>
>
>

Received on Friday, 18 October 2013 14:05:10 UTC