キマイラ・サイト内の記事では、タプルや集合の直積がしばしば登場するの で、それらの概念をまとめておく。内容は、月刊『JavaWorld』誌に掲載した 記事からの抜粋である。
この記事は、月刊『JavaWorld』誌(IDGジャパン)連載「XMLボキャブラリ の理論と実践」第41回の一部をわずかに変更したものである。
原記事には、レコード(構造体)の説明も含まれているが、それは割愛する。 レコードとは、名前と値の対をいくつか集めたもので、連載記事では、レコー ドを次のような記法で書き表していた。
{ givenName="トン吉", familyName="板東", age=26 }
タプル(tuple)とは、いくつかの値を並べてまとまりをつけたものである (*注1)。例えば、 ("トン吉", "板東", 26) はタプルの例である。レコードのように、それぞれ のデータ項目を名前で識別するのではなくて、出現の順番でデータ項目を区別す る。タプルに現れる値は「成分」と呼ぶことにする(下の表も参照)。成分は、 出現順に「第1成分」、「第2成分」、…などと呼ぶ。
データ構造 | レコード | タプル |
---|---|---|
データ項目 | フィールド | 成分 |
データ項目の識別 | 名前 | 出現の順番 |
表記で使う囲み記号 | 波括弧 | 丸括弧 |
データ項目の順序交換 | 可能 | 不可能 |
値の並びは、「配列」、「リスト」、「ベクトル」、「シーケンス」などと も呼ばれる。こらの用語を区別して使うこともあるが、一般的に合意された使 い分けはない。用語「タプル」は、抽象的/数学的な文脈で使うことが多い。
タプルもレコードと同様に入れ子にできる。次は入れ子のタプルの例である。
(("トン吉", "板東"), 26, ("古今東西トラベリング", "東京都××区△△町1-0-0", "http://www.kokontozai-traveling.jp"))
平坦化もレコードとまったく同様に定義できる。上の例の平坦化は次のとお り。
("トン吉", "板東", 26, "古今東西トラベリング", "東京都××区△△町1-0-0", "http://www.kokontozai-traveling.jp")
なお、特別なタプルとして、長さ0のタプル「()」がひとつだけ存在し、 長さ1のタプル「(値)」は、しばしば成分である値と同一視される。
一般に、なんらかの集合達A1、A2、…、Anがあるとき、 第1成分がA1に属し、第2成分がA2に属し、…、第n成分がAnに属するタ プルの全体をA1×A2×…×Anと書き、 これを「A1、A2、…、Anの直積」と呼ぶ。掛け算の記号を使うのが唐突 のように感じるかもしれないが、{a, b}×{1, 2, 3}が{(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}であることから分かるように、メンバーの個数 は掛け算で計算できること(この場合は、2×3=6)を、「×」使用のとりあ えずの理由としておこう。
実は、もっと掛け算との類似性がある。ただ1つのメンバー(そのメンバーは なんでもいい)からなる集合をIとすると、以下の法則が成立している。ここ で、記号「≒」は、完全に等しくはなくても、自然な1対1の対応があることを 示す(*注2)。
イコールの上にニョロンがのっかった記号(isomorphic)を使いたいのだが、 僕が容易に使える文字/記号のレパートリにはないので、「≒」で代用。
1番目は、a∈A、b∈B、c∈Cに対して、((a, b), c) も (a, (b, c))も平坦化 してしまえば(a, b, c)であることから分かる。2番目は、I={0}とすると(Iの メンバーは何でもよいから0とした)、(0, a)←→(a, 0)←→a という1対1の 対応関係から分かる。3番目は、(a, b)←→(b, a)という対応関係で「≒」が 成立するのである。
さらに、A×A×…×A(n個の直積)をAn と書く。すると、次も成立する。
1番目は、((a1, …, an), (b1, …, bm))という入れ子タプルを (a1, …, an, b1, …, bm)に平坦化する操作で「≒」の対応が与えられる。 2番目は、長さnのタプルがm個並んだ入れ子タプルを平坦化すればわかる。つ まり、「≒」は、((a1, …, an), …m個の並び… (z1, …, zn))←→ (a1, …, an, …平坦な並び… z1, …, zn) で与えられる。3番目は、 (a)←→a という対応から得られる。3番目は、A0 が長さ0のタプルの集合で あることからA0={()}であり、ただ1つのメンバーの集合はIと対応すること から分かる。
ここまで来れば、直積に掛け算の記号「×」を使ったことも十分に納得がい くだろう。なお、単に「積」ではなくて「直積」と呼んでいるのは、集合の共 通部分(インターセクション)を積と呼ぶことがあるからだろう。
レコードの場合は、フィールドの名前の任意性があるので、タプルの集合 (つまり直積)の場合ほどに単純な算術法則が成立しない。RDBの理論的展開 では、レコードよりタプルが好まれる理由の1つは、直積の計算が算数のよう に実行できるからである。