在图表中索引和查询路径的最有效方法

Question

我有一个代表图形的表格：边缘（从，到）。

我想使用“路径查询”查询此表，仅检索路径的源和目的地。

例如，假设我的表包含以下行：

+------+----+
| from | to |
+------+----+
| a    | b  |
| b    | c  |
| c    | d  |
| f    | g  |
| b    | f  |
| c    | a  |
+------+----+ 

假设我执行以下（伪）查询：

SELECT ?v1, ?v2 WHERE ?v1 to ?t1, ?t1 to ?t2, ?t2 to ?v2;

这意味着我想要包含 4 个节点的所有路径中存在的所有源和目标对。执行此查询应返回以下结果：

+-----+-----+
| ?v1 | ?v2 |
+-----+-----+
| a   | a   |
| a   | g   |
| a   | d   |
+-----+-----+

当然，也可能需要由不同数量的节点组成的路径，数字 4 不是硬编码的:-)

我的问题是：

1. 构建此类 SQL 查询的最佳方法是什么（请注意，我使用的是 SQLite，因此无法使用递归查询）。
2. 我目前有一个用于 from 列的索引和一个用于 to 列的索引。这是最优的吗？我是否应该为“from, to”对创建一个索引？相反？

假设

1. 没有自边（例如“a - a”）。

2. 没有两个相同的行。

。

Answer 1

广告 1。）
除非您事先知道您的路径将始终具有给定长度（或一小组给定长度），否则您无法用纯 sql 表达您的查询。但是，您可以选择逐步维护图的传递闭包，特别是如果

• 对图的更改不频繁
• 和/或主要是边缘插入（而不是删除），
• 或者主要是在允许进行某些预处理的情况下作为批量更改发生。

dong 等人的论文中概述了该技术，doi： //10.1.1.103.3314;不要被理论和数学吓倒，他们还提供现成的 SQL 代码，而且他们的基本思想很简单。

ad 2.)

如果维护传递闭包表是您的一个选择，那么它可以借给表示路径起始和结束顶点的一对列上的一个索引。

如果不是，您可能可以利用图表的结构：对于与扇入相比高（小）的平均扇出，您应该更好地在“to”（“from”）上建立索引） 柱子。

如果您无法对扇出/扇入比率做出假设，那么您最好在每列上建立一个索引。

希望它有帮助，

最诚挚的问候，卡斯滕