On Wed, Jun 03, 2009 at 12:25:14AM +0200, Jan scratched on the wall:
> Hi,
> > If you don't want to update, but you do want to query for entire
> > subtrees, do give nested sets more consideration.
>
> But as Jay pointed out: Nested sets only work with one parent. Do they?
You can think of nested sets as basically sets of parenthesis.
So the tree:
A
/ \
B C
/ /|\
D E F G
Turns into:
(A:(B:(D:))(C:(E:)(F:)(G:)))
As you can see, quite literally "nested sets" (or "sets of sets").
Each node can have exactly one parent (the containing set) and zero
or more (with "more" being > 2) children.
In the case of a family tree, you can get around the "one parent"
by extracting the table structure out to a detail table, so that the
tree table only has "person_id" values that point back to some
master "person" table. You can then just build two nested sets: one
that represents all fathers and one that represents all mothers. The
"father" table will still have daughters, but daughters will always
lack any children (in the "father" table).
[I think that will work. My morning coffee has just about worn off.]
Of course, this cancels out many of the query optimizations that
nested sets are good at, since you'll frequently need to combine data
from the two trees to get what you want. But it would be possible.
The bigger issue is that nested sets assume a perfect tree structure.
It has to lead back to a "point." You could, in theory, do a family
tree for a single person by turning the table up-side down, but if
you're trying to track breeding over a group of animals you need not
so much a tree as a scattered mesh that generally trends in one
direction. Unless you started out with exactly one male and one
female, a nested set isn't going to cut it.
I'm also unsure about cross-generational links (Like a son being a
half-brother kind of thing) that might happen in lab animals.
adjacency lists can deal with all of these quite easily. You can
have multiple NULL parents for the "tops" of different sub-trees, and
the tree structure is localized to a node and it's parents, meaning
the links can go all over the place.
As for AVL trees, I'm just confused by that suggestion. AVL trees,
like B-trees, Red/Black trees, or just about any kind of balanced
tree are designed to hold sorted lists. The whole idea of balanced
trees is that the tree structure can rearrange itself at will, just
as long as the leaf nodes keep their order and are fast to find. You
can't hold a tree structure in a AVL tree since the tree structure is
prone to changing if you add or remove leaf nodes.
Or am I missing something?
-j
--
Jay A. Kreibich < J A Y @ K R E I B I.C H >
"Our opponent is an alien starship packed with atomic bombs. We have
a protractor." "I'll go home and see if I can scrounge up a ruler
and a piece of string." --from Anathem by Neal Stephenson
_______________________________________________
sqlite-users mailing list
[email protected]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
