【数据库系统原理】第8篇：元组关系演算与域关系演算：基于谓词的声明式查询

目录一、关系演算的定位另一种表达同一组能力二、元组关系演算以元组为变量的逻辑表达式三、ALPHA语言元组关系演算的具体化身四、域关系演算以域值为变量的查询逻辑五、QBE域关系演算的用户界面革命六、过程性与声明性的哲学对勘七、结语从逻辑到语言从语言到系统一、关系演算的定位另一种表达同一组能力在前两篇文章中我们花了大量篇幅构建关系代数的运算体系——并、差、笛卡尔积、选择、投影、连接、除。每当我们表达一个查询我们实际上是在编写一个“程序”先从哪个关系取出数据对它施加何种运算再把中间结果送入下一个运算。这种表达方式规定了步骤顺序因此被归类为过程性语言。然而科德在他1971年至1972年的系列论文中提出了另一套截然不同的查询表达体系。这套体系不规定任何执行步骤它只要求用户用一阶谓词逻辑的公式来描述目标数据的特征。系统收到这样的描述后自行决定如何从数据库中获取满足条件的数据。这套体系被称为关系演算。关系代数与关系演算之间的关系是数据库理论中最优美的对偶性之一。科德证明了二者在表达能力上是等价的——任何可以用关系代数表达的查询都等价地存在一个关系演算表达式反之亦然。这一结论被称为关系完备性定理。两个起点截然不同的形式体系最终收敛于同一组可表达的查询集合这绝非巧合——它暗示着这组查询恰好穷尽了“从关系数据库中能够合理提出的所有问题”。关系演算的两种变体分别对应两种变量选择元组关系演算以整个元组为变量变量遍历关系中的所有元组域关系演算以域中的单个值为变量变量遍历某个属性的所有可能取值。二者在表达能力上同样等价差异仅在于表达某些特定类型的查询时的自然程度。二、元组关系演算以元组为变量的逻辑表达式元组关系演算的形式来源于一阶谓词逻辑。一个元组关系演算查询的基本结构为{ t | P(t) }读作所有满足谓词P的元组t的集合。其中t是一个元组变量——它的取值范围是某个关系或关系的笛卡尔积中的元组。P(t)是一个一阶逻辑公式由原子公式通过逻辑连接词∧、∨、¬和量词∃、∀组合而成。原子公式是谓词P的不可再分的基本构件。在元组关系演算中原子公式有三种类型其一成员资格原子t ∈ R。断言元组变量t是关系R中的一个元组。这是将变量绑定到关系的基本方式。其二比较原子t[A] θ s[B] 或 t[A] θ c。其中t和s是元组变量A和B是属性名c是常量θ是比较运算符。它断言两个元组在指定属性上的取值满足某种比较关系。其三比较原子t[A] θ s[B] 或 t[A] θ c。其中t和s是元组变量A和B是属性名c是常量θ是比较运算符。它断言两个元组在指定属性上的取值满足某种比较关系。这三种原子公式通过逻辑连接词和量词组合起来可以表达任意复杂的查询条件。一个简单查询的示例“查询所有年龄大于18岁的学生的姓名和学号”。用元组关系演算表达为{ t | ∃s ∈ 学生 ( s[年龄] 18 ∧ t[姓名] s[姓名] ∧ t[学号] s[学号] ) }这个表达式的逻辑结构清晰可辨存在一个学生元组s它的年龄大于18岁我们要找的元组t的姓名和学号分别等于s的姓名和学号。这里的量词∃存在表达了“在学生关系中能找到这样一个元组”的含义。一个包含全称量词的查询“查询那些在所有项目中都有参与的供应商名称”。设关系“供应(供应商, 项目)”关系“项目(项目名)”。用元组关系演算表达为{ t | ∃g ∈ 供应商 ( t[名称] g[名称] ∧ ∀x ∈ 项目 ( ∃y ∈ 供应 ( y[供应商] g[供应商] ∧ y[项目] x[项目名] ) ) ) }这个表达式的逻辑层次更为丰富存在一个供应商g对于所有的项目x都存在一条供应记录y表明g供应了x。全称量词∀与存在量词∃的交错嵌套精确捕获了“全部”语义。元组关系演算的安全性并非所有语法上合法的元组关系演算表达式都有实际意义。考虑表达式 { t | ¬(t ∈ 学生) }——它要求返回所有不在学生关系中的元组。学生关系是有限的但“所有不在学生关系中的元组”是一个无限集合任何不符合学生模式的元组都满足条件这个查询无法在有限时间内给出有限结果因此是不安全的。数据库理论定义了安全表达式的概念一个元组关系演算表达式是安全的当且仅当它的结果只依赖于数据库中的值且结果必定有限。在实践层面任何有意义的查询表达式都必须是安全的数据库系统的查询编译器会拒绝不安全的表达式。三、ALPHA语言元组关系演算的具体化身元组关系演算并非纯粹的理论构造它有一个直接的实际化身——ALPHA语言。ALPHA是科德在提出关系模型时同时设计的一种查询语言它直接基于元组关系演算的语法是世界上第一个关系数据库查询语言。虽然后来的历史选择了SQL而非ALPHA但理解ALPHA的语法结构对于理解SQL的设计逻辑至关重要——SQL的SELECT-FROM-WHERE骨架可以在ALPHA中找到直接的祖先。ALPHA语言的一个查询基本块称为一个语句其核心结构为操作空间 限定语句 条件语句操作空间GET/WORKSPACE声明操作类型限定语句指定元组变量及其遍历范围条件语句声明目标元组需满足的谓词。一个典型的ALPHA查询“获取在部门D1工作的所有员工的姓名和工资”写作RANGE EMPLOYEE IS EGET W (E.NAME, E.SALARY) : E.DEPT D1这几乎可以直接翻译为SQLSELECT E.NAME, E.SALARY FROM EMPLOYEE E WHERE E.DEPT D1。变量绑定RANGE/GET对应了FROM目标属性列表对应了SELECT条件对应了WHERE。ALPHA语言还包含一些SQL后来舍弃或改造了的结构。例如ALPHA使用显式的工作空间变量W来接收查询结果多个查询可以通过工作空间串联它允许使用全称量词∀和蕴涵连接词→来直接表达复杂的逻辑条件而SQL需要通过嵌套的NOT EXISTS间接表达。ALPHA的这些设计选择反映了关系演算“尽可能贴近逻辑表达”的原始理想——而SQL最终选择了在声明性与工程可行性之间折中的道路。四、域关系演算以域值为变量的查询逻辑元组关系演算以整个元组为变量表达查询时常常需要“先找到某个元组再取出它的某个属性值”。域关系演算则选择了一条更细粒度的路线变量直接遍历域中的值而非遍历元组。域关系演算的查询表达式结构为{ (x₁, x₂, ..., xₙ) | P(x₁, x₂, ..., xₙ) }其中x₁到xₙ是域变量每个域变量的取值范围是某个属性所基于的域。谓词P由域变量上的原子公式构成。域关系演算的原子公式也有三种类型其一成员资格原子(x₁, x₂, ..., xₙ) ∈ R。断言域变量组成的有序组是关系R中的一个元组。其二比较原子x θ y 或 x θ c。其中x和y是域变量c是常量θ是比较运算符。其三成员资格原子(x₁, x₂, ..., xₙ) ∈ R。断言域变量组成的有序组是关系R中的一个元组。同一个查询在两种演算中的对比“查询所有年龄大于18岁的学生的姓名和学号”。元组关系演算版本{ t | ∃s ∈ 学生 ( s[年龄] 18 ∧ t[姓名] s[姓名] ∧ t[学号] s[学号] ) }域关系演算版本{ (n, id) | ∃a ( (n, id, a) ∈ 学生 ∧ a 18 ) }域关系演算版本的简洁性显而易见。它不需要引入元组变量s再从中提取属性值而是直接用域变量n姓名、id学号、a年龄来表达——查询的逻辑结构与关系模式的属性列形成直接对应。这种表达方式更接近人类对数据的直觉我们希望找出所有的姓名和学号使得存在一个年龄这三者共同构成学生关系中的一个元组且年龄大于18。域关系演算在处理某些查询时展现出比元组关系演算更自然的表达能力。例如“查询至少选修了一门课程的学生姓名”——在域关系演算中只需表达为 { n | ∃c ( (n, c) ∈ 选课 ) }其中域变量c的存在量词自然地表达了“存在某门课程”的语义。而在元组关系演算中则需要先绑定一个选课元组再投影到姓名。五、QBE域关系演算的用户界面革命如果说ALPHA是元组关系演算的语言化身那么QBEQuery By Example示例查询则是域关系演算最具影响力的实际实现。QBE由IBM研究员莫什·兹卢夫Moshe Zloof于20世纪70年代中期设计。它的核心思想在当时极为超前用户不需要书写任何语法结构只需在屏幕上看到的空表格中填入示例值系统就能自动推断出查询意图。屏幕上显示的是关系模式的骨架——每个表呈现为一个空白的表格模板列名已经印好用户只需在相应的列中填入示例元素例如在“姓名”列填入“张三”作为示例并辅以特殊的标记符号如“P.”表示打印输出系统便能将用户的示例操作翻译为域关系演算表达式并执行。举例而言查询“年龄大于18岁的学生姓名和学号”在QBE中只需两步在“学生”表的“姓名”列和“学号”列下分别填入“P.”表示这两列需要输出在“年龄”列下填入“18”。没有SELECT没有FROM没有WHERE——用户面对的是数据本身的视觉模板操作方式是填入熟悉的表格单元格。QBE的深层逻辑正是域关系演算。用户在表格中填入的每一个示例常量都是一个隐式绑定的域变量用户填入的比较条件构成了域关系演算的谓词标有“P.”的列则构成了目标列表。QBE成功地将域关系演算的数学语法隐藏在一张表格之后使得不具备编程能力的业务人员也能进行数据库查询。这种“零语法”的交互范式深远地影响了后世的数据查询工具——从Microsoft Access的可视化查询设计器到Tableau的拖拽式探索界面都能追溯到QBE的思想源头。六、过程性与声明性的哲学对勘行文至此我们有必要进行一次哲学层面的审视关系代数与关系演算代表了两种截然不同的思维范式它们之间的分歧远远超出了数据库领域延伸到了整个计算机科学关于“如何与机器对话”的根本论争。关系代数是过程性的。它规定了查询的执行流程——先做什么运算再做什么运算中间结果如何流动。书写关系代数表达式类似于编写一个微观的执行计划每个运算符号都是对“下一步怎么走”的指令。过程性语言的优势在于可控——使用者明确知晓每一步的计算代价可以精细地调控执行策略。其劣势在于负担——使用者必须思考“怎么做”而不能只思考“要什么”。关系演算是声明性的。它不规定任何执行步骤只描述目标数据的逻辑特征。用户表达的是“什么条件必须成立”而非“通过什么路径找到它们”。声明性语言的优势在于简洁与聚焦——使用者可以全身心投入到查询逻辑本身将执行策略的选择完全委托给系统。其劣势在于黑箱感——使用者不知道系统是如何执行查询的当查询效率低下时难以自行诊断与优化。SQL语言的选择鲜明地体现了这一张力。SQL的SELECT-FROM-WHERE主干结构直接继承了关系演算的声明性传统——用户描述目标列SELECT和条件WHERE系统自行决定执行计划。但SQL中同时也混入了明显的过程性元素——ORDER BY规定了排序操作LIMIT限制了结果行数游标CURSOR允许逐行遍历结果集。这种混合并非理论上的不纯而是工程上的务实纯声明性语言在某些场景下的表达能力受限例如要求结果按特定顺序排列适当引入过程性结构能够更好地服务于真实世界的需求。两种范式的并存并没有谁取代谁。数据库查询优化器的内部运作恰恰是这一共存的缩影用户提交的声明性SQL首先被翻译为一棵关系代数表达式树过程性的然后优化器对树进行等价重写和物理计划选择仍然是过程性的最终提交给执行引擎。在这个流水线中声明性面向用户过程性面向机器——各司其职各擅胜场。七、结语从逻辑到语言从语言到系统元组关系演算和域关系演算的提出标志着科德对关系模型理论基础的全面竣工。关系代数提供了一套过程性的查询操作代数关系演算提供了一套声明性的查询逻辑语言而科德证明了这两套体系在表达能力上的等价性。这一“三方等价”的优美结构——关系代数、元组关系演算、域关系演算三者表达能力相同——构成了关系数据库查询语言的坚实理论地基。理解关系演算的价值不在于掌握ALPHA或QBE的具体语法它们已成为技术史上的注脚而在于认清SQL语言的逻辑本质。每一条SELECT-FROM-WHERE语句本质上都是一个被语法糖包裹的域关系演算表达式。当你书写WHERE子句中的复杂嵌套条件时你实际上是在用谓词逻辑的语言向数据库提出一个问题。这个认知将帮助你穿透语法的表面直达查询的逻辑核心——而逻辑是唯一不会随技术更迭而失效的通货。下一篇我们将正式踏入SQL语言的世界——看看这种继承了关系演算声明性精神、吸收了ALPHA语法结构、又在数十年工程实践中发展出庞杂生态的查询语言是如何将关系模型的全部理论力量交到每一个开发者手中的。