Re: Patch Issue: Blank Nodes and Tractability

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