主页 / dba / 问题 / 278567
Accepted
Christophe
Asked: 2020-10-24 05:54:18 +0800 CST

使用 PostgreSQL 确定网络中的节点

  • 772

我有一个表，其中每个条目都是一个节点，并且该表包含每个节点与其他节点的直接连接。我希望为每个节点创建一个包含链中所有节点的列的视图，而不仅仅是节点本身连接到的节点。

一个示例是从下表的前两列生成“链中的节点”列：

CREATE TABLE example
(
    node text,
    connections text[],
    nodes_in_chain text[]
)

INSERT INTO example VALUES
('a', ARRAY['a','b'],         null),
('b', ARRAY['a','b','c','d'], null),
('c', ARRAY['b','c'],         null),
('d', ARRAY['b','d'],         null),
('e', ARRAY['e','f'],         null),
('f', ARRAY['e','f'],         null);

Node   Connections    Nodes in Chain
"a"    "{a,b}"        "{a,b,c,d}"
"b"    "{a,b,c,d}"    "{a,b,c,d}"
"c"    "{b,c}"        "{a,b,c,d}"
"d"    "{b,d}"        "{a,b,c,d}"
"e"    "{e,f}"        "{e,f}"
"f"    "{e,f}"        "{e,f}"

这是真正问题的一个小简化版本。如果我能解决这个例子，全表应该没问题。

该表的数据可以通过以下方式可视化：

数据

我研究了几种不同的方法来解决这个问题。我研究了递归 CTE，但我没有设法让它们工作。

每个节点都连接到当前在数据库中的自身。如果有必要，在数据库中删除与自身的连接不是问题。

问题可能不必要的背景：

这个问题的根源来自试图识别交通中的车辆。原始数据库包含给定区域内每个时间步 t 的车辆位置和速度。目标是确定在红绿灯处花费的时间。为了解决这个问题，确定了交通信号灯的停车区域。该区域内每辆速度低于某个阈值的车辆都被认为正在等待红绿灯。然而，由于排长队，车辆可能在该区域外排队。因此，一条交通线（“节点链”）由所有彼此相距一定距离内且速度较低的车辆组成。从识别的队列区域内的车辆开始。这个问题是对飞机滑行时间的科学研究的一部分。

我首先使用 Python 和 pandas 执行计算以识别区域内的车辆。然而，代码的运行时间要长 10 倍，这使得该项目望而却步。该代码非常简单，无需手动引入循环，因此无法加速（我相信）。我还将比较在 Python 和 PostgreSQL 中执行排队算法的速​​度。

postgresql postgresql-11

1 个回答

  1. Best Answer

    方法一：

    乍一看，我似乎可以应用一个基本解决方案，因为根据您的示例数据，每个连接都包含在另一个连接中。

    SELECT 
    e1.node, 
    e1.connections, 
    COALESCE(e2.connections, e1.connections) nodes_in_chain
FROM
    example e1
LEFT JOIN 
    example e2
    ON e2.node <> e1.node
    AND e1.connections <@ e2.connections;

    节点 | 连接 | 节点链中
:--- | :------------ | :-------------
一个 | {a,b} | {A B C D}     
乙 | {a,b,c,d} | {A B C D}     
c | {b,c} | {A B C D}     
d | {b,d} | {A B C D}     
电子| {e,f} | {e,f}         
f | {e,f} | {e,f}

    方法二：

    但是，正如@ypercube指出的那样，如果连续有 3 个或更多线性点，则此解决方案不起作用。

    例如：e -> f -> g -> h

    作为解决此问题的参考，我使用了另一个相关问题中的答案：

    它使用一种称为传递闭包的方法来解决问题。

    传递闭包

    在数学中，二元关系 R 在集合 X 上的传递闭包是 X 上包含 R 且传递的最小关系。

    例如，如果 X 是一组机场并且 xRy 表示“从机场 x 到机场 y 有直飞航班”（对于 X 中的 x 和 y），那么 R 在 X 上的传递闭包是关系 R+，使得 x R+ y 的意思是“可以在一次或多次飞行中从 x 飞到 y”。非正式地，传递闭包为您提供了从任何起点可以到达的所有地点的集合。

    首先让我通过添加 4 个节点的线性连接来更改您的示例数据。

    DELETE FROM example WHERE node = 'f';
INSERT INTO example VALUES
('f', ARRAY['e','f','g'],     null),
('g', ARRAY['f','g','h'],     null),
('h', ARRAY['g','h'],         null);

    现在应用数学：

    WITH RECURSIVE al (dst, src) AS --adjacent list or list of all related nodes
(
  SELECT e1.node, e2.node
  FROM   example e1
  JOIN   example e2
         ON e1.node = any(e2.connections)   
), tc (dst, src) AS
   (
     SELECT dst, src FROM al -- transitive closure
     UNION
     SELECT a1.dst, a2.src
     FROM   al as a1 
     JOIN   tc as a2 
            ON a1.src = a2.dst
   )
   SELECT   src, array_agg(DISTINCT dst ORDER BY dst) AS nodes_in_chain
   FROM     tc
   GROUP BY src;

    给我们这个结果：

    src | nodes_in_chain
:-- | :-------------
a   | {a,b,c,d}     
b   | {a,b,c,d}     
c   | {a,b,c,d}     
d   | {a,b,c,d}     
e   | {e,f,g,h}     
f   | {e,f,g,h}     
g   | {e,f,g,h}     
h   | {e,f,g,h}

    db<>在这里摆弄

    注意：原始关系只有直接连接，可以看作长度为 1 的路径（每个 2 个节点）。方法 1 找到所有长度为 2（3 个节点）的路径，因为它应用了一种连接一次的方法。要找到长度为 N 的路径，您必须应用方法 N-1 次。要找到任意长度的所有路径（也就是传递闭包），您需要一个递归解决方案或一个 while 循环。它不能用简单的 SQL 来完成。（即：一个没有 CTE 的查询。）

    @ypercube

    • 6

相关问题