tom__bo’s Blog

MySQL!! MySQL!! @tom__bo

リレーショナル・データベースの"リレーション"とは何か?

リレーショナル・データベースにおけるリレーションとは何なのかについて調べ、リレーショナルモデルに基づいたデータベースを利用することのメリットは何なのかを考えてみた。

これから書く内容はブログ最後にまとめた参考文献の、リレーショナルモデルに関連する部分を読んだ私の理解をまとめたもの。 タイトルだけあげると以下の4つ。

  • "基礎情報数学" 1
  • "リレーショナルデータベース入門" 2
  • "データベース実践入門" 3
  • "C.J.Dateのデータベース実践講義" 4

数学・情報数学の超基礎の復習に"基礎情報数学", 残りの殆どを"リレーショナル・データベース入門"を参考にしている。 注釈記法では同じ番号を繰り返し使えないようなので、これ以降は[1], [2]などの[n]と表記する。

(理解が不十分であったり、端折って書いている部分もありますが、できるだけ言い切る(思う・〜みたい等の表現を避ける)ように書いています。間違いがあれば指摘してください)

目次

リレーショナル・データベースのリレーションとは何か

単刀直入に結論を書こう。

 D_1, D_2, ... , D_nを有限個のドメインとするとき、 D_1, D_2, ... , D_n上のリレーションRとは、直積 D_1 \times D_2 \times ... \times D_nの任意の有限部分集合をいう。[2]

つまり R \subseteq D_1 \times D_2 \times ... \times D_n

ここで、ドメイン(domain)とは何かしらの概念を持った値の集合である。例えば社員番号の集合や名前の集合などであり、これは無限集合でも有限集合でも構わない。また、プログラミング言語における型も整数や文字列といった概念を持ったドメインである。 実際、ドメインは型と同一と考えても問題なく、[4]ではドメインを型という表現に切り替えて説明している。 また、ドメインにはドメインの元が原始的(atomic)、つまり分解不可能(nondecomposable)であることという条件がある。 具体的にはドメインがいくつかのドメインの直積や冪集合によって構成されないということである。 これを満たしているリレーションを第1正規形(the first normal form, 1NF)という。

ただこのリレーションの定義では設計者の設計意図を伝えることが出来ないので、リレーション、属性に名前をつけ、これらを用いて定義し直したものが以下になる。

Rをリレーション名、 A_1, A_2, ... , A_nを属性名、domをドメイン関数とするとき、リレーション R(A_1, A_2, ... , A_n)は直積 dom(A_1) \times dom(A_2) \times ... \times dom(A_n)の有限部分集合である。[2]

つまり R \subseteq dom(A_1) \times dom(A_2) \times ... \times dom(A_n)

ここでドメイン関数(domain function) dom dom: A_i \rightarrow D_i ( i = 1, 2, ... , n)である。

結局、リレーション(relation, 関係)というのは数学用語の関係(relation)、さらに言うとn項関係(n-ary relation)のことである。

リレーションはいわゆるテーブルではない?

リレーションの説明として「リレーションはjoinでテーブル同士を関連づけるという意味ではなくて、リレーションとはいわゆるテーブルそのもの」というのがあるが、「リレーションとはいわゆるテーブル」という説明で理解に苦しんだ僕にとって、こうした説明に対する良い指摘が[4]でされていたので、これをそのまま引用しておく。

よりユーザーフレンドリな用語を使用することによって概念が理解しやすくなるのであれば、大筋においてそうすることに同意する。しかし、目下の状況においては、残念ながらそれらは概念を理解しやすくするどころか、かえって概念を歪め、芯の理解を大きく妨げる原因となっているように思える。真相はこうである。関係はテーブルではないし、タプルは行ではないし、属性は列ではない。砕けた解説では、ここまでこだわらなくても問題がないこともあり、筆者自身も、著書やその他の執筆物の多くでそのようにしてきた。だが、ユーザーフレンドリな用語を容認できるのは、それらが真実を大まかに表すだけで、実際に起きている事の本質を扱えるには至っていないことを、私達全員が理解している場合に限られる。[4]

