理論から学ぶデータベース実践入門 ch12 Webアプリケーションのためのデータ構造 (1/2)

gihyo.jp

---

まとめ

• 性能を得るためにリレーショナルモデルから逸脱せざるをえない場合の対処法
• キャッシュは実装に関わるデータ構造
  • 物理的な限界を打ち破るためのもの
    • 他には「金を積む」という方法もある
  • 論理データとは別に構造化されたデータを付け足す
    • 節度をもってデータモデルを維持しつつ、物理的な限界に立ち向かう
  • インデックスと通じる部分がある
    • RDBで利用可能なインデックスよりも複雑なデータ構造が必要なら役に立つ

キャッシュという考え方

• コンピュータシステムにはさまざまなキャッシュがある
  • CPUのキャッシュメモリ
  • TLB: Translation Lookaside Buffer
  • ディスク装置のキャッシュ
  • ブラウザのコンテンツキャッシュ
  • ファイルシステムキャッシュ
  • DNSキャッシュ
  • DBのバッファプール

メリット/デメリット

• メリット
  • コストの高い処理の回避
• デメリット
  • 複雑性の増大
    • システムの開発・保守コスト増大

DBアプリケーションにおけるキャッシュ

• 複雑さの増大と引き換えに、コストの高い処理をコストの低い処理でできるだけ代替
• データに局所性があると効果大
  • 時間
  • 空間
• データの構造を工夫することで処理の効率向上

キャッシュはあくまでもキャッシュ

• 消えてもかまわない
• 原本となる論理データとは明確に区別せよ

キャッシュとして使うための要件

• 下記が明確であること
  • キャッシュへの問い合わせがキャッシュミスしたときの対処法
  • キャッシュミスしたときにDBへ問い合わせる方法
  • キャッシュミスしたときに新たにキャッシュへエントリを追加する方法
  • データが更新されたときにキャッシュと同期する方法
  • データがすべて消失したときに1回再構築する方法
  • キャッシュの整合性を確認する方法
• 同期方法
  • トリガーで即時
  • バッチで定期
• タイムラグをどれだけ許容できるか等勘案して決める

キャッシュすべきデータの種別

キャッシュすべきでない

• トランザクション中に参照するデータ
  • 参照と更新が完全に同期していなければならない

キャッシュ可能

• きわめて頻繁にアクセスする
• アクセスに偏りがある
• 長期にわたり変更される予定がない
• 表示することが目的

キャッシュの実装方法

NoSQLをキャッシュとして使う

• 下記のような性能特性のものを使う
  • オーバヘッドが少なくアクセスが極めて速い
    • e.g. KVS
  • RDBが苦手とする種類の検索が可能
    • e.g. グラフDB、ドキュメント型DB、全文検索エンジン
  • 多数のサーバマシンを用いて分散処理ができる
• MySQL + memcachedとか
• 【補】AWS RDS + ElastiCacheとか

論理データはRDBで管理する

• 異常の発生を抑えられる
• 複数のDB製品を使用するため、複雑さは増大する

コラム: NoSQLでRDBは置き換えらるか？

• No
• よく言われる「スキーマレスであること」は良し悪し
  • 扱いやすい
  • データの重複や矛盾の問題からは逃れられない
    • むしろ守るすべがない
• 相補的
  • RDBの不得意がNoSQLには得意
  • RDBの得意がNoSQLには不得意

テーブルをキャッシュとして使う

• 何らかの加工を施してから別のテーブルに格納
  • 非正規化とか
• 論理データと混同しないこと
• メリデメ
  • 単一のDB製品だけで完結
  • 1つのDBサーバで管理すべきデータサイズが増えてしまう
  • 更新時オーバヘッド
• 使いどころ
  • 更新よりも参照のほうが圧倒的に多い

集計テーブル

• 「テーブルをキャッシュとして使う」例で代表的なもの
• 非常に高コストな集約関数をキャッシュ
• ランキングとか
  • 高コスト
  • わりに頻出要件
• 論理データの更新にどう追従する
  • マテリアライズドビュー機能に委ねる
    • クエリ実行結果をキャッシュするビュー
    • DB製品がサポートしていればぜひ
  • トリガーで即時更新
  • バッチで定期更新

結合済みのデータ

• データ件数が多い場合、1度のJOINも許容できないことがある
• 結合済データのテーブルを作っておく
  • 論理データよりも大きくなるが「キャッシュ」であることに変わりはない
