Lec 2: Relational Model⚓︎

• 关系模型 (relational model)

  • 特点：简单而优雅
  • 主要优势：简单的数据表示，容易表达复杂的查询（得益于 SQL）

• 关系型数据库 (relational database)：一组由单个或多个基于关系模型的关系构成的容器

  • 关系 (relations)：有行有列的表格
  • 联系 (relationship)：多个实体之间的关联

Structure of Relational Databases⚓︎

定义：对于给定的集合 \(D_1, D_2, \dots, D_n(D_i = a_{ij}|_{j=1 \dots k})\)，关系 \(r\) 为笛卡尔积 \(D_1 \times D_2 \times \dots \times D_n\) 的子集。

• 笛卡尔积可以用一张二维表表示
• 关系也是一个由 n 元组 (n-tuples) \((a_{1j}, a_{2j}, \dots, a_{nj})\) 构成的集合，其中 \(a_{ij} \in D_i\)

一些关键概念：

• 属性类型 (attribute types)

  • 关系内的每个属性都有一个名称
  • 每个属性的允许值的集合被称为属性的域 (domain)

  • 属性值（通常）要求具备原子性 (atomic)，即不可分割 (indivisible)（满足第一范式 (1st NF)）

    • 多值 (mutlivalued) 属性、复合 (composite) 属性到不具备原子性

  • 特殊值 null 是所有域的成员。该值的存在使得很多运算的定义变得复杂，因此我们先不考虑 null 值的影响

• 关系的两大概念：

  • 关系模式 (relation schema)：描述关系的结构
    • 假如有属性 \(A_1, A_2, \dots, A_n\)，那么 \(R = (A_1, A_2, \dots, A_n)\) 就是关系模式，而 \(r(R)\) 就是在关系模式 \(R\) 上的一个关系
  • 关系实例 (relation instance)：在某个时刻上，对关系内的数据的快照 (snapshot)
    • 关系上的当前值（即关系实例）会在表格中具体指明
    • 关系 \(r\) 的元素 \(t\) 是一个元组，在表格上就是一行的记录；可用 \(t[name]\) 表示 \(t\) 在 \(name\) 属性上的值

• 关系是无序的 (unordered)

  • 元组的顺序没有意义，可按任意顺序被存储
  • 同一个关系内，不能存在重复的元组

• 码 / 键 (keys)：令 \(K \subseteq R\)，有以下几类键：

  • 超键 (superkey)：对于每个可能的关系 \(r(R)\)，\(K\) 能识别出唯一的元组
  • 候选键 (candidate key)：最小数量的超键
  • 主键 (primary key)：是一种候选键，且由用户显式定义的键（通常用下划线标出）
  • 外键 (foreign key)：假设存在关系 \(r(A, B, C), s(B, D)\)，关系 \(r\) 的属性 \(B\) 是参照 \(s\) 的外键，其中 \(r\) 是参照关系 (referencing relation)，\(s\) 是被参照关系 (referenced relation)
    • 参照关系中外码的值必须在被参照关系中实际存在或为 null

例子：大学数据库的模式图

数据库内包含以下关系：

模式图：

在模式图中，参照关系通过一根箭头指向被参照关系。

• 查询语言：用户用来请求数据库信息的语言
  • “纯”语言：查询语言的基础
    • 关系代数 (relational algebra)：SQL 的基础
    • 元组关系演算 (tuple relational caculus)
    • 域关系演算 (domain relational calculus)

Relational Algebra⚓︎

• 关系代数是一种过程语言 (procedural language)
• 六种基本运算符
  • 选择 (select)
  • 投影 (project)
  • 并 (union)
  • 差 (difference)
  • 笛卡尔积 (Cartesian product)
  • 重命名 (rename)
• 运算符接受一个或两个关系作为输入，产生一个新的关系作为结果
• 更多运算：主要用于简化一般的查询
  • 交 (intersection)
  • 自然连接 (natural join)
  • 除 (divide)
  • 赋值 (assignment)

Select⚓︎

• 选择运算记作：\(\sigma_p(r) = \{t\ |\ t \in r \text{ and } p(t)\}\)
• 其中 \(p\) 称为选择谓词 (selection predicate)，它是一个关于命题演算的公式（用 \(\wedge, \vee, \neg\) 等符号连接的项）
• 每个项的格式为：\<attribute> op \<attribute>/\<constant>，其中 op 是比较运算符（\(=, \ne, >, \ge, <, \le\) 中的其中一种）
• 执行选择时，选择条件必须是针对同一元组中相应属性值代入进行比较

