元组关系演算

元组演算是埃德加·科德導入的演算，是关系模型的一部分，發展目的是提供宣告式的数据库查询语言。数据库查询语言QUEL和后来的SQL中的一些靈感是由元组演算而來。SQL和原來的关系模型和演算已有許多不同，後來成為實際上的数据库查询语言標準，几乎所有的关系数据库管理系统中都會用到SQL或是其變體。後來Lacroix和Pirotte提出了接近于一阶逻辑的域演算，并证明了这两种演算和关系代数在表达能力上是等价的。若关系数据库的查询语言可以表达一種以上上述的查询方式，則可称为具有「关系完备性」。

域关系演算与元组关系演算最大的区别是域关系演算中的变量表示数据库的表属性，而元组关系演算的变量表示元组，即数据库的一行。

演算的定义

关系数据库

由於元组关系演算是关系数据库的查询语言，因此要定義关系数据库。

• 关系数据库：其基本元件是域或数据类型。
• 属性：域和值的有序对。
• 元组：属性的有序多重集。
• 关系变量是域和名字的有序对的集合，是关系的表头。
• 关系是元组的集合。

这些关系概念雖是数学定义，但定义可以大致對應到传统的数据库概念。表是一種关系的可视表示法；元组类似于“行”的概念。

假定有一個包含各列名稱（"name", "author", "address" 等）的集合 C，再定义「表头」为 C 的有限子集。定义「关系数据库模式」为三元组 S = (D, R, h)，这里的 D 是原子值的域（更详细的域和原子值的概念参见关系模型），R 是关系名稱的有限集合，而

h : R → 2^C

是一個將关系名稱集合R的元素對應到表头的函数（此處是对完全关系模型的简化，完全关系模型中可能不止一个域，并且表头不單只是列名的集合，还要將列名映射一个域。） 给定一个域 D，可以定义在 D 上的“元组”为偏函数

t : C → D

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

在 D 上的所有元组的集合指示为 T_D。元组 t 定义于的 C 的子集叫做 t 的“域”(不要混淆于模式中的域)并指示为 dom(t)。

给定模式 S = (D, R, h) 最后我们定义“关系数据库”为函数

db : R → 2^T_D

它映射 R 中的关系名字到 T_D 的有限子集，使得对于所有 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 和一个元组变量绑定 val : V -> T_D，它映射元组变量到在 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. 如果 f₁ 和 f₂ 在 F[S,type] 中，则公式“f₁ ∧ f₂”也在 F[S,type] 中
3. 如果 f₁ 和 f₂ 在 F[S,type] 中，则公式“f₁ ∨ f₂”也在 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 -> T_D，给出如下公式的形式语义:

1. “f₁ ∧ f₂”为真，当且仅当“f₁”为真并且“f₂”为真，
2. “f₁ ∨ f₂”为真，当且仅当“f₁”为真或者“f₂”为真，或者二者都为真，
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# ) }

演算的语义和语法限制

域独立查询

由于量词的语义使得它们量化在模式中域上所有元组上，如果假定了另一个模式则对一个特定数据库的一个查询可能返回不同结果。例如考虑两个模式 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) }。如果我们采用域为无限集合，则查询的结果也会是无限的，这是很明显的。要解决这些问题我们将把我们的注意力限制于“域独立”的那些查询，就是说，对一个数据库的查询在它的所有模式下都返回同样的结果。

这些查询的一个有价值的性质是如果我们假定元组变量取值于所谓的这个数据库“活跃域”上的元组，它是在数据库或在查询表达式中的至少一个元组中出现的域的子集，则查询表达式的语言不变。事实上，在很多元组演算的定义中，量词语义就是这么定义的，这使得定义的所有查询都是域独立的。

安全查询

一个查询是安全的，如果它只有有限的解，并且解集依赖于数据库里的数据，而不是数据的定义域（数据类型）。安全的查询才能用关系代数表达。

为了限制查询表达式使得它们只表示域独立的查询，通常介入一个语法概念“安全查询”。要确定一个查询是否为安全的，我们要从查询导出两种类型的信息。首先是变量-列对 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. 在“f₁ ∧ f₂” 中所有的点对都被绑定于要么 f₁ 中要么 f₂ 中，
5. 在“f₁ ∨ f₂”中所有的点对都被绑定于 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₂”中 v.a == w.b 成立，如果它要么在 f₁ 中要么在 f₂ 中成立，
5. 在公式“f₁ ∨ f₂”中 v.a == w.b 成立，如果它在 f₁ 和在 f₂ 二者中都成立，
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 增加这个公式，可以用这个公式来把任何不安全的查询表达式重写为等价的安全查询表达式。这有效的使得所有变量都取值于活跃域之上，如果表达的查询是域独立的，象已经解说的那样不改变语义。

相關條目

• 关系代数_(数据库)
• 关系演算
  • 域关系演算

參考資料

• Edgar F. Codd: A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, 13(6):377–387, 1970.