- From: Andy Seaborne <andy@apache.org>
- Date: Wed, 11 Sep 2013 09:28:24 +0100
- To: public-ldp-patch@w3.org
On 08/09/13 17:00, Sandro Hawke wrote: > On 09/08/2013 06:33 AM, Andy Seaborne wrote: >> On 08/09/13 04:17, Sandro Hawke wrote: >>> In theory, patching a large branching subgraph of blank nodes is >>> intractable. It's the graph isomorphism problem, which has >>> complexity NP. >>> >>> I think rdf lists don't have this problem, at least with a clever >>> implementation, because the subgraph of blank nodes doesn't >>> significantly branch. >>> >>> I wonder if there are many RDF graphs that do have this problem. I can >>> easily imagine paths which are 2-4 blank nodes deep, coming out of >>> record structures that are mapped to RDF, but even an exponential search >>> is okay when the exponent is only 4. The question is: are there, in >>> practice, subgraphs where you have to traverse 20 or 30 blank nodes, >>> with branching, to get to the part you need to alter? If we don't know >>> of any, how confident are we there won't be any real need for them? >>> >>> Also, do SPARQL systems handle rdf:lists efficiently enough? Can I >>> append to an rdf:List like this: >>> >>> DELETE { ?last rdf:rest rdf:nil } >>> INSERT { ?last rdf:rest ( :NewLastElement ) } >>> WHERE { :myList :myProp ?n1. ?n1 rdf:rest ?n2. ?n2 rdf:rest ?n3. >>> ..... rdf:rest ?last } >> >> rdf:rest* >> Arbitrary length path. >> >> DELETE { ?last rdf:rest rdf:nil } >> INSERT { ?last rdf:rest ( :NewLastElement ) } >> WHERE { :myList :myProp ?list . >> ?list rdf:rest* ?last . >> ?last rdf:rest rdf:nil } >> > > Sorry, I should have disallowed that shortcut. Please consider my > question to be about inserting an element n items into a list that's > much longer. Also, assume the items in the list are all the same, so > you can't use value-matching to find the desired spot in the list. > > So there really would have to be n variables. Do you know how typical > SPARQL systems will do with thousands of variables like that? > Let's make it a bit more tricky - insert at the midpoint of a list, defined as insertion after the floor(N/2)-th element. That includes at the head, which is always different to other insertions (need to find the triple(s) that have the list as object). Neither the examples above work for a list of length zero. We need pointers to nodes in RDF! (There is a trick to avoid needing the list length explicitly.) Andy
Received on Wednesday, 11 September 2013 08:28:53 UTC