howdy,

Nested sets (or modified preorder tree transversal algorithm) work great
if a specific node only exists once inside the tree. I am using my tree
for user authentication. For example, a group may have users and other
groups in them. If the root groupA has groupB and groupC in it, and
groupB contains groupC then groupC exists twice in the tree. Now, my
issue is when I remove a subnode from groupC I need to remove that
subnode from every instance of groupC in the root tree. This can become
a nightmare of recursive functions (my reason for going with nested sets
was to avoid recursive functions).

In Joe Celko's book "Joe Celko's Trees and Hierarchies in SQL for
Smarties" he gives an example of copying a subtree inside a nested set
and naming it "subtree2" or somesuch (he uses military unit hierarchies
and MOS groups as his example) . But it doesn't seem to address how to
maintain the integrity of the copied subtree when the initial subtree is
changed.

Is there a better way to accomplish this task?
Thanks for your help
--
bernie

bernie wrote:
Sorry, but I do not quite see the problem.
as a tree structure isn't it equivalent to this image?

groupA
+- groupB
+- groupC

In words: groupA is the parent of groupB which is the parent of groupC
Why would groupC exist twice?

Ed

Ed Prochak wrote:
The full tree in my example would look something like this:

groupA
groupC -+- groupB
+- groupC

Because groupC exists in groupA and in groupB. So, when I add a fourth
group into groupC it would need to be added twice into this tree. This
may be what I need to do, but I am just checking to see if there is a
more efficient way to do it (somehow adding groups by reference or
something...).

thanks for the reply!
--
bernie

bernie wrote:

the node C logically has two parents, A and B:

A--+-------+--C

In a tree, nodes can only have 1 parent. If you're trying to model
generalized groups like these, trees are the wrong model. In sql terms,
a better model would be a users table, a groups table, users_contained
table, and a groups contained table.

Bob Stearns wrote:

That makes since. It always seemed like a hack to think of it they way
I was doing it. My goal is to get all of the user keys out of the group
even if those users are in nested groups in one select. Could you give
me an example of a select using the users_contained and groups_contained
tables that would do this?

Thanks!
--
bernie

bernie wrote:
occurrences of C from groups_contained; all users with no entries in
users_contained; then C itself.

If C is allowed to be parent, not just a leaf group, the problem is
slightly more complicated: delete from groups_contained all rows with C
as parent, then keep deleting rows from groups_contained which have no
parent(s) until there are no more deletions (in graph theory terms, a
width first delete of links). Then delete from users_contained every row
which names a group without parents, followed by all users without an
entry in users_contained, the the groups without parents in
groups_contained (they may have started as "parent" groups, but by now
in the process they have no users or "child" groups.

bernie wrote:
Handling graphs in sql is a real mess. I had to do it once and have the
following notes from my experiment. I wrote it merely to convince my
self that it would actually work, and the notes are rather sloppy.
Still, it might give you some ideas on an alternative aproach.

http://fungus.teststation.com/~jon/t...eeHandling.htm

Other klinks on the same subject can be found at:

http://troels.arvin.dk/db/rdbms/links/#hierarchical



/Lennart