recursividad SQL sin recursividad

Question

Tengo cuatro mesas

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 
} 

Quiero hacer una consulta que devuelve todos los grupos en los que pertenece un usuario, directa o indirectamente. La solución obvia es hacer una recursión en el nivel de la aplicación. Me pregunto qué cambios puedo hacer en mi modelo de datos para disminuir el acceso a la base de datos y como resultado tener un mejor rendimiento.

Answer 1

¿Puedes aclarar la diferencia entre una entidad y un usuario? De lo contrario, sus tablas se ven bien. Está asumiendo que existe una relación de muchos a muchos entre grupos y entidades.

En cualquier caso, con el uso de SQL estándar de esta consulta:

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

esto le dará una lista de nombres y group_ids, un par por línea. Si una entidad es miembro de múltiples grupos, la entidad se listará varias veces.

Si se está preguntando por qué no hay JOIN en la tabla de grupos, es porque no hay datos de la tabla de grupos que aún no estén en la tabla group_members. Si incluyó, por ejemplo, un nombre de grupo en la tabla de grupos, y desea que se muestre ese nombre de grupo, también deberá unirse a los grupos.

Algunas variantes de SQL tienen comandos relacionados con los informes. Le permitirían enumerar múltiples grupos en la misma línea que una sola entidad. Pero no es estándar y no funcionaría en todas las plataformas.

Answer 2

Si desea un nivel de anidamiento verdaderamente teórico infinito, la recursión es la única opción, lo que impide cualquier versión sana de SQL. Si está dispuesto a limitarlo, hay varias otras opciones.

Echa un vistazo this question.

Answer 3

Usted puede hacer lo siguiente:

• utilizando Iniciar CON/CONNECT BY PRIOR constructs.
• Crea una función 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 y abajo:

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

Hay son formas de evitar la repetición en las consultas de estructura jerárquica (en oposición a lo que se ha dicho aquí).

El que he usado más es Nested Sets.

Como con todas las decisiones técnicas y de vida, sin embargo, hay compensaciones que deben hacerse.Los conjuntos anidados a menudo son más lentos de actualizar pero mucho más rápidos de consultar. Hay formas ingeniosas y complicadas de mejorar la velocidad de actualización de la jerarquía, pero hay otra compensación; rendimiento vs complejidad del código.

Un ejemplo simple de un conjunto anidado ...

vista de árbol:

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

conjuntos anidados Representación

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

Usted querrá leer el article I linked para comprender plenamente esta , pero intentaré dar una breve explicación.

Un artículo es miembro de otro artículo si (el valor "lft" del niño (izquierda) es mayor que el valor "ltf" del padre) Y (el valor "rgt" del niño es menor que el valor "rgt" del padre)

"flash" es therfore un miembro de "reproductores MP3", "Electrónica portátil" y "Electrónica"

o, conversley, los miembros de "la electrónica portátil" son:
- reproductores de MP3
- Flash
- Reproductores de CD
- 2 vías de radios

Joe Celko tiene un libro completo sobre "Árboles y jerarquías en SQL". Hay más opciones de lo que piensas, pero hay muchas concesiones que hacer.

Nota: nunca digas que algo no se puede hacer, algunos mofo aparecerán para mostrarte eso en la lata.

Answer 6

No creo que haya necesidad de recurrencia aquí, ya que la solución publicada por barry-brown parece adecuada. Si necesita un grupo para poder ser miembro de un grupo, el método de cruce de árbol ofrecido por Dems funciona bien. Las inserciones, eliminaciones y actualizaciones son bastante sencillas con este esquema, y ​​la recuperación de toda la jerarquía se logra con una sola selección.

Sugeriría incluir un campo parent_id en su tabla group_members (suponiendo que ese sea el punto en el que ocurre su relación recursiva). En un editor de navegación que he creado una tabla de nodos de este modo:

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

... 

Mi editor crea objetos relacionados jerárquicamente de una clase nodo 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; 
     } 
     } 
} 

propiedad de los nodos contiene una lista de nodos secundarios. Cuando la capa empresarial carga la jerarquía, rectifica las relaciones padre/hijo. Cuando el editor de navegación se guarda, configuro recursivamente los valores de las propiedades izquierda y derecha, y luego los guardo en la base de datos. Eso me permite sacar los datos en el orden correcto, lo que significa que puedo establecer referencias padre/hijo durante la recuperación en lugar de tener que hacer un segundo pase. También significa que cualquier otra cosa que necesite mostrar la jerarquía (por ejemplo, un informe) puede sacar fácilmente la lista de nodos en el orden correcto.

Sin un campo parent_id, puede recuperar una ruta de navegación al nodo actual con

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

donde @id es el id del nodo que le interesa.

Bastante obvio, en realidad, pero se aplica a elementos como la membresía grupal anidada que podría no ser obvia, y como otros han dicho elimina la necesidad de ralentizar el SQL recursivo.