例子

Project⚓︎

• 投影运算记作：\(\prod_{A_1, A_2, \dots, A_k}(r)\)，其中 \(A_1, \dots, A_k\) 是属性名称
• 运算结果为包含指定的 \(k\) 列关系，那些没有指定的列会被删掉
• 由于关系本质上是一种集合，所以投影结果中重复的行也要删去

例子

Union⚓︎

• 并运算记作：\(r \cup s = \{t\ |\ t \in r \text{ or } t \in s\}\)
• 上述运算的合法条件为：两个关系必须是可兼容的，具体指
  • \(r, s\) 必须具备相同的元数 (arity)（即相同数量的属性）
  • 两者的属性域必须是可兼容的 (compatible)

例子

Difference⚓︎

• 差运算记作：\(r - s = \{t\ |\ t \in r \text{ and } t \notin s\}\)
• 差运算也必须在可兼容的关系中进行（具体含义见上）

例子

Cartesian Product⚓︎

• 笛卡尔积记作：\(r \times s = \{\{t, q\}\ |\ t \in r \text{ and } q \in s\}\)
• 理想情况下，假设 \(r(R)\) 和 \(s(S)\) 的属性是不相交的，即 \(R \cap S = \emptyset\)
• 若两者是相交的，那么首先要对重叠的属性进行重命名操作

例子

Rename⚓︎

• 命名运算记作：\(\rho_X(E)\) 返回在名称 \(X\) 下的表达式 \(E\)
• 如果 \(E\) 的元数为 \(n\)，那么 \(\rho_{X(A_1, A_2, \dots, A_n)}(E)\) 返回在名称 \(X\) 下的表达式 \(E\)，并且属性名改为 \(A_1, A_2, \dots, A_n\)

例子

给定一家银行的数据库：

问题：

Intersection⚓︎

• 交运算记作：\(r \cap s = \{t\ |\ t \in r \text{ and } t \in s\}\)
• 要求两个关系必须是可兼容的（具体含义见并运算部分）
• \(r \cap s = r - (r - s)\)

例子

Natural Join⚓︎

• 自然连接记作：\(r \bowtie s\)

• 令 \(r, s\) 的模式分别为 \(R, S\)，那么 \(r \bowtie s\) 的结果为一个在模式 \(R \cup S\) 上的关系，按照以下方法获得：

  • 考虑分别来自 \(r, s\) 的每一对元组 \(t_r, t_s\)
  • 如果 \(t_r, t_s\) 在 \(R \cap S\) 的每个属性上的取值相同，则将元组 \(t\) 加入到结果中，其中 \(t\) 有与 \(t_r\) 在 \(r\) 上，以及 \(t_s\) 在 \(s\) 上相同的值
  • 人话版：连接两个关系中同名属性值相等的元组，结果属性是二者属性集的并集，但小区重名属性

• \(r, s\) 必须有共同属性（名称、域对应相同）

• 扩展：Theta 连接，记作：\(r \bowtie_\theta = \sigma_\theta(r \times s)\)，其中 \(\theta\) 是关于模式上属性的谓词

例子

Divide⚓︎

• 除法运算记作：\(r \div s\)
• 性质：令 \(q = r \div s\)，那么 \(q\) 是最大的关系，满足 \(q \times s \subseteq r\)
• 定义：\(r \div s = \prod_{R - S}(r) - \prod_{R - S}((\prod_{R - S}(r) \times s) - \prod_{R - S, S}(r))\)
• 解释：
  • \(\prod_{R - S, S}(r)\) 仅重排了 \(r\) 的属性
  • \(\prod_{R - S}((\prod_{R - S}(r) \times s) - \prod_{R - S, S}(r))\) 找出 \(\prod_{R - S}(r)\) 的 \(t\)，满足对于某些元组 \(u \in s, tu \notin r\)
• 另一种表述：$\(r \div s = \{t\ |\ t \in \prod_{R - S}(r) \wedge \forall u \in s(tu \in r)\}\)
• 商来自于 \(\prod_{R-S}(r)\)，并且其元组 \(t, s\) 所有元组的拼接被 \(r\) 覆盖
• 该运算适用于带有 "for all" 字样的查询语句

例子

Assignment⚓︎

