跳转到内容

元组关系演算

维基百科，自由的百科全书

元组演算是埃德加·科德导入的演算，是关系模型的一部分，发展目的是提供宣告式的数据库查询语言。数据库查询语言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”