SQLで木構造を扱う(閉包テーブル)Zennsuimenka🌲SQLで木構造を扱う(閉包テーブル)2023/12/25に公開2024/04/07SQLtreetechはじめにSQLを使用して、ディレクトリのような木構造で以下の機能を実装したい。Table)というデータ構造で実装していく。閉包テーブルとは閉包テーブルとは、木構造内の各ノードにおいて、先祖-子孫間の関係(自身も含む)を格納するテーブルのことである。この記事では以下のような木構造を扱う。11-11-1-11-21-323先祖-子孫間の閉包テーブルは以下のようになる。0ancestorは先祖、descendantは子孫、weightは重みである。今回は兄弟間の順序も保持したい。長男をルート、末っ子をリーフとして考えると、兄弟間の閉包テーブルは以下のようになる。今回はPostgreSQLで実装する。テーブル定義は以下のようになる。descendant));上からノードのテーブル、先祖-子孫間の関係のテーブル、兄弟間の関係のテーブルになる。先の木構造で考えると、期待する結果は以下のようになる。name123ルートは、子孫を持たないノードである。閉包テーブルでは自身と自身との関係も含むので、子孫を1つしか持たないノードということになる。よって、ルートの一覧のidを取得するSQLは以下のようになる。1これを長男から順に並べ替えるには、node_sibling_relationshipsテーブルで、descendantごとにグループ化し、descendantの数が少ない順に並べ替えればよい。descendantの数を取得するSQLは以下のようになる。descendantこれらを組み合わせると、ルートの一覧を取得するSQLは以下のようになる。1のノードの子の一覧の場合、期待する結果は以下のようになる。name1-11-21-3子は、ancestorが親のidで、weightが1の、descendantのノードである。よって、子の一覧のidを取得するSQLは以下のようになる。1※$1は任意のノードのidこれを使うと、子の一覧を取得するSQLは以下のようになる。1-1-1のノードの先祖の一覧の場合、期待する結果は以下のようになる。今回はそのノード自身も含めることにする。name11-1先祖の一覧を取得するSQLは以下のようになる。1のノードの子孫の一覧の場合、期待する結果は以下のようになる。今回はそのノード自身も含めることにする。name11-11-21-31-1-1子の一覧の取得を応用すると、子孫の一覧を取得するSQLは以下のようになる。]}任意のノードからリーフまでの親子関係が必要になる。具体的には以下のようなデータである(実際には、idにはそれぞれuuidが入る)。1これを取得するには、以下の2つの方法がある。1)※$1は任意のノードのid1つ目の方法は、任意のノードの子孫の一覧を取得し、その子孫のそれぞれの子の一覧を取得している。RECURSIVEを使用して再帰的にまたその子の一覧を取得している。よって、任意のノードからリーフまでの親子関係を取得するSQLは以下のようになる。sibling_descendant_counts.count※$1は任意のノードのidこれらのSQLで取得したデータからツリーを組み立てるTypeScriptのコードは以下のようになる。以下のような木構造を作る場合、11-11-1-11-21-323nodesテーブル、node_relationshipsテーブル、node_sibling_relationshipsテーブルのデータはそれぞれ以下のようになる。0nodesまず、nodesテーブルにデータを挿入する。name※$1はnamenode_relationships次に、node_relationshipsテーブルにデータを挿入する。挿入するデータは、「追加するノード」自身との関係と、「追加先のノード」の先祖と「追加するノード」との関係である。1-1-1のノードを1-1のノードに追加する場合を考える。追加先の1-1のノードの先祖は、1のノード、1-1のノードである。重みに関しては、追加先の1-1のノードの子になるので、追加先のノードの先祖と追加先のノードとの関係のweightをインクリメントした値になる。