Coddの論文を見てみる

だいたい気になったものの専門家になりたいわけではないので、ある程度理解しやすいもので例えてくれるのも楽なんだけどな〜と思いつつ、たしかに原文を見たほうが正しい理解ができることもあるので、Codd本人の論文[5]を見てみる。 リレーショナルデータベースやSQLの基礎になっているリレーショナルモデルはこの1970年にエドガー F. コッド(Edgar F. Codd)によって提案されたデータモデルである。 この論文[5]は思っている以上に平易な文章で書かれていてこれなら割とあっさり読めそうと思わせてくれる(読み切ってない)

これにはリレーションについて以下のように説明している。

Given sets  S_1, S_2, ..., S_n (not necessarily distinct), R is a relation on these n sets if it is a set of n-tuples each of which has its first element from  S_1, its second element from  S_2, and so on.

優しい。注釈ではもう少しフォーマルに記述している。

More concisely, R is a subset of the Cartesian product  S_1 \times S_2 \times ... \times S_n.

数学における「関係」特にn項関係(n-ary relation)である説明としては以上で十分な気はするが、もう少しSQLのテーブルに近い説明として、[3][4]では以下のような説明もしている。これがcoddの論文を参照しているのかわからないが、これについては、後述するCodd自身の出したリレーショナルモデルに関する複数の論文で記述にブレがあるという指摘に説明されることなのではないかと思って詳細は調べていない。

関係は見出し(heading)と本体(body)からなる。 見出しは属性(属性名と型名の組み)の集合、本体は見出しに準拠するタプルの集合である。

ここまででリレーションは単に属性集合の直積の部分集合ということがわかったが、それで一体何だったっけ?という気持ちになる。 そこで、データモデルとは何か、リレーショナルモデルの要素についてもまとめてみる。

データモデルとは

データモデルとは実世界の情報をデータ化する上での、実世界記述の記号系である。 より具体的にはデータベースを構築するにあたり、概念モデルを論理モデルに変換(論理モデルを記述)する際に用いる記号系のことである。

また、データモデルはデータ構造、データ演算子など、ユーザが操作する抽象機械(abstract machine)の構成要素を、抽象的、自己完結的、論理的に定義したものである[4]。

データベース構築は概念モデルの構築と論理モデル構築の2段階からなる。

([2], P.6, 図1.4) f:id:tom__bo:20180722144731p:plain

第一段階では実世界のデータ構造と制約をある記号系(記号系Ⅰ)を用いて記述し、概念モデルとする。 この段階で必要な記号系Ⅰは概念把握された実世界のデータ構造と制約を記述するもので、1976年にPeter Chenによって提案された、実体ー関連モデル(entity-relationship model, ERモデル)がある。

([2], P.7, 図1.5) f:id:tom__bo:20180722144745p:plain

第一段階で得られた記号系をDBMSで管理可能な表現に記号系Ⅱを用いて変換する。 論理モデルは、例えばリレーショナルデータベーススキーマであり、これはデータベース管理システムの標準アーキテクチャを定めたANSI/X3/SPARCの用語で言う概念スキーマ(conceptual schema)である。

論理モデルを記述するのに使われている記号系には、リレーショナルデータモデルの他に以下のようなものがある。

リレーショナルモデルがCoddによって提案された当時は、階層型データモデルやネットワークデータモデルといえるデータベース製品が主に開発、利用されていた。これらはポインタや多重リンクといった実装をもとにモデルへと抽象化されたもので、実装から独立して定義されたものではない。

リレーショナルデータモデルとは

前に紹介したデータモデルが、実装に強く依存し、後付けでモデルとして定義されたものであるのと違い、リレーショナルモデルは1970年にCoddによって集合理論に基づいて、実装とは独立して定義されたデータモデルである。

