Нахождение наименьшего общего предка из таблицы переходного закрытия

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 - это организация с наибольшим количеством прохождений. В случае привязки самая дальняя от корня организация (т. Е. Max(расстояние)) - это фактическая LCA. Это лучше всего иллюстрируется на примере.

        A
        |
        B
       / \
      C   D

Предполагая, что мы хотим найти LCA узлов C и D из дерева выше. Хит 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, я могу поиграть с ними.