Как найти всех «родственных» родителей из таблицы, содержащей набор (parent, child)?

Question

У меня есть таблица SQL Server 2005 следующим образом:

parent  child
1       a
2       a
2       b
3       b
3       c
4       c
5       d
6       d
7       d
8       e
9       e
9       f
10      f

У каждого родителя может быть один или несколько детей, у каждого ребенка также может быть один или несколько родителей. Как я могу найти (или группу) всех родителей, которые связаны?

В вышеприведенном случае я хочу сгруппировать:

parent 1, 2, 3, 4 into group 1
parent 5, 6, 7 into group 2
parent 8, 9, 10 into group 3

Результат запроса будет выглядеть следующим образом: (не имеет значения, какой родитель использует группу, если он принадлежит одному из родительских элементов в группе, мин. Или макс. Идентификаторы)

parent  child  parent_group
1       a      1
2       a      1
2       b      1
3       b      1
3       c      1
4       c      1
5       d      5
6       d      5
7       d      5
8       e      8
9       e      8
9       f      8
10      f      8

Это похоже на те стандартные боссы - подчиненные рекурсивные вопросы SQL, за исключением того, что у подчиненного может быть более 1 босса.

Можно ли использовать SQL для генерации результата, как указано выше? Если так, то как?

Ценю любую помощь.

Answer 1

Нет способа сделать это за один запрос.Я нашел пост в блоге (с немного кода рубина ), описывающий, как вы можете вычислять связанные компоненты в SQL (разновидность MySQL).

Основываясь на статье, я написалследующий SQL (разновидность SQL Server):

-- Step 1: Create temporary tables
CREATE TABLE #items (
    id int PRIMARY KEY,
    component_id int
);

CREATE TABLE #links (
    first int,
    second int,
    PRIMARY KEY (first, second)
);

CREATE TABLE #components_to_merge (
    component1 int,
    component2 int
    PRIMARY KEY (component1, component2)
);

-- Step 2: Populate tables
INSERT INTO #items (id, component_id)
SELECT DISTINCT parent, parent
FROM children;

INSERT INTO #links (first, second)
SELECT DISTINCT c1.parent, c2.parent
FROM children c1
INNER JOIN children c2 ON c1.child = c2.child
WHERE c1.parent <> c2.parent;

-- Step 3: Merge components
WHILE 1 = 1 BEGIN
    -- Step 3.1: Update #components_to_merge
    TRUNCATE TABLE #components_to_merge;

    INSERT INTO #components_to_merge (component1, component2)
    SELECT DISTINCT t1.component_id, t2.component_id
    FROM #links l
    INNER JOIN #items t1 ON t1.id = l.first
    INNER JOIN #items t2 ON t2.id = l.second
    WHERE t1.component_id <> t2.component_id;

    INSERT INTO #components_to_merge (component1, component2)
    SELECT component2, component1
    FROM #components_to_merge m1
    WHERE component2 NOT IN (
        SELECT m2.component2
        FROM #components_to_merge m2
        WHERE m2.component1 = m1.component1
    );

    IF (SELECT COUNT(*) FROM #components_to_merge) = 0
        BREAK;

    -- Step 3.2: Update #items
    UPDATE i
    SET component_id = target
    FROM #items i
    INNER JOIN (
        SELECT
            component1 AS source,
            MIN(component2) AS target
        FROM #components_to_merge
        GROUP BY component1
    ) new_components
        ON source = component_id
    WHERE target < component_id;
END;

-- Step 4: Generate result
SELECT parent, child, component_id
FROM children
INNER JOIN #items ON id = parent;

Вы можете заключить это в хранимую процедуру:

CREATE PROCEDURE CalculateComponents AS
BEGIN
    SET NOCOUNT ON;
    BEGIN TRANSACTION;

    -- SQL code from above

    ROLLBACK TRANSACTION;
END;

И затем вызвать ее с помощью

EXEC CalculateComponents;

Вывод:

parent  child   component_id
1       a       1
2       a       1
2       b       1
3       b       1
3       c       1
4       c       1
5       d       5
6       d       5
7       d       5
8       e       8
9       e       8
9       f       8
10      f       8