前にデータモデルとは、概念モデルを論理モデルに変換する際に用いる記号系であると書いたが、[2]ではデータモデルは以下の要素からなるとしている。 また、リレーショナルデータモデルの構成要素を整理した。

  • 構造記述
  • 意味記述
    • データベースの一貫性制約の記述
    • キー制約、検査制約と表明(意味的制約)を含めた一貫性制約
  • データ操作言語
    • データを検索したり更新したりするためのデータ操作言語
    • リレーショナル代数、リレーショナル論理による演算

これらの全てを説明するのは難しいので、この内のいくつかを取り上げて書いておく。 詳細については参考文献、特に[2]を読むことをおすすめする。

リレーション

上述

リレーションスキーマインスタンス

リレーションは現実に利用するときは、タプルが挿入・更新・削除されることで時間とともに変化する。 そこで時間とともに変化しないリレーションの枠組みをリレーションスキーマ(relation schema )として規定し、時間とともに変化するタプルの集合をリレーションスキーマインスタンス(instance)として定義する。 つまり、

Rをリレーションスキーマ名、 A_1, A_2, ... , A_nを属性名、domをドメイン関数とするとき、リレーション R(A_1, A_2, ... , A_n)をリレーションスキーマという. このとき、 R \subseteq dom(A_1) \times dom(A_2) \times ... \times dom(A_n)Rインスタンスという[2].

リレーショナルデータベーススキーマ(relational database schema)

インスタンスとしてのリレーショナルデータベースを定める時間的に不変な構造的・意味的記述体系のこと。 具体的には次のような要素から成り立つ

データ操作言語

リレーショナルデータモデルにおいて、データ操作言語はCoddにより提案されたリレーショナル代数とリレーショナル論理がある。 リレーショナルデータ操作言語は、質問(query), 更新(update: SQLでいうinsert, update, delete)からなっており、 リレーショナル代数やリレーショナル論理は質問のためにある。

リレーショナル代数はリレーショナル論理と質問を記述する能力において等価であり、これらはリレーショナル完備(relational complete)と呼ばれる。 これらリレーショナル代数、リレーショナル論理は国際標準リレーショナルデータベース言語SQLの設計基盤を与えている。

[2]では、リレーショナルデータモデルは集合論に基づき定義されていることから、集合論に基づいたリレーショナル代数を中心に据えて解説している。 ここではこのリレーショナル代数についてと周辺の議論について簡単にまとめる。

  • リレーショナル代数

リレーショナル代数は4つの集合演算と4つのリレーショナル代数に特有の演算からなる。

集合演算

演算 対応するSQL
和集合演算 UNION
差集合演算 EXCEPT, NOT IN サブクエリ
共通集合演算 INTERSECT
直積演算 CROSS JOIN

リレーショナル代数特有の演算

演算 対応するSQL
射影演算 カラム指定によるSELECT
選択演算 WHERE句を含めたタプルの選択
結合演算 JOIN
商演算 対応なし

これらの演算を組み合わせ、リレーショナル代数表現(relational algebra expression)として、データに対して問い合わせを行う。

3値理論

リレーションにおいて、キー制約がない属性では値が空(null)を取る場合がある。 そこで、Coddは3値理論(three-valued logic)をリレーショナル代数に導入することでリレーショナル代数演算を拡張した。 具体的にはθ-選択演算, θ-結合演算の定義^が拡張され、演算の対象にnullがある場合はその結果を不定(unknown)とする。([4], p.60~70周辺参照)

3値理論の真理値表とnullを含む述語の値をまとめると以下のようになる。

真(TRUE, T), 偽(FALSE, F), 不定(UNKNOWN, U)

3値理論の真理値表

IS T F U
T T F F
F F T F
U F F T

nullを含む述語の値

A NOT A
T F
F T
U U

or

