タプルリレーショナル計算

タプル計算は、リレーショナル モデルの一部としてEdgar F. Coddによって作成および導入された計算であり、このデータ モデルでのデータ操作用の宣言型データベース クエリ言語を提供することを目的としています。これは、データベース クエリ言語QUELおよびSQLのインスピレーションとなりました。後者は、元のリレーショナル モデルと計算にはあまり忠実ではありませんが、現在では事実上の標準データベース クエリ言語となっています。SQL の方言は、ほぼすべてのリレーショナル データベース管理システムで使用されています。Michel Lacroix と Alain Pirotte は、より一階述語論理に近いドメイン計算を提案し、Codd とともに、これら 2 つの計算 (およびリレーショナル代数) は表現力において同等であることを示しました。その後、リレーショナル モデルのクエリ言語は、少なくともこれらのクエリすべてを表現できる場合、 リレーショナル完全であると呼ばれるようになりました。

微積分はリレーショナル データベースのクエリ言語なので、まずリレーショナル データベースを定義する必要があります。リレーショナル データベースの基本的な構成要素は、ドメイン(データ型に似ていますが、同じではありません) です。タプルは、ドメインと値の順序付けられたペアである属性の有限シーケンスです。リレーションは、(互換性のある) タプルのセットです。これらのリレーショナル概念は数学的に定義されていますが、それらの定義は従来のデータベース概念に緩くマッピングされています。テーブルは、リレーションの一般的な視覚的表現であり、タプルは行の概念に似ています。

まず、列名の集合Cが存在すると仮定します。列名の例としては、「名前」、「著者」、「住所」などがあります。ヘッダーはCの有限のサブセットとして定義されます。リレーショナル データベース スキーマは、タプル S = ( D、R、h )として定義されます。ここで、 Dはアトミック値のドメイン (ドメインとアトミック値の概念の詳細についてはリレーショナル モデルを参照)、Rはリレーション名の有限の集合、

h  : R → ^2C

R内の各リレーション名にヘッダーを関連付ける関数。(これは、複数のドメインがあり、ヘッダーが列名のセットであるだけでなく、これらの列名をドメインにマップする完全なリレーショナル モデルからの簡略化であることに注意してください。) ドメインDが与えられた場合、 D上のタプルを、いくつかの列名をD内のアトミック値にマップする部分関数として定義します。例は、(name : "Harry", age : 25) です。

t  : C ⇸ D

D上のすべてのタプルの集合は、T _Dと表記されます。タプルtが定義されているCのサブセットは、 tのドメイン(スキーマ内のドメインと混同しないでください)と呼ばれ、 dom ( t ) と表記されます。

最後に、スキーマS = ( D , R , h )を関数として 与えたリレーショナルデータベースを定義する。

db  : R → 2 ^{T _D}

これはR内の関係名をT _Dの有限部分集合に写像し、 R内のあらゆる関係名rとdb ( r )内のタプルtに対して次が成り立つ。

dom ( t ) = h ( r ) です。

後者の要件は、リレーション内のすべてのタプルに同じ列名、つまりスキーマで定義されている列名が含まれている必要があることを単に示しています。

式の構築には、タプル変数の無限セットV を前提とします。式は、データベース スキーマS = ( D、R、h ) と、 型の割り当て時に呼び出され、いくつかのタプル変数にヘッダーを割り当てる部分関数type  : V ⇸ 2 ^Cが与えられた場合に定義されます。次に、次の規則を使用して、 原子式のセットA [ S、type ]を定義します。

1. vとw がVに含まれ、a がtype ( v )に含まれ、 b がtype ( w )に含まれる場合、式v . a = w . b はA [ S、type ]に含まれる。
2. vがV、aがtype ( v ) 、k がDの値を表す場合、式v . a = k はA [ S、type ]にあり、
3. v がVに属し、r がRに属し、type ( v ) = h ( r )である場合、式r ( v ) はA [ S、type ]に属します。

原子の例は次のとおりです。

• ( t .age = s .age) — t には age 属性があり、s には同じ値の age 属性があります。
• ( t .name = "Codd") — タプルtには name 属性があり、その値は "Codd" です。
• Book( t ) — タプルtはリレーション Book に存在します。

このようなアトムの形式的な意味論は、 S上のデータベースdbと、タプル変数をS内のドメイン上のタプルにマッピングするタプル変数バインディングval  : V → T _Dが与えられれば定義されます。

1. v . a = w . b は、 val ( v )( a ) = val ( w )( b ) の場合にのみ真となる。
2. v . a = k は、 val ( v )( a ) = k の場合にのみ真となる。
3. r ( v ) は、 val ( v ) がdb ( r )に含まれる場合にのみ真となる。

原子は、一階述語論理でよくあるように、論理演算子 ∧ (and)、∨ (or)、¬ (not) を使用して式に組み合わせることができ、存在量指定子 (∃) と全称量指定子 (∀) を使用して変数を結合できます。次の規則を使用して、式のセット F [ S、type ] を帰納的に定義します。

