再论元组关系演算与SQL_关系演算 与sql

 1　引言
    20世纪60年代诞生的数据库技术，经过近半个世纪的发展，形成了坚实的理论基础、成熟的商业产品和广泛的应用领域。E.F Codd 提出的关系数据模型为当今主流的数据库管理系统提供了坚实的数学基础。关系数据模型有三种等价的操作语言：关系代数、SQL、关系演算(元组关系演算和域 关系演算)，它们的非过程化程度依次递增，主要应用领域也不同。SQL是关系数据库的标准语言，关系代数和关系演算是它的理论基础。大多商用的DBMS先 把用户提交的SQL查询转化成等价的扩展关系代数表达式，在执行之前需要根据等价规则对其优化[9]。关系演算是以数理逻辑中的谓词演算为中心的，按谓词 变元的不同，分为元组关系演算和域关系演算。在实际应用中，元组关系演算通常用来辅助生成带量词的SQL语句[3][4][6]，域关系演算以著名的 QBE为代表，直观易学，适合于非专业人员使用，目前在ACCESS、PowerBuilder的查询生成器中有类似的应用。
    将用户提出的查询要求转化为可执行的SQL语句，是一个非形式化描述向形式化规范转变的过程，完全借助计算机来实现是非常困难的，一般由专业技术人员根据 经验来完成。SQL语言是非过程化的，与常用的过程化的命令式语言有很大的区别。用户要完成一个查询，只需要用SQL语言提出要求，无须指明怎么做。在实 际应用中，用户往往提出含有“全部”、“至少”等条件的查询，它们不容易采用SQL表达，这时可求助于元组关系演算，大致过程为：①写出查询的元组关系演 算表达式；②根据等价转化规则得到不含全称量词的元组关系演算表达式；③将元组关系演算表达式转化为SQL语句。迄今为止，国内外有很多文献和书籍都讨论 过相关的内容，然而有些理论细节并没有详细解释，在一定程度上妨碍了人们对数据库知识的理解和应用，产生了一些错误[1][2][5]。本文将就这一问题 进行讨论。
2　元组关系演算与SQL
    确定一个元组关系演算表达式，首先要分析需要使用的关系模式，确定相互之间的参照完整性约束。在特殊情况下，一个关系模式还有可能使用多次，则可通过引入 不同的元组变量来区分。其次，将赋值和限定条件加入到元组关系演算表达式中。关于限定条件如何表示这一问题，很多数据库教材和文献中并没有仔细讨论，结果 产生了一些问题。
    在谓词逻辑中，全总个体域包含了所有个体变元的所有个体域，它统一了个体变元的取值范围，但不同论述对象需用不同的特性谓词加以再刻画[8]。对于全称量 词，特性谓词作为蕴涵式的前件加入；对于存在量词，特性谓词作为合取项加入。在元组关系演算表达式中，元组的限定条件即是特性谓词，书写时也必须遵循上述 两条基本规则。在文献[1]、[2]、[5]中，对于全称量词，均将限定条件作为合取项，这样造成元组关系演算表达式的语义不符合查询要求，无法表示正确 的查询结果。我们经常会遇到这样的情况：对于同一个查询，从不同的角度理解，可以写出不同的元组关系演算表达式。假定有两个不同的表达式A和B，且A是正 确的，那么根据谓词逻辑的完备性，如果由A无法通过推理规则得到B，则A与B的语义不同，那么B一定是一个错误的表达式。这种方法通常被用来判断一个元组 关系演算表达式是否正确。
    在上述分析的基础上，对于含“全部”、“至少”等条件的查询，从分析入手，得到元组关系演算表达式，再转化为SQL语句，一般要经历下面三个过程：
    根据查询的语义，以元组变量为主导，写出一个“规范”的元组关系演算表达式。这里所谓的“规范”，是指针对每个元组变量，其后的原子公式均以关系模式、限 定条件和赋值的顺序出现，在最大的限度上保证量词辖域收缩到最小情况。特别需要注意的是限定条件(关系模式也可认为是一种特殊的限定条件)针对全称量词和 存在量词的不同表示方法。
    将元组关系演算表达式中的全称量词∀全部转化为存在量词∃。因为在SQL语言中不存在全称量词，只有与存在量词对应的EXISTS谓词，需要使用下列的等价式将元组关系演算表达式中的全称量词转化为存在量词。
   
    将元组关系演算表达式转化为SQL语句，处理的过程由外向内，依次为：
    (1)将最外层的∃、本层的限定条件和最后的赋值部分转换为SELECT、FROM、WHERE子句。
    (2)内层的∃、本层的限定条件转化为SELECT、FROM、WHERE子句，此子查询作为EXISTS谓词的条件加入到上一层SQL语句的WHERE子句中。
    注意：由于带有EXISTS谓词的子查询只产生逻辑真假值，不返回任何数据，因此内层的SQL语句的目标列表达式通常都使用*。
