Постгрес направленного обхода графа вверх и вниз

У меня есть проблема, которую я могу решить для небольших наборов данных, но она не работает на больших наборах с (возможно) нечистыми данными.

База данных является реализацией ациклического (надеюсь) графа в PostgreSQL. С тремя столами

vertex_elements: id
edges: id, parent_id, child_id
element_associations: id, user_id, object_id (both are vertex elements, but it unconnected graphs)

У меня есть набор user_ids, из которого я получаю element_associations и начальный vertex_element в графе, и я хочу найти, что все дочерние узлы доступны из element_association с одним из user_ids. Узел считается доступным, если он или один из его предков является одним из кандидатов object_ids элемента element_association.

Граф имеет относительно треугольную форму (несколько корневых узлов с множеством листовых узлов), и из начального элемента вершины моя стратегия заключается в следующем:

  1. Проверьте текущий vertext_element по списку кандидатов element_associations; если это хорошо, все потомки доступны, в противном случае перейдите на...
  2. Проверьте, есть ли предки текущего vertex_element в списке кандидатов element_associations. Аналогично (1), если это хит, тогда все предки доступны, в противном случае перейдите к...
  3. Перейдите к каждому дочернему элементу vertex_element (поиск в ширину) и выполните шаги 1 и 2.

Проблема возникает, когда я хочу избежать двойной проверки одного и того же предка vertex_elements. Основной запрос - это обход вниз, проверка доступности каждого потомка с помощью набора кандидатов element_associations

        WITH RECURSIVE edges_recursive(child_id, parent_id, matching_element_association_id) AS (
          (
            SELECT e1.child_id, e1.parent_id, ea.id
            FROM edges e1
            LEFT OUTER JOIN element_associations ea ON e1.child_id = ea.object_id
              AND ea.id IN (?)
            WHERE parent_id = ?
          )
          UNION
          (
            SELECT e2.child_id, e2.parent_id, ea.id
            FROM edges e2
            INNER JOIN assignments_recursive
            ON edges_recursive.child_id = e2.parent_id
            LEFT OUTER JOIN element_associations ea 
            ON edges_recursive.child_id = ea.object_id
              AND ea.id IN (?)
            WHERE edges_recursive.matching_element_association_id IS NULL
          )
        )

        SELECT edges_recursive.child_id
        FROM edges_recursive
        WHERE edges_recursive.matching_element_association_id IS NOT NULL

Тем не менее, существует дополнительный рекурсивный подзапрос, который проверяет каждый элемент vertex_element в элементе LEFT OUTER JOIN element_associations, который выглядит следующим образом:

ea.id IN (
  WITH RECURSIVE parent_edges_recursive(child_id, parent_id, matching_element_association_id) AS (
    (
      SELECT edges.child_id, edges.parent_id, ea.id
      FROM edges
      LEFT OUTER JOIN element_associations ea 
      ON ea.id IN (?) AND edges.parent_id = ea.object_id
      WHERE edges.child_id = e1.parent_id AND edges.parent_id != e1.parent_id
    )
    UNION
    (
      SELECT edges.child_id, edges.parent_id. ea.id
      FROM edges
      JOIN parent_edges_recursive 
      ON parent_edges_recursive.parent_id = edges.child_id
      LEFT OUTER JOIN element_associations ea
      ON ea.id IN (?) AND edges.parent_id = ea.object_id
      WHERE parent_edges_recursive.matching_element_association_id IS NULL
    )
    SELECT parent_edges_recursive.matching_element_association_id
    FROM parent_edges_recursive
    WHERE parent_edges_recursive.matching_element_association_id IS NOT NULL
    LIMIT 1
 )
)

Проблема в том, что подзапросы стремятся избегать пересечения одной и той же родительской вершины дважды; однако, нет никакой гарантии, что при прохождении графа по потомкам мы не будем перечитывать ранее оцененных предков. Для небольших наборов данных это нормально, и производительность в порядке; тем не менее, это смехотворно не масштабируемо и чрезвычайно устойчиво к циклам.

Что мне нужно сделать, так это сохранить информацию о том, какие родительские vertex_elements я уже перебрал между подзапросами, чтобы избежать повторных шагов; Тем не менее, я застрял на том, как сделать это в единственном запросе.

Источник

1 ответ

Что мне нужно сделать, так это сохранить информацию о том, какие родительские vertex_elements я уже перебрал между подзапросами, чтобы избежать повторных шагов;

Не изучая ваши запросы подробно: вы можете сделать это, собирая идентификаторы в массиве. Примеры кода:

Источник
Другие вопросы по тегам