nested-set-model - 在嵌套集中查找最低公共(public)祖先

Question

我正在寻找一种方法，可以使用单个方程找到嵌套集中的最低公共(public)祖先。

例如，来自图像:https://commons.wikimedia.org/wiki/File:Clothing-hierarchy-traversal.svg

西装和女装之间的 LCA 是服装。我可以使用基于级别的系统来确定 parent 在哪里见面，但这个用例是在数据库设计中，因此提高级别会对性能产生不利影响。

我希望我可以使用西装 (3:8) 和女装 (10:21) 的单一计算得出服装的组合 (1:22)，前提是存在这样的等式。

Answer 1

嵌套集有一个有趣的属性，我们可以用它来找到所有共同的祖先。该属性很简单，一个节点的所有子节点都有一个大于其左侧的左侧和一个小于其右侧的右侧。

这意味着我们需要找到具有包含我们关心的所有节点的左右边界的节点。我们可以通过使用我们关心的节点集来设置我们正在寻找的边界来做到这一点。我们可以很容易地做到这一点，如下所示:

取你想要一个共同祖先的所有节点的左下角和右上角。在这种情况下，您选择的节点的左下角是西装 3，右上角是女式 21。然后，您可以在这个 3:21 的统一节点空间上执行祖先查询。

在这种情况下，您将寻找一组节点，其中 left < 3 和 right > 21。这将为您提供所有共同祖先的集合。在这种情况下，唯一的匹配是服装。衣服上的1小于3，22大于21。

如果你有多个共同的祖先，但你想要最低的，你可以按左列的降序对它们进行排序，并取第一个。

这在 SQL 中可能看起来像这样。我使用的是 T-SQL，因此“前 1”可能是限制 1 或您喜欢的 SQL 中的其他内容。

select top 1 * from Clothing where [left] < 3 and [right] > 21 order by [left] desc