ぱと隊長日誌

ブログ運用もエンジニアとしての生き方も模索中

リレーショナルモデルのタプルに順序はあるのか否か

概要

リレーショナルモデル (relational model) は1970年にコッド (E.F.Codd) によって考案されました。この時点ではリレーションのカラム(列)の順序には意味があるとしていましたが、現在ではリレーションのタプルの要素に順序はないとされています。

「カラム」と「タプルの要素」が同じものを指しているとすれば、これらの定義で順序の有無が変わったように見えます。ですが、この経緯や議論についてまとめた資料は見当たりませんでした。

そこで、この経緯や理由について調査を行い、現時点で判明したことをまとめます。そして、本エントリを今後の調査の礎とします。

前提

リレーションやタプルなどの用語の定義は割愛します。用語の定義について参考となる本を挙げます。

読みやすさでは「リレーショナルデータベース入門 [第3版]」がお勧めです。ただ、厳密さには多少欠けるかもしれません。

厳密さを求めるのであれば、「データベース実践講義」がお勧めです。論文を読んでいるような気持ちになるテキストです。

表記

本エントリもしくは他の資料で用いられることのある表記をまとめます。

  • リレーション(関係, relation)
  • カラム(列, column)
  • タプル(組, tuple)
  • 集合 (set)
  • テーブル(表, table)

参考文献

[1] E.F.Codd, A Relational Model of Data for Large Shared Data Banks, Communications of the ACM, Vol.13, No.6, pp.377-387, 1970

[2] C.J.Date, Codd's First Relational Papers: A Critical Analysis, 2015

[3] C.J.Date, データベース実践講義 ―エンジニアのためのリレーショナル理論 (THEORY/IN/PRACTICE), O'REILLY

コッドによるタプルの定義

コッドは [1] で次のように述べています。なお、ここでの R はリレーションのことです。

1. Each row represents an n-tuple of R.
(中略)
4. The ordering of columns is significant - it corresponds to the ordering S1,S2,...,Sn of the domains on which R is defined (see, however, remarks below on domain-ordered and domain-unordered relations).

この 4. の記述に対し、デイトは [2] で次のように指摘をしています。

■ "[See the] remarks below on domain-ordered and domain-unordered relations."
But the paper has already stated explicitly that relations are domain-ordered by definition. As far as that paper is concerned, therefore, domain-unordered relation is, or should be, simply a contradiction in terms.

ここでの "column" もしくは "domain" とはテーブルのカラムに紐づくものであり、カラムの順序ということはタプルの要素の順序とみなすことが可能です。このことから、コッドのオリジナルの定義ではタプルの要素の順序に意味を持たせているといえます。[1] にその例が挙げられています。

The meaning of component(x,y,z) is that part x is an immediate component (or subassembly) of part y, and z units of part x are needed to assemble one unit of part y. It is a relation which plays a critical role in the parts explosion problem.

コッドがリレーショナルモデルにおいてタプルの要素の順序に意味を持たせたのは、数学におけるn-項関係を参考にしたからです。Wikipedia二項関係の説明から例を引用します。

4つの「もの」{ボール, 車, 人形, 拳銃} と4人の人間 {ジョン, メアリ, イアン, ヴィーナス} を想定する。ジョンはボールを所有し、メアリは人形を所有し、ヴィーナスは車を所有するが、誰も拳銃は所有しておらず、またイアンは何も所有していないものとする。このとき、「~は~に所有される」という二項関係
R = ({ボール, 車, 人形, 拳銃}, {ジョン, メアリ, イアン, ヴィーナス}, {(ボール, ジョン), (人形, メアリ), (車, ヴィーナス)})
によって与えられる。

二項関係 - Wikipedia

[1] に出てくる component と Wikipedia二項関係の説明の例を見比べることで類似性が分かります。

変更されたタプルの定義

コッドが提唱したタプルの定義はその後に変更されました。これを裏付ける資料を見つけられませんでしたが、変更されたこととその理由が Wikipedia で説明されていました。

関係モデルを考案したエドガー・F・コッドは、当初はこの数学上の定義を使って組を定義していた。後に組の概念は変更されたが、組という概念名は変わっていない。この優れた組の概念により、直ちに重要な帰結として、関係モデルの関係代数の直積演算において交換法則が成立した。

関係モデル - Wikipedia

デイトはタプルをコンポーネント(属性と値の組み)の集合であるとしています([3] P44 のタプルの定義を参照のこと)。ここでの「集合」とは数学における集合 (set) と同じ意味です。

新しい定義ではタプルが数学の集合をベースにしていることから、タプルの要素の順序もなくなりました。数学上は {a,b,c} と {c,a,b} が同じ集合であるとの同じ理屈です。

タプルの定義を変更した理由

※注:本節は正確性に自信がありません。コメントもしくは Twitter (@pato_taityo) で情報提供いただけますと幸いです。

タプルをコンポーネントの集合であると定義し直した理由について明確に説明した資料を見つけられていませんが、先ほどの Wikipedia の説明にある『この優れた組の概念により、直ちに重要な帰結として、関係モデルの関係代数の直積演算において交換法則が成立した。』との記述より、これを実現させたかったことも理由の一つではないかと推測しています。

『関係代数の直積演算において交換法則が成立した』に着目して考えます。
ここで A={x,y}, B={1,2} とします。
A×B={(x,1), (x,2), (y,1), (y,2)}
B×A={(1,x), (2,x), (1,y), (2,y)}
順序対において (x,1) と (1,x) は異なります。

ですが、これをリレーショナルモデルで考えると困ったことが起きます。部品={x,y}, 個数={1,2} としたとき、 (x,1) と (1,x) はどちらも「部品xが1個」であることを表現したいはずですが、順序対としては異なるものとみなされてしまいます。もしこれを集合として {x,1} と {1,x} のように扱えれば、同じものとして扱うことができます。

これをテーブルにて表現します。

部品 個数
x 1
x 2
y 1
y 2

表A

個数 部品
1 x
2 x
1 y
2 y

表B

タプルを集合とみなすことで、表A・表B共に同じとみなすことができます。

まとめ

現時点ではタプルの概念が変更されたことを明確に裏付ける資料を見つけるに至っていません。また、私のリレーショナルモデルおよび数学の知識が足りず、あやふやな説明となっている箇所があることは否めません。これらを課題とし、今後も調査を続けていきます。