SQL Recursion

Question

i have the next tables. groups table which contains hierarchically ordered groups and *group_member* which stores to 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

I think you're going to need CURSORs for this, this link may help

Answer 2

I don't think that this can be accomplished without using recursion. You can accomplish it with with a single stored procedure using mySQL, but recursion is not allowed in stored procedures by default. This article has information about how to enable recursion. I'm not certain about how much impact this would have on performance verses the multiple query approach. mySQL may do some optimization of stored procedures, but otherwise I would expect the performance to be similar.

Answer 3

Didn't know if you had a Users table, so I get the list via the User_ID's stored in the Group_Member table...

SELECT GroupUsers.User_ID,
     (
     SELECT 
            STUFF((SELECT ',' + 
      Cast(Group_ID As Varchar(10))
      FROM Group_Member Member (nolock) 
      WHERE Member.User_ID=GroupUsers.User_ID
        FOR XML PATH('')),1,1,'') 
        ) As Groups
FROM (SELECT User_ID FROM Group_Member GROUP BY User_ID) GroupUsers

That returns:

User_ID    Groups
3          1
4          1
5          1
6          2,4
7          2
9          4
10         1
12         5

Which seems right according to the data in your table. But doesn't match up with your expected value list (e.g. User 9 is only in one group in your table data but you show it in the results as belonging to two)

EDIT: Dang. Just noticed that you're using MySQL. My solution was for SQL Server. Sorry.

-- Kevin Fairchild

Answer 4

There's no way to do this in the SQL standard, but you can usually find vendor-specific extensions, e.g., CONNECT BY in Oracle.

UPDATE: As the comments point out, this was added in SQL 99.

Answer 5

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 6

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.

Answer 7

There was already similar question raised.

Here is my answer (a bit edited):

I am not sure I understand correctly your question, but this could work My take on trees in SQL.

Linked post described method of storing tree in database -- PostgreSQL in that case -- but the method is clear enough, so it can be adopted easily for any database.

With this method you can easy update all the nodes depend on modified node K with about N simple SELECTs queries where N is distance of K from root node.

Good Luck!

Answer 8

I don't remember which SO question I found the link under, but this article on sitepoint.com (second page) shows another way of storing hierarchical trees in a table that makes it easy to find all child nodes, or the path to the top, things like that. Good explanation with example code.

---

PS. Newish to StackOverflow, is the above ok as an answer, or should it really have been a comment on the question since it's just a pointer to a different solution (not exactly answering the question itself)?