3

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

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

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

create table accessible (
    user         integer,
    organization integer
);

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

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

4

2 回答 2

2

I took a fresh look at this and developed the following solution. I used a common-table-expression to make it easier to understand how it operates but it could easily be written using a sub-query.

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
;

The hit CTE counts, for each organization in the hierarchy, the number of paths from a child to the root that traverse the organization. The LCA is then the organization with the most traversals. In the event of a tie, the organization farthest from the root (i.e., max(distance)) is the actual LCA. This is best illustrated with an example.

        A
        |
        B
       / \
      C   D

Assuming we wish to find the LCA of nodes C and D from the tree above. The hit CTE produces the following counts:

Node    Count
  A       2
  B       2
  C       1
  D       1

The main query adds the distance:

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

The main query then orders the results by descending count and distance

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

The LCA is the first item in the list.

于 2013-01-31T12:26:52.637 回答
0

只是预感而不是 db 不可知论 (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 中放一些数据，我可以玩一下。

于 2013-01-31T01:02:38.447 回答