What is the proper query to get all the children in a tree?

Question

Lets say I have the following MySQL structure:

CREATE TABLE `domains` (
`id` INT(10) UNSIGNED NOT NULL AUTO_INCREMENT,
`domain` CHAR(50) NOT NULL,
`parent` INT(11) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=MYISAM AUTO_INCREMENT=10 DEFAULT CHARSET=latin1

insert  into `domains`(`id`,`domain`,`parent`) values (1,'.com',0);
insert  into `domains`(`id`,`domain`,`parent`) values (2,'example.com',1);
insert  into `domains`(`id`,`domain`,`parent`) values (3,'sub1.example.com',2);
insert  into `domains`(`id`,`domain`,`parent`) values (4,'sub2.example.com',2);
insert  into `domains`(`id`,`domain`,`parent`) values (5,'s1.sub1.example.com',3);
insert  into `domains`(`id`,`domain`,`parent`) values (6,'s2.sub1.example.com',3);
insert  into `domains`(`id`,`domain`,`parent`) values (7,'sx1.s1.sub1.example.com',5);
insert  into `domains`(`id`,`domain`,`parent`) values (8,'sx2.s2.sub1.example.com',6);
insert  into `domains`(`id`,`domain`,`parent`) values (9,'x.sub2.example.com',4);

In my mind that is enough to emulate a simple tree structure:

            .com
             |             
           example                 
        /          \
      sub1          sub2

ect

My problem is that give sub1.example.com I want to know all the children of sub1.example.com without using multiple queries in my code.

I have tried joining the table to itself and tried to use subqueries, I can't think of anything that will reveal all the children.

At work we are using MPTT to keep in hierarchal order a list of domains/subdomains however, I feel that there is an easier way to do it.

I did some digging and someone did something similar but they required the use of a function in MySQL. I don't think for something simple like this we would need a whole function.

Maybe I am just dumb and not seeing some sort of obvious solution.

Also, feel free to alter the structure.

Answer 1

you should think about using nested sets for such data structures

see http://dev.mysql.com/tech-resources/articles/hierarchical-data.html for details on the implementation and usage

Answer 2

Mysql has a good article for you

Answer 3

you might like to try this method for adjacency list implementations: http://pastie.org/887130

Answer 4

Adjacency lists will only help you get wrong results.

a.d.f and b.d.c makes four nodes "adjacent" to d, but neither a.d.c nor b.d.f really exists. But the closure of an adjacency list would effectively pretend that they would.

So your query really does need to be something like "... WHERE ENDSWITH(domain, <parameter>).

Your likely problem is that this query will always need a full table scan.

Maybe this could be solved by creating a second table(domain1,domain2) which only says that "domain1 is a subdomain of domain2". You update this table using triggers or sprocs that run on every update of your base table. An insert of "a.b.c.d" inserts three rows in this second table : (a.b.c.d, b.c.d), (a.b.c.d, c.d), (a.b.c.d, d).

Your query can now be written as a join between the two, which would run fast enough if the proper indexes are in place.

EDIT

but there are severe problems to such an approach. If a.b.c.d gets deleted back again, then so should the other three rows, unless of course there still existed some x.b.c.d row which is not deleted ...

Answer 5

The solution was simple, albeit arguable on its efficiency.

I have modified the table structure as follows:

CREATE TABLE `domains` (
  `id` INT(10) UNSIGNED NOT NULL AUTO_INCREMENT,
  `domain` CHAR(50) NOT NULL,
  `level` INT(11) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MYISAM AUTO_INCREMENT=11 DEFAULT CHARSET=latin1

Level pertains to the depth in the tree.

Sample data:

insert  into `domains`(`id`,`domain`,`level`) values (1,'.com',0);
insert  into `domains`(`id`,`domain`,`level`) values (2,'example.com',1);
insert  into `domains`(`id`,`domain`,`level`) values (3,'sub1.example.com',2);
insert  into `domains`(`id`,`domain`,`level`) values (4,'sub2.example.com',2);
insert  into `domains`(`id`,`domain`,`level`) values (5,'s1.sub1.example.com',3);
insert  into `domains`(`id`,`domain`,`level`) values (6,'s2.sub1.example.com',3);
insert  into `domains`(`id`,`domain`,`level`) values (7,'sx1.s1.sub1.example.com',4);
insert  into `domains`(`id`,`domain`,`level`) values (8,'sx2.s2.sub1.example.com',4);
insert  into `domains`(`id`,`domain`,`level`) values (9,'x.sub2.example.com',3);
insert  into `domains`(`id`,`domain`,`level`) values (10,'t.sx1.s1.sub1.example.com',5);

So lets say we are given sub1.domain.com and we want to know all of its children the query is rather simple:

SELECT * FROM domains WHERE domain LIKE "%.sub1.example.com" ORDER BY level;

Of course if we want sub1.example.com in our result set we can just do:

SELECT * FROM domains WHERE domain LIKE "%sub1.example.com" ORDER BY level;

From the result set we get a list of all the children given a child.

To delete a child (and all the associated children) is simple and a very similar query

DELETE FROM domains WHERE domain LIKE "%sub1.example.com";

Insertions are easy, and it just takes 2 queries (assuming the user has a drop down box and chooses the parent):

SELECT level FROM domains WHERE domain = "sub2.example.com";

INSERT INTO domains (domain, level) VALUES ($sub + ".sub2.example.com", $level+1)

Please excuse the mixed PHP + MySQL syntax, but you get the idea.