• 赋值运算符 \(\leftarrow\) 提供了一种表达复杂查询的便捷方法
  • 可以将查询写成一个顺序的程序，里面包含了一系列的赋值语句，随后跟上一个表达式，其值作为查询的结果
  • 赋值必须用于临时的关系变量

例子

Extended Relational-Algebra-Operations⚓︎

Generalized Projection⚓︎

• 广义的投影运算允许在投影列表中使用算术表达式，即 \(\prod_{F_1, F_2, \dots, F_n}(E)\)
• 其中 \(E\) 是关系代数表达式，\(F_i\) 是一个包含常数和 \(E\) 的模式中的属性的算术表达式

例子

Aggregate Functions and Operations⚓︎

• 聚合函数 (aggregate function)：接受一组值，返回单个值，包括：
  • avg：平均值
  • min：最小值
  • max：最大值
  • sum：求和
  • count：计数

• 聚合运算 (aggregate operation) 的格式为：

  \[ _{G_1, G_2, \dots, G_n} {\Large g}_{F_1(A_1), F_2(A_2), \dots, F_n(A_n)}(E) \]

  其中：

  • \(E\) 是任意的关系代数表达式
  • \(G_1, G_2, \dots, G_n\) 为一组聚集在一起的属性（可以为空）
  • \(F_i\)：聚合函数
  • \(A_i\)：属性名

• 聚合的结果没有名称

  • 可以用重命名操作为结果赋予名称
  • 方便起见，我们将重命名作为聚合运算的一部分，如下面表达式中的 as 子句
  \[ _{G_1, G_2, \dots, G_n} {\Large g}_{F_1(A_1), F_2(A_2), \dots, F_n(A_n) \text{ as new\_name}}(E) \]

例子

Outer Join⚓︎

• 外连接 (outer join) ⟗ 是连接运算的扩展，用于避免信息的缺失
• 先计算连接，然后将来自一个关系中的，但没有与另一个关系有匹配的元组的元组加入到连接结果中

例子

Null Values⚓︎

• 元组中可能存在空值，用 null 表示那些缺失的属性值
• null 表示值是未知的或不存在
• 任何包含 null 的算术表达式的结果为 null
• 聚合函数仅仅忽略 null 值，它也有可能返回 null。我们遵循 SQL 在处理 null 值的语义
• 对于重复的删除 (elimination) 和分组 (grouping)，null 被看作一般的值，并且两个 null 被看作是相同的值
  • 也可以看作不同的值，但前者是 SQL 的规定，我们还是将它们看作相同的值
• 所有包含 null 的比较会返回一个特殊的真值 unknown（未知）
• 关于 unknown 的逻辑运算
  • OR
    • (unknown or true) = true
    • (unknown or false) = unknown
    • (unknown or unknown) = unknown
  • AND
    • (true and unknown) = unknown
    • (false and unknown) = false
    • (unknown and unknown) = unknown
  • NOT: (not unknown) = unknown
  • 当谓词求解得到 unknown，那么选择谓词的结果被看作 false

Modification of the Database⚓︎

可通过删除 (deletion)、插入 (insertion) 和更新 (updating) 运算修改数据库的内容，这些运算都要用赋值运算符表示。

Deletion⚓︎

• 删除请求的表述与查询类似，除了将选择出来的元组展示给用户的操作，变为从数据库中移除这些元组
• 只能删除整一个元组，不能只删除元组中的部分属性
• 用关系代数表示删除：\(r \leftarrow r - E\)，其中 \(r\) 为关系，\(E\) 为关系代数查询

例子

Insertion⚓︎

• 要想在关系中插入数据，我们需要：

  • 指明被插入的元组
  • 编写一个查询，其结果是一组将被插入的元组

• 用关系代数表示插入：\(r \leftarrow r \cup E\)，其中 \(r\) 为关系，\(E\) 为关系代数表达式

• 插入单个元组时，\(E\) 是一个仅包含一个元组的常量关系

例子

Updating⚓︎

• 更新操作可仅改变元组中的某一个值，而无需改变整个元组的值
• 使用广义投影运算来实现：\(r \leftarrow \prod_{F_1, F_2, \dots, F_n}(r)\)
• 其中 \(F_i\) 有两种表示的可能：
  • \(r\) 中没有更新的第 \(i\) 个属性
  • 如果对应属性要更新，那么 \(F_i\) 是一个包含常量和 \(r\) 的属性的表达式，用于将新的值赋给属性

例子

评论区