Hello
D I'm trying to get my head around doing hierarchies in SQL. I've been
D Googling and it appears Oracle and MS SQL have some extensions to help, but
D I'm trying to figure out what can be done with 'plain' SQL.
With tree structures in table, I like to use a pair of coordinates (x and
y), which together identify the location of a node in the tree.
So, the database schema could look like this:
CREATE TABLE directories (
dir_id INTEGER NOT NULL PRIMARY KEY AUTOINCREMENT,
dir_name VARCHAR (255),
dir_x INTEGER,
dir_y INTEGER
);
CREATE INDEX x_idx ON directories (dir_x);
CREATE INDEX y_idx ON directories (dir_y);
CREATE INDEX xy_idx ON directories (dir_x, dir_y);
Traverse the tree in depth-first order, giving each node the first
coordinate when going down, and the second when going back up. The first
child of a node N's x coordinate is 1 more than the x coordinate of node N.
If a node N has no children, then the y coordinate of node N is 1 more than
the x coordinate of node N. If node N has several child nodes, then the y
coordinate of node N is 1 more than the y coordinate of the last child of
node N.
For a sample tree structure, similar to your example:
(path x-coord y-coord)
/ 1 16
/home 2 15
/home/swithun 3 8
/home/swithun/hierarchy 4 5
/home/swithun/mail 6 7
/home/user2 9 14
/home/user2/foo 10 13
/home/user2/foo/bar 11 12
the INSERT statements would look like:
INSERT INTO directories (dir_name, dir_x, dir_y) VALUES ('', 1, 16);
INSERT INTO directories (dir_name, dir_x, dir_y) VALUES ('home', 2, 15);
INSERT INTO directories (dir_name, dir_x, dir_y) VALUES ('swithun', 3, 8);
INSERT INTO directories (dir_name, dir_x, dir_y) VALUES ('hierarchy', 4, 5);
INSERT INTO directories (dir_name, dir_x, dir_y) VALUES ('mail', 6, 7);
INSERT INTO directories (dir_name, dir_x, dir_y) VALUES ('user2', 9, 14);
INSERT INTO directories (dir_name, dir_x, dir_y) VALUES ('foo', 10, 13);
INSERT INTO directories (dir_name, dir_x, dir_y) VALUES ('bar', 11, 12);
To get the path and the number of subdirectories below that path, the
following query seems to produce the correct results:
SELECT GROUP_CONCAT('/', d2.dir_name) AS path,
d3.subdirectories
FROM directories AS d1
INNER JOIN directories AS d2
ON d2.dir_x <= d1.dir_x
AND d2.dir_y >= d1.dir_y
INNER JOIN (SELECT COUNT(*) - 1 AS subdirectories,
d4.dir_id AS dir_id
FROM directories AS d4
INNER JOIN directories AS d5
ON d5.dir_x >= d4.dir_x
AND d5.dir_y <= d4.dir_y
GROUP BY d4.dir_id) AS d3
ON d1.dir_id = d3.dir_id
GROUP BY d1.dir_id;
Table d1 is the driving table. d2 provides the ancestor directories for each
directory in d1, to generate the path. d3 is the count of how many
subdirectories are descendants (d5) of each directory in d4, then joined to
d1.
If you want to include the subdirectory in the count, remove the - 1.
It is a bit more complicated than the other suggestions, but the indexes
are only integers. You would need to write a script to generate the INSERT
statements.
Swithun.
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