3　例子
    下面以“供应商供应工程零件”这一数据库模式为例[6]，对由元组关系演算表达式得到SQL语句的过程加以解释。该数据库模式包含四个表：供应商表 S(Sno， Sname， Status， City)，各属性分别表示供应商代码、供应商姓名、供应商状态、供应商所在城市；零件表P(Pno， Pname， Color， Weight)，各属性分别代表零件代码、零件名、颜色、重量；工程项目表J(Jno， Jname， City)，各属性分别代表工程项目代码、项目名、项目所在城市；供应情况表SPJ(Sno， Pno， Jno， QTY)，各属性分别代表供应商代码、零件代码、工程项目代码、供应数量，表示某供应商将某种零件以一定数量供应给某工程项目。要求查询至少使用了供应商 S1所供应的全部零件的工程号Jno。

分析此查询，发现查询结果中的工程信息来源于表J，而供应商S1供应的所有零件，工程使用所有的零件这两种信息都来源于同一个表SPJ，在元组关系演算表达式中需要使用两个元组变量来加以区分，可得到如下的元组关系演算表达式：

    {t|∃u(J(u) ∧ ∀v(SPJ(v) ∧ v[1]='S1' → ∃w(SPJ(w) ∧ w[1]=v[1] ∧ w[2]=v[2] ∧ w[3]=u[1])) ∧ t[1]=u[1])}
    注意在上述的表达式中，蕴涵不能使用合取来替代。此查询的元组关系演算表达式可能出现多种形式，只要是正确的，就一定可以通过谓词逻辑的推理规则进行等价推导，得到上述“规范”的元组关系演算表达式。
    根据全称量词向存在量词的等价转换公式，可以得到：
    {t|∃u(J(u) ∧ ┐∃v(SPJ(v) ∧ v[1]='S1' ∧ ┐∃w(SPJ(w) ∧ w[1]=v[1] ∧ w[2]=v[2] ∧ w[3]=u[1])) ∧ t[1]=u[1])}
    这个元组关系演算表达式的语义为：对所求的工程，不存在这样的零件，供应商S1供应了它，而工程没有使用 。从而在语义上也印证了上面语法推导的正确性。
    根据前面的元组关系演算表达式到SQL语句的转化规则，写出如下SQL语句。
    SELECT Jno
    FROM J
    WHERE NOT EXISTS
        (SELECT *
        FROM SPJ X
         WHERE X.Sno='S1' AND NOT EXISTS
             (SELECT *
             FROM SPJ Y
             WHERE Y.Jno=J.Jno
                 AND Y.Pno=X.Pno
                 AND Y.SnoO=X.Sno))；
    参考文献[7]中的元组演算表达式和SQL语句，发现与本文有两点区别：
    文献[7]中的元组演算表达式和SQL语句使用的关系模式不是一一对应的，而且在SQL语句中使用的关系全部为SPJ。这样如果SPJ中没有任何元组，查询结果为空，而本文中的SQL语句将会从J中选择所有的工程号。
    对比本文的结果，文献[7]中的元组演算表达式缺少了限定条件w[1]=v[1]，相应在SQL语句中缺少了Y.Sno=X.Sno。假设出现这样的情 况：若供应商S1供应的零件供应商S2也供应，工程J2使用了S2供应的所有零件，但是没有使用S1生产的零件，那么执行文献[7]中的SQL语句，结果 将包含工程J2，而这显然是不正确的。
4　结语
    数理逻辑在计算机科学中具有不可动摇的重要地位，E.W.Dijkstra就曾经说过，我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟 了。我想，假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多的错误。数理逻辑是数据库理论研究的基础，同时谓词逻辑是SQL语言的数学基础。计 算机专业人员必须完全掌握谓词逻辑的语法、语义和推理规则，才能写出正确、优美的SQL语句。
参考文献：
[1]丁宝康，“SQL语言中量词和空值的使用技术[J]”，《计算机研究与发展》，1994，31
[2]刘智斌，“关系演算运行机制的分析与研究[J]”，《计算机应用研究.》，2003，10
[3]马林德，“浅谈带量词的SQL语句的使用方法[J]”，《苏州大学学报(工学版)》，2003，23
[4]宗恒，“关系演算和SQL中使用量词和实现蕴涵的教学方法探讨[J]”，《高师理科学刊》， 2005，25
[5]黄德才，数据库原理及其应用教程[M]，北京，科学出版社，2002
[6]萨师煊、王珊，数据库系统概论[M]，北京，高等教育出版社，2000
[7]王珊、朱青，《数据库系统概论》学习指导与习题解答[M]，北京，高等教育出版社，2003
[8]方世昌，离散数学[M]，西安，西安电子科技大学出版社，1996
[9]Ramez Elmasri，Shamkant B. Navathe，数据库系统基础[M]，北京，人民邮电出版社，2002