• 論理データの更新にどう追従する
  • 更新・削除
    • FKのカスケード
  • 挿入
    • INSERTのトリガー
• メリット
  • ディスクI/O削減
  • ソートとの相性が良い
  • NewSQLとの相性が良い

ディスクI/O削減

• 結合解決時、それぞれのテーブルへのアクセスが生じる
  • バッファプールに一切キャッシュされていなければ、都度ディスクI/O生じる
• 結合済ならばデータは1箇所
  • キャッシュミス時のI/O減る
    • ただしバッファプールのキャッシュヒット率自体が低下してしまう可能性がある
      • 大きなキャッシュデータを用いるため

ソートとの相性が良い

• 2つのテーブルを結合してからソートする場合、実行計画によってはファイルソートになってしまうことがある
• 結合済データに対してインデックスを作成しておけば、インデックスでソート解決できる

NewSQLとの相性が良い

• NewSQL
  • RDBに対してKVSのためのインタフェースを提供するハイブリッド型製品
• KVSでは等価比較によるデータ取得のみが可能
• 結合済テーブルならNewSQLという選択肢が増える

理論から学ぶデータベース実践入門 ch11 インデックスの設計戦略 (2/2)

gihyo.jp

---

リレーショナルモデルとインデックス

• インデックスは物理的な設計(実装)の一部
• 本来は論理が先立つ
  1. 欲しいデータは何かが決まる
  2. データを取得するクエリが決まる
  3. クエリの高速化のためにインデックスを設計する
• 現場では往々にして逆転
  1. インデックスを決め打ちする
  2. いかにインデックスを活用してデータを取得するか考える

インデックスはリレーショナルモデルの一部ではない

• とはいえ重要でないわけではない
• リレーショナルモデルとインデックスとの間はミッシングリンク
• いかに繋ぐかが開発者・DB設計者の腕の見せ所
• 基本は論理が先
• 主キー定義してプライマリインデックスを定義するのはアリ
  • DB設計時に候補キーは判明する
• 直感で「このカラムで検索されることが多くなる」という場合もアリ
• が、決め打ちインデックスにクエリが縛られることのなきよう
• インデックスの定義は柔軟に見直せ

正規化とインデックス

• 正規化は特に実践すべき
• なぜならば

カラム数が絞られる

• 逆に、正規化されていないテーブルはカラムが多い
  • 必要なインデックスも増える
• 正規化されたテーブルには少なくとも1つの候補キーがある(1NFの定義)
  • PKインデックスつけられる

問題児NULL

• IS NULL検索は非効率
  • NULLはインデックス上で先頭または最後尾にまとまって配置される
  • 連続領域のスキャンにほかならない
• 3VLなってしまう、排中律が成り立たない
  • 「20歳未満または年齢不明」
  • WHERE age < 20 OR age IS NULL
  • IS NULLが含まれていると台無しに
  • 【補】ORでインデックス効かない製品もある

指令: 最適なインデックスを探せ！

• 唯一の正解はない

必要なインデックス

• 作成しすぎNG
  • 更新のオーバヘッド
  • ディスクスペース増大
  • バッファプールのヒット率低下

インデックスのアクセス特性

• テーブルスキャンを避けるためのインデックス
• が、テーブルスキャンのほうがシステム全体としてスループット高いことも
  • クエリ実行頻度がきわめて低い
  • テーブルのサイズが非常に小さい
    • 【補】 O(n)とO(logn)
  • 検索結果が非常に多くの行にヒットする
    • カヴァリングインデックスなら高速
    • さもないと低速
      • derefしてランダムアクセスする必要があるため

インデックスが使用される構文

WHERE句

• 前方一致でなければならないことに注意
• 等号・不等号混在は特に注意

-- 低効率
-- 複合インデックス(col1, col2)
WHERE col1 > 100 AND col2 = 'abc'

-- 高効率
-- 複合インデックス(col2, col1)
WHERE col2 = 'abc' AND col1 > 100

• B+木インデックスは前方一致
• 前者はcol1のインデックスしか効かない
  • col1 > 100
• 後者はcol2, col1のインデックス両方効く
  • col2 = 'abc' AND col1 > 100

JOIN

• 駆動表
  • FROM句の指定する表
• 内部表
  • JOIN句で指定する表

SELECT *
  FROM t1
  JOIN t2 ON t1.col1 = t2.col2
 WHERE t1.col3 = 100
   AND t2.col4 = 'abc';

