Adjacency list model

1. 
   ficuscr permalink

   August 26, 2009

   Recursion? Recursion?
2. 
   Richard Knop permalink*

   August 26, 2009

   Recursion is simply wrong for this kind of thing. It is a major performance issue and should be avoided at all costs (unless I misunderstood you and you meant something else than selecting the whole tree with recursion database queries).
3. 
   Geoff permalink

   December 12, 2009

   For me, creating the ultimate adjacency model PHP/MySQL solution is one of the holy grail projects I will tackle before I die. The SQL you gave above doesn’t work for me. I get zero rows. I completely disagree with Richard Knop. Using a recursive function is the ideal way to handle an arbitrarily deep nested set. You ought to be able to make a single query and write a single recursive function that returns a nested array, but I’ve tried many times and it’s a lot harder than it seems.

   Here is some alternate SQL that I’ve used in the past but is nowhere near as elegant as the solution I really want to create. It uses MySQL’s WHERE … IN ( ) and sub-select/subquery syntax to find categories in the top level, then level 1, … one SQL query per level is required. Each deeper level requires an additional layer in the sub-select, but it’s pretty easy to follow, and each subquery is based on the previous level.

   # LEVEL 0 #################################

   SELECT
   t0.id as id0,
   t0.name as name0,
   FROM category t0
   WHERE
   t0.parent_id IS NULL
   ORDER BY
   t0.ord

   # LEVEL 1 #################################

   SELECT
   t1.id as id1,
   t1.parent_id as parent1,
   t1.name as name1,
   FROM caegory t1
   WHERE
   t1.parent_id IN
   (
   SELECT
   t0.id as id0
   FROM
   category t0
   WHERE
   t0.parent_pid IS NULL
   )
   ORDER BY
   t1.ord

   # LEVEL 2 #################################

   SELECT
   t2.id as id2 ,
   t2.parent_id as parent2 ,
   t2.name as name2
   FROM
   category AS t2
   WHERE
   t2.parent_id
   IN (
   SELECT t1.id as id1
   FROM category t1
   WHERE t1.parent_id IN
   (
   SELECT t0.id as id0
   FROM category t0
   WHERE t0.parent_id IS NULL
   )
   )
4. 
   Richard Knop permalink*

   December 12, 2009

   @Geoff: I just tested it in phpmyadmin and it works fine here. Are you sure your MySQL installation allows InnoDB tables? Because I used the InnoDB format in the CREATE TABLE query. Change that to MyISAM and it should work the same.
5. 
   Geoff permalink

   December 12, 2009

   I’m using a MyISAM table and I don’t have a foreign key explicitly defined as such; just

   CREATE TABLE category (
   id INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
   category VARCHAR(100) NOT NULL,
   parent_id INT UNSIGNED NOT NULL ,
   INDEX( parent_id )
   )

   but InnoDB & Foreign Key constraints are not required for adjacency SQL?
   Don’t you only get rows that have all 4 levels deep?
6. 
   Richard Knop permalink*

   December 12, 2009

   OK, I just tried it with MyISAM:

   CREATE TABLE categories (
   id INT NOT NULL AUTO_INCREMENT,
   name VARCHAR(255) NOT NULL,
   parent_id INT NULL DEFAULT NULL,
   INDEX (parent_id),
   PRIMARY KEY (id)
   ) ENGINE = MYISAM;

   Then:

   INSERT INTO categories (id, name, parent_id) VALUES
   (NULL, ‘Relational databases’, NULL),
   (NULL, ‘SQLite’, 1),
   (NULL, ‘MySQL’, 1),
   (NULL, ‘PostgreSQL’, 1),
   (NULL, ‘PDO’, 3),
   (NULL, ‘Transactions’, 3);

   Then:

   SELECT t0.id AS lvl0_id, t0.name AS lvl0_name,
   t1.id AS lvl1_id, t1.name as lvl1_name,
   t2.id AS lvl2_id, t2.name as lvl2_name,
   t3.id AS lvl3_id, t3.name as lvl3_name,
   t4.id AS lvl4_id, t4.name as lvl4_name
   FROM categories AS t0
   LEFT JOIN categories AS t1 ON t1.parent_id = t0.id
   LEFT JOIN categories AS t2 ON t2.parent_id = t1.id
   LEFT JOIN categories AS t3 ON t3.parent_id = t2.id
   LEFT JOIN categories AS t4 ON t4.parent_id = t3.id
   ORDER BY t0.id, t1.id, t2.id, t3.id, t4.id;

   And it works as expected.

   Yes, the point of this approach is that it has limited number of levels, so it can only go as deep as the number of levels defined in the SELECT query (I defined 4 levels in this example but you can define 10 or more if you need). But it doesn’t use a recursion which means it is much faster and overall more elegant solution.

   If you have a hierarchy with 10+ levels I would advise against using the adjacency list model. In that case use the nested set model.
7. 
   Geoff permalink

   December 12, 2009

   I’ve always thought that the easy way out was just doing SELECT * FROM category and passing the result to a PHP class that handles sorting out how everything is nested, having functions to getNestedArray( ), getDepth( $id ) and getParent( $id ) but the SQL purist in me wants to figure out a way to let the DB do as much as it can before PHP takes over.

   What I’m looking for is SQL that renders something like this:

   1 | Top 1 | Null | Null
   2 | Top 1 | Sub 1 | Null
   3 | Top 1 | Sub 1 | Third 1
   4 | Top 1 | Sub 2 | Null
   5 | Top 2 | Null | Null
   6 | Top 2 | Sub 3 | Null

   … just like you would logically think of how a menu would be constructed.

   Great blog, by the way! Lots of really useful stuff here. Keep going.
8. 
   Geoff permalink

   December 12, 2009

   You’re right, your SQL does work! Sorry about that – In my CMS I have an extra `status` field that I was checking in each table to force only ‘active’ categories to appear. Even though all my categories are active, the addition of a WHERE clause was throwing it all off. I think if I allow NULL on that column it may work again. Although, the total number of rows, and the order of the rows in the output aren’t what I was hoping for, either. Sigh.

   For what it’s worth, I think @ficuscr was after a PHP function that uses recursion to return a nested structure from a SELECT * scenario like I described in my previous comment. Basically a findChildren( $cat ) method that calls itself to ouput something like:

   $cats = array (
   ‘id’ => 1 ,
   ‘name’ => ‘Top 1′,
   ‘children’ => array (
   ‘id’ => 2,
   ‘name’ => ‘Sub 1′,
   ‘children’ => array(
   ‘id’ => 3
   ‘name’ => ‘Third 1′,
   ‘children => array()
   )
   )
   )

   If you have that, then you can use recursive function to output a nested ul li as well. The benefit to using recursive functions is that they’d work to any arbitrary depth.
9. 
   Richard Knop permalink*

   December 12, 2009

   Yeah that’s an alternative. You can just fetch all rows from the table and do all computing in PHP. I believe there are robust PHP classes floating around the Web with just that purpose.

   But when I wrote this I was working on a simple CMS application where the client would hardly ever create more than 1 level of hierarchy (so 4 levels were more than enough). And many applications are like that – with just one or two levels of hierarchy.

   If you need unlimited levels then, of course, either use the nested set model or the adjacency list model the way you are suggesting.

   Thanks for comments
10. 
    Chusa permalink

    December 27, 2009

    Perfect!! Thank you

Trackbacks and Pingbacks

1. Nested set model | Richard Knop's Blog
2. Back online | Zend Framework Blog Written By Richard Knop
3. Anonymous
4. Merge sort PHP implementation | Zend Framework Blog

Leave a Reply