sql - aws 新サービス 2019




フラットテーブルをツリーに解析する最も効率的でエレガントな方法は何ですか? (10)

順序付けられたツリー階層を格納するフラットなテーブルがあるとします。

Id   Name         ParentId   Order
 1   'Node 1'            0      10
 2   'Node 1.1'          1      10
 3   'Node 2'            0      20
 4   'Node 1.1.1'        2      10
 5   'Node 2.1'          3      10
 6   'Node 1.2'          1      20

ここに[id] Nameがある図があります。 ルートノード0は架空のものです。

                       [0] ROOT
                          /    \ 
              [1] Node 1          [3] Node 2
              /       \                   \
    [2] Node 1.1     [6] Node 1.2      [5] Node 2.1
          /          
 [4] Node 1.1.1

それをHTML(またはテキスト)として正しく整列され、正しくインデントされたツリーとして出力するには、どのような最小限のアプローチを使用しますか?

さらに、基本的なデータ構造(配列とハッシュマップ)、親/子参照の空想オブジェクト、ORM、フレームワークなし、ちょうど両手しか持たないと仮定します。 表は結果セットとして表され、ランダムにアクセスできます。

擬似コードまたは普通の英語は大丈夫です。これは純粋に概念的な質問です。

ボーナス問題:このようなツリー構造をRDBMSに格納する根本的に良い方法はありますか?

編集と追加

あるコメント作成者( Mark Besseyさん)の質問に答えるには:ルートノードは必ずしも表示されないため、必要ありません。 ParentId = 0は「これはトップレベルです」と表現するための規約です。 Order列は、同じ親を持つノードのソート方法を定義します。

私が話した「結果セット」は、ハッシュマップの配列として描くことができます(その用語にとどまる)。 私の例は既にそこにあることを意図していたからです。 いくつかの答えは余分に移動し、最初にそれを構築しますが、それは大丈夫です。

ツリーは、任意に深いことができます。 各ノードはN個の子を持つことができます。 しかし、私は正確に「何百万ものエントリー」ツリーを念頭に置いていませんでした。

私の選択したノード命名(「ノード1.1.1」)に頼るべきことを間違えてはいけません。 ノードは「Frank」または「Bob」とも呼ばれ、命名構造は暗示されません。これは単に読みやすくするためのものでした。

私は自分のソリューションを掲載しているので、皆さんはそれを引き出すことができます。


MySQL 8.0がリリースに近づいたので、一般的なすべてのSQLデータベースは 、標準構文で再帰クエリをサポートします。

WITH RECURSIVE MyTree AS (
    SELECT * FROM MyTable WHERE ParentId IS NULL
    UNION ALL
    SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;

2017年の私のプレゼンテーションであるRecursive Query Throwdownで、MySQL 8.0で再帰クエリをテストしました。

以下は2008年の私の元々の答えです:

ツリー構造のデータをリレーショナルデータベースに格納する方法はいくつかあります。 あなたの例では、次の2つの方法を使用しています。

  • 隣接リスト (「親」列)および
  • パス列挙 (あなたの名前列の点線番号)。

別のソリューションはネストセットと呼ば 、同じテーブルにも格納できます。 Joe Celkoによる「 SmartiesのためのSQLにおけるツリーと階層 」を参照して、これらの設計に関するさらに多くの情報を入手してください。

私は通常、木構造のデータを格納するClosure Table (別名「隣接関係」)というデザインを好んでいます。 別のテーブルが必要ですが、ツリーを照会するのはかなり簡単です。

私のプレゼンテーション「 SQLとPHP使った階層的データのモデル」と私の本「 SQL Antipatterns:データベースプログラミングの落とし穴の回避 」のClosure Tableを取り上げます

CREATE TABLE ClosureTable (
  ancestor_id   INT NOT NULL REFERENCES FlatTable(id),
  descendant_id INT NOT NULL REFERENCES FlatTable(id),
  PRIMARY KEY (ancestor_id, descendant_id)
);

あるノードから別のノードへの直接の祖先があるClosure Tableにすべてのパスを格納します。 各ノードがそれ自体を参照する行を含めます。 たとえば、質問に表示されたデータセットを使用します。

INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
  (1,1), (1,2), (1,4), (1,6),
  (2,2), (2,4),
  (3,3), (3,5),
  (4,4),
  (5,5),
  (6,6);

今度はノード1から始まるツリーを次のように取得できます:

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;

MySQLクライアントの出力は次のようになります。

+----+
| id |
+----+
|  1 | 
|  2 | 
|  4 | 
|  6 | 
+----+

言い換えると、ノード3とノード5は、ノード1から降りていない別の階層の一部であるため、除外されます。

Re:即時の子供(または親の直属の子)についてのe-satisからのコメント。 path_lengthpath_length 」列を追加して、直接的な子または親(またはその他の距離)を簡単に照会できるようにすることができます。

INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
  (1,1,0), (1,2,1), (1,4,2), (1,6,1),
  (2,2,0), (2,4,1),
  (3,3,0), (3,5,1),
  (4,4,0),
  (5,5,0),
  (6,6,0);

次に、特定のノードの直下の子を照会するための検索語を追加することができます。 これらは、 path_lengthが1の子孫です。

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
  AND path_length = 1;

+----+
| id |
+----+
|  2 | 
|  6 | 
+----+

@ashrafのコメント:「ツリー全体を名前で並べ替えるのはどうですか?」

ここでは、ノード1の子孫であるすべてのノードを返し、 nameなどの他のノード属性を含むFlatTableに結合し、 nameでソートするクエリの例を示します。

SELECT f.name
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;

@Nateからのコメント:

SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id) 
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id) 
WHERE a.ancestor_id = 1 
GROUP BY a.descendant_id 
ORDER BY f.name

