Запрос PostgreSQL SQL или PL/pgSQL для обхода ориентированного графа и возврата всех найденных ребер

Я не особо привык генерировать сложные SQL-запросы, и мне трудно смешивать свое понимание процедурных языков и операций над множествами при разработке рекурсивного запроса для обхода сети. Я хочу найти набор ребер, которые лежат «вверх по течению» от определенного узла, путем проведения поиска в глубину ориентированного графа (каждый узел может иметь более одного восходящего края) и в идеале реализовать это в SQL.

Псевдокод того, что я хочу сделать, выглядит следующим образом:

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

Я уже написал следующие функции на чистом SQL:

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

но я изо всех сил пытаюсь понять, как управлять областью видимости и возвращаемыми типами при переводе приведенного выше псевдокода либо в запрос PostgreSQL WITH RECURSIVE, либо в функцию PL/pgSQL. Большинство примеров запросов WITH RECURSIVE, которые я видел, были разработаны для обхода деревьев, где каждый узел имеет только одного родителя. Есть ли у кого-нибудь какие-либо советы/советы, как лучше всего это сделать?

Ваше здоровье,

Будут


postgresql sql recursion plpgsql
person Will Furnass    schedule 09.08.2010    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Видеть:

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

Этот запрос зациклится, если отношения ссылок содержат циклы. Поскольку нам требуется вывод «глубины», простое изменение UNION ALL на UNION не устранит зацикливание. Вместо этого нам нужно распознать, достигли ли мы снова той же строки, следуя определенному пути ссылок. Мы добавляем два столбца пути и цикла к склонному к циклу запросу:

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;
person Denis de Bernardy    schedule 11.08.2010
comment
Спасибо, Денис. Я смог использовать запрос «WITH RECURSIVE», представленный в приведенном вами примере, после того, как понял, что мне нужно создать представление «graph (pipe_id, downstream_node_id, upstream_node_id)», которое было выполнено как нерекурсивный подзапрос WITH для убедитесь, что он выполнялся только один раз для каждого вызова основного запроса обхода графа. Мои обходы графа теперь занимают в 1/200 раза меньше времени, чем при использовании Python/ODBC. - person Will Furnass; 12.08.2010