Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: matrix encoding IS adjacency list

Re: matrix encoding IS adjacency list

From: Vadim Tropashko <vadimtro_invalid_at_yahoo.com>
Date: 19 Sep 2005 20:14:29 -0700
Message-ID: <1127186069.165059.38590@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

???

> > 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.

> 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

> 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. 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 Mon Sep 19 2005 - 22:14:29 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US