1 сент. 2013 г.

Построение списка зависимых объектов

Замечательная задача для проверки программиста на знание SQL и реляционных БД. Пусть в одной таблице хранится список объектов. Объекты могут зависеть друг от друга. Связи хранятся в другой таблице ввиде пар ключей: объект - объект, от которого зависит данный объект. Требуется построить упорядоченный список, чтобы для любого объекта в нем, все объекты, от которых он зависит, располагались перед ним.

Решение с использованием рекурсивного CTE:

WITH RECURSIVE
  ns_tree AS (
    SELECT
      n.filename AS headname,
      0 AS usescount,
      CAST((n.xid || '_' || n.dbid) AS VARCHAR(1024)) AS path,
      n.filename
    FROM
      at_namespace_file n

    UNION ALL

    SELECT
      t.headname,
      (t.usescount + 1) AS usescount,
      (t.path || '-' || n.xid || '_' || n.dbid) AS path,
      n.filename
    FROM
      ns_tree t
      JOIN at_namespace_file_link l
        ON l.filename = t.filename
      JOIN at_namespace_file n
        ON l.uses_xid = n.xid and l.uses_dbid = n.dbid
    WHERE
      POSITION ((n.xid || '_' || n.dbid) IN t.path) = 0
    )
SELECT
  t.headname, sum(t.usescount)
FROM
  ns_tree t
GROUP BY
  1
ORDER BY
  2
В приведенном запросе at_namespace -- список объектов, а at_namespace_link -- связи между ними. Вычисление пути (path) и дополнительная проверка через функцию POSITION позволяют избежать зацикливания на кольцевых ссылках, если такие попадутся в исходных данных.

Комментариев нет:

Отправить комментарий