RDB

関係データベース以前のデータモデル

関係モデルの意義を理解するためには、それ以前に主流であったデータモデルとの対比が不可欠である。1960年代から1970年代初頭にかけて、大規模データベース管理システムとして広く用いられていたのは、階層モデル（hierarchical model）とネットワークモデル（network model）の二つであった。

階層モデルは、IBM社が1966年に開発した IMS（Information Management System）に代表される。データはツリー構造として表現され、各レコードは一つの親レコードのみを持つ。この制約により、多対多の関係を自然に表現することが困難であった。

一方、ネットワークモデルは、1969年にCODASYL（Conference on Data Systems Languages）によって標準化された。階層モデルと異なり、一つのレコードが複数の親を持つことを許容し、より柔軟な関係表現を可能にしたが、データへのアクセスはポインタを辿るナビゲーショナルな手続き（navigational access）に依存しており、アプリケーションプログラムがデータの物理的な格納構造を意識せざるを得ないという問題を抱えていた。

これらのモデルにおいては、問い合わせを行うたびに、プログラマがどの経路でレコード間のリンクを辿るかを明示的に記述する必要があり、データの格納構造を変更するとアプリケーションプログラムの修正が不可避であった。この「データ独立性の欠如」が、後に関係モデルが解決を試みる中心的課題となった。

エドガー・F・コッドの経歴と1970年の論文

エドガー・フランク・コッド（Edgar Frank Codd）は、英国生まれの数学者・計算機科学者であり、オックスフォード大学で数学を専攻した後、1949年にIBM社に入社した。1960年代を通じて多重処理システムの研究に従事した後、データベースの理論研究に転じた。

コッドは1970年、ACM（Association for Computing Machinery）の学会誌『Communications of the ACM』に論文「A Relational Model of Data for Large Shared Data Banks」を発表した。この論文でコッドは、データを集合論に基づく「関係（relation）」として捉え、データの論理構造を格納方式や探索アルゴリズムから完全に分離するという構想を提示した。

コッドがこの構想に至った背景には、当時のネットワークモデルに基づくシステムが抱えていた保守性の低さへの問題意識があった。コッドは、ユーザーやアプリケーション開発者が「データがどのように格納されているか」を意識することなく、「何を求めているか」のみを記述できる問い合わせ言語こそが望ましいと考えた。この思想は後に「宣言的（declarative）問い合わせ」という概念として結実する。

なお、コッドの提案は発表当初、IBM社内でも懐疑的に受け止められた。既存の階層モデル・ネットワークモデル製品（IMSなど）からの移行コストや、関係モデルの理論的な性能面での懸念があったためである。この懐疑を乗り越え、関係モデルの実用性を示す必要から、後述するSystem Rプロジェクトが立ち上げられることとなった。

関係モデルの形式的定義

関係モデルにおける基本的な構成要素を、より厳密に定義する。

属性の集合を $U = \{A_1、 A_2、 \ldots、 A_n\}$ とし、各属性 $A_i$ に対して定義域（ドメイン）$dom（A_i）$ が定められているとする。このとき、関係スキーマは属性集合として定義される。

\[R = \{A_1、 A_2、 \ldots、 A_n\}\]

関係スキーマ $R$ に対する関係インスタンス（実際のデータの集合）$r$ は、各属性の定義域の直積の有限部分集合として定義される。

\[r \subseteq dom（A_1） \times dom（A_2） \times \cdots \times dom（A_n）\]

$r$ の各要素はタプルと呼ばれ、次のように表記される。

\[t = \langle t[A_1]、 t[A_2]、 \ldots、 t[A_n] \rangle\]

ここで $t[A_i]$ はタプル $t$ の属性 $A_i$ に対する値を表す。関係は数学的には集合であるため、以下の性質が成立する。

• タプルの順序に意味はない（集合には順序がないため）。
• 重複するタプルは存在しない（集合には重複要素がないため）。ただし実装上のRDBMSでは、性能上の理由から重複行を許容する場合が多く、この点は理論と実装の乖離の一例である。
  候補キー（candidate key）は、関係 $r$ において次の二条件を満たす属性の部分集合 $K \subseteq U$ として定義される。