1. A [ S、タイプ]の原子はすべてF [ S、タイプ]にも存在します。
2. f ₁とf _{2 が}F [ S、型]に含まれる場合、式 f ₁ ∧ f _2もF [ S、型] に含まれる。
3. f ₁とf _{2 が}F [ S、型]に含まれる場合、式 f ₁ ∨ f _2もF [ S、型] に含まれる。
4. f がF [ S、タイプ]に含まれる場合、式 ¬ f もF [ S、タイプ]に含まれる
5. v がVに含まれ、H がヘッダーで、fがF [ S、type _{[ v -> H ]} ]に含まれる式である場合、式 ∃ v  : H ( f ) もF [ S、type ] に含まれます。ここでtype _{[ v -> H ]は、} v をHにマッピングすることを除いてtypeに等しい関数を表します。
6. v がVに含まれ、H がヘッダーで、 fがF [ S、型_{[ v -> H ]} ]の式である場合、式 ∀ v  : H ( f ) もF [ S、型]に含まれる。

数式の例:

• t .name = "CJ 日付" ∨ t .name = "H. ダーウェン"
• 本( t ) ∨ 雑誌( t )
• ∀ t  : {著者、タイトル、件名} ( ¬ ( Book( t ) ∧ t .author = "CJ Date" ∧ ¬ ( t .subject = "リレーショナルモデル")))

最後の式は、CJ Date によって書かれたすべての本の主題がリレーショナル モデルであることを示しています。通常どおり、式の意味に曖昧さが生じない場合は括弧を省略します。

量指定子は、スキーマ内のドメイン上のすべてのタプルのユニバースに対して量指定を行うものと仮定します。これにより、S 上のデータベース db とタプル変数バインディング val : V -> T D が与えられた場合の式に対して、次 の形式的意味論 が導かれます_。

1. f ₁ ∧ f _{2が真となるのは、} f ₁ が真であり、かつ f _{2 が} 真である 場合のみである 。
2. f ₁ ∨ f ₂ が真となるのは、 f ₁ が真であるか、 f _{2 が} 真であるか、あるいは両方が真である場合のみである。
3. ¬ f が真であるのは、 fが真でない ときのみである 。
4. ∃ v  : H ( f ) が真となるのは、dom ( t ) = H となるようなD上の組tが存在し、かつval _{[ v -> t ]}に対して式 f が真である場合のみであり、
5. ∀ v  : H ( f ) は、 dom ( t ) = HとなるD上のすべてのタプルtに対して、式 fがval _{[ v -> t ]} に対して真である場合に限り真です。

最後に、スキーマS = ( D , R , h ) が与えられた場合のクエリ式がどのようになるか定義します。

{ v  : H | f ( v ) }

ここで、vはタプル変数、H はヘッダー、f ( v ) はF [ S、type ]内の式で、 type = { ( v、H ) } であり、v が唯一の自由変数です。S上の特定のデータベースdbに対するこのようなクエリの結果は、dbに対してfが真であり、val = { ( v、t ) }であるような、 dom ( t ) = H を持つD上のすべてのタプルtのセットです。

クエリ式の例は次のとおりです。

