まとめ
-
グラフはリレーショナルモデルにない概念
- RDBでうまく扱うことは困難
- 絶対的に正しい方法はない
-
どのような戦略をとるべきか、都度考えて決定する
- 対象のグラフの特性
- クエリで求められる解が何であるか
- グラフDBの使用も視野に
グラフの構造
ノード、エッジ
@startuml
class a
class b
class c
class d
class e
a --- b
b --- c
b --- d
c --- c
c --- d
d --- e
d --- e
@enduml
-
グラフ
- ノードとエッジという2つの要素を使って、事象の関連性などを表現できる数学的なデータ構造
- ノードにはラベルがつけられることが多い
- ラベルがある場合、エッジはラベルのペアで表現
隣接
- ノードとノードの間にエッジが存在
- 「結ぶ」とも
次数
-
隣接するノード数
- 【補】エッジが多重の場合は本数分数える
歩道、小道、道
-
歩道(Walk)
- あるノードから別のノードへ映る、有限なエッジの列
-
例
- aからcへ至る歩道: ab,bd,db,bd,dc
-
小道(Trail)
-
歩道のうち、同じエッジを二度通らないもの
- 同じノードは通っていい
-
例
- aからbへ至る小道: ab,bd,dc,cb
-
-
道(Path)
- 小道のうち、同じノードを二度通らないもの
-
例
- aからcへ至る道: ab,bd,dc
- ディレクトリの「パス」はグラフ理論から来ている
多重辺
@startuml
class d
class e
d --- e
d --- e
@enduml
- ある1つのノードから別のノードに対し、複数のエッジが接続されている
- 多重辺を許容するかどうかでグラフの性質は大きく変わる
-
多重辺を許容する場合、エッジにもラベルをつける
- ノードのラベルのペアではエッジを特定できないため
ループ
@startuml
class c
c --- c
@enduml
- あるノードからノード自身へつながるノード
閉路
@startuml
class b
class c
class d
b --- c
b --- d
c --- d
@enduml
- あるノードから同じノードにへ至るパス
- ループも閉路の一種
連結
- すべての2ノード間のパスが存在すること
- わかりやすく言うと、1つにつながっていること
部分グラフ
- あるグラフから任意のエッジやノードを取り除いてできるグラフ
カットセット、ブリッジ
@startuml
class a
class b
class c
class d
class e
b --- c
b --- d
c --- c
c --- d
d --- e
d --- e
@enduml
-
非連結化集合
- 取り除くことで、その部分グラフが連結ではなくなるエッジの集合
- 例:
{bc,bd,cd}
,{ab}
-
カットセット
-
非連結化集合のうち、既約のもの
- どれを取り除いても連結を解除できない
- 例:
{bd,cd}
,{ab}
-
-
ブリッジ
- カットセットのうち、含まれるエッジが1つだけのもの
- 例:
{ab}
エッジの向きと重み
- 対象とする問題のテーマによってつけることがある
グラフの応用例
- ソーシャルネットワーク
- Webページのリンク
- 電子回路
- ネットワーク図
- 化学式
- 路線図
- 組織図
- 部品表(BOM: Bill of Materials)
- 掲示板
- ファイルシステム
グラフの種類
一般グラフ
-
一般グラフ
- エッジのつなぎ方に特別な制限がない
- 単に「グラフ」とも
単純グラフ
- 多重辺、ループがない
連結グラフ/非連結グラフ
- そのまんま
完全グラフ
@startuml
class a
class b
class c
class d
class e
a --- b
a --- c
a --- d
a --- e
b --- c
b --- d
b --- e
c --- d
c --- e
d --- e
@enduml
もうすこしキレイに描けなかったの
-
単純グラフのうち、すべてのノードがエッジで連結している
- エッジが
nC2
本
- エッジが
- 全ノード次数ぜんぶ同じ
正則グラフ
-
全ノード次数が同じ
- 完全グラフは正則グラフの一種
平面グラフ
-
どのエッジも交差しない
- プリント基板など
- 何層のプリント基板が必要になるか、などの問題の解決に応用される
有向グラフ/無向グラフ
-
有向グラフ
-
エッジの向きあり
- 道路とか
-
-
無向グラフ
- エッジの向きなし
重み付きグラフ
- エッジに重みをつける
- 最短経路探索などで使う
ツリー(木)
- 単純グラフのきわめて特殊なケース
- 後述
SQLとグラフの相性問題
-
データを格納するだけならば容易
- 「ノードaとノードbが隣接している」
- 問題はクエリ
グラフに対するクエリ
-
グラフに関する問いをSQLで表現することは不可能
- 「最短経路はどれか?」とか
無向グラフを表現できるか
node1 | node2 | weight |
---|---|---|
a | b | 3 |
a | e | 8 |
… |
-
1NFですらない
- 繰り返しパターンになっている(node1, node2)
-
そもそもエッジを1つのカラムとして表現したいところ
- ノードの非順序対
- が、SQLにそのようなデータ型はない
有向グラフを用いた表現
start_node | end_node | weight |
---|---|---|
a | b | 3 |
b | a | 3 |
a | e | 8 |
e | a | 8 |
… |
-
全二重の有向グラフとして表現
- 1NFにはなる
-
本来意図した無向グラフとは異なるモデルになってしまう。本末転倒
- アルゴリズムの変更が必要
リレーショナルな視点でモデルを理解する
- 1NFでない表現よりはマシ
「aとbがコスト3で隣接している」
- 導出される事実
「aからbへコスト3で到達できる」
「bからaへコスト3で到達できる」
行列を用いた表現
- 行と列には順序があるのでNG
-
列を追加するたびに
ALTER TABLE
文が必要なのもNG- アンチパターン「メタデータトリブル」
グラフに対するクエリ
- 例えば最短経路探索
-
何回JOINすれば解が得られるかわからない
- 最大
n-1
回(nはノード数) - 本質的に手続き型のループが必要
- 最大
手続き型による解法
-
専用のアルゴリズムを使う
- 最短経路探索ならダイクストラ法とか
- ストアドプロシージャとか必要
グラフDB
- 問題の中心がグラフであり、リレーショナルなDB設計が必要でない場合はグラフDBを使わない手はない
- リレーショナルなDB設計が必要なら併用
そのほかの問題
-
グラフ理論に基づいたデータの整合性を担保することが難しい
- エッジの追加後にループや閉路がない
- エッジを削除してもグラフが連結している
- 平面的である
ツリー(木)
ツリーはグラフの一種
@startuml
class a
class b
class c
class d
class e
class f
class g
class h
a --- b
a --- c
a --- d
b --- e
b --- f
c --- g
g --- h
@enduml
-
特徴
- 単純グラフの一種
- 閉路がなく連結している
- すべてのエッジはブリッジである
- 任意の2つのノードを結ぶパスは1つだけ
- 隣接していないどの2つのノードを結んでも閉路ができる
-
コンピュータ上でモデリングするときの一般的なやつはさらに
- 親子関係がある有向グラフ
- あるノードへ向かうエッジは1つのみ
- すべてのノードの出発点になるノードがある(根、root)
- 根からの距離が深さとして表される(階層構造)
- 条件がきついので上手に扱うためのテクニックが開発されている
コラム: ディレクトリのハードリンクが作成できない理由
- ファイルシステムはツリー構造
-
ディレクトリのハードリンクを許すとツリーでなくなる
- 閉路ができるから
-
ツリー構造前提のものが崩壊する
- プログラム
- アクセス権
隣接リストモデル
node_id | parent_id |
---|---|
a | NULL |
b | a |
c | a |
d | a |
e | b |
f | b |
g | c |
h | g |
- 正規化するならこう
nodes
node_id |
---|
a |
b |
c |
d |
e |
f |
g |
h |
edges
node_id | parent_id |
---|---|
b | a |
c | a |
d | a |
e | b |
f | b |
g | c |
h | g |
root_nodes
node_id |
---|
a |
- ただし、正規化しなくても実用上問題になることはあまりない
-
メリット
- シンプル
- 再帰的なSQLの表現をサポートしているRDB製品ならばクエリも簡単に書ける
-
デメリット
- 再帰がサポートされてないとむり
経路列挙モデル
node_id | path |
---|---|
a | /a |
b | /a/b |
c | /a/c |
d | /a/d |
e | /a/b/e |
f | /a/b/f |
g | /a/c/g |
h | /a/c/g/h |
-
メリット
- 任意のノード間の親子関係を一発で調べられる
-
デメリット
-
非正規化されているため…
- それ以外の問い合わせが困難
- 更新時不整合
-
入れ子集合モデル
- by Joe Celko
- 集合の包含関係のように親子関係を表現するやつ
node_id | lft | rgt |
---|---|---|
a | 1 | 16 |
b | 2 | 7 |
c | 8 | 13 |
d | 14 | 15 |
e | 3 | 4 |
f | 5 | 6 |
g | 9 | 12 |
h | 10 | 11 |
リレーショナルモデルと相性が悪い理由
-
そもそも1NFじゃない
-
lft,rgtが繰り返しパターン
- 両カラムは同一の数直線上の数値
- カラム間が直交でないため繰り返しパターン
-
- アプリケーション側で入れ子集合のロジックを正しく実装しなければデータの整合性を担保できない
- 更新処理が複雑
-
集合の使い方がリレーショナルモデルと異なる
- リレーショナルモデル: リレーションそのものが集合
- 入れ子集合: タプルが集合を表す(
{lft, rgt}
)
クロージャテーブル
- 先祖・子孫を列挙するやつ
ancestor | descendant |
---|---|
a | b |
a | c |
a | d |
a | e |
a | f |
a | g |
a | h |
b | e |
b | f |
c | g |
c | h |
g | h |
-
メリット
-
リレーショナルモデルに対して親和性が高い
- 正規化されている
- FK制約つけられる
-
-
デメリット
-
行数が多い
- 最悪
(n+1)C2
(nはrootの子孫数)
- 最悪
-
ツリーとSQLに関する考察
- 筆者おすすめはクロージャテーブル
-
いずれのモデルでも整合性の担保はアプリケーション側の責務
- DBはツリー構造を理解していない