目录一、引言一场关于“科学性”的争论二、集合论关系的数学定义三、域与属性从抽象集合到语义命名四、一阶谓词逻辑查询的语义基础五、关系模型的统治地位数学带来的信任六、结语站在巨人的肩膀上一、引言一场关于“科学性”的争论20世纪60年代末数据库领域正处于群雄逐鹿的草莽时代。IBM力推的层次模型以树形结构组织数据通用电气主导的网状模型则以图结构取胜。这两种模型有一个共同特征它们的数据结构都是物理存储结构的直接映射——程序员需要知道数据是如何在磁盘上连接的需要沿着指针在记录之间游走需要精确指定存取路径。数据操作是一门手艺效率依赖于程序员的经验与直觉。1970年科德提出了关系模型。他的核心主张在当时听来近乎异端用户不需要知道数据如何存储不需要指定存取路径甚至不需要了解底层的数据结构。他只需要用一种声明式的语言表达“想要什么”系统就能自动找出答案。这一主张之所以不是空想是因为科德为它找到了一个不可动摇的理论支点——数学。他证明了关系就是集合论的子集查询就是一阶谓词逻辑的表达式。既然数学命题可以被证明、被优化、被等价转换那么基于数学理论的数据操作也应该享有同样的属性。正是这种数学上的可证明性使得关系数据库的查询优化器能够存在——系统可以像代数化简一样重写用户的查询而不改变其结果这是层次模型和网状模型从未做到的。二、集合论关系的数学定义要理解关系模型必须首先回到一个看似基础却在日常使用中常被混淆的概念什么是“关系”在日常语言中“关系”是一个模糊的词汇。我们说“这两个事件之间有关系”、“他们关系很好”这里的“关系”表达的是某种关联或联系。但在关系模型的语境中“关系”是一个严格的数学概念它根植于集合论具有精确的外延定义。集合论是现代数学的基石它研究集合由确定元素构成的整体的性质与运算。关系模型借用集合论中的一个基本概念给定若干集合这些集合的笛卡尔积的任意一个子集就是一个关系。这个定义涉及两个关键术语需要逐一拆解。笛卡尔积是多个集合之间的全组合操作。设有集合A与集合B则A与B的笛卡尔积记作A×B其结果为所有可能的有序对(a, b)构成的集合其中a取自Ab取自B。例如设集合D₁ {张三, 李四}集合D₂ {数学, 英语, 物理}则D₁×D₂ {(张三, 数学), (张三, 英语), (张三, 物理), (李四, 数学), (李四, 英语), (李四, 物理)}总共2×36个有序对。笛卡尔积的规模增长极快——如果涉及n个集合每个集合分别有m₁, m₂, ..., mₙ个元素则笛卡尔积的规模为m₁×m₂×...×mₙ。对于实际业务场景而言这个数字通常是天文量级。更重要的是笛卡尔积中绝大多数的组合在现实中毫无意义。在D₁×D₂的六个有序对中如果实际业务中张三只选修了数学和英语李四只选修了物理那么(张三, 物理)和(李四, 数学)、(李四, 英语)这三个有序对虽然在数学上存在却对应着并不存在的事实。由此引出关系的严格定义关系是笛卡尔积的一个子集它仅包含那些在现实世界中真实成立的组合。在上述选课场景中关系{ (张三, 数学), (张三, 英语), (李四, 物理) }它是D₁×D₂的一个真子集。这个子集精确定义了“选课”这一关系在当前时刻的外延——它告诉我们在我们所关心的论域中哪些学生选了哪些课。这个定义中隐含了几个关键性质它们构成了关系模型的行为边界。其一关系中不允许有重复的元组——集合的定义决定了其中的元素必须互异因此关系的每一行必须是唯一的。其二关系的行之间没有隐含的顺序——集合是无序的关系的行自然也应当被视为无序的。其三关系的列之间同样没有固定的物理顺序——从集合论的角度看笛卡尔积的有序对确实规定了分量的顺序但在关系模型的实用层面列是通过名称而非位置来标识的。这几个性质看似简单却在数据库系统的实现中引发了大量工程上的权衡与妥协后续的文章将陆续触及。三、域与属性从抽象集合到语义命名上一节的讨论中关系的定义是完全抽象化的——我们只关心元素是哪个集合的成员而不关心这些集合代表什么。但在实际的数据库应用中集合本身是有语义的。D₁是“全体学生的集合”D₂是“全体课程的集合”。给抽象的集合赋予语义便引入了两个关键概念域与属性。域是具有相同数据类型和语义的一组合法取值。它类似于编程语言中“类型”的概念但通常包含更强的语义约束。例如“年龄”域可以是0到150之间的整数“性别”域可以是{‘男’, ‘女’}的枚举。域不仅限定了取值的数据类型还限定了取值的范围它是数据库完整性的第一道防线——如果一个值不属于它声称所在的域它就根本没有资格进入数据库。当我们将一个域赋予一个语义名称并放置在关系的特定位置上时这个带有名称的域角色就成为了属性。在学生选课的例子里D₁域被赋予了“学生姓名”这一属性名D₂域被赋予了“课程名称”这一属性名。属性是域的语义化封装它告诉用户这一列数据在业务世界中代表什么。由此我们可以给出关系模式的形式化记法。一个关系模式可以记为R(A₁:D₁, A₂:D₂, ..., Aₙ:Dₙ)其中R是关系的名称Aᵢ是属性名Dᵢ是属性Aᵢ所基于的域。而关系模式在某一时刻的实例——也就是一个具体的关系——是该笛卡尔积的一个子集。这一区分关系模式与关系实例是数据库理论中最基础的二分法之一模式是结构是相对稳定的实例是内容是随时间变化的。四、一阶谓词逻辑查询的语义基础如果说集合论提供了关系的结构定义那么一阶谓词逻辑则为关系的查询与操作提供了语义基础。这正是关系模型区别于其前辈模型的根本所在。层次模型和网状模型的查询是过程性的程序员必须指定数据访问的具体路径——从这个入口出发沿着这条指针链前进遇到分叉向左转在某个节点取出数据。这种查询方式要求程序员对数据的物理存储结构有清晰的了解。而关系模型开创性地提出了声明式查询用户只需描述目标数据的特征系统自行寻找数据。这一设想得以实现的关键在于科德将查询操作建立在一阶谓词逻辑之上。一阶谓词逻辑是形式逻辑的一个分支它允许我们对“对象具有什么性质”和“对象之间存在什么关系”这类命题进行严格的符号化表达与推理。在关系模型的语境下这些“对象”就是域中的取值而“关系”则是我们通过谓词断言的事实。每一个关系实例都可以被视为一组真命题的集合。例如关系“选课”中包含元组(张三, 数学)就意味着在逻辑上命题“张三选修了数学”为真。反过来不在关系中的组合则意味着命题为假。这种真值语义是关系模型与逻辑之间的第一层连接。更深层的连接在于查询语言。考察这样一个查询“找出所有选修了数学课程的学生姓名”。在一阶谓词逻辑中这个查询可以表达为{ x | ∃c (选课(x, c) ∧ c ‘数学’) }读作所有满足以下条件的x——存在一个c使得“x选修了c”为真并且c等于“数学”。这种表达形式被称为元组关系演算它是SQL语言的理论原型。当用户书写一条SQL查询时——SELECT 学生 FROM 选课 WHERE 课程‘数学’——他实际上是在用一种类自然语言的语法来表达上述逻辑表达式。一阶谓词逻辑赋予了关系查询几个关键能力其一声明性——用户只需描述结果应该满足什么条件而不必指定获取结果的步骤。其二可证明的等价性——两个逻辑表达式是否等价可以通过逻辑推理来判定这意味着系统可以安全地重写用户的查询以提升效率。其三封闭性——对关系进行查询操作的结果仍然是关系这保证了操作的嵌套能力。这些性质共同构成了关系模型的技术护城河。五、关系模型的统治地位数学带来的信任为什么是关系模型胜出从结果上看到20世纪80年代中期关系型数据库已经基本统一了市场层次模型和网状模型退守到特定的遗留系统领域。这一历史进程常被归因于SQL语言的易用性或IBM等厂商的商业推动。但更深层的原因在于关系模型的数学基础为整个产业提供了两个不可或缺的东西理论的确定性与实现的自由度。所谓理论的确定性是指关系模型对“正确结果”有着无可争议的定义。两个查询是否等价一个查询优化重写是否合法一个数据库设计是否消除了某种异常——这些问题在关系模型的数学框架下都有精确的答案。这种确定性意味着数据库管理系统可以内置一个查询优化器自动选择最高效的执行方案而用户和应用程序只需要关心结果的正确性。这是层次和网状模型从未实现的质变。所谓实现的自由度是指关系模型将“做什么”与“怎么做”彻底分离。正因为用户查询只声明目标不指定路径系统实现者可以在物理层自由地更换存储结构、索引策略和连接算法而完全不影响上层应用。这种自由度催生了数据库管理系统内部惊人的工程创新——B树索引、哈希连接、基于代价的优化器、多版本并发控制——所有这些技术都在关系模型的庇护下发育成熟因为它们可以在不惊扰用户的前提下被悄悄替换。数学的冷硬与工程的柔性在关系模型这里形成了完美的互补。这就是为什么半个世纪之后当NoSQL运动试图用“简单键值对”或“无模式文档”来挑战关系模型时这些新模型最终都重新拾起了声明式查询语言和声明式模式约束——它们不得不向关系模型那套已经被数学证明有效的范式靠拢。六、结语站在巨人的肩膀上理解关系模型的数学基础并非为了应对考试中的计算题而是为了在未来的学习和实践中能够看穿技术表象背后的不变逻辑。当你设计一个数据库模式你实际上是在定义一组域和这些域上的关系约束当你书写一条SQL查询你实际上是在构造一个一阶谓词逻辑的表达式。这种来自数学的洞察不会因数据库产品的更迭而失效。下一篇我们将从数学定义走向工程表达深入探讨关系数据结构在实际数据库系统中的形式化体现——关系模式、码、以及守护数据逻辑完整性的外码机制。
【数据库系统原理】第3篇：关系模型的数学基石：集合论与一阶谓词逻辑
目录一、引言一场关于“科学性”的争论二、集合论关系的数学定义三、域与属性从抽象集合到语义命名四、一阶谓词逻辑查询的语义基础五、关系模型的统治地位数学带来的信任六、结语站在巨人的肩膀上一、引言一场关于“科学性”的争论20世纪60年代末数据库领域正处于群雄逐鹿的草莽时代。IBM力推的层次模型以树形结构组织数据通用电气主导的网状模型则以图结构取胜。这两种模型有一个共同特征它们的数据结构都是物理存储结构的直接映射——程序员需要知道数据是如何在磁盘上连接的需要沿着指针在记录之间游走需要精确指定存取路径。数据操作是一门手艺效率依赖于程序员的经验与直觉。1970年科德提出了关系模型。他的核心主张在当时听来近乎异端用户不需要知道数据如何存储不需要指定存取路径甚至不需要了解底层的数据结构。他只需要用一种声明式的语言表达“想要什么”系统就能自动找出答案。这一主张之所以不是空想是因为科德为它找到了一个不可动摇的理论支点——数学。他证明了关系就是集合论的子集查询就是一阶谓词逻辑的表达式。既然数学命题可以被证明、被优化、被等价转换那么基于数学理论的数据操作也应该享有同样的属性。正是这种数学上的可证明性使得关系数据库的查询优化器能够存在——系统可以像代数化简一样重写用户的查询而不改变其结果这是层次模型和网状模型从未做到的。二、集合论关系的数学定义要理解关系模型必须首先回到一个看似基础却在日常使用中常被混淆的概念什么是“关系”在日常语言中“关系”是一个模糊的词汇。我们说“这两个事件之间有关系”、“他们关系很好”这里的“关系”表达的是某种关联或联系。但在关系模型的语境中“关系”是一个严格的数学概念它根植于集合论具有精确的外延定义。集合论是现代数学的基石它研究集合由确定元素构成的整体的性质与运算。关系模型借用集合论中的一个基本概念给定若干集合这些集合的笛卡尔积的任意一个子集就是一个关系。这个定义涉及两个关键术语需要逐一拆解。笛卡尔积是多个集合之间的全组合操作。设有集合A与集合B则A与B的笛卡尔积记作A×B其结果为所有可能的有序对(a, b)构成的集合其中a取自Ab取自B。例如设集合D₁ {张三, 李四}集合D₂ {数学, 英语, 物理}则D₁×D₂ {(张三, 数学), (张三, 英语), (张三, 物理), (李四, 数学), (李四, 英语), (李四, 物理)}总共2×36个有序对。笛卡尔积的规模增长极快——如果涉及n个集合每个集合分别有m₁, m₂, ..., mₙ个元素则笛卡尔积的规模为m₁×m₂×...×mₙ。对于实际业务场景而言这个数字通常是天文量级。更重要的是笛卡尔积中绝大多数的组合在现实中毫无意义。在D₁×D₂的六个有序对中如果实际业务中张三只选修了数学和英语李四只选修了物理那么(张三, 物理)和(李四, 数学)、(李四, 英语)这三个有序对虽然在数学上存在却对应着并不存在的事实。由此引出关系的严格定义关系是笛卡尔积的一个子集它仅包含那些在现实世界中真实成立的组合。在上述选课场景中关系{ (张三, 数学), (张三, 英语), (李四, 物理) }它是D₁×D₂的一个真子集。这个子集精确定义了“选课”这一关系在当前时刻的外延——它告诉我们在我们所关心的论域中哪些学生选了哪些课。这个定义中隐含了几个关键性质它们构成了关系模型的行为边界。其一关系中不允许有重复的元组——集合的定义决定了其中的元素必须互异因此关系的每一行必须是唯一的。其二关系的行之间没有隐含的顺序——集合是无序的关系的行自然也应当被视为无序的。其三关系的列之间同样没有固定的物理顺序——从集合论的角度看笛卡尔积的有序对确实规定了分量的顺序但在关系模型的实用层面列是通过名称而非位置来标识的。这几个性质看似简单却在数据库系统的实现中引发了大量工程上的权衡与妥协后续的文章将陆续触及。三、域与属性从抽象集合到语义命名上一节的讨论中关系的定义是完全抽象化的——我们只关心元素是哪个集合的成员而不关心这些集合代表什么。但在实际的数据库应用中集合本身是有语义的。D₁是“全体学生的集合”D₂是“全体课程的集合”。给抽象的集合赋予语义便引入了两个关键概念域与属性。域是具有相同数据类型和语义的一组合法取值。它类似于编程语言中“类型”的概念但通常包含更强的语义约束。例如“年龄”域可以是0到150之间的整数“性别”域可以是{‘男’, ‘女’}的枚举。域不仅限定了取值的数据类型还限定了取值的范围它是数据库完整性的第一道防线——如果一个值不属于它声称所在的域它就根本没有资格进入数据库。当我们将一个域赋予一个语义名称并放置在关系的特定位置上时这个带有名称的域角色就成为了属性。在学生选课的例子里D₁域被赋予了“学生姓名”这一属性名D₂域被赋予了“课程名称”这一属性名。属性是域的语义化封装它告诉用户这一列数据在业务世界中代表什么。由此我们可以给出关系模式的形式化记法。一个关系模式可以记为R(A₁:D₁, A₂:D₂, ..., Aₙ:Dₙ)其中R是关系的名称Aᵢ是属性名Dᵢ是属性Aᵢ所基于的域。而关系模式在某一时刻的实例——也就是一个具体的关系——是该笛卡尔积的一个子集。这一区分关系模式与关系实例是数据库理论中最基础的二分法之一模式是结构是相对稳定的实例是内容是随时间变化的。四、一阶谓词逻辑查询的语义基础如果说集合论提供了关系的结构定义那么一阶谓词逻辑则为关系的查询与操作提供了语义基础。这正是关系模型区别于其前辈模型的根本所在。层次模型和网状模型的查询是过程性的程序员必须指定数据访问的具体路径——从这个入口出发沿着这条指针链前进遇到分叉向左转在某个节点取出数据。这种查询方式要求程序员对数据的物理存储结构有清晰的了解。而关系模型开创性地提出了声明式查询用户只需描述目标数据的特征系统自行寻找数据。这一设想得以实现的关键在于科德将查询操作建立在一阶谓词逻辑之上。一阶谓词逻辑是形式逻辑的一个分支它允许我们对“对象具有什么性质”和“对象之间存在什么关系”这类命题进行严格的符号化表达与推理。在关系模型的语境下这些“对象”就是域中的取值而“关系”则是我们通过谓词断言的事实。每一个关系实例都可以被视为一组真命题的集合。例如关系“选课”中包含元组(张三, 数学)就意味着在逻辑上命题“张三选修了数学”为真。反过来不在关系中的组合则意味着命题为假。这种真值语义是关系模型与逻辑之间的第一层连接。更深层的连接在于查询语言。考察这样一个查询“找出所有选修了数学课程的学生姓名”。在一阶谓词逻辑中这个查询可以表达为{ x | ∃c (选课(x, c) ∧ c ‘数学’) }读作所有满足以下条件的x——存在一个c使得“x选修了c”为真并且c等于“数学”。这种表达形式被称为元组关系演算它是SQL语言的理论原型。当用户书写一条SQL查询时——SELECT 学生 FROM 选课 WHERE 课程‘数学’——他实际上是在用一种类自然语言的语法来表达上述逻辑表达式。一阶谓词逻辑赋予了关系查询几个关键能力其一声明性——用户只需描述结果应该满足什么条件而不必指定获取结果的步骤。其二可证明的等价性——两个逻辑表达式是否等价可以通过逻辑推理来判定这意味着系统可以安全地重写用户的查询以提升效率。其三封闭性——对关系进行查询操作的结果仍然是关系这保证了操作的嵌套能力。这些性质共同构成了关系模型的技术护城河。五、关系模型的统治地位数学带来的信任为什么是关系模型胜出从结果上看到20世纪80年代中期关系型数据库已经基本统一了市场层次模型和网状模型退守到特定的遗留系统领域。这一历史进程常被归因于SQL语言的易用性或IBM等厂商的商业推动。但更深层的原因在于关系模型的数学基础为整个产业提供了两个不可或缺的东西理论的确定性与实现的自由度。所谓理论的确定性是指关系模型对“正确结果”有着无可争议的定义。两个查询是否等价一个查询优化重写是否合法一个数据库设计是否消除了某种异常——这些问题在关系模型的数学框架下都有精确的答案。这种确定性意味着数据库管理系统可以内置一个查询优化器自动选择最高效的执行方案而用户和应用程序只需要关心结果的正确性。这是层次和网状模型从未实现的质变。所谓实现的自由度是指关系模型将“做什么”与“怎么做”彻底分离。正因为用户查询只声明目标不指定路径系统实现者可以在物理层自由地更换存储结构、索引策略和连接算法而完全不影响上层应用。这种自由度催生了数据库管理系统内部惊人的工程创新——B树索引、哈希连接、基于代价的优化器、多版本并发控制——所有这些技术都在关系模型的庇护下发育成熟因为它们可以在不惊扰用户的前提下被悄悄替换。数学的冷硬与工程的柔性在关系模型这里形成了完美的互补。这就是为什么半个世纪之后当NoSQL运动试图用“简单键值对”或“无模式文档”来挑战关系模型时这些新模型最终都重新拾起了声明式查询语言和声明式模式约束——它们不得不向关系模型那套已经被数学证明有效的范式靠拢。六、结语站在巨人的肩膀上理解关系模型的数学基础并非为了应对考试中的计算题而是为了在未来的学习和实践中能够看穿技术表象背后的不变逻辑。当你设计一个数据库模式你实际上是在定义一组域和这些域上的关系约束当你书写一条SQL查询你实际上是在构造一个一阶谓词逻辑的表达式。这种来自数学的洞察不会因数据库产品的更迭而失效。下一篇我们将从数学定义走向工程表达深入探讨关系数据结构在实际数据库系统中的形式化体现——关系模式、码、以及守护数据逻辑完整性的外码机制。
