3

I have a table with the following columns: group_id, parent_id, name

In this table parent_id is the group_id of another record. There is a 1 to N relationship of parents to children. This forms a hierarchy with only one top level group having NULL for a parent_id. There could be an arbitrary amount of depth, but in practice my hierarchy is never more than 20 levels deep.

I would like to retrieve every ancestor (a parent's parent and so on) of a group with a given group_id. I am concerned about the particular way this is returned.

I am using MS SQL 2005, but I am also interested in solutions using other RDBMSs.

I have found some similar questions, but they all seem to break down to recursion, looping or nested sets. I cannot use nested sets, because I cannot change the data structure. I would like to avoid recursion or looping where possible, or at least understand why it is not possible.

Here are some question I found while researching this:

How to select parent ids

Sql recursion without recursion

4

3 に答える 3

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

操作は本質的にループします。各ノードはルートに対して有限の関係を持っていないため、それを発見するにはトラバースする必要があります。

たとえば、最大深度が N であることがわかっている場合LEFT OUTER JOIN、1 つのステートメントで N 個の s を作成し、この方法で返された最後の null 以外の親 ID を表示できます。

ループの要件は、単純に N が何であるかを知らないことであり、SQL のような宣言型言語に「それを理解する」ように要求することはできません。

組み込みのメソッドでそれを達成できたとしても、難読化されたループまたは再帰になります。

于 2012-04-25T21:44:39.860 に答える
1

You can create a temporary table similar to yours and populate it like this:

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

Now perform the exact same SQL five times: 

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

After this, your table now tracks ancestors rather than parents, up to 32 levels of distance. (2^5 = 32 and 32 > 20).

This is one efficient way to compute "transitive closure", although if you add looping instead of just repeating the same INSERT five times, you will not need your assumption about 20 levels any more. You should just stop when the INSERT inserts zero new rows. This kind of looping will help rather than hurt performance as well as the number of iterations will be very small.

于 2012-04-25T21:56:38.943 に答える