3

組織階層の推移閉包を表すテーブルがあります（つまり、単一のルートを持つツリー）。

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

各ユーザーがアクセスを許可されている組織を含む別のテーブルがあります。

create table accessible (
    user         integer,
    organization integer
);

システムは、ユーザーがアクセスできる各組織に関連付けられた支出のロールアップをユーザーに表示します。私はいつでも、ユーザーに会社のビュー（つまり、ルート）を表示して、ユーザーに直接の子組織のリストと、彼の組織が合計にどれだけ貢献しているかを表示することから始めることができます。ほとんどの場合、子は1人であり、ユーザーは複数の子を表示する前に複数のレベルをドリルダウンする必要があります。私は、複数の子供を示す最初の組織（つまり、LCA）からプレゼンテーションを開始したいと思います。

特定のユーザーの場合、ルートへのパスのセットを簡単に見つけることができますが、最も一般的でない祖先を見つけるのに問題があります。私はpostgresql9.1を使用していますが、データベースに依存しないソリューションを好みます。最悪の場合、ルートへのパスをアプリケーションのコードに戻し、そこでLCAを計算できます。

4

2 に答える 2

2

私はこれを見直して、次のソリューションを開発しました。動作を理解しやすくするためにcommon-table-expressionを使用しましたが、サブクエリを使用して簡単に記述できました。

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を見つけたいと仮定します。ヒット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はリストの最初の項目です。

于 2013-01-31T12:26:52.637 に答える
0

データベースにとらわれず（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 に答える