mysql - 高效遍历关系数据库中存储为表的图

Question

我有一个表，它表示在边缘列表表示中没有循环依赖关系的图形数据结构，如下所示：

 ________________
| id | from | to |
 ________________
| 1  |  3   |  4 |
| 2  |  3   |  5 |
| 4  |  5   |  7 |
 ________________

是否可以进行 SQL 查询，以便对于特定的 vertex v，直接和间接地检索V由所有连接顶点组成的顶点集？

例如retrieve_all_connected_vertices(3)将返回 set (4, 5, 7)。

我正在研究的方法是那些使用 MySQL 支持的纯 SQL 语句（存储过程等没有选择），或者与某种伪编程语言结合使用的方法。我不是在寻找特定于语言的实现，尽管我将使用 Scala 来实现这个特定目的。

我知道我们基本上可以递归地跟踪链接，直到它到达最后一个顶点，但是，如果可以使用某种优化来减少内存使用或算法复杂性，我会很高兴。

score 0 · Accepted Answer

普通查询将在代码中参数化。

SELECT vertices.to FROM vertices WHERE vertices.from = ?

你必须传递你想要的顶点作为输入，你需要一个可以传递参数的 Scala SQL 连接器。

顺便说一句，请注意也可能是 MySQL 关键字的列名。

1 回答 1