Sql recursion without recursion

Question

I have four tables

create table entities{
integer id;
string name;
}

create table users{
integer id;//fk to entities
string email;
}

create table groups{
integer id;//fk to entities
}

create table group_members{
integer group_id; //fk to group
integer entity_id;//fk to entity
}

I want to make a query that returns all groups where a user belongs, directly or indirectly. The obvious solution is to make a recursion at the application level. I’m wondering what changes can I make to my data model to decrease the database access and as a result have a better performance.

Answer 1

In Oracle:

SELECT  group_id
FROM    group_members
START WITH
        entity_id = :user_id
CONNECT BY
        entity_id = PRIOR group_id

In SQL Server:

WITH    q AS
        (
        SELECT  group_id, entity_id
        FROM    group_members
        WHERE   entity_id = @user_id
        UNION ALL
        SELECT  gm.group_id, gm.entity_id
        FROM    group_members gm
        JOIN    q
        ON      gm.entity_id = q.group_id
        )
SELECT  group_id
FROM    q

In PostgreSQL 8.4:

WITH RECURSIVE
        q AS
        (
        SELECT  group_id, entity_id
        FROM    group_members
        WHERE   entity_id = @user_id
        UNION ALL
        SELECT  gm.group_id, gm.entity_id
        FROM    group_members gm
        JOIN    q
        ON      gm.entity_id = q.group_id
        )
SELECT  group_id
FROM    q

In PostgreSQL 8.3 and below:

CREATE OR REPLACE FUNCTION fn_group_members(INT)
RETURNS SETOF group_members
AS
$$
        SELECT  group_members
        FROM    group_members
        WHERE   entity_id = $1
        UNION ALL
        SELECT  fn_group_members(group_members.group_id)
        FROM    group_members
        WHERE   entity_id = $1;
$$
LANGUAGE 'sql';

SELECT  group_id
FROM    group_members(:myuser) gm

Answer 2

There are ways of avoiding recursion in tree hierarchy queries (in opposition to what people have said here).

The one I've used most is Nested Sets.

As with all life and technical decisions, however, there are trade offs to be made. Nested Sets are often slower to update but much faster to query. There are clever and complicated ways of improving the speed of updating the hierarchy, but there's another trade-off; performance vs code complexity.

A simple example of a nested set...

Tree View:

 -Electronics
 |
 |-Televisions
 | |
 | |-Tube
 | |-LCD
 | |-Plasma
 |
 |-Portable Electronics
   |
   |-MP3 Players
   | |
   | |-Flash
   |
   |-CD Players
   |-2 Way Radios

Nested Set Representation

+-------------+----------------------+-----+-----+
| category_id | name                 | lft | rgt |
+-------------+----------------------+-----+-----+
|           1 | ELECTRONICS          |   1 |  20 |
|           2 | TELEVISIONS          |   2 |   9 |
|           3 | TUBE                 |   3 |   4 |
|           4 | LCD                  |   5 |   6 |
|           5 | PLASMA               |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |  10 |  19 |
|           7 | MP3 PLAYERS          |  11 |  14 |
|           8 | FLASH                |  12 |  13 |
|           9 | CD PLAYERS           |  15 |  16 |
|          10 | 2 WAY RADIOS         |  17 |  18 |
+-------------+----------------------+-----+-----+

You'll want to read the article I linked to understand this fully, but I'll try to give a short explanation.

An item is a member of another item if (the child's "lft" (Left) value is greater than the parent's "ltf" value) AND (the child's "rgt" value is less than the parent's "rgt" value)

"Flash" is therfore a member of "MP3 PLAYERS", "Portable Electronics" and "Electronics"

Or, conversley, the members of "Portable Electronics" are:
- MP3 Players
- Flash
- CD Players
- 2 Way Radios

Joe Celko has an entire book on "Trees and Hierarchies in SQL". There are more options than you think, but lots of trade off's to make.

Note: Never say something can't be done, some mofo will turn up to show you that in can.