+------------+-------------+
| name       | breadcrumbs |
+------------+-------------+
| Node 1     | 1           |
| Node 1.1   | 1,2         |
| Node 1.1.1 | 1,2,4       |
| Node 1.2   | 1,6         |
+------------+-------------+

ユーザーが今日編集を提案しました。 SOモデレーターが編集を承認しましたが、私はそれを逆にしています。

この編集では、上記の最後のクエリのORDER BYはORDER BY b.path_length, f.nameでなければなりませんORDER BY b.path_length, f.nameはおそらく、順序が階層に一致することを確認するためです。 しかし、これは機能しません。なぜなら、「ノード1.2」の後に「ノード1.1.1」を注文するからです。

順序を合理的な方法で階層に一致させたい場合は、可能ですが、単にパスの長さで並べ替えるだけではありません。 たとえば、 MySQL Closureテーブル階層データベースの私の答えを見てください。 正しい順序で情報を引き出す方法


Oracle 9iでは、CONNECT BYを使用できます。

SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)

SQL Server 2005では、再帰的な共通テーブル式(CTE)を使用できます。

WITH [NodeList] (
  [Id]
  , [ParentId]
  , [Level]
  , [Order]
) AS (
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , 0 AS [Level]
    , CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
  WHERE [Node].[ParentId] = 0
  UNION ALL
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , [NodeList].[Level] + 1 AS [Level]
    , [NodeList].[Order] + '|'
      + CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
    INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
  INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]

どちらも次の結果を出力します。

Name
'Node 1'
'    Node 1.1'
'        Node 1.1.1'
'    Node 1.2'
'Node 2'
'    Node 2.1'

あなたの例に示されているように、要素がツリー順であれば、次のPythonの例のようなものを使うことができます:

delimiter = '.'
stack = []
for item in items:
  while stack and not item.startswith(stack[-1]+delimiter):
    print "</div>"
    stack.pop()
  print "<div>"
  print item
  stack.append(item)

これは、ツリー内の現在の位置を表すスタックを維持することです。 テーブルの各要素について、現在の項目の親を見つけるまでスタック要素をポップします(一致するdivを閉じる)。 次に、そのノードの開始点を出力し、それをスタックにプッシュします。

ネストされた要素ではなくインデントを使用してツリーを出力したい場合は、単にprintステートメントをスキップしてdivを出力し、各項目の前にスタックのいくつかの倍数のスペースを出力することができます。 例えば、Pythonでは:

print "  " * len(stack)

このメソッドを使用して、ネストされたリストまたはディクショナリのセットを簡単に作成することもできます。

編集:あなたの説明から、名前がノードパスではないことがわかりました。 これは代替アプローチを示唆しています。

idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))

これは、タプル(!)の配列のツリーを構築します。 idx [0]はツリーのルートを表します。 配列の各要素は、ノード自体とそのすべての子のリストからなる2つのタプルです。 構築したら、IDでノードにアクセスしない限り、idx [0]を保持してidxを破棄することができます。


