Re: pointers on representing tree in db?
Date: 18 Apr 2001 14:27:45 +0100
Message-ID: <u7hezmficu.fsf_at_sol6.ebi.ac.uk>
Lennart> Quite neet feature. Oracle seems to have a lot of things that DB2 doesnt. I Lennart> am however more interested in "classical" work using only standard SQL. The Lennart> solution I came up with is to use two tables
Lennart> Table Data (id integer not null, parent_id references...) id is p.k
Lennart> Table Ancestor (id, ancestor_id) both id and ancestor_id references id in Lennart> Data
Lennart> Both a subtree and a path for a particular node can be easily
Lennart> retrieved from the Ancestor table.
no they can't; it needs support in the form of SQL extensions such as
Oracle's CONNECT BY PRIOR.
A neat solution that is frequently posted by Joe Celko (and also described in
detail in his excellent "SQL for Smarties"), is the 'nested set'
solution. The advantage is that it represents trees really as sets of nodes,
whereas the (id,ancestor_id) approach ('adjacency list') really only gives
one node or one set of direct children of a node. It is completely standard
SQL, and is exceedingly fast.
The disadvantage is that in Celko's approach, it's not easy to select the
direct parent or direct children of a node.
In practice, I think it would make sense to mix the two approaches.
I am reposting it here. Cheers,
Philip
For details, see the chapter in my book JOE CELKO'S SQL FOR SMARTIES by Joe Celko, Morgan-Kaufmann, 1995, ISBN 1-55860-323-9 or my columns in DBMS magazine in 1996 March, April, May and June issues. I went into details as to how to manipulate this model.
--CELKO--
-- Why don't Alice and Bob simply get married? ----------------------------------------------------------------------------- Philip Lijnzaad, lijnzaad_at_ebi.ac.uk \ European Bioinformatics Institute,rm A2-08 +44 (0)1223 49 4639 / Wellcome Trust Genome Campus, Hinxton +44 (0)1223 49 4468 (fax) \ Cambridgeshire CB10 1SD, GREAT BRITAIN PGP fingerprint: E1 03 BF 80 94 61 B6 FC 50 3D 1F 64 40 75 FB 53Received on Wed Apr 18 2001 - 15:27:45 CEST