• 一意性:$r$ の任意の二つの異なるタプル $t_1、 t_2$ について、$t_1[K] \neq t_2[K]$ が成立する。
• 最小性:$K$ のいかなる真部分集合 $K' \subsetneq K$ についても、一意性が成立しない。
  複数存在しうる候補キーのうち、設計上選ばれた一つが主キー（primary key）となる。

関係代数の体系的整理

関係代数は、コッドが1970年の論文および1972年の続報で提示した、関係に対する演算の体系である。基本演算は以下の八種類に整理される。

・和集合（union）:$R \cup S$。両者が同じ属性構成（和両立、union-compatible）であることを要する。・差集合（set difference）:$R - S$・直積（Cartesian product）:$R \times S$・選択（selection）:$\sigma_{\theta}（R）$。条件 $\theta$ を満たすタプルのみを取り出す。・射影（projection）:$\pi_{A_1、 \ldots、 A_k}（R）$。指定属性のみを取り出し、結果として重複するタプルは除去される。・名前変更（rename）:$\rho_{S（B_1、 \ldots、 B_n）}（R）$

これらのうち、和集合・差集合・直積・選択・射影の五つが基本演算（primitive operations）であり、残りの演算（共通集合、結合、商など）はこれら基本演算の組み合わせとして定義可能であることが示されている。

たとえば結合（join）は、直積と選択の組み合わせとして定義できる。

\[R \Join_{\theta} S \;=\; \sigma_{\theta}（R \times S）\]

共通する属性名に基づく自然結合（natural join）は、次のように定義される。

\[R \Join S \;=\; \pi_{U}\big(\sigma_{R。A_1 = S. A_1 \,\land\, \cdots \,\land\, R.A_k = S. A_k}(R \times S)\big)\]

ここで $A_1, \ldots, A_k$ は $R$ と $S$ に共通する属性である。

さらに、通常の結合ではいずれかの関係にのみ存在するタプル（相手側に対応するタプルを持たないもの）が結果から除外されるのに対し、外部結合（outer join）は、対応するタプルが存在しない側の属性値をNULLで埋めた上で、そのタプルを結果に含める。左外部結合、右外部結合、完全外部結合の三種が存在する。

商演算（division）は、「$R$ に含まれるすべての $S$ の組み合わせを持つ」という、全称量化子に対応する問い合わせを表現するための演算であり、基本演算のみを用いると次のように構成できる。

\[R \div S \;=\; \pi_{X}(R) - \pi_{X}\big((\pi_{X}(R) \times S) - R\big)\]

ここで $X$ は $R$ の属性のうち $S$ に含まれないものの集合である。この商演算は「すべての」という条件を扱う問い合わせ（例:全科目で合格した学生を求める、など）に対応する。

関係論理:タプル論理とドメイン論理

関係代数が手続き的な言語であるのに対し、コッドは非手続き的な問い合わせ言語として関係論理（relational calculus）を提示した。関係論理には、タプル関係論理（tuple relational calculus）とドメイン関係論理（domain relational calculus）の二種がある。

タプル関係論理における問い合わせは、タプル変数 $t$ を用いて次の形式で表現される。

\[\{\, t \mid \varphi（t） \,\}\]

ここで $\varphi（t）$ は、タプル変数に関する原子論理式（atomic formula）を、論理積（$\land$）、論理和（$\lor$）、否定（$\lnot$）、存在量化子（$\exists$）、全称量化子（$\forall$）によって結合した論理式である。

ドメイン関係論理は、タプル全体ではなく個々の属性値（ドメイン変数）を対象とする点で異なる。

\[\{\, \langle x_1, x_2, \ldots, x_n \rangle \mid \varphi(x_1, x_2, \ldots, x_n) \,\}\]

QBE（Query By Example）は、このドメイン関係論理を視覚的な表形式のインターフェースとして実装したものであり、1970年代半ばにIBM社のモシェ・ザルーアによって開発された。

