SQL recursion

Question

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

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 get visible groups for this user. This means that the group includes users 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 get these values ​​using recursion and several database queries. But I would like to know if this can be done with a single SQL query to improve the performance of my application. I am using MySQL.

Answer 1

Two things come to mind:

1 - . You can reconnect the table to yourself to recursively approach 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 

This will give you the following results:

 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 connection for each level that you want to go through the tree. If your tree has less than, say, 20 levels, then you will probably be able to avoid this by creating a view showing 20 levels from each user.

2 - The only other approach I know is to create a recursive database function and call it from code. You will still have some search overhead (i.e., your # queries will still be equal to the number of levels that you go through the tree), but in general this should be faster as it all happens in the database.

I'm not sure about MySql, but in Oracle such a function will be similar to this (you have to change the names of tables and fields, I just copy what 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 Clecko's books "SQL for Smarties" and "Trees and Hierarchies in SQL for Smarties" describe methods that completely eliminate recursion using nested sets. This complicates the upgrade, but makes other queries (which usually need recursion) relatively easy. There are some examples in this article written by Joe back in 1996.

Answer 3

I think you need CURSOR for this, this link may help

Answer 4

I do not think that this can be done without using recursion. You can execute it with a single stored procedure using mySQL, but recursion is not allowed by default in stored procedures. This article has information on how to enable recursion. I'm not sure what impact this would have on performance than on a multi-query approach. mySQL may perform some optimization of stored procedures, but otherwise I expect the performance to be the same.

Answer 5

I don’t know if you had a Users table, so I get the list through User_ID 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 

This returns:

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

Which seems correct according to the data in your table. But it does not match your expected list of values ​​(for example, user 9 is in only one group in the table data, but you show it in the results as belonging to two)

EDIT: Dang. Just noticed that you are using MySQL. My solution was for SQL Server. Unfortunately.

- Kevin Fairchild

Answer 6

There was already a similar question raised.

Here is my answer (slightly edited):

I'm not sure I understood your question correctly, but this might work "I take trees in SQL . "

A related post is the described method of storing a tree in a database - PostgreSQL in this case - but the method is clear enough, so it can be easily used for any database.

Using this method, you can easily update all nodes depending on a modified node K with approximately N simple SELECT queries, where N is the distance from K from the root node.

Good luck

Answer 7

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

---

PS. Newish to StackOverflow, is this normal as an answer, or should it be a comment on this question, since it is just a pointer to another solution (not quite answering the question itself)?

Answer 8

There is no way to do this in the SQL standard, but you can usually find extensions for providers, such as CONNECT BY in Oracle.

UPDATE: As noted by the comments, this was added in SQL 99.