これはかなり古い質問ですが、多くの意見があるので、代替案を提示する価値があると思います。私の意見では非常にエレガントで解決策です。

ツリー構造を読み込むには、 再帰的な共通テーブル式 (CTE)を使用できます。 これは、一度にツリー構造全体をフェッチし、ノードのレベル、親ノードおよび親ノードの子内の順序についての情報を有する可能性を与える。

これがPostgreSQL 9.1でどのように機能するかを説明しましょう。

  1. 構造を作成する

    CREATE TABLE tree (
        id int  NOT NULL,
        name varchar(32)  NOT NULL,
        parent_id int  NULL,
        node_order int  NOT NULL,
        CONSTRAINT tree_pk PRIMARY KEY (id),
        CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) 
          REFERENCES tree (id) NOT DEFERRABLE
    );
    
    
    insert into tree values
      (0, 'ROOT', NULL, 0),
      (1, 'Node 1', 0, 10),
      (2, 'Node 1.1', 1, 10),
      (3, 'Node 2', 0, 20),
      (4, 'Node 1.1.1', 2, 10),
      (5, 'Node 2.1', 3, 10),
      (6, 'Node 1.2', 1, 20);
    
  2. クエリを書く

    WITH RECURSIVE 
    tree_search (id, name, level, parent_id, node_order) AS (
      SELECT 
        id, 
        name,
        0,
        parent_id, 
        1 
      FROM tree
      WHERE parent_id is NULL
    
      UNION ALL 
      SELECT 
        t.id, 
        t.name,
        ts.level + 1, 
        ts.id, 
        t.node_order 
      FROM tree t, tree_search ts 
      WHERE t.parent_id = ts.id 
    ) 
    SELECT * FROM tree_search 
    WHERE level > 0 
    ORDER BY level, parent_id, node_order;
    

    結果は次のとおりです。

     id |    name    | level | parent_id | node_order 
    ----+------------+-------+-----------+------------
      1 | Node 1     |     1 |         0 |         10
      3 | Node 2     |     1 |         0 |         20
      2 | Node 1.1   |     2 |         1 |         10
      6 | Node 1.2   |     2 |         1 |         20
      5 | Node 2.1   |     2 |         3 |         10
      4 | Node 1.1.1 |     3 |         2 |         10
    (6 rows)
    

    ツリーノードは、深さレベルで順序付けられます。 最終出力では、それを後続の行に表示します。

    各レベルについて、親内のparent_idとnode_orderによって順序付けられます。 これは、アウトプットリンクノードに親ノードをこの順序で提示する方法を示しています。

    このような構造を持つことで、HTMLで本当に素敵なプレゼンテーションを作るのは難しくありません。

    再帰CTEは、 PostgreSQL、IBM DB2、MS SQL ServerおよびOracleで利用できます

    再帰的なSQLクエリについてさらに詳しく知りたい場合は、お気に入りのDBMSのドキュメントをチェックするか、このトピックに関する2つの記事を読んでください:


まあ、選択肢があれば、私はオブジェクトを使用しています。 私はそれぞれのオブジェクトがchildrenコレクションを持っている各レコードのオブジェクトを作成し、そのオブジェクトがキーであるassoc配列(/ハッシュテーブル)にすべて格納します。 コレクションを一度爆撃し、関連する子フィールドに子供を追加します。 シンプル。

しかし、いくつかの良いOOPの使用を制限することによってあなたが楽しくないので、おそらく私は繰り返しに基づいています:

function PrintLine(int pID, int level)
    foreach record where ParentID == pID
        print level*tabs + record-data
        PrintLine(record.ID, level + 1)

PrintLine(0, 0)

編集:これは他のいくつかのエントリに似ていますが、私はそれが少しきれいだと思います。 追加することの1つは、これは非常にSQLを大量に使用することです。 それは厄介です。 選択肢があれば、OOPルートに進んでください。


ネストされたセットを使用する場合(変更済みプリオーダーツリートラバーサルとも呼ばれます)、ツリー構造全体またはツリー内のサブツリーを単一のクエリでツリー順に抽出することができます。ツリー構造を介して順序通りの経路を記述する列を管理する。

django-mpttでは、私は次のような構造を使いました:

