Re: Path lengths and TMQL

Hi Robert,

On 4 Apr 2011, at 6:21 PM, Robert Barta wrote:

> On Mon, Apr 04, 2011 at 12:02:20PM +0100, Andrew S. Townley wrote:
> 
>> I've been doing some reading on path languages, graph queries,
>> etc. over the last few days and I was wondering why the notion of
>> the path length wasn't included in any of the drafts I've seen.  If
>> you could qualify the depth of the search of the path expressions,
>> it seems like our disagreement over how to reference "direct" vs
>> "indirect" links of type X might disappear.
> 
> That would work, although most people would probably resort to either
> 
>   $p >> types(1)    # direct type
> 
> or
> 
>   $p >> types(*)    # any type
> 
> In terms of store mechanics, allowing
> 
>   $p >> types(23)
> 
> can be quite challenging to implement effectively once you deal with
> serious data.
> 
> So this brings us a only a bit forward.
> 
> \rho


Probably true for types, but I was looking at types as really a specialization of any kind of nested structure, e.g. containment or any other potentially recursive associative type of relationship.  In this case, if you were doing things like looking for how many people had great-grandparents who were still living or parts no more than X assemblies deep in a particular parts explosion, I'd think being able to expressly quantify the path depth of these relationships would allow pretty significant query optimization potential, provided you could find the right indexing mechanism.

I've spent most of the day doing some data structure analysis on some of the real data I've been using lately to see how this relates to some of the literature I'm reading.  Generally, my data has a high indegree and relatively low outdegree with not a lot of deep tree structures--except where I'm talking about containment type relationships (of which I would view superclass-subclass as a special case).

Having also now had the opportunity go through your 2008 draft and supporting material in more detail vs. some of the other graph/path query languages I've seen, I think TMQL @rho is actually relatively straightforward to implement in terms of the abstractions I already have (yay!), but I haven't seen any good way to do depth-based result pruning/optimizations by default.

It seems to me that it's one of those things that most of the time you won't need, but when you need it, you *really* need it. :)

Thanks for your thoughts, and I agree with you that this kind of segmentation does get tricky with large data.  Things like GRIPP[1][2] and some of the MS research[3] might make a difference, though.

ast

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.134.6128&rep=rep1&type=pdf
[2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.439&rep=rep1&type=pdf
[3] http://research.microsoft.com/pubs/144985/TODSFinal.pdf
--
Andrew S. Townley <[email protected]>
http://atownley.org