Re: matrix encoding IS adjacency list

"Vadim Tropashko" <vadimtro_invalid_at_yahoo.com> wrote in message news:1127186069.165059.38590_at_g14g2000cwa.googlegroups.com...
> VC wrote:
>> "Vadim Tropashko" <vadimtro_invalid_at_yahoo.com> wrote in message
>> news:1127179828.730374.139640_at_g14g2000cwa.googlegroups.com...
>> > This terminology is blamed on Celko:-) Seriously, we are talking about
>> > the relation analogous to adjacency matrix.
>>
>> Please explain.
>
> http://en.wikipedia.org/wiki/Adjacency_matrix
>
> ???

Did you read the reference you've supplied ? The a.m. is just an NxN matrix for N nodes with a bunch of zeroes for non-adjacent vertices. The a.l. is an optimization if an a.m. is sparse, Both contain the same information. How does the definition you've referenced answer my request for clarifiication of "... we are talking about the relation analogous to adjacency matrix" ?

>
>> > 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'
>> >
>>
>> Well, nothing is for free. For certain queries, an m.p. encoding may
>> cause
>> performance issues that can be resolved by maintaining a
>> separate/redundant
>> parent attribute, creating a function-based index, or using the real
>> adjacency list encoding.
>
> That's what the programmers in the field say: "Let's combine nested
> intervals/sets with adjacency list to have the best of both worlds.
> Little data redundancy would help speeding up some queries". It is not
> obvious that for matrix encoding you gain exactly nothing this way.

Do you mean that we gain something or that we gain nothing by adding the parent id (adjacency list) ?

>
>> Still, you did not show how the referential constraint helps with
>> finding
>> immediate children in the matrix encoding.
>
> Find all the children of [[15,-2],[8,-1]]:
>
> select * from MatrixNode
> where a12 = -15 and a22=-8
>

1. What does the example have to do with either having or not having a constraint ?
2. That's what I wrote in my prev. message since (a12, a22) are just a parent id.

>> I can see how you would use the parent pair of numbers, of course. Btw,
>> the pair is redundant: it can be deduced from the child pair if
>> disambiguated by a boolean value indicating which, out of two, rational
>> encoding you want to use.
>
> No need to disambiguate. (a11, a21) is a unique key, if matrices with
> determinant 1 are used.

The [ambiguous] materialized path is represented by (a11, a12) if I understand your encoding correctly. The parent id, (a12, a21) is used to disambiguate (a11,a12).

How is it better than specifying explicitely both the m.p. and the parent id ?

>They correspond to monothonic continues
> fractions, see last section in the june sigmod record article.
> Unfortunately, those matrices can't be arranged into a nice number
> wall:-)
>
Received on Tue Sep 20 2005 - 12:22:57 CEST