• { t  : {name} | ∃ s  : {name, wage} ( 従業員s ∧ s .wage = 50.000 ∧ t .name = s .name ) }
• { t  : {サプライヤー、記事} | ∃ s  : {s#、sname} ( サプライヤー( s ) ∧ s .sname = t .サプライヤー ∧ ∃ p  : {p#、pname} ( 製品( p ) ∧ p .pname = t .記事 ∧ ∃ a  : {s#、p#} ( 供給品( a ) ∧ s .s# = a .s# ∧ a .p# = p .p# ))) }

量指定子のセマンティクスは、スキーマ内のドメイン上のすべてのタプルを量化するものであるため、別のスキーマが想定されている場合、クエリが特定のデータベースに対して異なる結果を返す可能性があります。たとえば、ドメイン D 1 = {1}、D 2 = {1, 2}、リレーション名 R = { "r 1 " }、ヘッダー h = { ("r 1 ", {"a"}) } を持つ 2 つの_スキーマS 1 = ( _D 1 , R , h ₎とS 2 = ( D 2 _, R , h ) を考え_ます。_両方のスキーマには_共通のインスタンスがあります。

db = { ( "r ₁ "、{ ("a", 1) } ) }

次のクエリ式を考えてみましょう

{ t  : {a} | t .a = t .a }

db上の結果は、S ₁では { (a : 1) } 、 S ₂では { (a : 1), (a : 2) } のいずれかになります。ドメインを無限集合とすると、クエリの結果も無限になることも明らかです。これらの問題を解決するために、ドメインに依存しないクエリ、つまり、データベースのすべてのスキーマに対して同じ結果を返すクエリ に注目します。

これらのクエリの興味深い特性は、タプル変数がデータベースのいわゆるアクティブ ドメイン(データベースまたはクエリ式内の少なくとも 1 つのタプルに発生するドメインのサブセット) 上のタプルに及ぶと仮定すると、クエリ式のセマンティクスは変化しないことです。実際、タプル計算の多くの定義では、これが量指定子のセマンティクスの定義方法であり、すべてのクエリが定義によりドメインに依存しないものになります。

クエリ式がドメインに依存しないクエリのみを表現するように制限するために、通常は安全なクエリという構文概念が導入されます。クエリ式が安全かどうかを判断するために、クエリから 2 種類の情報を抽出します。1 つ目は、変数と列のペアt . aがリレーションまたは定数の列にバインドされているかどうか、2 つ目は、2 つの変数と列のペアが直接または間接的に等しくなっているかどうか ( t . v == s . wと表記) です。

有界性を導出するために、次の推論規則を導入します。

1. 「v . a = w . b」では変数と列のペアはバインドされません。
2. 「v . a = k」では変数と列のペアv . aがバインドされ、
3. 「r ( v )」では、すべてのv.aのペアはa ( v )型にバインドされ、
4. 「f ₁ ∧ f ₂」では、 f ₁またはf ₂のいずれかでバインドされているすべてのペアがバインドされます。
5. 「f ₁ ∨ f _{2 」では、} f ₁とf ₂の両方で結合されているすべてのペアが結合されます。
6. 「¬ f」ではペアは結合されていない。
7. 「∃ v  : H ( f ) 」において、 w . aのペアが束縛されているとは、それがfで束縛されており、かつw <> vであるときであり、
8. 「 ∀ v  : H ( f ) 」において、ペアw . aが束縛されるのは、それがfで束縛され、かつw <> vである場合です。

等価性を導くために、次の推論規則を導入します (同値関係の通常の推論規則である反射性、対称性、推移性に加えて)。

1. 「v . a = w . b 」では、 v . a == w . bが成り立ち、
2. 「v . a = k」ではどのペアも等しくない。
3. 「r ( v ) 」ではどのペアも等しくない。
4. 「f ₁ ∧ f _{2 」では、} f ₁またはf ₂のいずれかで成立する場合、v . a == w . bが成立します。
5. 「f ₁ ∨ f _{2 」では、} f ₁とf ₂の両方で成立する場合、v . a == w . bが成立します。
6. 「¬ f」ではどのペアも等しくない。
7. 「∃ v  : H ( f ) 」では、 fおよびw <> vかつx <> vが成り立つ場合、w . a == x . bが成り立ち、
8. 「 ∀ v  : H ( f ) 」では、 fで成立し、w <> vかつx <> vである場合に、 w . a == x . b が成立します。

クエリ式{ v : H | f(v) }が安全であると言えるのは、

• Hのあらゆる列名aに対して、 v . a はfの境界ペアと等しいことが分かる。
• fの「 ∀ w  : G ( g ) 」という形式のすべての部分式について、 Gのすべての列名aについて、 w . a がgの境界ペアと等しいことが分かります。
• fの形式 "∃ w  : G ( g ) "のすべての部分式について、Gのすべての列名aについて、 w . a がgの境界ペアと等しいことが分かります。

安全なクエリ式への制限は、表現力を制限するものではありません。表現できるすべてのドメイン非依存クエリは、安全なクエリ式でも表現できるからです。これは、スキーマS = ( D、R、h )、クエリ式内の定数の特定のセットK 、タプル変数v、およびヘッダーHについて、 H内のaを含むすべてのペアv . aに対して、値がアクティブ ドメイン内にあることを示す安全な式を構築できることを示すことで証明できます。たとえば、K ={1,2}、R ={"r"}、h = { ("r", {"a, "b"}) } と仮定すると、 v .b に対応する安全な式は次のようになります。

v .b = 1 ∨ v .b = 2 ∨ ∃ w ( r(w) ∧ ( v .b = w .a ∨ v .b = w .b ) )

この式は、式で使用されているすべての変数vと列名aの型にこのような式を追加することで、安全でないクエリ式を同等の安全なクエリ式に書き換えるために使用できます。実質的には、すべての変数の範囲をアクティブ ドメインに収めることを意味します。既に説明したように、表現されたクエリがドメインに依存しない場合は、セマンティクスは変更されません。

• DES – タプルリレーショナル計算やその他の形式言語を扱うための教育ツール
• WinRDBI – タプルリレーショナル計算やその他の形式言語を扱うための教育ツール

• リレーショナル代数
• 関係計算
  • ドメインリレーショナル計算(DRC)

• エドガー・F・コッド「大規模共有データバンクのためのリレーショナルデータモデル」Communications of the ACM、13(6):377–387、1970年。