• 内部表t2にマルチカラムインデックス(col2,col4)があると、col2単体のインデックスよりもアクセスが効率的になる可能性がある
  • オプティマイザが内部表と駆動表を入れ替えることがある
  • すると、テーブルから行がフェッチされる時点で両条件で絞り込まれる
    • t1.col1 = t2.col2
    • t2.col4 = 'abc'
  • フェッチ後に絞り込むよりも高効率

SELECT *
  FROM t2
  JOIN t1 ON t1.col3 = 100
 WHERE t1.col1 = t2.col2
   AND t2.col4 = 'abc';

• 【補】↑こういうこと？多分

相関サブクエリ

• INとかEXISTSとか
• これもWHEREとおなじこと(略)

ソート

• 前方一致
  • 順序が一致
  • 抜けがない
  • 最後のカラム以外等価比較

カヴァリングインデックス

• クエリの実行に必要なカラムがすべてインデックスに含まれている
  • deref・テーブルアクセスがおこらない
• 功罪
  • 非常に高速
  • インデックスのサイズが大きくなってしまう
    • ディスクスペース増大
    • 更新性能劣化

ORとインデックス

• インデックスマージ
  • ORで条件が結合されている場合
  • それぞれの条件にインデックスがある必要がある
  • インデックスを使って取得したROWIDがUNIONされる
• インデックスマージが実装されているかは製品次第
  • 使用不可or精度が低い場合は自前UNION
• ANDには適用できないの(マルチカラムインデックス必要ない説)
  • 絞り込み効率悪い

最適なインデックスを探すための戦略

インデックス≠候補キー

• インデックス
  • 制限の高速解決
  • 候補キーに限らない(セカンダリインデックス)
    • 同じ値が並び、範囲検索になる
• カヴァリングインデックス
  • さらに射影の高速解決

カラムの並び順

• カラムの順序のある/なし
  • インデックス: あり(重要)
  • リレーショナルモデル: なし
• 範囲検索やソートのクエリを記述する場合は、検索条件が前方一致になるようにカラムを配置する
• パフォーマンスのために、同じカラムの組み合わせで、並び順だけが異なるインデックスを作成することも

カーディナリティ

• カーディナリティが高いカラムだけ含んだインデックスを作るというテクニック
  • カーディナリティが低いカラムもわざわざ含める価値はない

最適な組み合わせを探す

• まず可能性を網羅
  • 製品を熟知することが重要
    • どのようなタイプのインデックスが使用できるか
    • 実行計画のどこでインデックスが利用可能になるか
      • 【補】インデックスマージ効く、とか
• つぎに必要なもののみ残す
  • 判断基準
    • 個々のカラムのカーディナリティ
    • テーブルのサイズ
    • クエリ実行頻度
  • 全体のバランスを取る
    • 1つのクエリの高速化のために更新が遅くなり、システム全体のパフォーマンスが悪化する、等はNG
• 本質は組み合わせ最適化問題
  • 難問
    • しかも試行錯誤に時間がかかる

難しい作業に立ち向かう

• 技術力が必要
• 基本が大事
  • B+ツリーインデックスの働き
  • B+ツリー以外のインデックスの種類
  • インデックス設計の前にしっかりと正規化を行う
  • 論理設計が決まってから物理設計
  • SQLのどのような個所にインデックスが必要か
  • カラムの並び順だけが異なるインデックスがあっても良い
  • 最大公約数的にカーディナリティが高いカラムだけを含んだインデックスを作る
  • 必要なインデックスの組み合わせを網羅する方法

真の最適解にこだわらない

• さっさと妥協せよ
  • 真の最適値を見つけることは困難
    • 割に合う保証もない
    • 運用している間に最適解が変化することもある

コラム: こんなインデックス設計はゴミ箱行きだ！

• すべてのカラムにインデックスがある
• インデックスに含まれているカラムが1つしかない
• たくさんあるマルチカラムインデックスに同じカラムの組が登場し、常に同じ順序で並んでいる
  • 【補】 順序が異なるならわかる(前方一致のため)
• 0か1しか値を取らない、フラグのようなカラムのインデックスがある
  • 【補】カーディナリティ低いので、deref・ランダムアクセスぶん性能が劣化するまである

SQL Antipatterns ch11 31 Flavors (WIP)

pragprog.com

---

31 flavors

Use metadata when validating against a fixed set of values.
Use data when validating against a fluid set of values.

• 「いくつかの決まった値しかとらないデータ」というものが存在する
  • 典型例: Salutation (あいさつの文句、Mrs.とか)
