Patch Issue: Blank Nodes and Tractability

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 }

where the chain is 20 or 200 or 2000 or even 20,000 elements long and 
have the the system handle it comfortably?

If the answers to the above questions are not good, then we might want a 
patch format that sidesteps the whole problem, for instance by having a 
limited way to refer to blank nodes in the protocol. For example, 
patches are often written relative to a particular resource 
representation, pointed to by an ETag.   I don't see any technical 
reason the patch couldn't say "I'm using the same blank-node-names as 
that representation does", and if the server cares enough to retain that 
mapping, it can do patch processing in linear time.

         -- Sandro

Received on Sunday, 8 September 2013 03:17:50 UTC