W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > April to June 2010

Re: [TF-PP] Moving forward

From: Matthew Perry <matthew.perry@oracle.com>
Date: Wed, 9 Jun 2010 05:40:19 -0700 (PDT)
Message-ID: <5b6ec87b-eb13-461a-a7ea-c8b2e79d734c@default>
To: <andy.seaborne@talis.com>
Cc: <public-rdf-dawg@w3.org>
Thanks for the summary Andy.

I do not like the triple marking with backtracking/unwinding approach to determine the cardinality for arbitrary length paths. I think this will be too hard to implement efficiently on systems that store graphs on disk. Using "distinct" or "no node repetition" semantics, most property path queries can be evaluated efficiently in a DBMS using recursive SQL, but the triple marking approach is a different story and would most likely require a really convoluted representation on disk. Since we are only talking about differences in cardinality of results, I worry that the elegance of the formalization may not justify the additional burden on developers. 

Cheers,
Matt  

----- Original Message -----
From: andy.seaborne@talis.com
To: public-rdf-dawg@w3.org
Sent: Wednesday, June 9, 2010 8:15:06 AM GMT -05:00 US/Canada Eastern
Subject: [TF-PP] Moving forward

To summarise where I think we are:

1/ Use the expansions approach that Birte proposed in:
http://lists.w3.org/Archives/Public/public-rdf-dawg/2010AprJun/0293.html

2/ Define operators for zero length paths and for arbitrary length paths 
(i.e. +).

2a/ zero length paths include all subjects/objects/constant terms as 
possible bindings (and check this makes sense).

2b/ arbitrary length paths based on triple marking with 
backtracking/unwinding.  Define the operator by algorithm (of course, 
you can implement anyway you want but this defines the correct answers 
and cardinality).

3/ Need to compare the cardinality for arbitrary length paths and {n,m} 
forms since they should agree, and if not, we need to understand why 
(this is why I think the triple marking with unwinding is the way to go)
It may make sense to define {n,m} in terms of the arbitrary length paths 
algorithm.

4/ Examples, examples, examples.

	Andy
Received on Wednesday, 9 June 2010 12:41:08 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:42 GMT