efficient List handling

On Wed, 2012-02-01 at 13:23 +0000, Andy Seaborne wrote:
> 
> On 01/02/12 13:03, Sandro Hawke wrote:
> > On Wed, 2012-02-01 at 10:43 +0000, Steve Harris wrote:
> >> On 2012-02-01, at 00:23, Sandro Hawke wrote:
> >>> On Fri, 2012-01-27 at 12:27 +0000, Steve Harris wrote:
> >>>> On 2012-01-27, at 10:35, Ivan Herman wrote:
> >>>>> On Jan 27, 2012, at 10:33 , Andy Seaborne wrote:
> >>>>>> On 27/01/12 03:45, Sandro Hawke wrote:
> >>>>>>> On Thu, 2012-01-05 at 11:09 +0000, Andy Seaborne wrote:
> >>>>>>>> On 04/01/12 19:23, David Wood wrote:
> ...
> 
> >>>> I bought this kind of argument with RDF Lists (collections), and accessor functions - storing the lists natively, and also reflecting them into triples. Coming up with an implementation that was both correct and efficient turned out to be so hard that we gave up, and just elected not to use Lists in production.
> >>>
> >>> I'm sad to hear about this experience with lists.  Sometime I'd like to
> >>> hear more about why that was so hard.   (Have you folks
> >>> written/presented about it?)
> >>
> >> No, but I think I mentioned it at the last F2F.
> >>
> >> In essence, to make it have anything like decent performance you have to maintain a parallel copy of the list structure in a vector (of some kind), and tracking changes in the triples, and updating the vector appropriatly (and vice versa, if you allow useful list manipulation functions) is /extremely/ difficult, and computationally expensive, especially at scale. Quite simply, it's just not worth the effort.
> >>
> >> I believe Andy said something similar too.
> >
> > Do your systems do inference, eg RDFS?   I'm guessing not.
> 
> Yes, they do and it does not make any difference.
> 
> There is no list membership property and if there were, it does not 
> preserve order, which is the point of a list.
> 
> rdfs:member does not apply to lists.
> 
> > My sense is
> > that given the machinery for doing fairly-simple inference, this kind of
> > list handling isn't bad.
> 
> Please give the details.  I don't see it.

If you don't mind, I'm going to back burner this.   It's very
interesting to me, but probably doesn't help us with graphs.  I'm not
sure if it helps with anything else the WG is going to do.

   -- Sandro

Received on Wednesday, 1 February 2012 14:17:39 UTC