sql - すべてのパスのリストへの隣接リスト階層のフラット化

Question

隣接リストモデルを使用して階層情報を格納するテーブルがあります。（自己参照キーを使用します-以下の例。この表は見覚えがあるかもしれません）：

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層階層で機能します。

score 11 · Accepted Answer

単純な隣接リスト全体でマルチレベルのクエリを実行するには、常に自己左結合が必要です。右揃えのテーブルを作成するのは簡単です:

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層階層で機能します。

申し訳ありませんが、隣接リストモデルでは任意の深さのクエリは実行できません。この種のクエリを頻繁に実行している場合は、スキーマを階層情報を格納する他のモデルのいずれかに変更する必要があります: 完全な隣接関係 (すべての祖先と子孫の関係を格納)、マテリアライズドパス、またはネストされたセット。

カテゴリがあまり移動しない場合 (これは通常、あなたの例のようなストアの場合です)、ネストされたセットに向かう傾向があります。

score 9 · Accepted Answer

前述のように、SQL には、動的に変化する列数を持つテーブルを実装する明確な方法はありません。私が以前に使用した唯一の 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'

score 1 · Accepted Answer

一部の DBMS の特別な機能を使用しない限り、任意の深さのツリーをトラバースするには、通常、再帰的な手続き型コードが必要です。

Oracle では、ここで行ったように、隣接リストを使用する場合、CONNECT BY 句を使用すると、ツリーを最初の順序で深くトラバースできます。

ネストされたセットを使用する場合、左側のシーケンス番号はノードを訪問する順序を提供します。

score 0 · Accepted Answer

実際には、ストアプロシージャ内で動的 SQL を使用して実行できます。その後、ストアドプロシージャを使用して実行できることは限られます。予想される列の数がわからないまま、結果を一時テーブルに実行するのは明らかに困難です。ただし、目標が Web ページまたは他の UI に出力することである場合は、努力する価値があるかもしれません...

sql - すべてのパスのリストへの隣接リスト階層のフラット化

4 に答える 4

Related

Reference