• かといって追加変更がないわけではない
• メタデータで管理するとテーブル定義の変更が必要になってしまい大変
  • 影響範囲甚大
  • 可用性を損ねる

Objective: Restrict a Column to Specific Values

• バグトラッキングシステムなら、バグにラベルをつけたくなる
  • NEW
  • IN PROGRESS
  • FIXED
• 変なラベルを付けられないように縛りたい
  • BANANA とか

Antipattern: Specify Values in the Column Definition

• メタデータによる縛り
  • ENUM (MySQL)
  • Check制約 (MySQL以外)
  • domain
  • UDTs: User Defined Types
  • トリガー

コラム: Baskin-Robbins 31 Ice Cream

• 今や31種類じゃないよね、という話
• システムでも同じ。ドメインはきっと広がるはず

What Was the Middle One?

• UI上で「設定可能な値」だけ表示するにはどうするか
• 「今設定されている値」をSELECT DISTINCTするのでは駄目
  • 鶏と卵の問題
  • 今設定されていない新しい値を設定できない
• じゃあどうする
  • メタデータの文字列を取得してアプリケーション側で解析する
    • ENUM('NEW, 'IN PROGRESS', 'FIXED')とか
  • アプリケーションコードに独立して記述する
    • DBとの同期がとれなくなる

Adding a New Flavor

• ALTER TABLE文でテーブル定義を変更する必要がある
• DB製品によっては、データがすでに入っているテーブルのテーブル定義を変更できない
  • ETLが必要
    1. データを退避(Extract)
    2. テーブル再定義(Transform)
    3. データ再読込(Load)
  • ダウンタイム生ずる
• データがすでに入っているテーブルのテーブル定義を変更できる製品もある
• が、いずれにせよ複雑で高コストなオペレーションである
• 一般論として、テーブルのメタデータの変更は頻繁に行うべきではなく、行う際には最新の注意をもってテスト・品質保証しなければならない

Old Flavors Never Die

• FIXEDをさらに2段階に分けたくなった
  • CODE COMPLETE
  • VERIFIED
• FIXEDはObsoleteなのでUI上からは消したい
• FIXEDを制約のホワイトリストから消す場合
  • もともとFIXEDだったデータはどうする？
• FIXEDを残す場合
  • FIXEDがObsoleteであることをどう表現する？

Portability Is Hard

• いずれも移植性が低い
  • ENUM (MySQL)
  • Check制約 (MySQL以外)
  • domain
  • UDTs: User Defined Types
  • トリガー

How to Recognize the Antipattern

• 取りうる値の集合が変わるかもしれない場合、ENUMやCheck制約で制限をかけるべきではない
• こんなのが聞こえてきたら注意
  • 「アプリケーションのメニューに選択肢を追加するためにダウンタイムが必要」
    • 取りうる値の集合がカラム定義 = テーブルのメタデータに織り込まれてしまっている
  • 「取りうる値のリストを変更する必要があるべきではない」
    • わざとあいまいにした言葉
      • できなくはないがやりたくない
  • 「アプリケーションコード中の『取りうる値のリスト』がDBと乖離してしまったよ、まただ」
    • 多重管理

Legitimate Uses of the Antipattern

• 取りうる値が変化しない場合
  • LEFT/RIGHT
  • ACTICE/IN-ACTIVE
  • ON/OFF
  • INTERNAL/EXTERNAL
• ENUM的でない制約をCHECK制約で課す場合
  • startがend未満である、など

Solution: Specify Values in Data

Querying the Set of Values

Updating the Values in the Lookup Table

Supporting Obsolete Values

Portability Is Easy

---

英語

• weasel words
  • わざとあいまいにした言葉

理論から学ぶデータベース実践入門 ch11 インデックスの設計戦略 (1/2)

gihyo.jp

---

まとめ

• 元になるDBの論理設計がしっかりしていることが重要
  • 1つのテーブルに膨大なカラムが含まれる、という事態を避ける
  • さもないと作成可能なインデックスの組み合わせは膨大な数になる
    • 難しいインデックス設計がさらに困難に

インデックスの働き

• 索引
• 本の索引は結局索引をフルスキャンする必要がある
• RDBの索引はもう少しスマート

RDBのインデックス

• 例えばB+ツリーインデックス
• ルートノードからリーフノードへ至る1本のパスだけを検索すれば済む
  • 平衡木ならO(log(n))

インデックスの左端と範囲検索

• B+ツリーインデックスは、等価比較および範囲検索に利用できる
  • <, >, <=, >=
  • BETWEEN
  • LIKE前方一致
• マルチカラムインデックスの場合もLIKE前方一致と同様
  • 指定順がインデックス定義順であること
  • 抜けがないこと

セカンダリインデックスの更新

• 主キー
  • めったに書き換えられることはない
• セカンダリインデックス
  • 更新ありまくり
• インデックス更新コストは高い
  • 削除・挿入と等価
  • 安易につけてはいけない

インデックスの種類

• B+ツリー以外にも種類あり
  • RDB製品次第
  • 要件次第で必要になる

ハッシュインデックス

• 検索速度が非常に速い
• 等価比較のみ。範囲検索には利用できない
  • 主キーは等価比較だけでよい場合が多い

全文検索インデックス

• 後方一致や中間一致を扱う
• 転値インデックス

rowid	text
1	Relational Model
2	Model View Controller
3	Materialized View

word	rowid
Controller	2
Materialized	3
Model	1
Model	2
Relational	1
View	1
View	2

• 行に含まれる単語あるいは部分文字列から行へのポインタが格納されている
• わかち書きがない言語(e.g.日本語)ではどうする？
  • 形態素解析
  • Nグラム

形態素解析

• 辞書を用いて文章の文法を解析、単語を抽出
• メリット
  • 無駄が少ない
• デメリット
  • 単語抽出能力の限界
    • ぎなた読み
    • 口語

Nグラム

• N文字ずつの部分文字列に分割
• 「外国人参政権」のバイグラム
  • 外国
  • 国人
  • 人参
  • 参政
  • 政権
• メリット
  • 網羅的
• デメリット
  • 検索ノイズが多い
    • 上記の例の「人参」など
  • インデックスのサイズ大きい

Rツリーインデックス

• 地図上の地点を検索するのに用いる
• Spacial Indexとも
• 最小外接矩形(MBR: Minimum Bounding Rectangle)を用いてインデックスを構築
• MBRをMBRで再帰的にくるむ
  • 子は適切な個数
  • なるべくオーバーラップしないよう
• MBRのツリーができあがる

関数インデックス

• WHERE year(date_col) = 2013とかにもインデックス適用できるやつ
• 関数適用後の値に対してB+ツリーインデックスを作成

ビットマップインデックス

• オンライン分析処理(OLAP: OnLine Analytical Processing)などで用いられる
• カラムごとに複数のビットマップが作成される

name	grade
飛鳥	2
葛城	3
斑鳩	3
柳生	1
雲雀	1

value	bitmap
1	00011
2	10000
3	01100

• メリット
  • インデックスのサイズが小さい
    • スキャン高速
• デメリット
  • ビットマップの更新に時間がかかる
    • オンライントランザクション処理(OLTP: Online Transaction Processing)には不向き
    • カラムがとりうる値のバリエーションが多い場合、期待したパフォーマンスが出ない
      • 必要なビットマップ数が増えてしまうため

コラム: クラスタインデックス

• テーブルそのものがインデックスでできている
  • 索引構成表(IOT: Index Organized Table)とも
  • InnoDBストレージエンジンではクラスタインデックス強制
• 主キーのリーフノードに他のカラムの値も一緒に格納
  • 主キー検索は速い
  • セカンダリインデックス検索はオーバヘッドあり
    • ツリーを辿らなければならない

パーティショニング

• 水平パーティショニングのことを指す

パーティショニング

• テーブル同じ構造のパーティションに分割
  • 日付ごとに分ける等
• 検索条件でパーティションを刈り込める(Partition Pruning)
• パーティションごとにインデックスが存在
  • 刈り込んだ後にインデックス検索できる
• パーティショニングの種類
  • レンジ
    • キーの範囲でパーティション決定
    • 日付ごとに分割する場合など
  • リスト
    • キーの値によってパーティション決定
    • カラムが取りうる値がごく少数の場合など
  • ハッシュ
    • キーから計算したハッシュ値の剰余などにしたがってパーティション決定

パーティショニングが適しているケース

• 刈り込みが有向なクエリの実行頻度が高い場合
• カーディナリティが低い場合
  • インデックスの効率がよくない
• アクセスの局所性がある場合
  • 「直近の月のみ検索対象」とか

パーティショニングと一意性制約

ローカルインデックス

• パーティションごとに作成されるインデックス
  • テーブル全体としては一意性を保証しない
• 多くの製品でローカルインデックスに課せられる制限
  • 主キーやユニークインデックスには必ずパーティションキーを含めなければならない
  • 元々ユニークインデックスを構成していたカラムの組が一意性を保証できなくなる可能性がある

パーティションキー追加前

hoge(PK)	fuga(PK)	year
1	1	2010
1	2	2010
2	1	2011
2	2	2011

パーティションキー追加後

hoge(PK)	fuga(PK)	year(PK)
1	1	2010
1	2	2010
2	1	2011
2	2	2011
1	1	2011

• {hoge,fuga}が一意性を失う例
  • 重複データを登録できてしまうように
• パーティショニングにより一意性を保証できなくなるくらいならパーティショニングすべきでない

グローバルインデックス

• 個々のパーティションではなく、テーブル全体を対象としたインデックス
• 一意性制約が損なわれる心配がない
• 反面、そのインデックスを使用する場合、パーティションの刈り込みができない
  • パーティショニングの旨味を損なう

パーティショニングについてよくある誤解

• 「パーティショニングすればそれだけでアクセスが高速化する」
• 基本的に刈り込みが効かなければ意味がない
• むしろ遅くなるケースも
  • 刈り込みがない & ローカルインデックス
  • パーティションの数だけインデックス検索が発生する

理論から学ぶデータベース実践入門 ch10 グラフに立ち向かう

gihyo.jp

---

まとめ

• グラフはリレーショナルモデルにない概念
  • 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はツリー構造を理解していない

理論から学ぶデータベース実践入門 ch9 履歴データとうまく付き合う

gihyo.jp

---

まとめ

• 日時を表すカラムがある場合に限らない
• すぐに気づきにくい
  • 「時間軸とリレーションが直行していない」など
• 本質的なまずさは「特別な意味を持つタプル」が一緒くたになっていること
  • テーブル分割せよ
  • ただし、集計処理で利用するだけならば分割しなくても何ら問題ない
• ヒント
  • ステータスやフラグを示すカラムがある
  • 初期値がNULLのカラムがある
  • 現在時刻との比較をしている
  • オンライントランザクション中にORDER BY N DESC LIMIT 1もしくはMAX()/MIN()/COUNT()が用いられている
  • バージョンを表すカラムがある
  • INSERT/DELETEよりもUPDATEの比率が高い

履歴データの問題点

• 遅いクエリの多くが履歴データの扱いに失敗している
  • 本質的にRDBと相性が良くない

世界は履歴データで溢れている

• わりに上手に付き合えているケースは少ない

履歴とリレーショナルモデルの相性問題

• そもそも履歴データをリレーションとして表現できるかどうか
  • リレーションは集合なので各要素に順序はない
  • 履歴には順序がある
• テーブルが巨大になりやすい

履歴データの具体例

item	price	start_date	end_date
ダンベルセット	10000	2010-01-01	9999-12-31
グリッパー	4000	2013-04-01	2014-03-31
グリッパー	5000	2014-04-01	9999-12-31
懸垂マシン	18000	2010-01-01	2011-12-31
懸垂マシン	20000	2012-01-01	2014-12-31
懸垂マシン	22000	2015-01-01	9999-12-31

• 懸垂マシンの現在の価格を調べるクエリ

SELECT price 
  FROM price_list
 WHERE item = '懸垂マシン'
   AND NOW() BETWEEN start_date AND end_date;

• 本章で本クエリ、テーブルの問題を認識できるようになること

履歴データの何が問題になるのか

リレーションと時間軸との直交性

• 同じクエリでも実行時刻により結果が異なる
• リレーションは「ある時点における事実の集合」
• 時間軸と直行でない(相関がある)ものはリレーションではない
  • = 1NFですらない

NULLの可能性

• 9999-12-31は「設定値なし」を表す特殊な値
  • 【補】前章で「誤ったNULL対策」として挙げられていたパターン
• 代わりにNULLを使用する設計も考えられる

特定の行だけ意味が違う

• 簡単のために題材を少し変更
  • end_dateなし
  • 未来日付なし

item	price	start_date
ダンベルセット	10000	2010-01-01
グリッパー	4000	2013-04-01
グリッパー	5000	2014-04-01
懸垂マシン	18000	2010-01-01
懸垂マシン	20000	2012-01-01

• 懸垂マシンの現在の価格を求めるクエリ

SELECT price
  FROM price_list
 WHERE item = '懸垂マシン'
   AND start_date = (SELECT MAX(start_date)
                       FROM price_list
                      WHERE item = '懸垂マシン');

• 集計でもないのになぜ集約関数MAX()が必要なんですか
  • リレーショナルな演算でないので使わないに越したことはない
• タプルの意味が命題関数だけで決まらず、均一でない
  • 暗黙の決まりごとがある
    • 「日付が最新の価格が現在の価格を表す」
  • 閉世界仮説に反する
    • リレーションの個々のタプルの意味は命題関数だけで決まり、それ以上でも以下でもいけない

履歴データに対する解決策

• 絶対的な解はない
  • リレーショナルモデルに収まらない以上、次善の策の域を出ない

リレーションを分割する

• 同一の命題関数で評価できないタプルを同一のテーブルに混ぜない
• DB設計の盲点
  • 正規化プロセスでは発見できない

最もシンプルな分割方法

price_list

item	price	start_date
ダンベルセット	10000	2010-01-01
グリッパー	5000	2014-04-01
懸垂マシン	20000	2012-01-01

price_list_history

item	price	start_date
グリッパー	4000	2013-04-01
懸垂マシン	18000	2010-01-01

• 現在の懸垂マシンの価格

SELECT price
  FROM price_list
 WHERE item = '懸垂マシン';

• メリット
  • 現在の価格を取得するクエリがシンプルに
• デメリット
  • 過去から現在までの全価格に対してクエリする場合はUNIONが必要に
    • WHERE句のNOW()や、集計でもないのにサブクエリに現れるMAX()よりはマシ
  • FK制約効かない
  • 整合性の確保が必要
    • トリガー
• 元の設計よりはずっと好ましい

重複した行を許容する

price_list

item	price	start_date
ダンベルセット	10000	2010-01-01
グリッパー	4000	2013-04-01
グリッパー	5000	2014-04-01
懸垂マシン	18000	2010-01-01
懸垂マシン	20000	2012-01-01

price_list_history

item	price	start_date
グリッパー	4000	2013-04-01
懸垂マシン	18000	2010-01-01

• メリット
  • FK制約使える
• デメリット
  • 直交性失う

サロゲートキー

• 重複は許さないが、FK制約は使いたい

price_id_master

price_id
1
2
3
4
5

price_list

price_id	item	price	start_date
1	ダンベルセット	10000	2010-01-01
3	グリッパー	5000	2014-04-01
5	懸垂マシン	20000	2012-01-01

price_list_history

price_id	item	price	start_date
2	グリッパー	4000	2013-04-01
4	懸垂マシン	18000	2010-01-01

• メリット
  • 単一のprice_id_masterテーブルに対してFK制約使える
  • 価格データの重複ない
• デメリット
  • 結合多い
  • オーバヘッド
    • 余計な列
    • 余計なインデックス

未来の価格はどうすべきか

• やはり分ける
  • 意味が異なるから

price_id_master

price_id
1
2
3
4
5

price_list

price_id	item	price	start_date
1	ダンベルセット	10000	2010-01-01
3	グリッパー	5000	2014-04-01
5	懸垂マシン	20000	2012-01-01

price_list_upcoming

price_id	item	price	start_date
7	ダンベルセット	12000	2014-08-01
8	懸垂マシン	20000	2015-01-01

price_list_history

price_id	item	price	start_date
2	グリッパー	4000	2013-04-01
4	懸垂マシン	18000	2010-01-01

• 「未来」そのときがやってきたら？
  • 「現在の価格」を更新するバッチ処理が必要
  • この設計ではリアルタイムに価格を切り替えることはできない
    • そのような要件を盛り込まないように注意する

履歴データのアンチパターン

フラグを立てる

item	price	start_date	end_date	active
ダンベルセット	10000	2010-01-01	9999-12-31	1
グリッパー	4000	2013-04-01	2014-03-31	0
グリッパー	5000	2014-04-01	9999-12-31	1
懸垂マシン	18000	2010-01-01	2011-12-31	0
懸垂マシン	20000	2012-01-01	2014-12-31	1
懸垂マシン	22000	2015-01-01	9999-12-31	0

• 現在の懸垂マシンの価格を取得
  • WHERE句のNOW()は消えた

SELECT price
  FROM price_list
 WHERE item = '懸垂マシン'
   AND active = 1;

問題

• フラグカラムはカーディナリティ低い
  • 効率悪い
• 2NFでない
  • 候補キーは{item, start_date, end_date}
  • フラグカラムが候補キーの真部分集合に関数従属

{start_date, end_date) -> {active}

• activeカラムの更新バッチ処理が必要
  • start_date/end_dateとNOW()を使ったクエリとactiveを使ったクエリが混在すると不整合が生じる
• active = 1なる行は常に1つでなければならない
  • トリガー

手続き型として実装する

• 最後の手段

コラム1 フラグのお化け

• 異なる意味合いのタプルは異なるリレーションに含めよ
• 安易にフラグカラムを追加する前に、リレーション分割を検討する
• さもないとフラグのおばけになる
  • 検索条件だらけのスパゲティクエリ
  • 実行速度も遅い

コラム2 テーブルを分けたときの物理的なメリット

• テーブルのサイズが小さくなる
• 検索速くなる
  • インデックス: O(log(n))
  • フルスキャン: O(n)
• 頻繁にアクセスするテーブルの分離
  • たいてい「現在の値」のほうがヒストリよりもアクセス頻度高い

理論から学ぶデータベース実践入門 ch8 SELECTを攻略する (2/2)

gihyo.jp

---

リレーショナルではない操作

リレーショナルな操作のおさらい

• SELECTによるリレーショナルな操作

リレーションの演算	SELECTによる表現
制限	基本形: WHERE句
射影	基本形: select list
直積	基本形: FROM句, JOIN句
結合	基本形: FROM句, JOIN句
積	基本形: FROM句, JOIN句
和	UNION
差	NOT EXISTSサブクエリ, MINUS
属性名変更	基本形: select list
拡張	基本形: select list

• IN, ANY, EXISTSサブクエリはJOINとDISTINCTを用いて書けることが知られている
• 他のはリレーショナルな演算でない
  • FROM句のサブクエリで集約を行っている場合など

ソート

• ORDER BY句による結果セットの並べ替えはリレーショナルモデル上の演算ではない
  • 何しろ集合の要素に順序はない
• ORDER BYはカーソルの操作である (SQL標準より)
  • SELECT自身のではない
• アプリケーション開発上有用だが、リレーショナルモデルから逸脱する危険な要素であるため要注意

明示的に定義されていないカラム

• ROWID、ROWNUMなど
• やはり順序絡みなのでリレーショナルモデルを逸脱する。要注意

ストアドファンクション(ユーザ定義関数)

• ストアドファンクションのロジックは手続き型で記述される
• ストアドファンクションがSELECTに含まれると、手続き型の処理になる
• オプティマイザ困惑
• SQLは宣言型プログラミング言語である
  • 手続き型ロジックを持ち込むと破綻する

コラム: 集約とGROUP BY

• GROUP BYは数学的には「要約」(Summarizatoin)だよ、という話
  • リレーションからリレーションを求める
    • 閉包である
  • cf. 「集約」(Aggregate)はリレーションからスカラを求める
    • 閉包でない
• 要約は拡張の一種
  • リレーションの演算以外の何らかの方法で集計を行い、新たに属性を追加している
• 学生の人数を学科ごとに集計する例

SELECT department
     , COUNT(*)
  FROM students
 GROUP BY department;

• 同等の結果を得るサブクエリ

SELECT department
     , (SELECT COUNT(*)
          FROM students
         WHERE department = t1.department
       ) AS COUNT
  FROM (SELECT DISTINCT
               department
          FROM students
       ) AS t1;

• 見出し列

SELECT DISTINCT
       department
  FROM students

• これに集計結果の列を追加している(拡張)

SELECT COUNT(*)
  FROM students
 WHERE department = t1.department

リレーショナルではない操作の扱い方

• アプリケーション開発ではリレーショナルではない操作も必要
  • 例: ソート
• 大事なのは、リレーショナルな操作とそうでない操作とを明確に区別すること
• 指針
  • リレーショナルモデルの範疇でできることをリレーショナルではない操作で実装しない
    • オプティマイザによる最適化はリレーショナルモデルの範疇で最大の威力を発揮するため
  • リレーショナルモデルの範疇でうまく記述できないと思ったら、DB設計を見直す
    • 見直しができない場合、泥沼に足を踏み入れることになる
  • リレーショナルではない操作がどうしても必要な場合は、リレーショナルな操作に関するロジックを必ず先に行う
    • 【補】リレーショナルな操作の入力はリレーション
      • 先にリレーショナルではない操作を行ってしまうと、後にリレーショナルな操作を続けられない

インデントでSQLを読みやすくする

• MySQL Workbenchとかでやると良いよ