Re: matrix encoding IS adjacency list

Vadim Tropashko wrote:
> VC wrote:
> > It's not. We do not need a separate colum, the parent id can be extracted
> > from a node m.p. using a function ( 'parent(materialized_path)' ).
>
> At the risk being annoying, formally, materialized path is not an
> adjacency relation. For one thing, materialized path schema design
>
> table (
> path varchar(1000)
> )
>
> has only one column, while for adjacency relation you need at least
> two.

The m.p. encoding does contains adjacency information (plus some more). Saying that it does not is sort of denying the obvious. Moreover, if need be, the m.p. can be split into two parts: the parent path/aka a parent id and the node id, but I do not see a substantial difference except perhaps improved performance implications.

> Matrix encoding has more than enough columns - 4. (Well, object
> propellerheads might insist there is only one:-)
>

Speaking of which, it's enough to have only three columns because the parent id can easily be reconstructed from the disambiguated child id which is nothing but a diguised m.p. Clearly, the matrix encoding parent id is a performance trick very much in the same fashion as it is with the m.p. encoding augmented with an extra column.

I am not saying that the matrix encoding is devoid of any merit, just that I have not seen a convincing argument in its favour just yet.

> Materialized path encodes the global position of a node in a hierarchy,
> so that you can derive all the nodes in the local neighourhood. The
> adjacency relation, however, is encoded implicitly, not like explicit
> foreign key constraint.

I am not sure why you keep talking about referential integrity constraints whose role is, well, to enforce integrity and as such unrelated to the way we want to represent a hierarchy, be it an a.l., m.e. or something else. What's explicit, though, is having the child/parent ids in separate columns, something which is not a dogma but a practical consideration. Besides, see my comment about storing the path prefix (a parent id) and the node id in separate columns.

> In a word, you can prove your point if you show
> how to declare foreign key constraint.
>AFAIK, foreign key constraints
> can't be declared on derived columns.

1. See my comment about separating the m.p. into two columns.
2. The impoverished constraint tool set 'modern' database vendors, such as Oracle, offer does not allow one to implement something slightly more complicated than a unique/not null/or referential constraint, it's true. E.g. the simplistic CHECK constraint does not allow subqueries.

However, even in this case one can find a work around, without splitting the column into the parent/child pair, namely implementing an m.p. referential constraint via a trigger. I am sure you know how. Received on Tue Sep 20 2005 - 19:43:24 CEST