récursion Sql sans récursion

Question

J'ai quatre 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 
} 

Je veux faire une requête qui retourne tous les groupes où un utilisateur appartient, directement ou indirectement. La solution évidente est de faire une récursion au niveau de l'application. Je me demande quels changements puis-je apporter à mon modèle de données pour diminuer l'accès à la base de données et, par conséquent, avoir de meilleures performances. Pouvez-vous clarifier la différence entre une entité et un utilisateur?

Answer 1

Sinon, vos tableaux semblent OK. Vous faites l'hypothèse qu'il existe une relation plusieurs-à-plusieurs entre les groupes et les entités.

Dans tous les cas, avec l'utilisation standard SQL cette requête:

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

Cela vous donnera une liste des noms et group_ids, une paire par ligne. Si une entité est membre de plusieurs groupes, l'entité sera listée plusieurs fois.

Si vous vous demandez pourquoi il n'y a pas de JOIN dans la table des groupes, c'est parce qu'il n'y a aucune donnée de la table des groupes qui n'est pas déjà dans la table group_members. Si vous incluez, par exemple, un nom de groupe dans la table des groupes, et que vous vouliez que ce nom de groupe soit affiché, vous devrez également vous joindre à des groupes.

Certaines variantes SQL ont des commandes liées à la création de rapports. Ils vous permettraient de lister plusieurs groupes sur la même ligne qu'une seule entité. Mais ce n'est pas standard et ne fonctionnerait pas sur toutes les plateformes.

Answer 2

Si vous voulez un niveau d'imbrication vraiment théoriquement infini, alors la récursivité est la seule option qui exclut toute version saine de SQL. Si vous êtes prêt à le limiter, il existe plusieurs autres options.

Découvrez this question.

Answer 3

Vous pouvez effectuer les opérations suivantes:

• Utilisez la touche START AVEC/CONNECT BY PRIOR constructs.
• Créez une fonction PL/SQL.

Answer 4

En Oracle:

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

En 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 

En 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 

En PostgreSQL 8.3 et ci-dessous:

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

Il sont façons d'éviter la récursivité dans les requêtes de la hiérarchie des arbres (en opposition à ce que les gens ont dit ici).

Celui que j'ai le plus utilisé est Nested Sets.

Comme pour toutes les décisions techniques et de vie, il y a des compromis à faire.Les ensembles imbriqués sont souvent plus lents à mettre à jour, mais beaucoup plus rapides à interroger. Il y a des façons intelligentes et compliquées d'améliorer la vitesse de mise à jour de la hiérarchie, mais il y a un autre compromis; performance vs complexité du code.

Un exemple simple d'un ensemble imbriqué ...

Arbre Vue:

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

Nested Set Représentation

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

Vous voulez lire le article I linked pour comprendre pleinement , mais je vais essayer de donner une courte explication. Un élément est membre d'un autre élément if (la valeur "lft" (Left) de l'enfant est supérieure à la valeur "ltf" du parent) AND (la valeur "rgt" de l'enfant est inférieure à la valeur "rgt" du parent)

"flash" est therfore un membre de "lECTEURS MP3", "Appareils électroniques portatifs" et "électronique"

Ou, conversley, les membres de "l'électronique portable" sont:
- lecteurs MP3
- Flash
- Lecteurs CD
- Radios 2 voies

Joe Celko a un livre entier sur "Arbres et Hiérarchies en SQL". Il y a plus d'options que vous ne le pensez, mais beaucoup de compromis à faire.

Note: Ne dites jamais que quelque chose ne peut pas être fait, certains mofo se présenteront pour vous montrer que dans can.

Answer 6

Je ne pense pas qu'il y ait un besoin de récursion ici car la solution affichée par barry-brown semble adéquate. Si vous avez besoin d'un groupe pour pouvoir être membre d'un groupe, alors la méthode de traversée d'arbre proposée par Dems fonctionne bien. Les insertions, suppressions et mises à jour sont assez simples avec ce schéma, et la récupération de la hiérarchie entière est accomplie avec un seul select.

Je suggère d'inclure un champ parent_id dans votre table group_members (en supposant que c'est le point où votre relation récursive se produit). Dans un éditeur de navigation que j'ai créé une table de nœuds comme ceci:

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

... 

Mon éditeur crée des objets hiérarchiquement liés à partir d'un noeud C# classe

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; 
     } 
     } 
} 

propriété des noeuds contient une liste de nœuds enfants. Lorsque la couche de gestion charge la hiérarchie, elle corrige les relations parent/enfant. Lorsque l'éditeur de navigation enregistre, je récursivement définir les valeurs de propriété gauche et droite, puis enregistrer dans la base de données. Cela me permet d'obtenir les données dans le bon ordre, ce qui signifie que je peux définir des références parent/enfant au cours de la récupération au lieu d'avoir à faire une seconde passe. Cela signifie également que tout ce qui doit afficher la hiérarchie (par exemple, un rapport) peut facilement extraire la liste de nœuds dans le bon ordre.

Sans un champ id_parent, vous pouvez récupérer une piste de navigation au noeud courant avec

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

où @id est l'identifiant du nœud qui vous intéresse.

Assez évident, mais cela s'applique à des éléments tels que l'appartenance à un groupe imbriqué qui peut ne pas être évident, et comme d'autres l'ont dit, il n'est plus nécessaire de ralentir le SQL récursif.