问题标签 [transitive-closure]

我有一个元组列表（每个元组由 2 个数字组成），例如：

可以说，这些数字是一些 db 对象（记录）的 id，在一个元组中，有重复对象的 id。这意味着 1 和 2 是重复的。1 和 3 是重复的，这意味着 2 和 3 也是重复的。

如果 a == b 和 b == c 那么 a == c

现在我想将所有这些重复的对象 id 合并到一个元组中，如下所示：

我知道我可以使用循环和冗余匹配来做到这一点。我只想要一些具有低处理/计算（如果有的话）的更好的解决方案。

我的目的是在 Prolog 中实现一个简单的传递性示例（仅针对我自己）。

这些是我的事实：

我写了这个谓词来检查是否A信任C，只要有一个B信任C并A信任这个的，这就是真的B：

谓词例如返回true或trusts(p1, p2)，trusts(p1, p5)但trusts(p5, p6)已经返回ERROR: Out of local stack。

Prolog 会这么快地淹没堆栈吗？

还是我的想法/实施trusts不良/浪费系统内存？

我以与此答案类似的方式使用闭包表。我有以下两个表：

哪个是保存数据的表。

这是关闭表。它使用列长度来记录您在树中的深度。这是我正在使用的测试数据：

在每个孩子只有一个父母的情况下，以下查询以正确的顺序输出整个树：

但是，当数据库中有同一个孩子的多个父母时，这不起作用。我得到的是：

我想要的是：

我明白为什么会发生这种情况，但我不知道如何解决它。我应该使用什么查询以正确的顺序拉动整个树？

我在 swipl 中有一个非常简单的程序

但是当我进行查询时，edge(a,c).我得到一个 Out of local stack 异常。奇怪的是，当我在 Windows 中执行相同的查询时，程序运行良好。

我试图增加本地堆栈，但只是程序需要更长的时间来抛出异常。

是否可以保证 SPARQL 中的传递查询的结果按照它们被遍历的顺序返回？

所以，给定一些简单的数据：

（在实践中，这种关系可以重复很多次）

查询（使用 sparql 1.1）：

这样你总是会回来[step0，step1，step2]。在耶拿尝试这个时，我得到一致但随机排序的结果。

或者，如果我可以在传递步行中取回父母和孩子，这样我就可以在外面重新排序它会很好，但我不知道如何绑定?parent ex:contains* <http://example.com/step3>和取回中间关系的对象而不编写一个非常慢的带有过滤的嵌套查询。

我正在寻找一种方法来返回传递 SPARQL 查询中的父和子，并且只返回构成路径的关系。

以下查询返回指向http://example.com/child的父对象和中间对象对，但如果任何 ?parents 有其他包含语句，那么也会返回这些语句。这可以产生非常大的结果集。

有没有办法既可以将传递查询中的终端对象绑定到特定资源，又可以返回每个关系中的对象，但不是所有其他的 ex:contains 每个父对象的关系？

例如，使用下图：

结果将是：

我正在使用 Jena 和 Fuseki 运行此查询。谢谢！

我想知道在 python 库 graph_tool 中计算无向图的传递闭包的最佳方法是什么。

到目前为止，我的解决方案是从原始图创建一个有向图并在其上使用 transitive_closure 方法：

当然必须有更好，更有效的方法来做到这一点？

以下是我的知识库中的事实（http://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/recursion.html（递归练习 2））：

现在我想用递归来推断出明显的“鲍勃”比“乔治”高。

我试图添加这个规则来解决这个问题：

我需要您的帮助来为此递归设置停止条件，因为现在我遇到了堆栈溢出错误：

谢谢

我很难找到不是等价关系的关系的传递闭包的例子。

我正在使用一些代表文件系统的表，我需要选择每个文件夹的完整路径作为扁平字符串。

第一个表列出了每个文件夹的详细信息：

第二个表列出了文件夹关系的传递闭包：

对于示例数据，假设存在以下文件夹：

这些将保留在这些表中，如下所示：

一些需要注意的细节：

1. 每个文件夹在 中都有一个“身份行” FolderClosures，其中AncestorFolderID = DescendantFolderID AND IsDirect = 0.

2. 每个不是顶级文件夹的文件夹在FolderClosureswhere 中都只有一行IsDirect = 1

3. FolderClosures每个文件夹可以包含许多行，其中AncestorFolderID <> DescendantFolderID AND IsDirect = 0. 这些中的每一个都代表“祖父母”或更远的关系。

4. 由于没有列可以为空，因此没有行明确声明给定文件夹是顶级文件夹。这只能通过检查有问题的文件夹的 ID在FolderClosures哪里没有行来辨别。IsDirect = 1 AND DescendantFolderID = SomeIDSomeID

我希望能够运行返回此数据的查询：

文件夹可以无限嵌套，但实际上可能最多只有 10 层。查询可能需要返回几千个文件夹的路径。

当数据作为邻接列表持久存在时，我发现了很多关于创建此类查询的建议，但我无法找到像这样的传递闭包设置的答案。我发现的邻接列表解决方案依赖于使用可为空的父文件夹 ID 持久化的行，但这在这里不起作用。

如何获得所需的输出？

如果有帮助，我正在使用 SQL Server 2016。