跳至內容

元組關係演算

維基百科，自由的百科全書

元組演算是埃德加·科德導入的演算，是關係模型的一部分，發展目的是提供宣告式的數據庫查詢語言。數據庫查詢語言QUEL（英語：QUEL）和後來的SQL中的一些靈感是由元組演算而來。SQL和原來的關係模型和演算已有許多不同，後來成為實際上的數據庫查詢語言標準，幾乎所有的關係數據庫管理系統中都會用到SQL或是其變體。後來Lacroix和Pirotte提出了接近於一階邏輯的域演算，並證明了這兩種演算和關係代數在表達能力上是等價的。若關係數據庫的查詢語言可以表達一種以上上述的查詢方式，則可稱為具有「關係完備性」。

域關係演算與元組關係演算最大的區別是域關係演算中的變量表示數據庫的表屬性，而元組關係演算的變量表示元組，即數據庫的一行。[1]

演算的定義

關係數據庫

由於元組關係演算是關係數據庫的查詢語言，因此要定義關係數據庫。

這些關係概念雖是數學定義，但定義可以大致對應到傳統的數據庫概念。表是一種關係的可視表示法；元組類似於「行」的概念。

假定有一個包含各列名稱（"name", "author", "address" 等）的集合 C，再定義「表頭」為 C 的有限子集。定義「關係數據庫模式」為三元組 S = (D, R, h)，這裏的 D 是原子值的域（更詳細的域和原子值的概念參見關係模型），R 是關係名稱的有限集合，而

h : R → 2C

是一個將關係名稱集合R的元素對應到表頭的函數（此處是對完全關係模型的簡化，完全關係模型中可能不止一個域，並且表頭不單只是列名的集合，還要將列名映射一個域。） 給定一個域 D，可以定義在 D 上的「元組」為偏函數

t : C → D

它映射某些列名到 D 中的原子值。例如(name : "Harry", age : 25)。

在 D 上的所有元組的集合指示為 TD。元組 t 定義於的 C 的子集叫做 t 的「域」(不要混淆於模式中的域)並指示為 dom(t)。

給定模式 S = (D, R, h) 最後我們定義「關係數據庫」為函數

db : R → 2TD

它映射 R 中的關係名字到 TD 的有限子集，使得對於所有 R 中的關係名字和db(r) 中的元組 t 有着

dom(t) = h(r).

後者要求簡單的聲稱在關係中所有元組都應該包含同樣的列名，也就是在模式中所定義的那些。

原子

對於公式構造，我們假定元組變量的一個無限集合 V。定義公式要給定一個數據庫模式 S = (D, R, h) 和一個偏函數 type : V -> 2C，它定義指派表頭到某些元組變量的「類型指派」。接着用如下規則定義「原子公式集合」 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 和一個元組變量綁定 val : V -> TD，它映射元組變量到在 S 中的域上的元組:

  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) 中

公式

同一階邏輯一樣，原子可用通過邏輯算子∧(與)、∨(或)和¬(非)組合成公式，而且我們可以使用存在量詞(∃) 和全稱量詞(∀)來綁定變量。通過如下規則歸納定義「公式集合」 F[S,type]:

  1. 所有在 A[S,type] 中原子也在 F[S,type] 中
  2. 如果 f1 和 f2 在 F[S,type] 中，則公式「f1 ∧ f2」也在 F[S,type] 中
  3. 如果 f1 和 f2 在 F[S,type] 中，則公式「f1 ∨ f2」也在 F[S,type] 中
  4. 如果 f 在 F[S,type] 中，則公式「¬ f」也在 F[S,type] 中
  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,type[v->H]] 中的一個公式，則公式「∀ v : H ( f )」也在 F[S,type] 中

公式的例子:

  • t.name = "C. J. Date" ∨ t.name = "H. Darwen"
  • Book(t) ∨ Magazine(t)
  • ∀ t : {author, title, subject} ( ¬ ( Book(t) ∧ t.author = "C. J. Date" ∧ ¬ ( t.subject = "relational model")))

注意最後的公式聲稱 C. J. Date 所寫的所有書籍都有關係模型的主題。如果不導致歧義，我們通常省略圓括號。

我們將假定在量詞量化於在模式中的域上所有元組的全集之上。給定在 S 上的數據庫 db 和元組變量綁定 val : V -> TD，給出如下公式的形式語義:

  1. 「f1 ∧ f2」為真，若且唯若「f1」為真並且「f2」為真，
  2. 「f1 ∨ f2」為真，若且唯若「f1」為真或者「f2」為真，或者二者都為真，
  3. 「¬ f」為真，若且唯若「f」不為真，
  4. 「∃ v : H ( f )」為真，若且唯若存在一個 D 上的元組 t 使得 dom(t) = H 並且公式「f」對於 val[v->t] 為真，
  5. 「∀ v : H ( f )」為真，若且唯若對於所有 D 上的元組 t 使得 dom(t) = H 並且公式「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 的這種查詢的結果是在 D 上帶有 dom(t) = H 的使得 f 對於 db 為真並且 val = { (v, t) } 的所有元組 t的集合。

