Formal RQL

Relational Algebra

关系代数 是一种 过程化查询语言，它以 关系 作为输入，同时输出 关系 。

关系 是定义在一组域 上的 笛卡尔积

Basic Relational-Algebra

Select Operation

选择 (Select) $\sigma$ 选出 满足给定谓词的元组。

Project Operation

投影 (Project) $\Pi$ 选出 指定的属性

由于 关系 不允许 重复元组，所以 投影 运算之后需要再次 对元组进行去重

Set-Union Operation

参与 集合运算 的 两个关系 必须是 相容的 (Compatible)：

• $r$ 和 $s$ 是 同元的，即 属性数量 相同
• 对所有的 i，r的第i个属性的域 与 s的第i个属性的域 要相同。

Set-Difference Operation

Cartesian Product Operation

笛卡尔积 用于 组合/串接 两个 关系。

参与 笛卡尔积 的两个 关系 的 属性名 必须 不同，当存在 同名属性 (Common Attribute) 时，需要添加 关系名前缀 用于 区分。

n.b. $|r \times s| = |r| * |s|$，即 笛卡尔积 保留了 关系r的元组 和 关系s元组 的 所有可能的串接方式。

所得的 结果关系 可能有 某些元组 是 不符合 关系r 和 关系s 所提供的 信息 的。

可以使用下列的 选择运算 来 过滤掉 这些不符合事实的元组

Renaming Operation

更名 (Rename) $\rho$ 用于为 关系代数表达式 提供 可供后续进行引用的标识符。

考虑 查询最高工资 的例子。

任何 更名运算 都是 可替代的。可以使用 位置标记 来 隐含地 引用 关系的属性。如 $1 = 第1个属性

前面的例子可以 改写 为

Additional Relational-Algebra

所有的 附加关系代数运算 都可以用 基本关系运算 来 描述。

Set-Intersection Operation

Natural-Join Operation

自然连接 $\Join$ 是 笛卡尔积 和 选择 的一种 合并。

当 两个关系 不存在 相同属性 时， $r \Join s = r \times s$

自然连接 只不过是 Theta连接 的一个 特例

我们经常需要 笛卡尔积 和 选择 一起使用，那么可以转而使用 Theta连接 来 简化书写

自然连接 满足 结合律。

Assignment Operation

赋值运算 $\gets$ 用于将 关系代数表达式 存储为 常量，以便后续的 引用 。

这非常类似于 PL的赋值

n.b. 赋值运算 必须 赋值 给 临时变量，而不能直接 赋值 给 永久关系，否则将造成对 数据库的修改。

Outer-Join Operation

外连接运算 可以处理 缺失的信息。

共有3种类型：

• 左外连接 $\sqsupset \Join$
• 右外连接 $\Join \sqsubset$
• 全外连接 $\sqsupset \Join \sqsubset$

Extended Relational-Algebra

不同于 附加关系代数，拓展关系代数 不能用 基本关系代数 来 描述。

Generalized-Project

广义投影 (Generalized Project)：可以对 投影的属性 进行 常量运算

Aggregate

聚集运算 (Aggregate Operation) 的输入是 值的集合，输出 单个值。

上面例子给出 查询所有系的教师的平局工资 和 查询每个系的教师的平均工资 的例子。

当 省略左侧分组 时，默认为：将 输入关系的所有元组 分组 为 唯一的一组

Tuple Relational Calculus

Definition

元组关系演算 的 形式 如下：$\s{t | P(t)}$

其中 $P$ 为 公式。公式 中出现的 变量 分为 自由变量 和 受限变量。

公式 由 如下的 原子 构成：

• $t \in r$

  $\notin$ 运算符未定义

• $t_1[x] \Theta t_2[y]$

  $\Theta$ 为 5个比较运算符

• $t[x] \Theta c$

公式 可以由 如下的 规则 来 构造：

• 原子 是 公式
• 如果 $P_1$ 是 公式，则 $\neg P_1$ 和 $(P_1)$ 也是 公式
• 如果 $P_1$ 和 $P_2$ 是 公式，则 $P_1 \or P_2$ ，$P_1 \and P_2$ 以及 $P_1 \implies P_2$ 均是 公式
• 如果 $P_1(t)$ 是包含 自由元组变量 $t$ 的 公式，且 $r$ 是 关系，则 $\exists t \in r(P_1(t))$ 和 $\forall t \in r (P_1(t))$ 也是 公式

Example

• 查询 2009年秋季学期 或 2010年春季学期 这两个学期 都开设 的 所有课程的集合

• 查询 所有选修了生物系的全部课程的学生

n.b. 红色部分 可以正确处理 当生物系没有开设任何课程 的情况

Expression Security

考虑如下的 元组关系表达式

我们称 该表达式 是 不安全的表达式。原因在于：neg 会产生 无限的结果。

进一步地，这是因为我们并没有事先定义 $instructor$ 的 取值范围。

为了解决上述问题，我们引入 域 (Domain) 的概念：

公式 $P$ 的 域 $dom(P)$ 用于描述 $P$ 所引用的所有值的集合：

• $P$ 自身所用到的值
• $P$ 中涉及的关系的元组中所出现的值

即：P的域 = P中显式出现的值 +名称出现在P中的那些关系的所有值

如果 元组关系表达式 $\s{t | P(t)}$ 结果中的所有值 均来自 $dom(P)$，则称该表达式是 安全的。

安全的表达式 必定包含 有限个结果

Domain Relational Calculus

Definition

域关系演算 的 形式 如下：$\s{<x_1,x_2,\cdots,x_n> | P(x_1,x_2,\cdots,x_n)}$

域关系演算 由 如下的 原子 构成：

• $<x_1,x_2,\cdots,x_n> \in r$
• $x \Theta y$
• $x \Theta c$

公式 的 构造规则 类比 元组关系演算。

Example

• 找出 工资在80000美元以上 的教师的信息

• 查询 2009年秋季学期 或 2010年春季学期 这两个学期 都开设 的 所有课程的集合

• 查询 所有选修了生物系的全部课程的学生

Expression Security

我们使用与 元组关系演算 同样的策略来解决 表达式安全性问题：引入 域 的概念

下面几种 语言 在 表达能力 上是 等价的：

• 基本关系代数
• 安全的元组关系演算
• 安全的域关系演算