A B A OR B
T U T
U T T
F U U
U F U
U U U

and

A B A AND B
T U U
U T U
F U F
U F F
U U U

nullに関しては、1969年にリレーショナルモデルを定義してから1979年まで、Coddがnullを導入しなかった(中略) 初期の実装についても、nullがなくてもまったく問題がなかった[4]。
一方で、リレーショナルモデルは2値論理(2VL)に基づいている[4]。

NULLによる弊害

NULLが含まれることによる、実用上最も大きな弊害は問い合わせの結果が正しくない可能性があることだ。 (A != 10)と言う条件に対してNULLはTRUEではないので、10ではない全てのタプルを取ろうとしたときには(A != 10 AND A IS NULL)と書く必用がある。

NULLに関する議論は[3]の7章, NULLとの戦いが詳しいのでこちらを参照のこと。

リレーショナルデータモデルの変遷(進化)

1970~1990にかけてCoddがリレーショナルモデルの定義を多少見直していて、それによってMike Stonebrakerは4つのモデルが考えられると言っているらしい。

4つのモデル[4]

  • 1970年にCACMの論文で定義されたもの
    • CACM 13, No.6 "A Relational Model of Data for Large Shared Data Banks", 1970/6月
  • 1981年にチューリング章を受賞した論文で定義されたもの
    • CACM 25, No.2, "Relational Database: A Practical Foundation for Productivity", 1982/2月
  • Codの12の規則と評価システムによって定義されたもの
    • Coddが"Computerworld"に寄稿した"Is Your DBMS Really Relational?", 1985/10/14. and "Does Your DBMS Run By Rules?", 1985/10/219
  • Coddの著書で定義されたもの
    • "The Relational Model For Database Management Version 2", Addison-Wesley, 1990年

これらは簡単に手に入らなかったので、違いは確認していない。これらの差異の原因であるリレーショナルモデルの進化的な変化については[4]のp186に概要がまとめられている。

リレーショナルモデルとSQLの違い

リレーショナルモデル、リレーショナル代数の演算を直接扱うのは難しい上、データの操作として現実的によくある条件付けや問い合わせに実現できないものがある。 そこで、リレーショナル完備5であり、計算完備(computationally complete , Turing complete)6なインタフェースSQL(Structured Query Language)がデータベースへのインターフェース言語として標準化されている。

リレーショナルモデルにはない処理や性質には以下のものがある。

  • 要素の重複
  • 要素間の順序
  • NULL
  • 集計処理(合計、平均、最大値など)
  • ストアドプロシージャ
  • 推移的閉包(transitive closure, ある人物の子孫の検索など)
  • トランザクション

リレーショナルデータベースの何が嬉しいか

Webアプリケーションをはじめとする情報処理システムのデータベースとしてとしてリレーショナルデータベースが主に利用されるのにはどういった理由があるのだろうか。 現実世界の情報を抽象化しデータモデルとしデータベースを設計する上で、実装に依存せず、集合論や述語論理に裏付けされたリレーショナルモデルに準ずることにどのくらいの価値があるのか。 (当然、実際にアプリケーションのバックエンドを設計する際は全てをRDBで作るのではなく、KVストアやグラフデータベースなどなど適材適所にデータベースを選択することは言うまでもない。)

リレーショナルモデルとSQLの違いでみたように、現在主要なリレーショナルデータベースが完全にリレーショナルモデルに準じていないことは明らかな上に、リレーショナルデータベースを熟知しているわけでもない、さらに他のデータモデルについて全く理解していない僕の現状の考えを挙げておく。 (これについてはより正しい理解が紹介されるか、数年後の自分が「あーあーこんなこと言ってるよ」と思えるようになっていることを期待している。。。)

  • 論理的・物理的データが独立していて、実装に依存したモデルの構築をしなくてよいこと
  • 構造記述、意味記述、データ操作言語に至るまで、集合論に基づいてモデルが定義されていることで、現実世界の情報をどのようにリレーショナルデータベーススキーマに落とし込むべきかが明確であること
  • 一貫性記述や正規化理論(ここではあえて書かなかった)に従って適切にスキーマを設計することで、データの整合性が担保されること
  • モデルの平明性から、ハードウェアのアクセス方法やトランザクション処理などのデータベースに必要不可欠な実装も発展しやすく、SQLのような操作言語の標準化や、内部実装のパフォーマンスの向上がなされてきたこと