查詢表達式的例子:

  • { t : {name} | ∃ s : {name, wage} ( Employee(s) ∧ s.wage = 50.000 ∧ t.name = s.name ) }
  • { t : {supplier, article} | ∃ s : {s#, sname} ( Supplier(s) ∧ s.sname = t.supplier ∧ ∃ p : {p#, pname} ( Product(p) ∧ p.pname = t.article ∧ ∃ a : {s#, p#} ( Supplies(a) ∧ s.s# = a.s# ∧ a.p# = p.p# ) }

演算的語義和語法限制

域獨立查詢

由於量詞的語義使得它們量化在模式中域上所有元組上，如果假定了另一個模式則對一個特定數據庫的一個查詢可能返回不同結果。例如考慮兩個模式 S1 = ( D1, R, h ) 和 S2 = ( D2, R, h )，帶有域 D1 = { 1 }, D2 = { 1, 2 }，關係名字 R = { "r1" } 和表頭 h = { ("r1", {"a"}) }。兩個模式有一個公共實例:

db = { ( "r1", { ("a", 1) } ) }

如果我們考慮如下查詢表達式

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

在它在 db 上的結果要麼是在 S1 下的 { (a : 1) } 要麼是在 S2 下的 { (a : 1), (a : 2) }。如果我們採用域為無限集合，則查詢的結果也會是無限的，這是很明顯的。要解決這些問題我們將把我們的注意力限制於「域獨立」的那些查詢，就是說，對一個數據庫的查詢在它的所有模式下都返回同樣的結果。

這些查詢的一個有價值的性質是如果我們假定元組變量取值於所謂的這個數據庫「活躍域」上的元組，它是在數據庫或在查詢表達式中的至少一個元組中出現的域的子集，則查詢表達式的語言不變。事實上，在很多元組演算的定義中，量詞語義就是這麼定義的，這使得定義的所有查詢都是域獨立的。

安全查詢

一個查詢是安全的，如果它只有有限的解，並且解集依賴於數據庫里的數據，而不是數據的定義域（數據類型）。安全的查詢才能用關係代數表達。

為了限制查詢表達式使得它們只表示域獨立的查詢，通常介入一個語法概念「安全查詢」。要確定一個查詢是否為安全的，我們要從查詢導出兩種類型的信息。首先是變量-列對 t.a 是否綁定到一個關係或一個常量的列上，其次是兩個變量-列對是否直接或間接的相等(指示為 t.v == s.w)。

為了推導綁定性，我們介入如下推理規則:

  1. 在「v.a = w.b」中沒有變量-列對被綁定
  2. 在「v.a = k」中變量-列對 v.a 被綁定
  3. 在「r(v)」中所有的對 v.a 被綁定於 type(v) 中的 a，
  4. 在「f1 ∧ f2」 中所有的點對都被綁定於要麼 f1 中要麼 f2 中，
  5. 在「f1 ∨ f2」中所有的點對都被綁定於 f1 和 f2 二者中，
  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. 在「f1 ∧ f2」中 v.a == w.b 成立，如果它要麼在 f1 中要麼在 f2 中成立，
  5. 在公式「f1 ∨ f2」中 v.a == w.b 成立，如果它在 f1 和在 f2 二者中都成立，
  6. 「¬ f」沒有點對相等，
  7. 在「∃ v : H ( f )」中 w.a == x.b 成立，如果它在 f 中成立並且 w<>v 並且 x<>v，
  8. 在「∀ v : H ( f )」中 w.a == x.b 成立，如果它在 f 中成立並且 w<>v 並且 x<>v。

我們接着聲稱一個查詢表達式 { v : H | f(v) } 是安全的，如果

  • 對於所有 H 中的列名 a，我們可以得出 v.a 等於一個 f 中的綁定對，
  • 對於形如「∀ w : G ( g )」的所有 f 的子表達式，我們可以得出對於所有 G 中的列名 a 我們可以得出 w.a 等於一個 g 中的綁定對，
  • 對於形如「∃ w : G ( g )」的所有 f 的子表達式，我們可以得出對於所有 G 中的列名 a 我們可以得出 w.a 等於一個 g 中綁定對。

安全查詢表達式的限制不限制表達能力，因為所有能被表達出來的域獨立查詢都可以用安全查詢表達式表達。這可以做如下證明，對於模式 S = (D, R, h)，給定在這個查詢表示式中常量的集合 K，元組變量 v 和表頭 H，我們可以為所有的對 v.a 構造一個安全公式，它帶有 a 在 H 中並聲稱其值在活躍域中。例如，假定 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 增加這個公式，可以用這個公式來把任何不安全的查詢表達式重寫為等價的安全查詢表達式。這有效的使得所有變量都取值於活躍域之上，如果表達的查詢是域獨立的，象已經解說的那樣不改變語義。

相關條目

參考資料

  1. ^ Carlo Zaniolo. Advanced Database Systems. Morgan Kaufmann Publishers. 1997: 168. ISBN 1-55860-443-X. 
取自 "https://zh.wikipedia.org/w/index.php?title=元组关系演算&oldid=74786880"