階層の深さが可変なツリー構造データを格納するDB設計

Question

通信会社に勤めていてルーターやスイッチに収容されているユーザー回線数を集計する簡単なWebアプリを作っています。最終的にこんな感じの表を出力させたいです。

rt_host	rt_port	sw1_host	sw1_port	sw2_host	sw2_port	users
RT01	Gi0/0/0	-	-	-	-	10
RT01	Gi0/1/0	SW01	Gi1/1	-	-	8
RT01	Gi0/1/0	SW01	Gi1/2	-	-	14
RT01	Gi0/1/1	SW02	Gi1/1	-	-	7
RT02	Gi0/0/0	SW03	Gi1/1	-	-	53
RT02	Gi0/0/0	SW03	Gi8/1	SubSW01	Gi0/1	11

- になっているところがありますが、実は

• RT --- Aプランユーザー
• RT --- SW --- Bプランユーザー
• RT --- SW --- SubSW --- Cプランユーザー

といった具合に契約プラン等によってネットワークの階層数が異なっており、頭を抱えています。

上表をそのままDBにするとNULLだらけになってしまう上に主キーも張れず悪手に思えます。- などのNULL代替ワードを使うことも検討しましたが、xxx_host カラムにホスト情報テーブルに対する外部キー制約をかけたいので避けたいところです。

このように深さが可変のツリー構造(複合主キーにするカラム数が可変)な場合どうテーブルを設計すべきでしょうか？具体的なスキーマではなく、考え方やデザインパターンの名称でも構いません。

条件

• ネットワーク機器の階層は2〜4（例が雑多になるので本質問では最大3で取り扱っています）
• 'SW03' の例のように、SW03 に直接ぶらさがっているユーザーが居るし、その下に 'SubSW01' があってそのさらに下にぶらさがっているユーザーも居る場合があります。と末端にだけデータノードが付いたシンプルなツリー構造ではありません
• アプリの目的: ネットワーク機器のつながり情報の閲覧と、「SW01は全部で22ユーザー」のように任意カラムでのユーザー数集計
• 環境: MySQL + Python (Flask + SQLalchemy)

---

以下は自分に考えてみた案です。長いので無視して構いません。

代案1：通信機器のつながり情報とユーザー収容情報を分け再帰検索

neighbors テーブル:

self_host(PK)	self_port(PK)	dest_host	dest_port
RT01	Gi0/1/0	SW01	Gi1/1
RT01	Gi0/1/1	SW02	Gi1/1
RT02	Gi0/0/0	SW03	Gi8/1
SW03	Gi8/1	SubSW01	Gi0/1

users テーブル(ユーザーに隣接するホストにユーザー数情報を紐付け)

last_host(PK)	last_port(PK)	users
RT01	Gi0/0/0	10
SW01	Gi1/1	8
SW01	Gi1/2	14
SW02	Gi1/1	7
SW03	Gi1/1	11
SubSW01	Gi0/1	23

たとえば "SW03" で検索した場合、

1. users テーブルを　'SW03' で検索：ヒット有り('SW03', 'Gi1/1', 11) → 一部結果取得
2. neighbors テーブルの self_host を 'SW03' で検索：ヒット有り(SW03', 'Gi8/1', 'SubSW01, 'Gi0/1')
3. users テーブルを 'SubSW01', 'Gi0/1' で検索：ヒット有り('SubSW01', 'Gi0/1', 23) → 一部結果取得
4. neighbors テーブルの self_host を 'SubSW01', 'Gi0/1' で検索：ヒット無し → 下方向探索終了
5. neighbors テーブルの dest_host を 'SW03' で検索：ヒット有り('RT02', 'Gi0/0/0', 'SW03', 'Gi8/1')
6. neighbors テーブルの dest_host を 'RT02', 'Gi0/0/0' で検索：ヒット無し → 上方向探索終了、情報確定
7. 上記で取り出した情報からHTMLの表を作成し表示

と処理が非常に煩雑になってしまいます。問い合わせ回数が多く、アプリ側で親・子・孫のどのレイヤーの情報なのか分からない上に、集計処理(GROUP BY + SUM)を自前で行う必要があり、「リレーショナルデータベースを使う意味があるのか？？ もうNULLだらけでもいいんじゃないか！？」と思い始めています。