まとめ・感想

リレーショナルデータベースのリレーションとは何かとその周辺知識についてまとめた。 [2]のリレーショナルデータベース入門の4章(設計理論, 正規化理論)を除く1~5章の内容の一部だが、実際は14章まであり、リレーショナルデータベースに限らない様々な内容がとても良くまとまっているのおすすめ。 正規化理論についてとトランザクションの整合性についてはそれぞれ別にまとめを書こうと思う。

参考文献

  • [1] 横森 貴, 小林 聡, 基礎情報数学, サイエンス社
    • 情報数学に関する基礎知識の復習に良い
    • 最近この本を別件の目的で読み直していて、2章のn項関係の説明あたりでn項関係の応用として「関係データベースの理論」が出てきたのがリレーショナルモデルについて調べなおそうと思ったきっかけ。
  • [2] 増永 良文, リレーショナルデータベース入門, サイエンス社
    • 日本データベース学会を設立された、大御所データベース研究者の方の本。
    • 僕は教科書だと思って読んでいて、この本以上に日本語でデータベースの理論面の学習に良い本は知らない。(あれば教えてください(英語でも可))
    • 参考文献が充実している。文献ごとに著者のコメントがあって参考になるし、当時の経緯が知れて面白い
  • [3] 奥野 幹也, データベース実践入門, 技術評論社
    • データベース特にMySQLコミュニティの大御所の方が書いた本
    • だいぶ前にこの本を読んで、リレーションとはjoinしてテーブル同士を結合することではなく、表(Table)自体のことであるという程度理解をしていた
    • 読者に優しくするためか表現や内容が手加減されて書かれているので、読みやすいようでかえって本質がわかりづらい部分もある。一方で、実践入門というタイトル通り、SQLの仕様と理論の差異や、SQLを通じてデータベースを操作するときに避けるべきアンチパターンが具体的に書かれている。
    • 参考文献の項目がない
  • [4] C.J.Date著 株式会社クイープ訳, C.J.Dateのデータベース実践講義, O'REILLY
    • 数式を使わないように全部文章で説明されている
    • リレーショナル代数における演算の説明がSQLを使って書かれている。
      • おそらく殆どの人がリレーショナル代数の演算より先にSQLを学ぶと思うので、この説明はわかりやすさを優先した結果なのだろうけど、本来は順序逆じゃない?って感じ。
    • こちらも参考文献に関する著者のコメントがあって良い
  • [5] E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970
    • リレーショナルモデルが提案された論文
  • [6] CODD, E. V. Further normalization of the database relational model. In Database Systems, Courant Computer Science Symposia 6, R. Rustin, Ed., Prentice-Hall, Enghwood Cliffs, N.J., 1971, pp. 65-98.
    • リレーションの正規化
  • [7] E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979
    • 3値理論

  1. 横森 貴, 小林 聡, 基礎情報数学, サイエンス社

  2. 増永 良文, リレーショナルデータベース入門, サイエンス社

  3. 奥野 幹也, データベース実践入門, 技術評論社

  4. C.J.Date著 株式会社クイープ訳, C.J.Dateのデータベース実践講義, O'REILLY

  5. 少なくともリレーショナル代数あるいはリレーショナル論理の質問記述能力を持つとき、リレーショナル完備という

  6. SQL/PSM(Persistent Stored Module, 永続格納モジュール)を使用することで、計算完備なプログラミングパラダイムが提供されている