3

我有一个包含以下列的表：group_id、parent_id、name

在这个表中 parent_id 是另一个记录的 group_id。父母与孩子之间存在一对多的关系。这形成了一个层次结构，其中只有一个顶级组的 parent_id 为 NULL。可以有任意数量的深度，但实际上我的层次结构永远不会超过 20 层。

我想检索具有给定 group_id 的组的每个祖先（父母的父母等）。我担心返回的特定方式。

我正在使用 MS SQL 2005，但我也对使用其他 RDBMS 的解决方案感兴趣。

我发现了一些类似的问题，但它们似乎都分解为递归、循环或嵌套集。我不能使用嵌套集，因为我不能改变数据结构。我想尽可能避免递归或循环，或者至少理解为什么不可能。

以下是我在研究时发现的一些问题：

如何选择父ID

没有递归的sql递归

4

3 回答 3

1

该操作本质上是循环的。因为每个节点与其根没有任何有限关系，所以您必须遍历才能发现它。

例如，如果您知道最大深度为 N，那么您可以LEFT OUTER JOIN在单个语句中创建 N 并显示以这种方式返回的最后一个非空父 ID。

循环要求是您根本不知道 N 是什么，并且您不能要求像 SQL 这样的声明性语言来“弄清楚”

即使您可以使用一些内置方法来完成它，它仍然是一个循环或递归，只是被您混淆了。

于 2012-04-25T21:44:39.860 回答
1

如果你确切地知道你的数据结构有多深，你可以手动写出代码：

DECLARE
    @parentId1 int
   ,@parentId2 int
   ...
   ,@parentId19 int
   ,@parentId20 int

SELECT
    @parentId1 = parent_id
FROM
    myTable
WHERE
    group_id = <someid>

SELECT
    @parentId2 = parent_id
FROM
    myTable
WHERE
    group_id = @parentId1

等等。然而，这会给你一大堆额外的代码，并且不会比循环更好，而且它非常脆弱。向树中添加新级别需要您修改代码，这应该是即时的代码味道。

用任何其他语言来考虑它。您必须总共执行任务 X N 次，其中 N 是可变的。你打算怎么写这个？你会使用一个循环。现在假设您的数据结构是一棵树（这就是您在这里得到的）。你会怎么写这个？您可能会使用递归，除非您将递归扁平化为循环。

唯一针对 MSSQL 的警告是，默认情况下，递归堆栈的深度限制为 16。在 MSSQL 中使用循环比使用递归要好得多。

我通常会做这样的事情：

-- Temp table will hold the results starting from the ID of the source item
-- through all its ancestors in ascending order
DECLARE @table TABLE (
    sequence int IDENTITY(1, 1)
   ,group_id int
)

DECLARE @groupId int

SELECT @groupId = <someid>

-- Loop backwards through the group's hierarchy inserting all parent IDs
-- into the temporary table
WHILE @groupId IS NOT NULL
BEGIN
    INSERT INTO @table (
        group_id
    )

    VALUES (
        @groupId
    )

    -- Get the ID of the group's parent ready to loop again
    SELECT @groupId = parent_id
    FROM mutable
    WHERE group_id = @groupId
END

-- Print the results
SELECT group_id
FROM @table

可能有更好的方法，但这将以一种您可以轻松操作的形式为您提供所有 ID，而且它们的顺序正确。

于 2012-04-25T21:47:32.767 回答
1

您可以创建一个类似于您的临时表并像这样填充它：

INSERT INTO #T(group_id, parent_id) SELECT group_id, parent_id FROM Your_Table

现在执行五次完全相同的 SQL：

INSERT INTO #T(group_id, parent_id) SELECT T2.group_id, T1.parent_id FROM #T T1 JOIN #T T2 ON T2.parent_id = T1.group_id LEFT JOIN #T C ON T2.group_id = C.group_id AND T1.parent_id = C.parent_id  AND C.group_id IS NULL
INSERT INTO #T(group_id, parent_id) SELECT T2.group_id, T1.parent_id FROM #T T1 JOIN #T T2 ON T2.parent_id = T1.group_id LEFT JOIN #T C ON T2.group_id = C.group_id AND T1.parent_id = C.parent_id  AND C.group_id IS NULL
INSERT INTO #T(group_id, parent_id) SELECT T2.group_id, T1.parent_id FROM #T T1 JOIN #T T2 ON T2.parent_id = T1.group_id LEFT JOIN #T C ON T2.group_id = C.group_id AND T1.parent_id = C.parent_id  AND C.group_id IS NULL
INSERT INTO #T(group_id, parent_id) SELECT T2.group_id, T1.parent_id FROM #T T1 JOIN #T T2 ON T2.parent_id = T1.group_id LEFT JOIN #T C ON T2.group_id = C.group_id AND T1.parent_id = C.parent_id  AND C.group_id IS NULL
INSERT INTO #T(group_id, parent_id) SELECT T2.group_id, T1.parent_id FROM #T T1 JOIN #T T2 ON T2.parent_id = T1.group_id LEFT JOIN #T C ON T2.group_id = C.group_id AND T1.parent_id = C.parent_id  AND C.group_id IS NULL

在此之后，您的表现在跟踪祖先而不是父母，最多 32 级距离。（2^5 = 32 和 32 > 20）。

这是计算“传递闭包”的一种有效方法，尽管如果您添加循环而不是仅仅重复相同的INSERT五次，您将不再需要您假设大约 20 个级别。INSERT当插入零个新行时，您应该停止。这种循环将有助于而不是损害性能，并且迭代次数将非常少。

于 2012-04-25T21:56:38.943 回答