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 15:22:14 -0700
Message-ID: <1127168534.689248.131360@g43g2000cwa.googlegroups.com>

vc wrote:
> Vadim Tropashko wrote:
> > As it has been written elsewhere, Nested Intervals gradually evolved
> > into matrix encoding. To summarize, each node of a tree is encoded with
> > 4 integers, which translates into the following schema design:
> >
> > table MatrixTreeNodes (
> > a11 integer,
> > a12 integer,
> > a21 integer,
> > a22 integer
> > );
> >
> > As the title of the message says, there is adjacency list relation
> > hidden there!
>
>
>
> It's not surprising since you maintain a sort of materialized path in
> every node containing pairs (parent, child), So given a path 1.2.3.4,
> in order to access the fifth sibling just use 1.2.3.5, that's all.
> Much simpler than the matrix encoding.

I don't follow. In adjacency relation there is an explicit foreign key constraint from child_id to parent_id. 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.

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

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! Received on Mon Sep 19 2005 - 17:22:14 CDT

Original text of this message

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