Need Help with Hierarchical Mysql Query

Question

I'm trying to wrap my head around querying a table that has hierarchical category data (used for a cms) which is also tied to my posts data and a many-to-many type relationship with my post2cat table. Specifically, my question is how can I get all posts that belong to any of the subcategories (not limited to direct descendant but can be n levels deep) of a specific category id? Here are my tables:

'categories' table:

+-----------+-------------+------+-----+---------+----------------+
| Field     | Type        | Null | Key | Default | Extra          |
+-----------+-------------+------+-----+---------+----------------+
| id        | int(11)     | NO   | PRI | NULL    | auto_increment |
| name      | varchar(45) | YES  |     | NULL    |                |
| parent_id | int(11)     | YES  | MUL | 0       |                |
+-----------+-------------+------+-----+---------+----------------+
3 rows in set (0.00 sec)

'post2cat' table:

+---------+---------+------+-----+---------+-------+
| Field   | Type    | Null | Key | Default | Extra |
+---------+---------+------+-----+---------+-------+
| post_id | int(11) | NO   | MUL | NULL    |       |
| cat_id  | int(11) | NO   | MUL | NULL    |       |
+---------+---------+------+-----+---------+-------+
2 rows in set (0.00 sec)

'posts' table:

+---------------+--------------+------+-----+---------+----------------+
| Field         | Type         | Null | Key | Default | Extra          |
+---------------+--------------+------+-----+---------+----------------+
| id            | int(11)      | NO   | PRI | NULL    | auto_increment |
| title         | varchar(256) | NO   |     | NULL    |                |
| content       | text         | NO   |     | NULL    |                |
| end_date      | datetime     | NO   |     | NULL    |                |
| format_id     | int(11)      | NO   |     | NULL    |                |
| featured      | int(1)       | NO   |     | NULL    |                |
| status        | int(3)       | NO   |     | NULL    |                |
| publish_date  | datetime     | NO   |     | NULL    |                |
| date_created  | datetime     | NO   |     | NULL    |                |
| date_modified | datetime     | NO   |     | NULL    |                |
+---------------+--------------+------+-----+---------+----------------+

post_id name description

post2cat

You `categories` table is an adjacency list model. Use MySQL session variables to walk the tree. My question on hierarchical data in SQL covers a lot more on this general question: http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database — orangepips, Apr 19 '11 at 14:38

score 4 · Accepted Answer · edited Oct 30 '11 at 20:50

4

It is a challenge to fetch the tree to an arbitrary depth n using just SQL in MySQL (See: Managing Hierarchical Data in MySQL and Hierarchical Queries in MySQL).

If you are dealing with a small dataset, it makes the most sense to select all of the categories from the database and then build the tree in a scripting language. Then the tree can be traversed to find parent node and the parent node's children, which can then be used to query the database for the posts using a join.

edited Oct 30 '11 at 20:50

Paŭlo Ebermann

73,284
20
146
210

answered Apr 17 '11 at 00:10

gcorne

439
2
5

+1 for the first link you provided. However, your comment is at odds with the content of the link. It seems like you don't need to make use of a scripting language is you use the nested set model. – VinnyD Apr 18 '11 at 17:14
In MySQL, in order to retrieve a tree from an an adjacency list model, you need to know the depth. The second link is an attempt to work-a-round this. – gcorne Apr 19 '11 at 00:40

score 1 · Answer 2 · answered Apr 16 '11 at 22:19

There are perhaps better methods, but here's an idea:

