从传递闭包表中查找最近公共祖先

Question

我有一个表格，代表组织层次结构的传递闭包（即一棵带有单个根的树）:

create table ancestry (
    ancestor   integer,
    descendant integer,
    distance   integer
);

我还有另一个表，里面包含每个用户被允许访问的组织：

create table accessible (
    user         integer,
    organization integer
);

系统向用户展示与每个用户可以访问的组织相关的支出概览。我可以从显示用户公司（根）的视图开始，展示用户直接子组织的清单以及他的组织对总支出的贡献。在大多数情况下，只会有一个子组织，用户需要一级级下钻才能看到多个子组织。我更倾向于从第一个显示多个子组织（即LCA）的组织开始呈现。

对于给定的用户，我可以轻松找到到根路径的集合，但是查找最近公共祖先时遇到了麻烦。我正在使用postgresql 9.1，但更希望能够找到一个与数据库无关的解决方案。在最坏的情况下，我可以将路径拉回应用程序代码中，并在那里计算LCA。

- Faron

---

请求查询的输入是一对用户ID吗？ - wildplasser

顺便问一下：你提到的这两个表之间有没有关系？这可能非常重要。 - wildplasser

Answer 1

我重新审视了这个问题，并开发了以下解决方案。我使用了一个公共表达式来使其更易于理解，但也可以轻松地使用子查询来编写它。

with
hit (id, count) as (
    select
        ancestry.ancestor
       ,count(ancestry.descendant)
    from
        accessible
        inner join ancestry
            on accessible.organization = ancestry.descendant
    where
        accessible.user = @user_id
    group by
        ancestry.ancestor
)
select
    ancestry.descendant as lca
from
    hit
    inner join ancestry
        on ancestry.descendant = hit.id
       and ancestry.ancestor = @company_id
order by
    hit.count desc
   ,ancestry.distance desc
limit 1
;

CTE（通用表达式）是一种技术，它可以计算每个组织在层次结构中的路径数量，这些路径从子级到根节点都经过该组织。然后，LCA（最近公共祖先）是具有最多遍历次数的组织。如果存在平局，则距离根节点最远的组织（即max(distance)）将成为实际的LCA。以下示例更好地说明了这一点。

        A
        |
        B
       / \
      C   D

假设我们希望从上面的树中找到节点C和D的LCA。 hit CTE会生成以下计数：

Node    Count
  A       2
  B       2
  C       1
  D       1

主查询添加了距离：

Node    Count    Distance
  A       2         0
  B       2         1
  C       1         2
  D       1         2

主查询会按照计数和距离的降序对结果进行排序。

Node    Count    Distance
  B       2         1
  A       2         0
  C       1         2
  D       1         2

LCA是列表中的第一项。

- Faron

Answer 2

只是一种直觉，不是数据库无关的（SQL Server），但是可以适应。

SELECT TOP 1
       a1.ancestor
FROM   ancestor a1
       INNER JOIN
       ancestor a2 ON a1.ancestor=a2.ancestor
WHERE  a1.descendent = @Dec1
       AND
       a2.descendent = @Dec2
ORDER BY a1.distance DESC

如果您想在SQLFiddle中放置一些数据，我可以试着操作一下。

- Dale M

---

看起来，给定两个组织，这个查询应该产生这两个节点的LCA。我通过将DESC更改为ASC使其工作，因为我们想要最深的节点。使用DESC始终返回根节点。然而，我需要找到一组节点的LCA，而不仅仅是两个。 - Faron