沒有遞歸

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的速度。