Re: What value should be used to identify the root of a tree stored in a parent/child table?

Hi Steve,

I'm not an expert in the formalism of certain rel. DB. What I can suggest
is the way OLAP Database treat this problem, especially Express. There they
use the NA value - in your case the NULL - to identify the the root or one
of the highest levels items in the tree. For all other levels they calculate
and identify the level by an integer.
An other topic is if you need to use more than one hierarchy ! Did you considered that ?

Hope this helps.
Jury

For any further information feel free to contact me directly.

Steven Tolkin wrote:
>
> Suppose I represent a tree in a relational table, e.g. the table is
> named tree and there are two text string columns named parent and
> child. I also define a unique index on these two columns, to help
> ensure that it really is a tree. (This is necessary but not sufficent.)
> What value should be used to identify the root?
>
> In other words, givemn that the first query will have the form
> select child from tree where parent ...
> what should appear instead of ... ?
>
> I can think of a few approaches:
> 1. IS NULL; i.e. use the null value.
> Pro: It is the "distinguished value" available in all modern relationbal
> databases systems.
> Con: Some (all?) systems do not allow a primary key to include any null
> values, so the index cannot be defined as a primary key. (I can
> probably live with this limitation.)
> Con: Some systems do not index rows with a leading null value, so the
> performance of that first query might suffer slightly. (I can live with
> this, as the number of rows is only a few hundred, and scanning the on
> the first query will just bring all the blocks into the cache for the
> subsequent queries.)
>
> 2a. = ''; i.e. use the null string
> 2b. = ' '; i.e. use a string containing a blank
> Pro: Is another kind of distinguished value
> Con (for 2a): Some systems treat the null string equivalently to the
> null value, i.e. it is not indexed. I believe this is true for Oracle
> -- can anyone confirm this, and also state what happens in other
> systems, Informix, etc.
> Con: Will not be visible if the data from the table is written out, e.g.
> in ASCII, and so will make parsing it harder. (This also applies to the
> null value, in the common case where there is no non-whitespace
> character chosen for it.)
>
> 3. Invent a "magic" string for this purpose, e.g. /..
> Pro: Has none of the disadvantages described above.
> Con: Is a hack.
> Con: Most people will not understand the string if they see it in the
> output.
>
> The reason I propose /.. specifically is that at first I planned to just
> use / by analogy to the root directory. But what if I want to store
> actual directories names in the tree table? So I have tentatively
> decided that the best magical string is /.. meaning "the root's parent".
> If you like this approach feel free to suggest other strings.
>
> --
> Steven Tolkin steve.tolkin_at_fmr.com 617-563-0516
> Fidelity Investments 82 Devonshire St. R27C Boston MA 02109
> I'm not really an actor, I just play one on TV. Remarks are mine.
 

-- 
================================================
Jury Witschnig
Technical University of Munich
mailto: witschnig_at_bwl.blm.tu-muenchen.de
================================================