sql - 没有递归的sql递归

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
}

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

score 16 · Accepted Answer

在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

score 7 · Accepted Answer

有一些方法可以避免树层次结构查询中的递归（与人们在这里所说的相反）。

我用得最多的是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 |
+-------------+----------------------+-----+-----+

您需要阅读我链接的文章以完全理解这一点，但我会尝试给出一个简短的解释。

如果（子项的“lft”（Left）值大于父项的“ltf”值）并且（子项的“rgt”值小于父项的“rgt”值），则一个项是另一个项的成员

“Flash”因此是“MP3 PLAYERS”、“Portable Electronics”和“Electronics”的成员

或者，conversley，“便携式电子产品”的成员是：
- MP3 播放器
- Flash
- CD 播放器
- 2 路收音机

Joe Celko 有一整本关于“SQL 中的树和层次结构”的书。有比你想象的更多的选择，但需要做出很多权衡。

注意：永远不要说不能做某事，一些mofo会出现在can中告诉你。

score 1 · Accepted Answer

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

在任何情况下，使用标准 SQL 使用以下查询：

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

这将为您提供名称和 group_id 列表，每行一对。如果一个实体是多个组的成员，该实体将被多次列出。

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

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

score 0 · Accepted Answer

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

看看这个问题。

score 0 · Accepted Answer

您可以执行以下操作：

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

score 0 · Accepted Answer

我认为这里不需要递归，因为 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;
         }
      }
}

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

如果没有 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 的需要。

sql - 没有递归的sql递归

6 回答 6

Related

Reference