Est-il possible de faire une requête SQL récursive?

Question

J'ai une table semblable à ceci:

CREATE TABLE example (
    id integer primary key, 
    name char(200), 
    parentid integer, 
    value integer); 

je peux utiliser le champ parentid pour organiser des données dans une structure arborescente.

Maintenant, voici le peu que je ne peux pas travailler. Étant donné un parentid, est-il possible d'écrire une instruction SQL pour additionner tous les champs de valeur sous ce parentid et recurse la branche de l'arbre? J'utilise posgreSQL pour que les fonctions MS-SQL de fantaisie ne me soient pas accessibles. Dans tous les cas, j'aimerais que cela soit traité comme une question SQL générique.

BTW, je suis très impressionné d'avoir 6 réponses dans les 15 minutes de poser la question! Allez pile débordement!

Answer 1

Il existe plusieurs façons de faire ce dont vous avez besoin dans PostgreSQL.

• Si vous pouvez installer des modules, consultez la contribution de tablefunc. Il a une fonction connectby() qui gère les arbres traversants. http://www.postgresql.org/docs/8.3/interactive/tablefunc.html

• Consultez également le contrib ltree, que vous pouvez adapter votre table à utiliser: http://www.postgresql.org/docs/8.3/interactive/ltree.html

• Ou vous pouvez traverser l'arbre vous-même avec une fonction PL/PGSQL.

Quelque chose comme ceci:

create or replace function example_subtree (integer) 
returns setof example as 
'declare results record; 
     child record; 
begin 
    select into results * from example where parent_id = $1; 
    if found then 
    return next results; 
    for child in select id from example 
        where parent_id = $1 
     loop 
     for temp in select * from example_subtree(child.id) 
     loop 
      return next temp; 
     end loop; 
     end loop; 
    end if; 
    return null; 
end;' language 'plpgsql'; 

select sum(value) as value_sum 
    from example_subtree(1234); 

Answer 2

est ce SQL Server? Ne pourriez-vous pas écrire une procédure stockée TSQL qui boucle et les syndicats les résultats ensemble?

Je suis également intéressé s'il existe une méthode SQL uniquement pour cela. À partir des bits dont je me souviens de la classe de mes bases de données géographiques, il devrait y avoir.

Answer 3

utilisez un common table expression.

Peut vouloir indiquer que c'est SQL Server 2005 ou supérieur seulement. Dale Ragan

here's an article sur récursion par SqlTeam sans expressions de table commune.

Answer 4

Je pense qu'il est plus facile dans SQL 2008 avec HierarchyID

Answer 5

Si votre utilisation de SQL Server 2005, il existe un moyen vraiment cool de le faire en utilisant des expressions de table commune.

La création d'une table temporaire vous enlève tout le gruntwork et vous permet fondamentalement de tout faire avec juste un WITH et un UNION.

Voici un bon tutoriel:

http://searchwindevelopment.techtarget.com/tip/0,289483,sid8_gci1278207,00.html

Answer 6

Oracle a "COMMENCER" et "CONNECT BY"

select 
    lpad(' ',2*(level-1)) || to_char(child) s 

from 
    test_connect_by 

start with parent is null 
connect by prior child = parent; 

http://www.adp-gmbh.ch/ora/sql/connect_by.html

Answer 7

Si vous voulez une solution portable qui sera fonctionne sur n'importe quel SGBDR ANSI SQL-92, vous devrez ajouter une nouvelle colonne à votre table.

Joe Celko est l'auteur original de l'approche Nested Sets pour le stockage des hiérarchies dans SQL. Vous pouvez Google "nested sets" hierarchy pour en savoir plus sur l'arrière-plan.

Ou vous pouvez simplement renommer parentid à leftid et ajouter un rightid.

Voici ma tentative de résumer des ensembles imbriqués, qui tomberont terriblement courts parce que je ne suis pas Joe Celko: SQL est un langage basé sur des ensembles, et le modèle d'adjacence (enregistrement parent parent) n'est pas une représentation basée sur des ensembles d'une hiérarchie. Par conséquent, il n'existe pas de méthode basée sur des ensembles purs pour interroger un schéma d'adjacence.

