それが僕には楽しかったんです。

ミドルウェアとかやってます

CMU Database Systems をひたすら追っていく ~01 Relational Data Model~

この記事は「 けんつの1人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar 」1日目の記事です。

はじめに

どうも、最近やたらと B 級 SF 映画にドハマりしているけんつです。直近だと「リディック:ギャラクシーバトル」がまぁまぁおもしろかったです。
ついでに「ピッチブラック」をその前に見ておくとまぁまぁおもしろいです。

ところで、以前 TL 警備をしていたらこんなブログ記事が登場した。
buildersbox.corp-sansan.com

えぇ、「DBMS」、「Go」、「実装」の単語をみてもう既にやる以外の選択肢がないですね。
データベース好きにはたまらない内容だった。

それで、その記事のなかで紹介されていた「CMU Database Systems」というカーネギーメロン大学のデータベースに関する講義の動画をちょっと見ていたら
めちゃくちゃ面白かったので勉強がてら記事にしていく。

英語、全く得意では無いので割とあやふやな内容になるかもしれませんが何かあればコメントください。

動画リストを見た感じの大まかな流れ

動画内でも紹介されているが、下のレイヤーから上にたどっていく形になっているみたい。

  • リレーショナルモデル(今回まとめるやつ)
  • Advanced SQL(なにを指しているのか?)
  • ストレージ
  • バッファプール
  • ハッシュテーブル
  • ツリーインデックス
  • Index Concurrency Control(同時実行制御に関することだと思うけど index はどこに出てくる?)
  • Query Processing(??)
  • ソートと集約アルゴリズム
  • ジョインアルゴリズム
  • クエリの最適化
  • 並列実行
  • Embedded Logic(?)
  • Two-Phase Locking Concurrency Control
  • Timestamp Ordering Concurrency Control
  • Multi-Version Concurrency Control
  • Logging Schemes
  • Database Recovery
  • Distributed OLTP Database
  • Distributed OLAP Database

今日の動画

www.youtube.com

今回は初回ということで少し単純な内容になっている。
ほとんど和訳に近い。

Database とは

現実世界の相互関連的なデータを組織的に、あるいは形式的にまとめたコレクションを扱うものであり
多くのコンピュータアプリケーションの中核を担うもの。

例題

例えば音楽配信サイトを考えた時に曲とアーティスト、アルバム情報を保持するデータベースを考える。
それを実現するために、アーティストの情報とどのアーティストがどのアルバムをリリースしたかという情報を保持することを考える。

これを解決する場合にまず想定されることは CSV(comma-separated value) ファイルなどの Flat File *1を使用すること。
それによって、アプリケーション側のコードでデータ等を管理することが出来る。

データベースとしての Flat Files の問題点

データの整合性をどうやって担保するかという課題が出てくる。
例題をもとに表すならアーティストが各アルバムエントリで同じであることをどのように確認するかという問題が発生する。
さらに言えば誰かがアルバムの発売年を適切でない値に置き換えてしまうかもしれないという問題も起こる。
またひとつのアルバムに複数のアーティストが存在する場合なども実装が難解になってしまう。

整合性の問題の次は、実装上の問題が露呈する。
たとえば、特定のレコードをどのように見つけるか?
複数のアプリケーションで同じデータベースを使うにはどうしたらよいか?
2つのスレッドが同時に書き込みを行ったらどういう挙動をするか?

次に耐久性の問題。
データを更新している最中にマシンがクラッシュしたらレコードはどうなるか?
高可用性のためにデータベースのレプリケーションを複数取りたい場合はどうなるか?

これらを解決するための方法の一つとして DBMS (DataBase Management System) の利用が挙げられる。

DataBase Management System

DataBase Management System (DBMS) とはアプリケーションがデータベース内にデータを保管・分析するためのソフトウェアを指す。
これらいわゆる汎用DBMSは、データベースの定義、作成、クエリ、更新、および管理を可能にするように設計されている。

しかし、初期の DBMS ではデータベースアプリケーションの構築と保守が論理層と物理層が密結合するため困難だった。
またデータベースにデプロイする以前にアプリが実行するクエリを大まかにでも知っておく必要があった。

そのためにリレーショナルモデルが考案された。

リレーショナルモデル

1970 年代に エドガー・コッド (Edgar Frank "Ted" Codd) によって考案された。 *2

複雑なメンテナンスを回避するために、以下の様にデータベースを抽象化する。

  • データベースを単純なデータ構造として表現
  • 高級言語を介してデータを操作
  • 物理ストレージ関連のものは実装依存にする
データモデル

今回、というかこの一連の内容で取り上げられるのはリレーショナルモデルだが他にも

  • Key/Value
  • Graph
  • Document
  • Column-family
  • Array/Matrix
  • Hierarchical
  • Network

などが存在する。

さらに詳しくリレーショナルモデル

リレーショナルモデルにはいくつかの定義が存在する。

まずリレーショナルモデルを取った場合その構造はデータとそのリレーションの定義から構築される。
次に、そのデータベースが保持するデータは制約を満たしていることが確認される。
最後に、それらリレーショナルモデルはデータベースのデータにアクセス、変更する方法が提供される。(SQLのこと?)

リレーションとタプル

リレーショナルモデルを扱うためにまずリレーションとタプルが定義される。

リレーションとは、エンティティを表現する属性と関係を含む順序の無い集合を指す。
タプルは属性値の集合でドメインとも呼ばれる。ただし、値は Atomic/Scalar で Null は全てのドメインのメンバーとされる。

そのため n-ary relation *3 *4と n 列を持つテーブルは同値となる。

主キー(Primary keys)

主キーは単一のタプルを一意に識別することができる性質を持つ。
ただし一部の DBMS では主キーを定義しない場合、自動的に作成する場合がある。

MySQL においてユニークな数値を主キーとする場合は AUTO_INCREMENT を使うことがよく知られている。

外部キー

外部キーは主キーと似たようなもので、あるリレーションの属性を別の関係のタプルにマッピングする必要があることを指定するものを指す。

DML (Data Manipulation Language)

Data Manipulation Language とは SQL を構築する 3 つの言語の一つ*5でその名の通りデータ操作に関連することを行う言語を指す。
具体的には SELECT, INSERT, UPDATE, DELETE などである。

また関係代数 においてはクエリ、今回で言えば DML とは DBMS が目的の結果を見つけるために使用する戦略を指定することで
関係計算 においては必要なデータのみが指定され検索方法等は指定されないという特性を持つ。

クエリ

リレーショナルモデルが保持するデータをクエリを使って操作することは出来るが、クエリの実装がリレーショナルモデルには影響しないことがクエリとリレーショナルモデルを考える上で重要となってくる。
実際 SQLMySQLPostgreSQL に置いて独自構文等を備えているが、ベースとなっているのは ANSI/ISO SQL という標準規格であって
その規格もリレーショナルモデルそのものに関与するものでなくあくまでそのインターフェースにすぎないことがわかる。

おわりに

今回は、あくまで一般的な DBMS とは、リレーショナルモデルとはという話になってしまったが DBMS やリレーショナルモデルは集合論の上にあり
どのような特性をもち、どのように操作するのかは今後の学習において重要な基盤となるのでしっかりと抑えて置きたい。

次回は CMU Database Systems では「Advance SQL」となっているが、その回を飛ばしてストレージの話に移ろうか迷っている。