id  parent_id  tree_id  level  lft  rght
--  ---------  -------  -----  ---  ----
 1       null        1      0    1    14
 2          1        1      1    2     7
 3          2        1      2    3     4
 4          2        1      2    5     6
 5          1        1      1    8    13
 6          5        1      2    9    10
 7          5        1      2    11   12

これは次のようなツリーを表します( idは各アイテムを表します)。

 1
 +-- 2
 |   +-- 3
 |   +-- 4
 |
 +-- 5
     +-- 6
     +-- 7

あるいは、入れ子にされた集合図として、 rght値とrght値がどのように働くかをより明白にする:

 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

見て分かるように、指定されたノードのサブツリー全体をツリー順にrghtするには、 lft値とrght値の間にlftrght値を持つすべての行を選択するだけです。 また、特定のノードの先祖のツリーを取得することも簡単です。

level列は、何よりも便宜上の非正規化ビットですtree_id列では、各最上位ノードのlftrght番号付けを再開できます。これにより、挿入、移動、削除の影響を受ける列の数がlftこれらの操作がギャップを作成または閉じるために行われるときには、それに応じて列を調整する必要があります。 私は、各操作に必要なクエリの周りを頭で囲んでいたときに、いくつかの開発ノートを作成しました。

実際にこのデータを使ってツリーを表示するという観点からは、各ノードごとに必要な表示を生成するのに十分な情報を与えるtree_item_iteratorユーティリティ関数を作成しました。

MPTTの詳細:


ハッシュマップを使用して他のデータ構造をエミュレートすることはできますが、それはひどい制限ではありません。 上から下に向かってスキャンすると、データベースの各行に対して、各列のエントリを持つハッシュマップが作成されます。 これらのハッシュマップのそれぞれをidでキー入力された「マスター」ハッシュマップに追加します。 いずれかのノードに、まだ見ていない「親」がある場合は、そのノードのプレースホルダエントリをマスターハッシュマップに作成し、実際のノードが表示されたら入力します。

それを印刷するには、単純な深度優先のデータをパスし、途中でインデントレベルを追跡します。 これを簡単にするには、各行の「子」エントリを保持し、データをスキャンするときに入力します。

データベースにツリーを格納する「より良い」方法があるかどうかは、データをどのように使用するかによって異なります。 階層の各レベルごとに異なるテーブルを使用した既知の最大深度を持つシステムを見てきました。 ツリーのレベルが全く同じではない場合(トップレベルのカテゴリはリーフとは異なる)、それは多くの意味があります。


ビルのSQLソリューションを拡張するには、基本的にフラットな配列を使用して同じことができます。 さらに、文字列の長さがすべて同じで、子の最大数がわかっている場合(バイナリツリーで)、文字列(文字配列)を使用して文字列を作成できます。 あなたが子供の任意の数を持っている場合、これは少し複雑です...私は何ができるか見るために私の古いノートをチェックする必要があります。

そして、少しのメモリを犠牲にして、特にあなたのツリーが疎であるならば、インデックスの数学的な計算では、ツリーを格納することによってランダムにすべての文字列にアクセスできます。木):

String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...

あなたの文字列の長さを知っているよ、あなたはそれを知っている

私は今仕事中ですので、それに多くの時間を費やすことはできませんが、関心を持って、これを行うためのコードを少し取り出すことができます。

我々は、DNAコドンで作られたバイナリーツリーを検索するために、ツリーを構築した後、テキストパターンを検索するためにそれを平坦化し、インデックスの数学(上から逆転)高速で効率的な、厳しいツリーでは空ノードはめったにありませんでしたが、ジッピーでデータを検索できました。


ルート要素がゼロであることを知っていると仮定すると、テキストに出力する擬似コードは次のようになります。

function PrintLevel (int curr, int level)
    //print the indents
    for (i=1; i<=level; i++)
        print a tab
    print curr \n;
    for each child in the table with a parent of curr
        PrintLevel (child, level+1)


for each elementID where the parentid is zero
    PrintLevel(elementID, 0)

階層構造のためにneo4jのようなnosqlツールを使用することを考えてください。 例えば、linkedinのようなネットワークアプリケーションはcouchbase(別のnosqlソリューション)

ただし、データマート・レベルの問合せに対してのみnosqlを使用し、トランザクションを格納/保持しない





hierarchical-data