SQL Recursive Tables

Question

I have the following tables, the groups table which contains hierarchically ordered groups and group_member which stores which groups a user belongs to.

groups
---------
id  
parent_id
name

group_member
---------
id
group_id
user_id

ID  PARENT_ID  NAME
---------------------------
1   NULL       Cerebra
2   1          CATS 
3   2          CATS 2.0 
4   1          Cerepedia 
5   4          Cerepedia 2.0
6   1          CMS 

ID GROUP_ID USER_ID
---------------------------
1  1        3
2  1        4
3  1        5
4  2        7
5  2        6
6  4        6
7  5        12
8  4        9
9  1        10

I want to retrieve the visible groups for a given user. That it is to say groups a user belongs to and children of these groups. For example, with the above data:

USER  VISIBLE_GROUPS
9     4, 5 
3     1,2,4,5,6
12    5 

I am getting these values using recursion and several database queries. But I would like to know if it is possible to do this with a single SQL query to improve my app performance. I am using MySQL.

Answer 1

Two things come to mind:

1 - You can repeatedly outer-join the table to itself to recursively walk up your tree, as in:

SELECT *
FROM
  MY_GROUPS MG1
 ,MY_GROUPS MG2
 ,MY_GROUPS MG3
 ,MY_GROUPS MG4
 ,MY_GROUPS MG5
 ,MY_GROUP_MEMBERS MGM
WHERE MG1.PARENT_ID = MG2.UNIQID (+)
  AND MG1.UNIQID = MGM.GROUP_ID (+)
  AND MG2.PARENT_ID = MG3.UNIQID (+)
  AND MG3.PARENT_ID = MG4.UNIQID (+)
  AND MG4.PARENT_ID = MG5.UNIQID (+)
  AND MGM.USER_ID = 9

That's gonna give you results like this:

UNIQID PARENT_ID NAME      UNIQID_1 PARENT_ID_1 NAME_1 UNIQID_2 PARENT_ID_2 NAME_2  UNIQID_3 PARENT_ID_3 NAME_3 UNIQID_4 PARENT_ID_4 NAME_4 UNIQID_5 GROUP_ID USER_ID
4      2         Cerepedia 2        1           CATS   1        null        Cerebra null     null        null   null      null       null   8        4        9

The limit here is that you must add a new join for each "level" you want to walk up the tree. If your tree has less than, say, 20 levels, then you could probably get away with it by creating a view that showed 20 levels from every user.

2 - The only other approach that I know of is to create a recursive database function, and call that from code. You'll still have some lookup overhead that way (i.e., your # of queries will still be equal to the # of levels you are walking on the tree), but overall it should be faster since it's all taking place within the database.

I'm not sure about MySql, but in Oracle, such a function would be similar to this one (you'll have to change the table and field names; I'm just copying something I did in the past):

CREATE OR REPLACE FUNCTION GoUpLevel(WO_ID INTEGER, UPLEVEL INTEGER) RETURN INTEGER
IS
BEGIN
  DECLARE
    iResult INTEGER;
    iParent INTEGER;
BEGIN
  IF UPLEVEL <= 0 THEN
    iResult := WO_ID;
  ELSE
    SELECT PARENT_ID
    INTO iParent
    FROM WOTREE
    WHERE ID = WO_ID;    
    iResult := GoUpLevel(iParent,UPLEVEL-1);  --recursive
  END;
  RETURN iResult;
  EXCEPTION WHEN NO_DATA_FOUND THEN
    RETURN NULL;
  END;
END GoUpLevel;
/

Answer 2

Joe Cleko's books "SQL for Smarties" and "Trees and Hierarchies in SQL for Smarties" describe methods that avoid recursion entirely, by using nested sets. That complicates the updating, but makes other queries (that would normally need recursion) comparatively straightforward. There are some examples in this article written by Joe back in 1996.