CREATE VIEW subcategories AS
( SELECT 0        AS level
       , cat_0.id AS cat_id
       , cat_0.id AS subcat_id
  FROM categories cat_0

  UNION ALL

  SELECT 1        AS level
       , cat_0.id AS cat_id
       , cat_1.id AS subcat_id
  FROM categories cat_0
    JOIN categories cat_1
      ON cat_0.id = cat_1.parent_id

  UNION ALL

  SELECT 2        AS level
       , cat_0.id AS cat_id
       , cat_2.id AS subcat_id
  FROM categories cat_0
    JOIN categories cat_1
      ON cat_0.id = cat_1.parent_id
    JOIN categories cat_2
      ON cat_1.id = cat_2.parent_id

  UNION ALL

  SELECT 3        AS level
       , cat_0.id AS cat_id
       , cat_3.id AS subcat_id
  FROM categories cat_0
    JOIN categories cat_1
      ON cat_0.id = cat_1.parent_id
    JOIN categories cat_2
      ON cat_1.id = cat_2.parent_id
    JOIN categories cat_3
      ON cat_2.id = cat_3.parent_id
) ;

Then, use the above to have:

SELECT sub.subcat_id
     , sub.level
     , p.post_id
     , p.title
FROM subcategories sub
  JOIN post2cat p2c
    ON sub.subcat_id = p2c.cat_id
  JOIN posts p
    ON p2c.post_id = p.id
WHERE sub.cat_id = CAT_ID        <--- the category id you want to search for

score 0 · Answer 3 · answered Apr 16 '11 at 22:43

The following stored procedure should provide a good starting point or provide some inspiration.

Hope it helps :)

Example calls

You can call the stored procedure from php as follows:

$result = $conn->query(sprintf("call category_hier(%d)", 1));

or from the mysql command line:

mysql> call category_hier(1);
+--------+---------------+---------------+----------------------+-------+
| cat_id | category_name | parent_cat_id | parent_category_name | depth |
+--------+---------------+---------------+----------------------+-------+
|      1 | Location      |          NULL | NULL                 |     0 |
|      3 | USA           |             1 | Location             |     1 |
|      4 | Illinois      |             3 | USA                  |     2 |
|      5 | Chicago       |             3 | USA                  |     2 |
+--------+---------------+---------------+----------------------+-------+
4 rows in set (0.00 sec)

Full script

drop table if exists categories;
create table categories
(
cat_id smallint unsigned not null auto_increment primary key,
name varchar(255) not null,
parent_cat_id smallint unsigned null,
key (parent_cat_id)
)
engine = innodb;

insert into categories (name, parent_cat_id) values
('Location',null), 
('Color',null), 
   ('USA',1), 
      ('Illinois',3), 
      ('Chicago',3), 
   ('Black',2), 
   ('Red',2);


drop procedure if exists category_hier;
delimiter #

create procedure category_hier
(
in p_cat_id smallint unsigned
)
begin

declare v_done tinyint unsigned default 0;
declare v_depth smallint unsigned default 0;

create temporary table hier(
 parent_cat_id smallint unsigned, 
 cat_id smallint unsigned, 
 depth smallint unsigned default 0
)engine = memory;

insert into hier select parent_cat_id, cat_id, v_depth from categories where cat_id = p_cat_id;
create temporary table tmp engine=memory select * from hier;

/* http://dev.mysql.com/doc/refman/5.0/en/temporary-table-problems.html */

while not v_done do

    if exists( select 1 from categories c
        inner join tmp on c.parent_cat_id = tmp.cat_id and tmp.depth = v_depth) then

        insert into hier select c.parent_cat_id, c.cat_id, v_depth + 1 from categories c
            inner join tmp on c.parent_cat_id = tmp.cat_id and tmp.depth = v_depth;

        set v_depth = v_depth + 1;          

        truncate table tmp;
        insert into tmp select * from hier where depth = v_depth;

    else
        set v_done = 1;
    end if;

end while;

select 
 c.cat_id,
 c.name as category_name,
 p.cat_id as parent_cat_id,
 p.name as parent_category_name,
 hier.depth
from 
 hier
inner join categories c on hier.cat_id = c.cat_id
left outer join categories p on hier.parent_cat_id = p.cat_id
order by
 hier.depth;

drop temporary table if exists hier;
drop temporary table if exists tmp;

end #

delimiter ;

call category_hier(1);

call category_hier(2);

Need Help with Hierarchical Mysql Query

3 Answers3

Linked