PostgreSQL Requête SQL ou PL/pgSQL pour parcourir un graphe orienté et retourner toutes les arêtes trouvées

Question

Je ne suis pas particulièrement habitué à générer des requêtes SQL complexes et j'ai du mal à mélanger ma compréhension des langages procéduraux et des opérations basées sur les ensembles dans concevoir une requête récursive pour la traversée de réseau. Je souhaite trouver l'ensemble des arêtes qui se trouvent 'en amont' d'un noeud particulier en effectuant une première recherche en profondeur d'un graphe orienté (chaque noeud peut avoir plus d'un arête amont) et idéalement implémenter ceci en SQL.

Le pseudo-code pour ce que je veux faire se présente comme suit:

interesting_pipes = Pipes[] 

func find_all_pipes_upstream(node n) 
if is_inlet(nodename) 
    return Nil 
else 
    for p in upstream_pipes: 
    if p in interesting_pipes: 
     return Nil 
    else 
    interesting_pipes.append(p) 
    find_all_pipes_upstream(upstream_node(p)) 

Je l'ai déjà écrit les fonctions suivantes dans le plus pur SQL:

upstream_pipes(node_name varchar) RETURNS SETOF "Pipes" 
upstream_node(pipe_name varchar) RETURNS "Node" 
is_inlet(node_name) RETURNS boolean 

, mais je suis mal à comprendre comment pour gérer les types de portée et de retour lors de la traduction du pseudo-code ci-dessus en requête PostgreSQL WITH RECURSIVE ou en une fonction PL/pgSQL. La plupart des exemples que j'ai vus de WITH RECURSIVE requêtes ont été conçus pour traverser à travers les arbres où chaque nœud a seulement un parent. Quelqu'un at-il des conseils/conseils sur la meilleure façon de s'y prendre?

Cheers,

Will

Answer 1

Voir:

http://www.postgresql.org/docs/8.4/static/queries-with.html

Cette requête boucle si les relations de liaison contiennent des cycles. Parce que nous avons besoin d'une sortie "en profondeur", le simple changement de UNION ALL en UNION n'éliminerait pas la boucle. Au lieu de cela, nous devons reconnaître si nous avons atteint à nouveau la même ligne tout en suivant un chemin particulier de liens. Nous ajoutons deux colonnes path et cycle à la requête sujette à une boucle:

WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS (
     SELECT g.id, g.link, g.data, 1, 
      ARRAY[g.id], 
      false 
     FROM graph g 
     UNION ALL 
     SELECT g.id, g.link, g.data, sg.depth + 1, 
      path || g.id, 
      g.id = ANY(path) 
     FROM graph g, search_graph sg 
     WHERE g.id = sg.link AND NOT cycle 
) 
SELECT * FROM search_graph;