I have a hierarchy that I have represented as a closure table, as described by Bill Karwin. I am trying to write a query that will return the nodes sorted as a depth-first traversal. This reply would solve my problem, except that in my structure some nodes appear more than once because they have multiple parents.

My sample data looks like this:

• 1
  • 2
    • 5
  • 3
    • 5
  • 4
    • 6
    • 2
      • 5

As you can see, node 2 appears twice, both as a child and a grandchild of the root. Node 5 appears twice as a grandchild of the root (each time with a different parent), and then again as a great-grandchild because its parent, node 2, is repeated.

This will set up the data as a closure table:

or as an adjacency list:

I can produce a breadth-first traversal (although 5 only appears as a grandchild once):

but my attempt at a depth-first traversal using breadcrumbs fails (it shows the repeated nodes only once because of the GROUP BY a.descendant):

Is it possible to output a depth-first traversal using a closure table representation?

Should I use an alternative representation? I can't use recursive CTEs, because I'm restricted to MySql (which doesn't implement them).

我正在使用 PostgreSQL 9.1 来查询分层树结构数据，这些数据由连接到节点的边（或元素）组成。这些数据实际上是针对流网络的，但我已将问题抽象为简单的数据类型。考虑示例tree表。每条边都有长度和面积属性，用于从网络中确定一些有用的指标。

如下图所示，其中由 AE 表示的边与节点 1-5 相连。NULL to_node(Ø) 表示结束节点。总是独一无二的from_node，所以它可以充当PK。如果这个网络像流域一样流动，它将是从上到下的，其中起始支流边缘是 A、B、C，结束流出边缘是 E。

文档为WITH如何在递归查询中使用搜索图提供了一个很好的示例。因此，要获取“转发”信息，查询从末尾开始，并向后工作：

以上是有道理的，并且适用于大型网络。例如，我可以看到B边缘距离末端有 3 条边，而前向路径{B,D,E}从末端到末端的总长度为 3.5。

但是，我想不出构建反向查询的好方法。也就是说，从每条边来看，累积的“上游”边、长度和面积是多少。使用WITH RECURSIVE，我拥有的最好的是：

我想在递归查询的第二项中构建聚合，因为每个下游边缘都连接到 1 个或许多上游边缘，但是递归查询不允许聚合。另外，我知道连接是草率的，因为with recursive结果有多个连接条件edge。

反向/反向查询的预期结果是：

如何编写此更新查询？

请注意，我最终更关心的是累积准确的长度和面积总数，并且路径属性用于调试。在我的实际案例中，前向路径多达几百条，我预计大型复杂流域的反向路径有数万条。

我在思考 SQL 闭包表时遇到了一些困难，希望在理解我找到的一些示例方面得到一些帮助。

假设我有一个sample_items使用以下分层数据调用的表：

树结构实际上应该是这样的：

为了便于查询树（例如查找特定 id 的所有后代），我使用 Bill Karwin 在这篇出色的 SO 帖子中描述的方法调用了sample_items_closure一个表。我还使用一个可选path_length列来在需要时查询直接子级或父级。如果我正确理解此方法，我的闭包表数据将如下所示：

现在的每一行在表中sample_items都有一个条目，sample_items_closure用于它自己和它的所有祖先。到目前为止，一切都说得通。

然而，在研究其他闭包表示例时，我遇到了一个为链接到根级别 (ancestor_id 0) 并且路径长度为 0 的每一行添加一个额外的祖先的示例。使用我上面的相同数据，这就是闭包表如下所示：

为了提供更好的上下文，这是该站点上使用的选择查询，已修改以适合我的示例：

我有两个与此方法相关的问题：

问题一：

为什么要添加一个额外的行将每个后代链接到根级别（id 0）？

问题2：

为什么这些条目的 path_length 为 0，而不是前一个祖先的 path_length+1？例如：

奖励问题：当树的完整结构已经在闭包表中表达时，为什么某些示例仍然包含邻接列表（我的示例中的parent_id列）？sample_items

I'm trying to retrofit a transitive closure table into a system that currently uses adjacency lists using MySQL, based on the recipe given in SQL Antipatterns. However, I've run into a snag with the implementation of moving subtrees.

I've constructed an extreme simplification of the existing system and the closure table for the development effort, and will port this over to the real data once I've got it to work in a satisfactory manner. My tables are as follows:

My test data is as follows:

I've implemented triggers that will insert rows into the closure table on row creation in the product table and delete rows from the closure table when product rows are deleted and they work fine, but MySQL limitations are keeping me from getting the update case (where the parent in the product table changes) to work.

If I wanted to update node 4 so that it was the child of node 2 instead of node 1.

The SQL antipatterns book gives queries for doing this. The first one is intended to orphan the existing subtree by deleting the relevant rows from the closure table.

But of course MySQL won't let you do this because of a deficiency in its design that doesn't let you alter any table you're using in a subquery.

I'm attempting to re-write the query into a self-join because then I can delete the rows from that. I've changed the original query to select instead of delete because that does work, and I can use it as a baseline for comparison. However my attempt to replicate the query with joins returns an empty set.

I need to be able to keep the query that's executed relatively simple because it needs to go in a trigger. I also can't use temporary tables because the live SQL server is running in a cluster and we've had issues in the past where the use of temporary tables has broken replication. If anyone can help with re-writing the query into a form that will allow me to delete rows in MySQL I'd appreciate it.

问题/示例/预期值

我需要为表示流网络的有向图确定Strahler 数或Strahler 流顺序。我可以使用查询向前和向后WITH RECURSIVE推导信息，但似乎我需要做一些不同的事情来确定 Strahler 数。

例如，这里有一个 19 段的流网络，有 10 个支流和一个出口。每个段的上游部分由节点 ID 表示。

和表结构中的相同数据，其中段由 连接to_node，对于盆地出口为空。

expected_orderStrahler 数的预期结果 ( ) 在此处可视化：

共有三个规则（来自GRASS 7.0 手册）：

1. 如果该节点没有子节点，则它的 Strahler 顺序为 1。
2. 如果该节点有一个且只有一个支流具有 Strahler 最大阶i，并且所有其他支流的阶小于 i ，则该阶保持为i。
3. 如果节点有两个或多个最大阶i的支流，则该节点的 Strahler 阶为i + 1。

我发现/尝试了什么

从我在挖掘解决这个问题的过程中发现，这个计算可以用 SQL 完成（除了我认为他们的“SQL 脚本”是为 MS SQL Server 编写的）。但是，我还没有找到可以用 PostgreSQL 9.1 完成的事情。

我最好的尝试之一是计算来自每个节点的上游节点的数量，它正确地识别了支流（一阶），但不是其他的：

一个想法是使用具有适当设置的窗口框架范围的nth_value(value any, nth integer) 窗口函数。但是，我不确定如何设置它，或者是否可以设置它来识别 Strahler 号码。另一个 [不那么令人兴奋的] 想法是为每个 Strahler 数字手动运行迭代，我希望我的真实世界数据在 5 到 8 个订单（迭代）之间。这可以通过一个语句来完成。但任何更好的想法都会受到欢迎。DO

我正在为 Doctrine 2 和 Closure Table Strategy 使用 Tree - Nestedset 行为扩展。在我的网站上，用户可以创建文件夹和子文件夹并查看它们。我通过使用 Closure Table 策略实现了这一点，并使用childrenHierarchy()方法渲染文件夹：

它工作正常，但它返回所有用户的所有文件夹，我不知道在这种情况下如何定义user_id以仅呈现属于登录用户的文件夹。有没有办法做到这一点？

我会很高兴你的回答。

我有一个要求，我需要为特定职位选择家长部门。我有桌子

现在，一个职位可以有一个父级作为另一个职位或部门。假设 Pos1 的父项为 Pos2，Pos2 的父项为 Pos3，而 Pos3 现在的父项为 Dept1。所以在这里我如何通过其他位置获得作为 Pos1 的父级的 Dept1。现在在这里，如果 Dept1 是 Pos1 的直接父级，那么我可以找到并修复它，但是如果某个职位间接在部门中有父级，如何编写查询。

感谢所有回复。现在说如果我想获得 Pos3 的家长部门。那我就简单的说

现在这将给该职位的家长部门并且由于 Pos1 没有作为直接家长的部门所以现在我说

希望这可以帮助。

我有一些使用闭包表模型存储的现有数据。我是 Doctrine 的新手，并试图为此“Doctrine 方式”实现一个实体，但不确定如何进行。我试图遵循的理念是实体应该只是一个普通的旧 PHP 对象，并且应该使用某种注释来配置父子关联。

在这篇文章中，我将使用 Category 作为示例实体。这是我想象的实体的样子：

闭包表如下所示：

这个表本质上是一个连接表——它只存储父子关系，所以我认为这里有一个实体没有意义，类似于创建多对多关系时没有实体与@JoinTable.

我希望能够像任何其他实体一样使用我的类别实体，当我从存储库中获取它时填充$parent/并在被调用时执行 SQL 以反映新添加的子项。$children$em->flush()

此处使用的一些 SQL 示例：

添加一个新的孩子：

将子树移动到新父级：

获取类别的所有子项：

我在这里有几个问题。首先，这似乎是一种合理的方法/可以用 Doctrine 实现的东西吗？如果没有，有没有更好的方法来解决这个问题？

如果这看起来确实是一种合理的方法，我想知道如何去攻击它？我更多的是寻找我需要将这些文件放在哪里/我需要如何设置类而不是有人给我一个实际的实现。任何可以帮助我入门的文档或示例将不胜感激。我对 Doctrine 的经验几乎为零——希望我在这里没有遗漏任何明显的东西。

我正在尝试使用数据宏更新闭包表，每当将新记录插入主表时，都需要运行以下代码：

如您所见，可以使用嵌套循环执行此操作：

主表（tblNodes）和闭包表（tblClosure）都存储在后端数据库中，所以看起来数据宏应该能够做我想要的。

数据宏似乎也有函数Create Record (in...)和For Each Record (in...)。但我根本无法让第二个开火。

这是我的代码（我已经定义temp_node并temp_parent作为参数）：

我知道传递闭包概念用于存储树结构数据。这个概念还用于以非常高效和快速的方式检索分层数据，并以最少的复杂查询。

在 SQLite 查询浏览器中，我尝试了以下查询：

我可以使用查询号创建表。1 但查询没有。2 不工作。

有人可以提供使用 SQLite 在 Android 中的具体示例吗？