Formal RQL

Relational Algebra

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

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

Basic Relational-Algebra

Select Operation

选择 (Select) 选出 满足给定谓词的元组

Project Operation

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

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

Set-Union Operation

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

  • 同元的,即 属性数量 相同
  • 对所有的 ir的第i个属性的域s的第i个属性的域 要相同。

Set-Difference Operation

 

Cartesian Product Operation

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

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

n.b. ,即 笛卡尔积 保留了 关系r的元组关系s元组所有可能的串接方式

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

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

Renaming Operation

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


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


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

前面的例子可以 改写

Additional Relational-Algebra

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

Set-Intersection Operation


Natural-Join Operation

自然连接 笛卡尔积选择 的一种 合并

两个关系 不存在 相同属性 时,

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

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


自然连接 满足 结合律

Assignment Operation

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

这非常类似于 PL的赋值

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

Outer-Join Operation

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

共有3种类型:

  • 左外连接
  • 右外连接
  • 全外连接

Extended Relational-Algebra

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

Generalized-Project

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

Aggregate

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


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

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

Tuple Relational Calculus

Definition

元组关系演算形式 如下:

其中 公式公式 中出现的 变量 分为 自由变量受限变量

公式 由 如下的 原子 构成

  • 运算符未定义

  • 5个比较运算符

 

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

  • 原子公式
  • 如果 公式,则 也是 公式
  • 如果 公式,则 以及 均是 公式
  • 如果 是包含 自由元组变量 公式,且 关系,则 也是 公式

 

Example

  • 查询 2009年秋季学期2010年春季学期 这两个学期 都开设所有课程的集合
  • 查询 所有选修了生物系的全部课程的学生

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

 

Expression Security

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

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

进一步地,这是因为我们并没有事先定义 取值范围


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

公式 用于描述 所引用的所有值的集合

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

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


如果 元组关系表达式 结果中的所有值 均来自 ,则称该表达式是 安全的

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

Domain Relational Calculus

Definition

域关系演算形式 如下:

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

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

Example

  • 找出 工资在80000美元以上 的教师的信息
  • 查询 2009年秋季学期2010年春季学期 这两个学期 都开设所有课程的集合
  • 查询 所有选修了生物系的全部课程的学生

Expression Security

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

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

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