関係論理を無制限に用いると、無限集合を結果として導出しうる論理式（例:「$x$ が $R$ に属さない」といった否定条件のみからなる式）を記述できてしまうため、有限のデータベースに対して意味のある（有限の）結果を常に返すことを保証するために、論理式を「安全（safe）」なものに制限する必要がある。コッドは、関係代数によって表現可能な問い合わせのクラスと、安全な関係論理式によって表現可能な問い合わせのクラスが完全に一致することを証明し、これを関係的完全性（relational completeness）と呼んだ。この定理は、後にSQLをはじめとする問い合わせ言語が備えるべき表現力の基準として広く参照されることとなった。

関数従属性理論の精緻化

関数従属性 $X \rightarrow Y$ の理論は、コッド自身による初期の提示の後、ウィリアム・アームストロング（William W。 Armstrong）によって1974年に公理化された。アームストロングの公理系は以下の三規則から構成される。

• 反射律（reflexivity）:$Y \subseteq X$ ならば $X \rightarrow Y$
• 増加律（augmentation）:$X \rightarrow Y$ ならば、任意の属性集合 $Z$ について $XZ \rightarrow YZ$
• 推移律（transitivity）:$X \rightarrow Y$ かつ $Y \rightarrow Z$ ならば $X \rightarrow Z$

この三規則は健全（sound）かつ完全（complete）であることが証明されている。すなわち、これらの規則から導出可能な関数従属性の集合は、実際に成立する関数従属性の集合と過不足なく一致する。さらに、これらの基本規則から以下の派生規則が導かれる。

• 結合律（union）:$X \rightarrow Y$ かつ $X \rightarrow Z$ ならば $X \rightarrow YZ$
• 分解律（decomposition）:$X \rightarrow YZ$ ならば $X \rightarrow Y$ かつ $X \rightarrow Z$
• 擬推移律（pseudotransitivity）:$X \rightarrow Y$ かつ $WY \rightarrow Z$ ならば $WX \rightarrow Z$

関数従属性の集合 $F$ が与えられたとき、$F$ から論理的に導出可能な関数従属性すべての集合を、$F$ の閉包（closure）と呼び、$F^+$ と表記する。また、属性集合 $X$ に対し、$F$ のもとで $X$ から関数的に決定される属性すべての集合を $X$ の属性閉包と呼び、$X^+$ と表記する。正規化の判定やキーの導出は、この属性閉包の計算アルゴリズムに基づいて機械的に行うことができる。

正規形の階層とその限界

正規化理論は、関数従属性に基づく異常性の排除を段階的に進める設計指針として整理されている。

• 第一正規形（1NF）:すべての属性値が原子値であること。繰り返し項目や複合値を許容しない。
• 第二正規形（2NF）:1NFを満たし、かつすべての非キー属性が、いかなる候補キーに対しても部分関数従属していないこと。
• 第三正規形（3NF）:2NFを満たし、かつ非キー属性間に推移的関数従属が存在しないこと。
• ボイス-コッド正規形（BCNF）:非自明な関数従属 $X \rightarrow Y$ がすべて、$X$ が候補キー（スーパーキー）であるものに限られること。

BCNFは3NFよりも厳密であるが、BCNFへの分解を行うと、元の関係が持っていたすべての関数従属性を分解後の関係の結合によって復元できなくなる（従属性保存性、dependency preservation の喪失）場合があることが知られている。このトレードオフは、正規化理論における既知の限界の一つである。

さらに、関数従属性だけでは捉えられない冗長性に対応するため、多値従属性（multivalued dependency）の概念に基づく第四正規形（4NF）、および結合従属性（join dependency）に基づく第五正規形（5NF、射影結合正規形とも呼ばれる）が、1970年代後半にロナルド・ファーギン（Ronald Fagin）によって定式化された。

