Re: matrix encoding IS adjacency list

David Cressey wrote:
> "Vadim Tropashko" <vadimtro_invalid_at_yahoo.com> wrote in message
> news:1127168534.689248.131360_at_g43g2000cwa.googlegroups.com...
>
> > Trivial with adjacency list.
>
> What does this mean?

... finding all the children for a given node is easy with the adjacency list encoding:

Given a relation R (parent, child) implementing an a.l. :

{ (a, {}), (a,b), (x,y), (b,x), (b,c) },

a query might look: select * from R where parent = b

Using an m.p. encoding ( R(m_p) we would have { 'a', 'a.b', 'x.y', 'a.b.x', 'a.b.c' }

and the query might be: select * from R where parent(m_p) = 'a.b', with parent(m_p) being a user function extracting the parent prefix for a given node. Alternatively, one can include an extra 'parent' column to speed up this sort of queries, or use some other performance trick. Received on Tue Sep 20 2005 - 15:15:37 CEST