Recursión sqq sin recursión

Tengo cuatro tablas

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 devuelva todos los grupos a 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 model de datos para disminuir el acceso a la database y, como resultado, tener un mejor performance.

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 siguientes:

 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 

Hay forms de evitar la recursión en las consultas de jerarquía de tree (en oposition a lo que las personas han dicho aquí).

El que he usado más es Conjuntos nesteds .

Sin embargo, al igual que con todas las decisiones técnicas y de vida, se deben realizar intercambios. Los sets nesteds a menudo son más lentos de actualizar pero mucho más rápidos de consultar. Hay forms ingeniosas y complicadas de mejorar la velocidad de actualización de la jerarquía, pero hay otra compensación; performance vs complejidad del código.

Un simple ejemplo de un set nested …

Vista de tree:

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

Representación del set nested

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

Querrá leer el artículo que he vinculado para entenderlo completamente, 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) AND (el valor "rgt" del niño es menor que el valor "rgt" del padre)

"Flash" es por lo tanto un miembro de "REPRODUCTORES DE MP3", "Electrónica Portátil" y "Electrónica"

O, en cambio, los miembros de "Portable Electronics" son:
– Reproductores de mp3
– Destello
– Reproductores de CD
– Radios de 2 vías

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, aparecerá un mofo para mostrarte eso en la lata.

¿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 SQL estándar use esta consulta:

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

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

Si se pregunta 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á join a los grupos.

Algunas variantes de SQL tienen commands 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 plataforms.

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

Mira esta pregunta .

Puedes hacer lo siguiente:

  • Utilice las construcciones START WITH / CONNECT BY PRIOR.
  • Crea una function PL / SQL.

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 tree 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 include 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 navigation, he creado una tabla de nodos como esta:

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

Mi editor crea objects relacionados jerárquicamente desde una class de 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; } } } 

La propiedad Nodos contiene una list de nodos secundarios. Cuando la capa empresarial carga la jerarquía, rectifica las relaciones padre / hijo. Cuando el editor de navigation se guarda, configuro recursivamente los valores de las properties izquierda y derecha, y luego los guardo en la database. Eso me permite sacar los datos en el order correcto, lo que significa que puedo establecer references 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 list de nodos en el order correcto.

Sin un campo parent_id, puede recuperar un rastro de navigation 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 la identificación del nodo que le interesa.

Es 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.