代案2. 階層ごとにテーブルを分けて外部結合

最大階層数が3なのでつながり情報のテーブルを2つ用意し外部結合して検索

neighbors1 テーブル:

self_host(PK)	self_port(PK)	dest_host	dest_port
RT01	Gi0/0/0	NULL	NULL
RT01	Gi0/1/0	SW01	Gi1/1
RT01	Gi0/1/1	SW02	Gi1/1
RT02	Gi0/0/0	SW03	Gi8/1

neighbors2 テーブル:

self_host(PK)	self_port(PK)	dest_host	dest_port
SW01	Gi1/1	NULL	NULL
SW01	Gi1/2	NULL	NULL
SW02	Gi1/1	NULL	NULL
SW03	Gi1/1	NULL	NULL
SW03	Gi8/1	SubSW01	Gi0/1

users テーブル

(略)

実装は案1よりシンプルになりそうですが、それでも neighbors1 の self、neighbors2 の self、neighbors2 の dest とそれぞれJOINした３つの users テーブルの内容をアプリ側で合算する必要があり、なんだかなーという感じです。。。

以上、雑文で申し訳ありませんがアドバイスよろしくお願いします。

Answer 1

末端だけ属性を持たせたいということであっても、正規化を重視するならナイーブツリーで問題なさそうですけどね。
ただ、Mysqlは最新でないと再帰が使えないみたいですけど。

SQL: ナイーブツリーと再帰クエリ

正規化を緩める場合（ツリーでない場合）は、データは末端に合わせて、経路情報は配列型で持たせる方法。

DBMSが自由に選択できるんだったらpostgresをお勧めします。
再帰は使えるし再帰中で経路情報を配列で生成もできます。
また配列操作用の関数や演算子も充実しています。（例えば配列の要素数を取得する関数だったり）

追記

ツリーとユーザー情報を分けて、ユーザー情報はツリーとリンクさせるのが、正規化の観点からは理想ですね。

Comments

[miyahan]

おっしゃる通りつながり情報とユーザー情報をわけつつ、つながり情報はナイーブツリーで表現するのがRDBらしくて良さそうですね。また、再帰検索が難しそうという懸念がありましたが、これも確かにポスグレを使えばアンチパターンを回避できますね。

DBMSの変更を含め検討してみます。ありがとうございました。

Answer 2

木構造を表すときに代表的な「経路列挙モデル」は検討されたでしょうか？
↓はSQL関係の書籍で有名なミック氏のページです。
SQLで木と階層構造のデータを扱う（２）―― 経路列挙モデル

Comments

[miyahan]

経路列挙・入れ子集合・閉包テーブルは軽く調べました。ですがどれも一長一短がありどれを選んで良いかわからず、さらに今回の場合は最大階層数が固定という条件があるので他のうまい方法をやっている方が居たら教えて欲しいなと思い投稿させていただいました。

文字通り『経路」情報を記録するデータベースなので、経路列挙モデルと親和性が高そうですね。検討してみます。アドバイスありがとうございました。

[hihijiji]

別件ですが、複合主キーはよほどのことが無い限りお勧めできません。
BプランのユーザーがAプランに変更したいとか、スイッチの収容台数を減らしたい時を考えてみてください。
とても面倒ですよね？
ユニークである制約が欲しいときは別途ユニークなキーを付ければいいだけです。

Answer 3

入れ子集合モデルというのがあります。
http://www.geocities.jp/mickindex/database/db_tree_ns.html

自分の知る例では、RedmineのProjectやIssueの無制限の親子関係を表現するのに使用されています。
ネットワーク機器の繋がりを入れ子集合モデルで表現して、各ノードにユーザーを関連付けるのが良いと思います。

Comments

[miyahan]

シンプルかつ効果的なモデルですが、今回のように親のこのポートに子のこのポートが繋がっているという経路情報を付与するのが難しそうですね。ホストノードの下にポートノードを1段足せば表現できそうですが、ノード名が RT01.slot1.port0 みたいに複数の情報を持たせるのはRDBらしくない気がしますし、かといってカラムを分けてホストノードの場合はslotとportは NULL ってのもそれでいいのかなという感じです。

紹介いただいたURLのサイトを熟読してもう少し考えてみます。ありがとうございます。