反饋

元組關係演算

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

中文名: 元組關係演算
外文名: Tuple Relational Calculus
差: R-S＝{t│R(t)∧┐S（t）}

並: R∪S={t│R(t)∨S(t)}
表達式: {t│Q（t）}
公式形式: 三種
簡稱: 元組表達式

元組關係演算簡介

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

元組關係演算定義

元組關係演算關係數據庫

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

關係數據庫：其基本元件是域或數據類型。
屬性：域和值的有序對。
元組：屬性的有序多重集。
關係變量是域和名字的有序對的集合，是關係的表頭。
關係是元組的集合。

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

元組關係演算語義和語法限制

元組關係演算域獨立查詢

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

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

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

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

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

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

元組關係演算安全查詢

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

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

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

在“v.a=w.b”中沒有變量-列對被綁定
在“v.a=k”中變量-列對v.a被綁定
在“r(v)”中所有的對v.a被綁定於type(v) 中的a，
在“f₁∧f₂” 中所有的點對都被綁定於要麼f₁中要麼f₂中，
在“f₁∨f₂”中所有的點對都被綁定於f₁和f₂二者中，
在“¬f”中沒有點對被綁定，
在“∃v:H(f)”中對w.a被綁定，如果它被綁定在f中並且w<>v，
在“∀v:H(f)”中對w.a被綁定，如果它在f中被綁定並且w<>v。

為了推導相等性，我們介入下列推理規則(位於常用的等價性推理規則: 自反性、對稱性和傳遞性之後):

在“v.a=w.b”中v.a==w.b成立，
在“v.a=k”中沒有點對相等，
在“r(v)”中沒有點對相等，
在“f₁∧f₂”中v.a==w.b成立，如果它要麼在f₁中要麼在f₂中成立，
在公式“f₁∨f₂”中v.a==w.b成立，如果它在f₁和在f₂二者中都成立，
“¬f”沒有點對相等，
在“∃v:H(f)”中w.a==x.b成立，如果它在f中成立並且w<>v並且x<>v，
在“∀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 對應的安全公式為: