postgre SQL中图形的连接组件数

Question

我的PostgreSQL数据库中有一个图，为了示例起见，让我们将其定义为：

CREATE TABLE nodes (node_id INTEGER);
CREATE TABLE roads (road_id INTEGER, nodes INTEGER[]);
INSERT INTO nodes VALUES (1), (2), (3), (4), (5);
INSERT INTO roads VALUES (1, {1, 2}), (2, {3, 4}));

我想创建一个SQL查询，返回图中连接组件的数量，在这个例子中，这个数字是3，因为节点1/2是连接的，3/4也是连接的，而5没有连接到任何东西。

我试着搜索find&SQL中的联合实现，但没有用，然后我转向了CTE，但我不能独自完成，我想到了这样的东西：

WITH RECURSIVE cc(iterator_id, node_id, rank, iterator) AS
(
        SELECT row_number() OVER(), n.node_id, row_number() OVER (), 1 FROM nodes AS n
    UNION ALL
        # Something here that does the magic
)
SELECT
    COUNT(DISTINCT rank) AS no_of_cc
FROM
    cc,
    (SELECT COUNT(*) FROM nodes) AS last_iterator_id
WHERE iterator = last_iterator_id;

其中在每次迭代中，我们更新迭代器_id<=迭代器。我们迭代直到iterator等于最大的iterator_id但我想不出递归部分。

你能帮我找到连接的组件的数量吗？

Answer 1

你现在怎么了？尽管我向您推荐用PL/Python编写存储过程，但后来我还是决定编写单个sql查询，只是为了好玩。以下是我所做的。我使用了RECURSIVE CTE。

WITH RECURSIVE graph_search(node_id, connected_to, path, cycle) AS (
        SELECT node_id, connected_to, ARRAY[node_id], false FROM paths
    UNION 
        SELECT p.node_id, p.connected_to, gs.path || p.node_id, p.node_id=ANY(gs.path)
        FROM graph_search gs JOIN paths p ON gs.connected_to = p.node_id AND NOT gs.cycle
 ),
 paths AS (
    SELECT node_id, connected_to
    FROM (
        SELECT n.node_id, unnest(r.nodes) AS connected_to
        FROM nodes n JOIN roads r ON n.node_id = ANY(r.nodes)
    ) sub
    WHERE node_id <> connected_to
 ) 
SELECT count(DISTINCT component)
FROM (
        SELECT node_id,
               array_agg(DISTINCT reachable_node ORDER BY reachable_node) as component
        FROM (
            SELECT node_id, unnest(path) as reachable_node from graph_search 
        ) sub
        GROUP BY node_id
    UNION ALL /*need to append lonely nodes - they are components for themselves*/
        SELECT node_id, ARRAY[node_id]
        FROM nodes
        WHERE node_id NOT IN (SELECT node_id from paths)
) sub;

• 首先，我需要图形本身的不同表示。名为paths的普通CTE创建了具有成对连接节点的两列表
• 然后，我只是稍微修改了PostgreSQL手册中的示例，这样我就有了节点列表和从中可以访问的每个节点
• 聚合为我提供了图形的组件
• 最后我数了数不同的组成部分

Answer 2

如果节点数量过大，上述解决方案将不起作用。

最有效的解决方案（只要你有足够的RAM来读取所有数据）是用C或C++等语言将数据读取到内存中，并在那里进行计算。

但如果数据太大，你别无选择，那么你可能可以这样做：

（plpgssql实现，假设我们有表路（node1，node2））

CREATE TABLE node AS
  SELECT DISTINCT node1 AS id, node1 AS color
  FROM roads
  CREATE OR REPLACE FUNCTION merge_node()
  RETURNS VOID
AS
$$
DECLARE
left_to_do INT := 1;
counter INT :=1;
row record;
BEGIN
    DROP TABLE IF EXISTS t;
CREATE TEMP TABLE t  (
    node1 INT,
    prev INT,
    next INT
);
    WHILE left_to_do > 0
    LOOP
        WITH joined_table AS (
            SELECT roads.node1,
                   MAX (v1.color) AS prev,
                   MAX (v2.color) AS next
            FROM roads
            JOIN node v1 ON roads.node1 = v1.id
            JOIN node v2 ON roads.node2 = v2.id
            GROUP BY roads.node1
        )
        INSERT INTO t (node1, prev, next)
        SELECT node1,
               prev,
               next
        FROM joined_table
        WHERE prev < next;
        SELECT COUNT(*) INTO left_to_do FROM t;
        UPDATE node color
        SET color = t.next
        FROM t
        WHERE color.id = t.node1;
        DELETE FROM t;
        counter := counter + 1;
    END LOOP;
END;
$$
LANGUAGE plpgsql;

如果节点度与节点数量相比较低，则这应该会更好地工作。在具有2.4mln节点和24mln边的图上对其进行了测试，使用索引大约需要30-60分钟。（相比之下，在C++中，它需要2.5分钟，大部分时间从csv读取数据/将数据写入csv）

Answer 3

本文在数据库连接组件分析中描述了一种基于SQL的算法。它使用了相当多的表来存储中间结果。本文在Apache HAWQ数据库管理系统中评估了该算法，但它似乎可以移植到PostgreSQL。