まとめ

グラフはリレーショナルモデルにない概念
- 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})