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

Question

我有一个代表图表的表格:Edges(from, to)。

我想用“路径查询”查询这个表，只检索路径的源和目标。

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

+------+----+
| 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 et al., doi://10.1.1.103.3314 的论文中有所概述。 ;不要被理论和数学吓倒，他们还提供随时可用的 sql 代码，他们的基本思想很简单。

广告 2.)

如果维护传递闭包表是您的一个选项，它会在表示路径的开始和结束顶点的一对列上借出一个索引。

如果不是，您也许可以利用图表的结构:对于与扇入相比高(小)的平均扇出，您最好在“to”上使用索引( '来自') 列。

如果您不能对扇出/扇入比率做出假设，您最好在每一列上使用索引。

希望对你有帮助

最好的问候，卡斯滕