1.3. リレーショナルデータモデルの操作

1.3.1. リレーショナル代数

リレーショナル代数は1972年に E.F.Codd 氏によって提示されました。これはリレーションにおける演算の集 まりからなります。

• 選択 (σ): リレーションから条件を満たすタプル を抜き出します。リレーション Rは属性Aを含むテー ブルとしましょう。σ_A=a(R) = {t ∈ R ∣ t(A) = a}のように表すことができます。 tはRのタプルで、 t(A)はタプルtの属性の Aの値を意味します。

• 射影 (π): リレーションから属性(列)を 特定します。Rは属性 Xを含むリレーションとしましょう。 π_X(R) = {t(X) ∣ t ∈ R}のように定義することが できます。ここで、 t(X) はタプル tの属性Xの値を意味し ます。

• 直積 (×): 2つのリレーションを集合とみたてて直積をとりま す。Rは要素数 k₁のテーブル、 Sは要素数 k₂のテーブルとします。 R × S は要 素数 k₁ + k₂からなる集合で、そ の最初のk₁個の属性は Rの要素であり、かつ残りの k₂個の属性は Sの要素であるようなもののすべてからなり ます。

• 和集合 (∪): 2つのテーブルの集合論的な和を構成します。 RとSというテーブ ルがある(両方とも同じ要素数)とき、和 R ∪ Sとは、Rに 現れるタプルとSに現れるタプルからなる集 合です。両方に現れるタプルも含みます。

• 共通集合 (∩): 2つのテーブルの集合論的な共通集合を構成しま す。R と Sという テーブルがあるものとします。R ∩ S は R と S の両方に含まれるタプルの集合です。 R と S は要素数 が同じであることが必要です。

• 差集合 (− もしくは ∖): 2つのテーブルの差集合からな ります。R と S は同じ要素数をもつ2つのテーブルであるとします。 R - S は R に含まれるが S に含まれないタプルの集合です。

• 結合 (∏): 共通の属性で2つのテーブルを結合することです。テー ブル R は属性 A,B ,C をもち、テーブル S は属性 C,D ,E をもつものとします。属性 C は両方のリレーションに共通の属性です。 R ∏ S = π_{R.A,R.B,R.C,S.D,S.E} (σ_R.C=S.C(R × S)). これで 何が起こるでしょう?まず最初に直積 R × Sを演算します。それから、共通の 属性Cが同一であるようなタプルを選択しま す。(σ_{R.C = S.C})ここで同じ属性 Cを2つもつ1つのテーブルができあがります。 そして、これに重複した列を取り除く修正を行います。

  Example 1-2. 内部結合

  結合に必要なステップを評価することでできあがるテーブルを見て みましょう。以下の2つのテーブルがあります。

  R:                 S:
   A | B | C          C | D | E
  ---+---+---        ---+---+---
   1 | 2 | 3          3 | a | b
   4 | 5 | 6          6 | c | d
   7 | 8 | 9
  	 

  まず、直積 R × S の演算を行うと以下の結果が得られます。

  R x S:
   A | B | R.C | S.C | D | E
  ---+---+-----+-----+---+---
   1 | 2 |  3  |  3  | a | b
   1 | 2 |  3  |  6  | c | d
   4 | 5 |  6  |  3  | a | b
   4 | 5 |  6  |  6  | c | d
   7 | 8 |  9  |  3  | a | b
   7 | 8 |  9  |  6  | c | d
  	

  次に、射影 σ_R.C=S.C(R × S) を行うと以下のような結果が得られます。

   A | B | R.C | S.C | D | E
  ---+---+-----+-----+---+---
   1 | 2 |  3  |  3  | a | b
   4 | 5 |  6  |  6  | c | d
  	

  重複した列 S.C を削除するには、以下の操作でそれを射影します。 π_{R.A,R.B,R.C,S.D,S.E} (σ_R.C=S.C(R × S))。これによっ て以下の結果が得られます。

   A | B | C | D | E
  ---+---+---+---+---
   1 | 2 | 3 | a | b
   4 | 5 | 6 | c | d
  	

• 商 (÷): テーブルR は属性 A, B, C, D をもつもの、テーブルS は属性 C と Dを持つものとします。商を定義すると以下のようになります。

  R ÷ S = {t ∣ ∀ ts ∈ S ∃ tr ∈ R,tr(A,B)=t∧tr(C,D)=ts}
  	

  t_r(x,y) は、テーブル R のタプルから要素x と yだけを取り出したものを表しています。タ プルt はリレーション Rの要素A と Bからのみ生成されることに注意してくださ い。

  以下のテーブルがあるものとします。

  R:                    S:
   A | B | C | D         C | D
  ---+---+---+---       ---+---
   a | b | c | d         c | d
   a | b | e | f         e | f
   b | c | e | f
   e | d | c | d
   e | d | e | f
   a | b | d | e
  	

  R ÷ S により以下の結果が得られます。

   A | B
  ---+---
   a | b
   e | d
  	

リレーショナル代数の定義と詳細な解説は [Ullman, 1988] もしくは [Date, 1994] を参照してください。

πSUPPLIER.SNAME(σPART.PNAME='Screw'(SUPPLIER ∏ SELLS ∏ PART))
      

 SNAME
-------
 Smith
 Adams
      

1.3.2. リレーショナル論理

リレーショナル論理は一階述語論理に基づくも のです。リレーショナル論理には2つの種類があります。

• ドメインリレーショナル論理 (DRC) 変数がタプルのコンポーネント(属性)を表 す

• タプルリレーショナル論理 (TRC) 変数がタプルを表す

たいていのリレーショナル言語の基礎をなしているものでもあるので、 ここではタプルリレーショナル論理についてのみ議論してみようと思い ます。DRC (と TRC について も)詳細な議論はDate, 1994 もしくは Ullman, 1988 をご覧下さい。

1.3.3. タプルリレーショナル論理

TRC で使われる問い合わせは、以下の形式です。

x(A) ∣ F(x)
     

例:リレーショナル代数を使った問い合わせを TRC を使って答えを求めるには以下のような論理式 で問い合わせを行います。

{x(SNAME) ∣ x ∈ SUPPLIER ∧
    ∃ y ∈ SELLS ∃ z ∈ PART (y(SNO)=x(SNO) ∧
    z(PNO)=y(PNO) ∧
    z(PNAME)='Screw')}
     

この質問をSUPPLIER と PART データベース の テーブルに対して再び評価すると、リレーショナル代数を使った問い合わせ と同じ結果が得られます。

1.3.4. リレーショナル代数 vs. リレーショナル論理

リレーショナル代数とリレーショナル論理は同じ表現力 を持っています。すなわち、リレーショナル代数を使って 表すことができる問い合わせはすべてレーショナル論理で表すことが でき、またその逆も可能なのです。これは、1972 年に E. F. Codd によっ て最初に証明されました。この証明は、リレーショナル論理の任意の式 を、それと意味論的に等価なリレーショナル代数の式に変換するアルゴリ ズム("Codd's reduction algorithm")に基づいています。これに関する より詳細な議論に関しては、Date, 1994 や Ullman, 1988 をご 覧ください。

時に、リレーショナル論理に基づく言語がリレーショナル代数に基づく 言語よりも「より高水準である」とか「より宣言的である」と言われま す。これはリレーショナル代数では演算の順番を(部分的に)指定してし まうことになるのに対して、リレーショナル論理では効率的な評価順の 決定をコンパイラやインタプリタにまかせられるからです。