没有递归

Question

我有四个表

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 
} 

的Sql递归我想要返回其中一个用户属于直接或间接所有组的查询。显而易见的解决方案是在应用程序级进行递归。我想知道我可以对数据模型进行哪些更改以减少数据库访问，并因此获得更好的性能。

Answer 1

你能澄清实体和用户之间的区别吗？否则，你的表格看起来不错。您假设组和实体之间存在多对多关系。

在任何情况下，与标准的SQL使用此查询：

SELECT name, group_id 
FROM entities JOIN group_members ON entities.id = group_members.entity_id; 

这会给你的名字和group_ids的列表，每行一对。如果一个实体是多个组的成员，则该实体将被多次列出。

如果您想知道为什么组表中没有JOIN，这是因为组表中没有数据不在group_members表中。如果您在组表中包含组名称，并且希望显示该组名称，那么您也必须加入组。

某些SQL变体具有与报告相关的命令。他们将允许您在同一行上列出多个组作为单个实体。但它不是标准的，并不适用于所有平台。

Answer 2

如果你想要一个真正理论上无限级别的嵌套，那么递归是唯一的选择，它排除任何理智的SQL版本。如果你愿意限制它，那么还有其他一些选择。

结帐this question。

Answer 3

你可以做到以下几点：

• 使用START WITH/CONNECT BY PRIOR constructs。
• 创建一个PL/SQL函数。

Answer 4

在Oracle：

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

在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 

在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 

在PostgreSQL 8.3及以下：

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 5

There are避免树层次结构查询中递归的方式（与人们在这里所说的相反）。

我最常用的一个是Nested Sets。

然而，与所有生命和技术决策一样，要做出折衷。嵌套集的更新速度通常较慢，但查询速度要快得多。有一些聪明和复杂的方法来提高更新层次结构的速度，但还有另一种折衷方案;性能与代码复杂度。

的一组嵌套一个简单的例子...

树视图：

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

嵌套集表示

+-------------+----------------------+-----+-----+ 
| 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 | 
+-------------+----------------------+-----+-----+ 

你想读的article I linked充分理解这，但我会尽量给出一个简短的解释。

如果项目是另一个项目的成员（孩子的“lft”（左侧）值大于父母的“ltf”值）AND（孩子的“rgt”值小于父母的“rgt”值）

“闪光” 是therfore “MP3播放器” 中的一员， “便携式电子产品” 和 “电子”

或者conversley， “便携式电子” 的成员是：
- MP3播放器
- 闪存
- CD播放机
- 双向无线电

Joe Celko有一本关于“SQL中的树和层次结构”的书。有比你想象的更多的选择，但很多折衷的做法。

注意：永远不要说不能做的事情，一些mofo会出现，告诉你，在可以。

Answer 6

我不认为这里需要递归，因为barry-brown发布的解决方案似乎足够了。如果你需要一个组来成为一个组的成员，那么Dems提供的树遍历方法就可以很好地工作。这种方案的插入，删除和更新非常简单，只需一次选择即可完成检索整个层次结构。

我建议在你的group_members表中包含一个parent_id字段（假设这是发生递归关系的点）。在导航编辑，我已经创建了一个节点的表像这样：

tbl_nodes  
---------- 
node_id 
parent_id 
left  
right 
level 

... 

我的编辑从C＃节点类创建分层相关对象

class node { 
     public int NodeID { get; set; } 
     public Node Parent { get; set; } 
     public int Left { get; set; } 
     public int Right { get; set; } 
     public Dictionary<int,Node> Nodes { get; set; } 
     public int Level { 
     get { 
      return (Parent!=null) ? Parent.Level+1 : 1; 
     } 
     } 
} 

节点属性包含子节点的列表。当业务层加载层次结构时，它会纠正父/子关系。当导航编辑器保存时，我递归设置左右属性值，然后保存到数据库。这让我能够以正确的顺序获取数据，这意味着我可以在检索过程中设置父/子引用，而不必进行第二次传递。也意味着需要显示层次结构的其他任何内容（例如报表）都可以轻松地按照正确的顺序获取节点列表。

如果没有PARENT_ID场，你可以检索浏览路径当前节点与

select n1.* 
from nodes n1, nodes n2 
where d1.lft <= d2.lft and d1.rgt >= d2.rgt 
and d2.id = @id 
order by lft; 

其中@id是你感兴趣的节点的ID。

很明显的东西，真的，但它适用于可能不明显的嵌套组成员资格等项目，正如其他人所说的那样消除了减慢递归SQL的速度。