从传递闭包表中查找最小公元

Question

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

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

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

create table accessible (
    user         integer,
    organization integer
);

系统向用户显示与用户可以访问的每个组织关联的支出汇总。我总是可以从向用户显示公司视图（即根）开始，向用户显示直接子组织的列表以及他的组织对总数的贡献。在大多数情况下，将有一个子级，用户需要向下钻取多个级别，然后才能看到多个子级。我更愿意从第一个显示多个孩子的组织（即 LCA）开始演示。

对于给定的用户，我可以很容易地找到到根的路径集，但很难找到最不常见的祖先。我正在使用postgresql 9.1，但更喜欢与数据库无关的解决方案。在最坏的情况下，我可以将根路径拉回应用程序的代码中并在那里计算 LCA。

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 是遍历次数最多的组织。在平局的情况下，离根最远的组织（即最大（距离））是实际的LCA。最好用一个例子来说明这一点。

        A
        |
        B
       / 
      C   D

假设我们希望从上面的树中找到节点 C 和 D 的 LCA。命中的 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 是列表中的第一项。

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中放一些数据，我可以玩一玩。