Subject Re: [firebird-support] Hierarchical tree
Author unordained
---Joe Celko---
I know I've seen several Joe Celko articles on tree structures and SQL, here's one

I'm pretty sure I've also come across equivalent stuff from Date/Darwen/Pascal. Celko's technique
is clever, but requires a lot of maintenance. His ideas tend to be like that -- interesting but

Your structure is logically good, though you do have the risk of having a circular dependency --
someone being his own boss, for example. You could probably avoid that with a CHECK constraint that
made sure (after any update) that a person wasn't his own boss/ancestor/etc., but that requires
some sort of iterative/recursive query. (You probably want to make sure that a node always has
a "topmost" parent, not just the rows you modified. There are well-known algorithms for this, such
as node-coloring. That involves updating all rows, or using a temp table to avoid concurrency
problems. If that's something you want, you might ask for suggestions here on that topic alone.)

I've personally always found it's easier to just build trees in-memory. If I have to, I'll run some
sort of iterative query that constantly grabs new children of any parents I found in the previous
pass -- start with one parent, find all children, lather, rinse, repeat. It's not the fastest way,
but it does avoid getting more than you need.

---Reason for problem---
Relational databases are by nature prohibited from allowing top-level data structures that are not
relations, and all results of queries must be relations -- but a tree (as a result) doesn't fit the
mold. That's why you'll have trouble finding it as such. 'Course, it doesn't help that people don't
like providing built-in language features for this ... (and digraph-related queries -- trees aren't
the only thing we like to do!) From a relational point of view, "select * from ..." with the table
as you have it is just as logically true as what you want, just not as convenient. That's part of
why constructs aren't provided.

---Shortcut in Oracle---
Some SQL dialects (not Firebird's) allow for a CONNECT BY or equivalent construct to do this

They have an equivalent snippet of PL/SQL to replace the "easy" way of doing it, maybe someone can
translate it to firebird's dialect. If it's something you need to do often, you might consider
using a database product with this as a feature. (I wasn't a marketing major in college.)

---Order by of some sort?---
You might want to take a few minutes and think about what you want the result to "mean" -- the one
you have shows some dashes to indicate hierarchy, but it seems you're relying on order? You might
consider solutions that return something like

> ================= ===================== ================================
> 1 1 Microsoft Windows
> 2 1 Microsoft Windows 9x
> 4 2 Microsoft Windows 98
> 3 2 Microsoft Windows 95
> 5 3 Microsoft Windows 95 SE
> 6 6 Linux

There's some sort of pattern here involving an order, at least of the parent_id. That's not quite
enough though as you want children to come right after their parent, not just near. The order isn't
entirely defined, either, as '98' could have come before '95' or after '95 SE', just not between
them. Anybody thinking more clearly than I am? (Should be easy enough.)

Most solutions will have you making the parent_id NULL rather than self-referencing. (1, NULL) and
(6, NULL) rather than (1, 1) and (6, 6).


---------- Original Message -----------
From: "SebastiĆ£o Carlos Santos" <scarlosantos@...>
> ================= ===================== ================================
> 1 1 Microsoft Windows
> 2 1 Microsoft Windows 9x
> 3 2 Microsoft Windows 95
> 4 2 Microsoft Windows 98
> 5 3 Microsoft Windows 95 SE
> 6 6 Linux
> I need to mount the structure, in accordance with the example
> - Microsoft Windows
> ----- Microsoft Windows 9x
> --------- Microsoft Windows 95
> ------------- Microsoft Windows 95 SE
> --------- Microsoft Windows 98
> - Linux
> I anticipate gratefulness for the aid
------- End of Original Message -------