sql - 从传递闭包表中查找最小公祖

我有一个表表示组织层次结构的可传递闭包（即，它是一个具有单个根的树）：

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

我还有一个表，其中包含允许每个用户访问的组织：

create table accessible (
    user         integer,
    organization integer
);

系统向用户显示与用户可以访问的每个组织相关联的支出汇总。我总是可以从向用户显示公司的视图（即根）开始，向用户显示直接子组织的列表，以及他的组织在总数中所占的比例。在大多数情况下，只有一个子级，用户需要在看到多个子级之前向下钻取多个级别。我更愿意从第一个显示多个孩子的组织（即LCA）开始演示。
对于给定的用户，我可以很容易地找到到根的路径集，但是很难找到最不常见的祖先。我使用的是postgresql 9.1，但我更喜欢不依赖数据库的解决方案。在最坏的情况下，我可以将根路径拉回到应用程序的代码中，并在那里计算LCA。

最佳答案

我重新审视了这个问题，并开发了以下解决方案。我使用了一个通用的表表达式，以便更容易理解它是如何操作的，但是可以很容易地使用子查询编写它。

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
;

对于层次结构中的每个组织，hit CTE计算从子级到遍历该组织的根级的路径数。生命周期评价是最具遍历性的组织。在平局的情况下，离根最远的组织（即最大（距离））是实际的生命周期评价。这最好用一个例子来说明。

        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

生命周期评价是列表中的第一项。