Re: matrix encoding IS adjacency list

VC wrote:
> OK, at first you talked about an adjacency list, but no matter. Let
> a,b,c,d,e be some nodes. Then an adjacency list for some DAG/tree might be
> a set of pairs:
>
> {(a, {b,c}), (b, {d,e}) or, equivalently, {(a,b), (a,c), (b,d), (b,e)}
>
> In the RM, an adjacency list is usually emulated by a (child, parent,
> data) relation with the 'child' attribute being the primary key. One can
> enforce a referential integrity constraint if need be, but that's although
> desirable is not required in order to express a hypothetical tree topology.

This terminology is blamed on Celko:-) Seriously, we are talking about the relation analogous to adjacency matrix.

> >Where do you see this constraint
> > with materialized path encoding? In other words, given parent node
> > materialized path encoding, how do I find all the (immediate) children?
> > Trivial with adjacency list.
>
> It's as trivial with a materialized path: in the above example in order to
> find all node a.b 's children, just say 'find tuples where
> prefix(materialized_path) = a.b'.

Nope. You query looks for descendants, not (immediate) children. You can say: "aha, just add a postfilter", or in other words find all the descendants, that are on the next level, but that is not guaranteed to be efficient. For the root node the descendants index scan would return the whole hierarchy, and then you'd have to filter out almost all of them.

> > Referring to the problem of (a11,a21) being not unique, I actually
> > figured it out. There are exactly 2 nodes with the same (a11,a21). This
> > follows from the equation
> >
> > a11*a22-a21*a12 = 1 or -1
>
> This actually follows from the fact that a rational number, as a continued
> fraction, has two encodings (if we are talking about the same thing).

Yes

> > It is possible to amend matrix encoding in such a way that determinant
> > of [[a11,a12],[a21,a22]] matrix is always 1. Then, (a11,a21) is unique,
> > and we can decare foreing key constraint. Matrix encoding IS adjacency
> > list!
>
> Of course it is, m.e being a materialized path encoding. You seem to imply
> that the constraint makes finding, say, all the immediate children somehow
> easier compared to the constraint-less search. Could you please elaborate ?

Once again, your query should be written as

'find tuples where prefix(materialized_path) = a.b and length(materialized_path)=3'

which is not the same as

'find tuples where parent_id = 5' Received on Tue Sep 20 2005 - 03:30:28 CEST