Re: Hierarchical queries and indexes

Troels Arvin <troels_at_arvin.dk> wrote in message news:<pan.2004.10.05.11.46.48.266310_at_arvin.dk>...
> Should such encondings really belong on explicit table columns? Aren't
> the different encodings actually specialized indexes which ought to exist
> as such?
>
> My thought is that it should be possible to create a table like
>
> CREATE TABLE ancestor (
> fullname VARCHAR(100) PRIMARY KEY,
> ancestor_fullname VARCHAR(100)
> );
>
> -and then add an index:
>
> CREATE INDEX anc_hier
> ON ancestor(ancestor_fullname CONNECT BY fullname);
>
> The SQL standard (and DB2) offers a general, and powerful
> (expression-wise) syntax for recursive queries: WITH RECURSIVE. That
> syntax is probably too general to build indexes for, but a query type like
> Oracle's CONNECT BY should be able to make use of a specialized index for
> hierarchical queries.

Why wouldn't normal index suffice? In fact, both "recursive with" and

"connect by" recommend creating indexes on both columns. Indexing
"parent_id" clearly would speed up ancestor queries, while indexing
"id" would speed up finding all the descendants. See chapter on

> The creation of the special CONNECT BY index could be implemented through
> a suitable encoding scheme like nested intervals or nested set, but the
> encodings should not be user visible, in the same way that the internals
> of b-trees in normal indexes aren't user visible.

CONNECT BY handles generic graphs, while almost all encoding schemes trees only. It's not obvious that practical encoding schemes for graphs really exist. Received on Mon Oct 11 2004 - 04:36:30 CEST