隣接リスト階層をすべてのパスのリストに平坦化
https://stackoverflow.com/questions/764497
-
11-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
隣接リスト モデルを使用して階層情報を格納するテーブルがあります。(自己参照キーを使用します - 以下の例。この表は次のように見えるかもしれません おなじみ):
category_id name parent
----------- -------------------- -----------
1 ELECTRONICS NULL
2 TELEVISIONS 1
3 TUBE 2
4 LCD 2
5 PLASMA 2
6 PORTABLE ELECTRONICS 1
7 MP3 PLAYERS 6
8 FLASH 7
9 CD PLAYERS 6
10 2 WAY RADIOS 6
上記のデータをこのようなものに「平坦化」する最良の方法は何ですか?
category_id lvl1 lvl2 lvl3 lvl4
----------- ----------- ----------- ----------- -----------
1 1 NULL NULL NULL
2 1 2 NULL NULL
6 1 6 NULL NULL
3 1 2 3 NULL
4 1 2 4 NULL
5 1 2 5 NULL
7 1 6 7 NULL
9 1 6 9 NULL
10 1 6 10 NULL
8 1 6 7 8
各行は、階層を通る 1 つの「パス」です。ただし、 各ノード (それぞれだけではありません リーフノード）。category_id 列は現在のノードを表し、「lvl」列はその祖先です。現在のノードの値は、右端の lvl 列にもなければなりません。lvl1 列の値は常にルート ノードを表し、lvl2 列の値は常に lvl1 の直接の子孫を表します。
可能であれば、この出力を生成する方法は SQL であり、n 層階層で機能するはずです。
解決
単純な隣接リストに対してマルチレベル クエリを実行するには、必ず自己左結合が必要になります。右揃えの表を作成するのは簡単です。
SELECT category.category_id,
ancestor4.category_id AS lvl4,
ancestor3.category_id AS lvl3,
ancestor2.category_id AS lvl2,
ancestor1.category_id AS lvl1
FROM categories AS category
LEFT JOIN categories AS ancestor1 ON ancestor1.category_id=category.category_id
LEFT JOIN categories AS ancestor2 ON ancestor2.category_id=ancestor1.parent
LEFT JOIN categories AS ancestor3 ON ancestor3.category_id=ancestor2.parent
LEFT JOIN categories AS ancestor4 ON ancestor4.category_id=ancestor3.parent;
あなたの例のように左揃えにするのは少し難しいです。これが思い浮かびます:
SELECT category.category_id,
ancestor1.category_id AS lvl1,
ancestor2.category_id AS lvl2,
ancestor3.category_id AS lvl3,
ancestor4.category_id AS lvl4
FROM categories AS category
LEFT JOIN categories AS ancestor1 ON ancestor1.parent IS NULL
LEFT JOIN categories AS ancestor2 ON ancestor1.category_id<>category.category_id AND ancestor2.parent=ancestor1.category_id
LEFT JOIN categories AS ancestor3 ON ancestor2.category_id<>category.category_id AND ancestor3.parent=ancestor2.category_id
LEFT JOIN categories AS ancestor4 ON ancestor3.category_id<>category.category_id AND ancestor4.parent=ancestor3.category_id
WHERE
ancestor1.category_id=category.category_id OR
ancestor2.category_id=category.category_id OR
ancestor3.category_id=category.category_id OR
ancestor4.category_id=category.category_id;
n 層階層で機能します。
申し訳ありませんが、隣接リスト モデルでは任意の深さのクエリは実行できません。この種のクエリを頻繁に実行する場合は、スキーマを次のいずれかに変更する必要があります。 階層情報を保存する他のモデル:完全な隣接関係 (すべての祖先と子孫の関係を保存)、実体化されたパス、またはネストされたセット。
カテゴリがあまり移動しない場合 (例のようなストアの場合は通常これに当てはまります)、私はネストされたセットを使用する傾向があります。
他のヒント
前述したように、SQL には動的に変化する列数を持つテーブルを実装するきれいな方法がありません。私がこれまでに使用した解決策は次の 2 つだけです。1.固定数のセルフで、固定数の列を与えます（Bobinceに従って）2。結果を単一列の文字列として生成します
2 番目のものは、最初はグロテスクに聞こえます。IDを文字列として保存?!しかし、出力が XML などの形式になっている場合、人々はそれほど気にしないようです。
同様に、SQL で結果を結合する場合にも、これはほとんど役に立ちません。結果がアプリケーションに提供される場合、これは非常に適しています。ただし、個人的には、SQL ではなくアプリケーションでフラット化を行うことを好みます。
ここでは SQL にアクセスできない 10 インチの画面で立ち往生しているため、テストされたコードを提供することはできませんが、基本的な方法は何らかの方法で再帰を利用することです。
- 再帰的スカラー関数はこれを行うことができます
- MS SQL では、再帰的な WITH ステートメントを使用してこれを行うことができます (より効率的)
スカラー関数 (のようなもの):
CREATE FUNCTION getGraphWalk(@child_id INT)
RETURNS VARCHAR(4000)
AS
BEGIN
DECLARE @graph VARCHAR(4000)
-- This step assumes each child only has one parent
SELECT
@graph = dbo.getGraphWalk(parent_id)
FROM
mapping_table
WHERE
category_id = @child_id
AND parent_id IS NOT NULL
IF (@graph IS NULL)
SET @graph = CAST(@child_id AS VARCHAR(16))
ELSE
SET @graph = @graph + ',' + CAST(@child_id AS VARCHAR(16))
RETURN @graph
END
SELECT
category_id AS [category_id],
dbo.getGraphWalk(category_id) AS [graph_path]
FROM
mapping_table
ORDER BY
category_id
しばらく再帰 WITH を使用していませんでしたが、何もテストするための SQL がない場合でも、構文を試してみます :)
再帰的 WITH
WITH
result (
category_id,
graph_path
)
AS
(
SELECT
category_id,
CAST(category_id AS VARCHAR(4000))
FROM
mapping_table
WHERE
parent_id IS NULL
UNION ALL
SELECT
mapping_table.category_id,
CAST(result.graph_path + ',' + CAST(mapping_table.category_id AS VARCHAR(16)) AS VARCHAR(4000))
FROM
result
INNER JOIN
mapping_table
ON result.category_id = mapping_table.parent_id
)
SELECT
*
FROM
result
ORDER BY
category_id
編集 - 両方の出力は同じです:
1 '1'
2 '1,2'
3 '1,2,3'
4 '1,2,4'
5 '1,2,5'
6 '1,6'
7 '1,6,7'
8 '1,6,7,8'
9 '1,6,9'
一部の DBMS の特殊機能を利用しない限り、任意の深さのツリーを走査するには、通常、再帰的な手続きコードが必要になります。
Oracle では、ここで行ったように、隣接リストを使用する場合、CONNECT BY 句を使用してツリーを深さ順にたどることができます。
ネストされたセットを使用する場合、左側のシーケンス番号により、ノードにアクセスする順序がわかります。
実際には、ストアプロシージャ内の動的 SQL を使用して実行できます。その場合、ストアド プロシージャ内で実行できることは制限されます。明らかに、予想される列の数がわからないまま、結果を一時テーブルに実行するのは困難になります。ただし、Web ページまたは他の UI に出力することが目的の場合は、努力する価値があるかもしれません...
