sql - 有向图 SQL

Question

我有以下数据集，它表示有向图中的节点。

CREATE TABLE nodes (NODE_FROM VARCHAR2(10),
                    NODE_TO VARCHAR2(10));

INSERT INTO nodes VALUES('GT','TG');
INSERT INTO nodes VALUES('GG','GC');
INSERT INTO nodes VALUES('AT','TG');
INSERT INTO nodes VALUES('TG','GC');
INSERT INTO nodes VALUES('GC','CG');
INSERT INTO nodes VALUES('TG','GG');
INSERT INTO nodes VALUES('GC','CA');
INSERT INTO nodes VALUES('CG','GT');

视觉表示： http ://esser.hopto.org/temp/image1.JPG

使用此数据集，我希望用户输入一个级别（例如 2），这将返回距离特定节点 2 个“跃点”的所有节点）：

NODE_FROM  NODE_TO

TG        GC
TG        GG
AT        TG
GT          TG

http://esser.hopto.org/temp/image2.JPG

我目前的尝试如下所示：

SELECT node_from, node_to
  FROM nodes
  WHERE level <= 2   -- Display nodes two "hops" from 'AT'
START WITH node_from = 'AT'
CONNECT BY NOCYCLE PRIOR node_to = node_from
    OR    node_to = PRIOR node_from
GROUP BY node_from, node_to;

http://esser.hopto.org/temp/image3.JPG

如您所见，缺少关系：GT -> TG。

Answer 1

所以你的图表看起来像这样：

您可以使用 Oracle 的START WITH/CONNECT BY功能来做您想做的事。如果我们从节点 GA 开始，我们可以到达图中的所有节点，如下所示。

CREATE TABLE edges (PARENT VARCHAR(100), CHILD VARCHAR(100));

insert into edges values ('AT', 'TG');
insert into edges values ('CG', 'GT');
insert into edges values ('GA', 'AT');
insert into edges values ('GC', 'CA');
insert into edges values ('GC', 'CG');
insert into edges values ('GG', 'GC');
insert into edges values ('GT', 'TG');
insert into edges values ('TG', 'GA');
insert into edges values ('TG', 'GC');
insert into edges values ('TG', 'GG');
COMMIT;

SELECT *
  FROM edges
START WITH CHILD = 'GA'
CONNECT BY NOCYCLE PRIOR CHILD = PARENT;

输出：

    PARENT  CHILD
1   TG      GA
2   GA      AT
3   AT      TG
4   TG      GC
5   GC      CA
6   GC      CG
7   CG      GT
8   CG      GT
9   GC      CA

注意 由于您的图表有循环，因此使用 上的NOCYCLE语法很重要CONNECT BY，否则这将不起作用。

基于 OP 最新编辑的编辑答案

首先，我假设“2 跳”是指“最多 2 跳”，因为您当前的查询使用level <= 2. 如果你想要 2 跳，它应该是level = 2.

在您更新的图表 (image2.JPG) 中，没有从 AT 到 GT 的路径需要 2 跳，因此查询返回了我所期望的。从 AT 到 GT，我们可以去AT->TG->GC->CG->GT，但那是 4 跳，大于 2，所以这就是为什么你没有得到那个结果。

如果您希望能够在 2 跳内到达 AT 到 GT，那么您需要在 TG 和 GT 之间添加一条边，如下所示：

INSERT INTO nodes VALUES('TG','GT');

现在，当您运行查询时，您将获得以下数据：

NODE_FROM NODE_TO AT TG TG GC TG GG TG GT

请记住，START WITH/CONNECT BY只有在节点之间存在路径时才会起作用。在您的图表中（在我添加上面的新边之前），没有路径AT->TG->GT，所以这就是您没有得到结果的原因。

现在，如果您添加了 edge TG->AT，那么我们将拥有 path GT->TG->AT。因此，在这种情况下，AT 距离 GT 有 2 跳（即我们现在要走相反的路，从 GT 开始，到 AT 结束）。但是要找到这些路径，您需要设置 START WITH node_from = 'GT'。

如果您的目标是找到从起始节点到任何级别 <= 2 跳或更少的目标节点的所有路径，那么上面应该可以工作。

但是，如果您想全部找到从某个目标节点返回到源节点的所有路径（即我给出的反向示例 from GT->TG->AT），那么这在此处行不通。您必须对图中的所有节点运行查询。

将START WITH/CONNECT BY其视为进行深度优先搜索。它将从一个起始节点到任何地方。但它不会做更多的事情。

概括：

鉴于上述限制，我认为查询工作正常。我已经解释了为什么GT-TG不返回路径，所以我希望这是有道理的。

但是请记住，如果您也尝试遍历反向路径，则必须遍历每个节点并运行查询，START WITH每次都更改节点。

Answer 2

听起来您需要一份Joe Celko 的 Trees and Hierarchies in SQL for Smarties的副本。