Re: Other tree representations in SQL

From: Lennart Jonsson <lelle2_at_bonetmail.com>
Date: Thu, 05 Dec 2002 18:51:11 +0100
Message-ID: <aso3kt$sha4o$1@ID-167942.news.dfncis.de>

On Wed, 04 Dec 2002 23:48:56 +0000, Greg Boland wrote:

> I posted Top only because you don't need to read the rest to get an idea of
> what I'm thinking. The tree model, no matter how you do it, is contrived
> under the sql model. I do an app in which I need to know parents and
> siblings. Quite simple. I found it much more natural to store children with
> a parent. But to traverse the tree you still have to do some procedural
> programming which sql is not up to the task. And it could be recursive, but
> doesn't have to be. The hierarchal model that Celko describes is much better
> up to the task, but I wouldn't use it. So, SQL should just just return
> tuples, and your procedural code should do the rest.
>
> Best Regards,
>
> Greg

There is another way to go as well. Assume the relation

create table user (

	id   		integer not null,
	parentid 	integer not null,
	name		varchar (20) not null,
	constraint pk_user primary key (id),
	constraint fk1_user foreign key (parentid)
		references user on delete restrict

)

then add the relation

create table ancestor (

	id		integer not null,
	ancestorid	integer not null,
	constraint pk_ancestor primary key (id, ancestorid),
	constraint fk1_ancestor foreign key (id) 
		references user
			on delete no action
			on update no action
	constraint fk2_ancestor foreign key (ancestorid) 
		references user
			on delete no action
			on update no action

)

Assuming that the ancestor table is correct one can ask things like "who belongs to the subtree of x"

select id from ancestor where ancestorid = x

"what is the largest subtree below x"

select a.id from ancestor a, user u
where u.parentid = x and a.ancestorid = u.id group by a.id
having count(1) = (select max(...) ... )

etc.

The trick is of course to maintain the ancestor table so that it reflects the current situation in the user table. There are three situations that must be watched.

1. A user is added. Since the user cant have any children at this point, we add the following tuples to ancestor (using u as an alias for the new user):

	(u.id, u.parentid) union (select u.id, ancestorid from ancestor
                                      where id = u.parentid)

b) A user is deleted. fk1_user ensures that the user cant have children at this point, so we delete the following tuples from ancestor:

        delete from ancestor where id = u.id

c) A user is moved. At this point we cant guarantee that the user doesnt have children so we will have to take that into concideration. There is no need to change any ancestor relations within the moving subtree, instead we first delete all tuples where id belongs to the subtree of u, and ancestorid belongs to the old ancestors of u. The we add tuples according to id belongs to the subtree of x, and ancestorid belongs to the new ancestors of u:

delete from ancestor where

	(id = u.id) or id in (select id from ancestor where ancestorid = u.id)) and
         ancestorid in (select ancestorid from ancestor where id = u.id)

• u.parentid refers to new parentid of u below insert into ancestor ( (values u.id, u.parentid) union (select u.id, ancestorid from ancestor where id = u.parentid) union (select id, u.parentid from ancestor where ancestorid = u.id) union (select a.id, b.ancestorid from ancestor a, ancestor b where a.ancestorid = u.id and b.id = u.parentid) )

the rules a), b) and c) is well suited to keep in for example triggers. The relation ancestor is sometime refered to as the "transitive closure" of user.

Anyhow, questions regarding trees and other hierarcical structures seems to pop in to this and other news groups on a regular basis. I think it would be nice if there where some kind of faq regarding such questions. A starter would be if one could come to some sort of "agreement" of what the typical tree queries are. Then anyone interested could provide implementations for these queries in different flavors (nested set, adjancy list, transitive closure, different OO solutions etc). Any thoughts, anyone?

/Lennart    Received on Thu Dec 05 2002 - 11:51:11 CST