Cependant, la plupart des plates-formes majeures ont introduit des extensions ces dernières années pour faire face à ce problème précis. Donc, si quelqu'un répond avec une solution spécifique à Postgres, utilisez-le par tous les moyens.

Answer 8

Si vous devez stocker des graphiques arbitraires, non seulement les hiérarchies, vous pourriez pousser Postgres sur le côté et essayer une base de données de graphique tels que AllegroGraph:

Tout dans la base de données graphique est stockée en tant que triple (nœud source, edge, node cible) et il vous offre un support de première classe pour manipuler la structure du graphe et l'interroger en utilisant un langage similaire à SQL. Il ne s'intègre pas bien avec quelque chose comme Hibernate ou Django ORM, mais si vous êtes sérieux au sujet des structures de graphes (pas seulement les hiérarchies comme le modèle de jeu imbriqué vous le donne), vérifiez-le.

Je crois aussi qu'Oracle a finalement ajouté un support pour de vrais graphiques dans leurs derniers produits, mais je suis étonné que cela ait pris si longtemps, beaucoup de problèmes pourraient bénéficier de ce modèle.

Answer 9

Le code suivant compile et il est testé sur OK.

 
create or replace function subtree (bigint) 
returns setof example as $$ 
declare 
    results record; 
    entry record; 
    recs record; 
begin 
    select into results * from example where parent = $1; 
    if found then 
     for entry in select child from example where parent = $1 and child parent loop 
      for recs in select * from subtree(entry.child) loop 
       return next recs; 
      end loop; 
     end loop; 
    end if; 
    return next results; 
end; 
$$ language 'plpgsql'; 

La condition « enfant <> parent » est nécessaire dans mon cas parce que les noeuds pointent eux-mêmes.

Amusez-vous :)

Answer 10

Depuis la version 8.4, PostgreSQL a recursive query support pour les expressions de table communes utilisant le standard SQL WITH syntaxe.

Answer 11

Tout comme une brève part, bien que la question a été très bien répondu, il convient de noter que si nous traitons cela comme un:

question SQL générique

alors l'implémentation SQL est assez simple, car SQL'99 permet une récursion linéaire dans la spécification (bien que je ne crois pas que les SGBDR implémentent complètement la norme) via l'instruction WITH RECURSIVE. Donc, d'un point de vue théorique, nous pouvons le faire maintenant.

Answer 12

Aucun des exemples travaillé bien pour moi si je l'ai fixé comme ceci:

 
declare 
    results record; 
    entry record; 
    recs record; 
begin 
    for results in select * from project where pid = $1 loop 
     return next results; 
     for recs in select * from project_subtree(results.id) loop 
      return next recs; 
     end loop; 
    end loop; 
    return; 
end; 

Answer 13

Une méthode standard pour faire une requête récursive dans SQL sont CTE récursive. PostgreSQL les prend en charge depuis 8.4.

Dans les versions précédentes, vous pouvez écrire une fonction renvoyant un ensemble récursif:

CREATE FUNCTION fn_hierarchy (parent INT) 
RETURNS SETOF example 
AS 
$$ 
     SELECT example 
     FROM example 
     WHERE id = $1 
     UNION ALL 
     SELECT fn_hierarchy(id) 
     FROM example 
     WHERE parentid = $1 
$$ 
LANGUAGE 'sql'; 

SELECT * 
FROM fn_hierarchy(1) 

Voir cet article:

• Hierarchical queries in PostgreSQL

Answer 14

Voici un exemple de script en utilisant le tableau commun expression:

with recursive sumthis(id, val) as (
    select id, value 
    from example 
    where id = :selectedid 
    union all 
    select C.id, C.value 
    from sumthis P 
    inner join example C on P.id = C.parentid 
) 
select sum(val) from sumthis 

Le script ci-dessus crée une table 'virtuelle' appelée sumthis qui a les colonnes id et val. Il est défini comme le résultat de deux sélections fusionnées avec union all. Le premier select obtient la racine (where id = :selectedid).

Deuxième select suit les enfants des résultats précédents itérativement jusqu'à ce qu'il n'y ait rien à retourner. Le résultat final peut ensuite être traité comme une table normale. Dans ce cas, la colonne val est additionnée.