多値従属性 $X \twoheadrightarrow Y$ は次のように定義される。関係 $r$ の任意の二つのタプル $t_1、 t_2$ が $t_1[X] = t_2[X]$ を満たすならば、$r$ の中に次を満たすタプル $t_3、 t_4$ が存在する。

\[t_3[X] = t_4[X] = t_1[X]、\quad t_3[Y] = t_1[Y]、\ t_3[Z] = t_2[Z]、\quad t_4[Y] = t_2[Y]、\ t_4[Z] = t_1[Z]\]

ここで $Z = U - X - Y$ である。この従属性は、互いに独立した二つの多値の属性を一つの関係に無理に格納した際に生じる冗長性を捉えるものである。

System RとIngres:実装研究の詳細

コッドの理論を実用システムとして検証するため、1970年代に二つの主要な研究プロジェクトが並行して進められた。

IBM社サンノゼ研究所の System R プロジェクト（1974年開始）では、以下の要素技術が確立された。

・SEQUEL（後にSQLと改称）と呼ばれる問い合わせ言語の設計。当初は「構造化英語問い合わせ言語」を志向し、自然言語に近い構文（SELECT、 FROM、 WHEREなど）を採用した。

• 問い合わせ最適化（query optimization）:関係代数式に対して複数の実行計画（access path）を生成し、推定コストに基づき最適な計画を選択する仕組み。System Rで確立されたコストベース最適化の手法は、その後のRDBMS実装の標準となった。
• トランザクション管理とロック機構:二相ロック（two-phase locking）による同時実行制御、および障害からの復旧を目的としたログ機構（WAL、ログ先行書き込み）の原型が実装された。
• ビュー（view）の概念:実データを持たない仮想的な関係として、問い合わせ結果を定義する機構。

一方、カリフォルニア大学バークレー校の Ingres プロジェクト（マイケル・ストーンブレーカー、ユージン・ウォンらが主導、1973年開始）では、独自の問い合わせ言語 QUEL が開発された。Ingresは大学発のプロジェクトであったため、そのソースコードは比較的自由に配布され、後年多くの派生プロジェクト（Sybase、Informixなど）や、ストーンブレーカー自身による後継プロジェクトである POSTGRES（1980年代後半、オブジェクト関係モデルの導入を志向）を通じて、PostgreSQLの直接の源流となった。

商用化と標準化の過程

System Rの成果が公開されると、これに触発されたラリー・エリソンらが1977年にリレーショナル・ソフトウェア社（後のオラクル社）を設立し、1979年、SQLを採用した商用RDBMSとして初めて Oracle Version 2 を市場に投入した（興味深いことに、IBM自身が商用製品としてSQL/DS、DB2を発表するよりも先行していた）。

IBM社は1981年にSQL/DSを、1983年には汎用機向けにDB2を発表した。同時期、Sybase（1984年設立）やInformix、Ingresを商用化した Relational Technology 社などが市場に参入し、1980年代を通じてRDBMSは企業の基幹業務システムにおける標準的なデータ管理方式としての地位を確立した。

問い合わせ言語としてのSQLは、複数ベンダーの実装が乱立する状況を踏まえ、1986年にANSI（米国規格協会）によってSQL-86として標準化され、1987年にはISO（国際標準化機構）によっても採択された。その後も以下のように継続的に改訂されている。

• SQL-89:軽微な修正
• SQL-92（SQL2）:大幅な機能拡張、結合構文の整理
• SQL:1999（SQL3）:再帰問い合わせ（WITH RECURSIVE）、トリガー、オブジェクト指向拡張
• SQL:2003:ウィンドウ関数、XML対応、自動採番列
• SQL:2006以降:XQuery連携、JSON対応（SQL:2016）、多次元配列など

トランザクション理論とACID特性

ACID特性（原子性・一貫性・独立性・永続性）という語は、1983年にテオ・ハーダー（Theo Härder）とアンドレアス・ロイター（Andreas Reuter）による論文において初めて明示的にまとめられた。

