元组关系演算

数学术语

元组演算是埃德加·科德导入的演算，是关系模型的一部分，发展目的是提供宣告式的数据库查询语言。数据库查询语言QUEL和后来的SQL中的一些灵感是由元组演算而来。SQL和原来的关系模型和演算已有许多不同，后来成为实际上的数据库查询语言标准，几乎所有的关系数据库管理系统中都会用到SQL或是其变体。后来Lacroix和Pirotte提出了接近于一阶逻辑的域演算，并证明了这两种演算和关系代数在表达能力上是等价的。若关系数据库的查询语言可以表达一种以上上述的查询方式，则可称为具有“关系完备性”。

简介

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

定义

关系数据库

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

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

语义和语法限制

域独立查询

由于量词的语义使得它们量化在模式中域上所有元组上，如果假定了另一个模式则对一个特定数据库的一个查询可能返回不同结果。例如考虑两个模式S1= (D1,R,h) 和S2= (D2,R,h)，带有域D1= { 1 },D2= { 1, 2 }，关系名字R1h1

如果我们考虑如下查询表达式

在它在db上的结果要么是在S1下的 { (a: 1) } 要么是在S2下的 { (a: 1), (a: 2) }。如果我们采用域为无限集合，则查询的结果也会是无限的，这是很明显的。要解决这些问题我们将把我们的注意力限制于“域独立”的那些查询，就是说，对一个数据库的查询在它的所有模式下都返回同样的结果。

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

安全查询

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

为了限制查询表达式使得它们只表示域独立的查询，通常介入一个语法概念“安全查询”。要确定一个查询是否为安全的，我们要从查询导出两种类型的信息。首先是变量-列对t.a是否绑定到一个关系或一个常量的列上，其次是两个变量-列对是否直接或间接的相等(指示为t.v==s.w)。

为了推导绑定性，我们介入如下推理规则:

为了推导相等性，我们介入下列推理规则(位于常用的等价性推理规则: 自反性、对称性和传递性之后):

我们接着声称一个查询表达式 { v: H | f(v) } 是安全的，如果

安全查询表达式的限制不限制表达能力，因为所有能被表达出来的域独立查询都可以用安全查询表达式表达。这可以做如下证明，对于模式S= (D,R,h)，给定在这个查询表示式中常量的集合K，元组变量v和表头H，我们可以为所有的对v.a构造一个安全公式，它带有a在H中并声称其值在活跃域中。例如，假定K={1,2}、Rhv.b 对应的安全公式为:

接着通过在这个表达式中用到地方对所有变量v和它的类型中的列名a增加这个公式，可以用这个公式来把任何不安全的查询表达式重写为等价的安全查询表达式。这有效的使得所有变量都取值于活跃域之上，如果表达的查询是域独立的，象已经解说的那样不改变语义。