第 9 章 关系
# 第 9 章 关系
# 9.1 关系及其性质
# 9.1.1 引言
可以用两个相关元素构成的有序对来表达两个集合的元素之间的关系
#
二元关系的定义
# 9.1.2 函数作为关系
函数表示了一种关系
- 即对于
中的每个元素恰好只有一个 中的元素与之相关 - 其中
为定义域, 为陪域
- 其中
- 关系是函数的一般表示,可以用关系表示集合之间更为广泛的联系
# 9.1.3 集合的关系
#
集合上的关系
# 9.1.4 关系的性质
#
自反性
#
对称性与反对称性
- 对称与反对称的概念不是对立的, 因为一个关系可以同时有这两种性质或者两种性质都没有
#
传递性
# 9.1.5 关系的组合
#
关系的合成
#
关系的幂
#
传递性与关系的幂
# 9.2 n 元关系及其应用
# 9.2.1 引言
可以用 n 元关系来表示关系型数据库
# 9.2.2 n 元关系
#
n 元关系的定义
# 9.2.3 数据库和关系
数据库由记录组成, 这些记录是由域构成的 n 元组
- 用于表示数据库的关系也称为表, 因为这些关系常常用表来表示
- 表中的每个列对应于数据库的一个属性
学生数据库的示列
# 9.2.4 n 元关系的运算
#
选择运算
-
- 在
元关系中确定满足特定条件的所有 元组
- 在
#
投影运算
-
- 可用于删除关系中每条记录中相关的域
#
连接运算
-
- 当两个表中具有某些相同的域时, 连接运算可将这两个表合成一个表
# 9.2.5 SQL
数据库查询语言 SQL(Structured Query Language, 结构化查询语言), 可以用来实现本节所描述的运算
注意:SQL 使用 SELECT
表示一个投影, 而不是一个选择运算
# 9.2.6 数据挖掘中的关联规则
以商场购物为示例进行说明
- 主要用途是根据用户已经购买的商品来预测用户是否会购买某个特定的商品
#
支持度(support) 的定义
-
- 商店里的每一件商品都称为项
是所有项的集合 - 则项集
是 的子集
是一组事务的集合 - 事务可以理解为购物篮或者购物记录
- 一个事务可以包含多个项集
- 商店里的每一件商品都称为项
#
关联规则的支持度和置信度(confidence)
-
- 关联规则就是 形如
的蕴含式, 其中 和 是 的不相交的子集 - 关联规则
的支持度是指在 中,同时包含 和 的事务的概率 - 关联规则
的置信度是指在包含 的事务集合中,包含 的概率
- 关联规则就是 形如
数据挖掘中的一个重要问题是寻找强关联规则
- 这些规则的
- 支持度大于或等于最小支持度
- 置信度大于或等于最小置信度
# 9.3 关系的表示
# 9.3.1 引言
个人理解
- 用矩阵表示关系有助于计算机计算
- 用图表示关系,有助于人理解和分析
# 9.3.2 用矩阵表示关系
用 0-1 矩阵表示一个有穷集之间的关系
定义在单个集合上的关系矩阵是一个方阵,可以用这个方阵确定关系是否具有某种性质
布尔运算也可用在两个关系矩阵的运算上
# 9.3.3 用图表示关系
#
有向图的定义
表示关系的有向图可以用来确定关系是否具有各种性质
# 9.4 关系的闭包
# 9.4.1 引言
重点
- 闭包的定义
- 关系的传递闭包
- 连通性关系
- 传递闭包的计算
- 沃舍尔算法
# 9.4.2 不同类型的闭包
#
闭包的定义
-
闭包即是在关系图中加入最少的连接线,使得新得到的关系具有某种性质
自反闭包
对称闭包
构造关系的传递闭包比构造它们的自反闭包或对称闭包更复杂
- 关系的传递闭包可以通过增加那些一定会出现的有序对来得到, 不断重复这个过程, 直到没有新增加的有序对为止
- 后面的章节即是为了说明如何构造关系的传递闭包
# 9.4.3 有向图中的路径
#
有向图中的路径的定义
- 有向图的一条路径可以多次通过一个顶点
- 有向图的一条边也可以多次出现在一条路径中
#
有向图中的路径与关系的幂
-
- 证明可以使用数学归纳法
# 9.4.4 传递闭包
#
连通性关系的定义
#
关系的传递闭包和相关的连通性关系是等同的
#
引理 941
-
- 结合 有向图中的路径与关系的幂的关系 和 关系的传递闭包和相关的连通性关系是等同的 可以简化
的计算
- 结合 有向图中的路径与关系的幂的关系 和 关系的传递闭包和相关的连通性关系是等同的 可以简化
#
连通性关系关系矩阵的计算
- 可由 引理 941 推出
计算传递闭包的算法
- 原理是 连通性关系关系矩阵的计算
- 时间复杂度为
- 共需
次比特运算
- 共需
# 9.4.5 沃舍尔算法
内部顶点
0-1 矩阵的含义
迭代计算 0-1 矩阵的方法
#
引理 942
沃舍尔算法的时间复杂度
- 为
,需要 次比特运算
# 9.5 等价关系
# 9.5.1 引言
等价关系的应用
- 当编译器要检查两个变量是否相同时,对字符的数最就有限制
- 其会把所有字符串的集合分成多个类, C 编译器认为在特定类中的所有字符串是相同的
- 当我们仅关心一个整数被4整除的余数时,我们只需要知道它在哪个等价类而不必知道它的特定值
# 9.5.2 等价关系
#
等价关系的定义
#
等价元素的定义
-
- 最常使用的等价关系是模
同余关系
- 最常使用的等价关系是模
# 9.5.3 等价类
#
等价类,代表元的定义
- 此处翻译有误,应为
的关于 的等价类记为
模 m 同余类
- 整数
模 的同余类记作 ,满足
# 9.5.4 等价类与划分
#
定理 951
- 证明方法参照 证明一组命题等价
集合的划分
等价类构成的集合的划分
- 上述两个结论证明了等价类构成了
的划分
#
定理 952
# 9.6 偏序
# 9.6.1 引言
#
偏序和偏序集的定义
符号约定
#
可比与不可比
#
全序集的定义
#
良序集的定义
#
良序归纳定理
-
- 不需要基础步骤,基础步骤可以使用空证明来证明
# 9.6.2 字典顺序
笛卡尔积上字典顺序的定义
字符串上的字典顺序
# 9.6.3 哈塞图
哈塞图的构造过程
覆盖关系的定义及其与哈塞图的关系
# 9.6.4 极大元与极小元
极大元与极小元的定义
- 一个偏序集可以有多个极大元和多个极小元
最大元与最小元的定义
- 最大元或最小元,如果存在,则一定是唯一的
偏序集子集的上界与下界的定义
偏序集子集的最小上界和最大下界
# 9.6.5 格
格的定义
-
- 即每对元素组成的子集都有最小上界与最大下界
# 9.6.6 拓扑排序
拓扑排序即是从一个偏序构造一个相容的全序
- 全序的定义
- 偏序相当于是其相容的全序的子集
#
引理 961
拓扑排序算法
- 由 引理 可以得到拓扑排序算法
- 拓扑排序算法可以用来对任务进行排序