• 原子性（Atomicity）:トランザクションを構成する一連の操作は,不可分な単位として,すべて実行されるか全く実行されないかのいずれかとなる.障害発生時には,ログに基づき未完了のトランザクションの操作を取り消す（ロールバック,undo）ことで実現される.
• 一貫性（Consistency）:トランザクションの実行前後で,データベースはあらかじめ定義された整合性制約（キー制約,参照整合性制約,チェック制約など）を満たし続ける.
• 独立性（Isolation）:複数のトランザクションが並行実行されても,各トランザクションはあたかも単独で実行されているかのような結果を得る.独立性の厳密さには段階があり,ANSI SQL標準では以下の分離レベルが定義されている.
  • READ UNCOMMITTED:他のトランザクションの未コミットの変更を読み取りうる（ダーティリード）
  • READ COMMITTED:コミット済みのデータのみを読み取る
  • REPEATABLE READ:同一トランザクション内で同じ行を再読み取りしても値が変化しない
  • SERIALIZABLE:並行実行の結果が,何らかの逐次実行と等価になることを保証する最も厳格なレベル
  独立性を実現する手法として,ロックに基づく手法（二相ロック）と,ロックを用いずタイムスタンプやバージョン番号に基づき制御する多版型同時実行制御（MVCC）がある.PostgreSQLやOracleはMVCCを採用しており,読み取り操作が書き込み操作をブロックしないという利点を持つ.
• 永続性（Durability）:コミットが完了したトランザクションの結果は,その後にシステム障害が発生しても失われない.ログ先行書き込み（WAL）により,データ本体への書き込みに先立って変更内容をログに記録し,障害復旧時にはログを再生（redo）することで,コミット済みの変更を再現する.

クエリ処理と最適化の内部構造

RDBMSにおいて、SQLで記述された宣言的な問い合わせは、以下の段階を経て実行される。

• 構文解析（parsing）:SQL文を構文木に変換する。
• 意味解析（semantic analysis）:テーブルや列の存在確認、型の整合性検証を行う。
• 論理最適化（logical optimization）:構文木を関係代数式に変換し、選択や射影をできるだけ早い段階で適用する（プッシュダウン）など、同値変換規則に基づき代数式を書き換える。
• 物理最適化（physical optimization）:各演算に対して具体的なアルゴリズム（結合であればネステッドループ結合、ソートマージ結合、ハッシュ結合など）と、インデックスの利用可否を検討し、統計情報（テーブルの行数、列値の分布など）に基づき推定コストを算出した上で、最小コストの実行計画を選択する。
• 実行（execution）:選択された実行計画に基づき、実際にデータへアクセスし結果を生成する。

  インデックス構造として広く用いられるB木（B-tree、および多分岐平衡木の一種であるB+木）は、ディスクI/Oの回数を対数オーダーに抑えることで、大規模なテーブルに対する検索性能を保証する。

分散環境とNoSQLとの理論的対比

2000年代後半以降、ウェブサービスの大規模化に伴い、単一のRDBMSでは水平方向のスケーラビリティ（複数の機器への分散）の実現が困難であるという課題が顕在化した。この文脈で、エリック・ブリューワー（Eric Brewer）が2000年に提示したCAP定理が広く参照されるようになった。CAP定理は、分散システムにおいて一貫性（Consistency）、可用性（Availability）、分断耐性（Partition tolerance）の三特性を同時に完全に満たすことはできないとする定理である。

この理論的制約を踏まえ、厳密なACID特性よりも、可用性とスケーラビリティを優先し、一定の遅延の後にデータの一貫性が達成されることを許容するBASE特性（Basically Available、 Soft state、 Eventually consistent）を志向するNoSQLデータベース（キーバリュー型、ドキュメント型、カラム指向型、グラフ型）が台頭した。

もっとも、近年ではGoogle Spannerに代表されるNewSQLと呼ばれる分野のように、分散環境においてもSQLインターフェースと強い一貫性・ACID特性を維持しようとする設計も登場しており、関係モデルの理論的枠組みそのものが分散システムの文脈で再評価されている。

Mathematics is the language with which God has written the universe.