タプルと直積

檜山正幸 (HIYAMA Masayuki)
Mon Mar 14 2005:start
Mon Mar 14 2005:prefinal

キマイラ・サイト内の記事では、タプルや集合の直積がしばしば登場するの で、それらの概念をまとめておく。内容は、月刊『JavaWorld』誌に掲載した 記事からの抜粋である。

目次

この記事は、月刊『JavaWorld』誌(IDGジャパン)連載「XMLボキャブラリ の理論と実践」第41回の一部をわずかに変更したものである。

原記事には、レコード(構造体)の説明も含まれているが、それは割愛する。 レコードとは、名前と値の対をいくつか集めたもので、連載記事では、レコー ドを次のような記法で書き表していた。

{
  givenName="トン吉", 
  familyName="板東", 
  age=26
}

1. タプル -- 値を並べたデータ構造

タプル(tuple)とは、いくつかの値を並べてまとまりをつけたものである (*注1)。例えば、 ("トン吉", "板東", 26) はタプルの例である。レコードのように、それぞれ のデータ項目を名前で識別するのではなくて、出現の順番でデータ項目を区別す る。タプルに現れる値は「成分」と呼ぶことにする(下の表も参照)。成分は、 出現順に「第1成分」、「第2成分」、…などと呼ぶ。

TABLE: レコードとタプルの比較
データ構造レコード タプル
データ項目 フィールド 成分
データ項目の識別 名前 出現の順番
表記で使う囲み記号 波括弧 丸括弧
データ項目の順序交換 可能 不可能
注1

値の並びは、「配列」、「リスト」、「ベクトル」、「シーケンス」などと も呼ばれる。こらの用語を区別して使うこともあるが、一般的に合意された使 い分けはない。用語「タプル」は、抽象的/数学的な文脈で使うことが多い。

タプルもレコードと同様に入れ子にできる。次は入れ子のタプルの例である。

(("トン吉", "板東"), 26, 
  ("古今東西トラベリング", 
   "東京都××区△△町1-0-0",
   "http://www.kokontozai-traveling.jp"))

平坦化もレコードとまったく同様に定義できる。上の例の平坦化は次のとお り。

("トン吉", "板東", 26, 
  "古今東西トラベリング",
  "東京都××区△△町1-0-0",
  "http://www.kokontozai-traveling.jp")

なお、特別なタプルとして、長さ0のタプル「()」がひとつだけ存在し、 長さ1のタプル「(値)」は、しばしば成分である値と同一視される。

2. タプルと集合の直積

一般に、なんらかの集合達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)

  1. (A×B)×C ≒ A×(B×C) ≒ A×B×C
  2. I×A ≒ A×I ≒ A
  3. A×B ≒ B×A
注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. An×Am ≒ An+m
  2. (An)m ≒ An×m
  3. A1 ≒ A
  4. A0 ≒ I

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つは、直積の計算が算数のよう に実行できるからである。