数据库关系代数操作,函数依赖,属性集的闭包——总结自《数据库系统基础教程》

论坛 期权论坛 脚本     
匿名技术用户   2021-1-14 14:27   11   0

描述关系代数操作前,简要回顾一些基础概念。


以一张简单的表(表1)为例,包含名字、年龄、学号信息。

表1. Students
nameagenumber

小明

13b001
小红14c012
小刚12a003
  • 属性——关系的列,即表中的“name”“age”“number”三列
  • 元组——除属性名(表头)外的其他每一行,如(小明, age, number)就是一个元组

一、关系代数操作

  1. 常见操作:交、并、差
  2. 除去某些行或列的操作:选择、投影
  3. 组合两个关系元组的操作:连接、笛卡尔积
  4. “重命名”操作:更改属性名称、关系名称

选择——满足一定条件的元组集合,记为σc(R)σc(R)

其中,c为条件,R为关系。举例说明:σ age>12(Students),即选择age大于12的所有元组,得到结果为

name

agenumber

小明

13b001
小红14c012

投影——选择部分列,记为π a1,a2,a3(R)

表示只包含关系R中的a1,a2,a3列。举例说明:π name,age (Students)只包含name和age列,得到的结果为

nameage

小明

13
小红14
小刚

12

笛卡尔积——两个关系的叉积

自然连接——两个关系满足某些属性相配的所有元组配对集合,记为RS

属性配对并合并相同属性。举例说明:City为表2,与Students有共同属性name,自然连接StudentsCity的结果如表3所示。

表2. City
namecitygrade

小明

武汉10
小红鄂州15
小刚黄石13
表3. 自然连接
nameagenumbercitygrade

小明

13b001

武汉

10
小红14c012鄂州15
小刚12a003黄石13

可以看到属性name相同的元组(行)配对了起来。

θ连接——所有满足一定条件的元组配对,所有属性保留,记为RcS

其中c为条件,该连接的结果这样来构造

  1. 先得到R和S的积
  2. 在得到的关系中找到所有满足条件c的元组

该连接与自然连接不同在于:

  1. 自然连接要求两个关系有公共属性,属性值相同才进行配对,而θ连接指任意条件,可以不同属性之间进行配对。
  2. 自然连接后公共属性合并了(只保留一个),θ连接后所有属性都保留。

以表1、表2为例说明,Students age > grade City,其中条件c为age > grade 。结果如表4所示(表名简写为S和C)。

表4. θ连接
S.nameagenumberC.namecitygrade

小明

13b001小明

武汉

10
小红14c012小明武汉10
小红14c012小刚黄石13
小刚12a003小明武汉10

可以看到S和C的name属性都还包含其中,只有满足age > grade的元组配对才保留了下来。


二、 函数依赖

函数依赖、平凡函数依赖、非平凡函数依赖、完全函数依赖、部分函数依赖、传递函数依赖

函数依赖——属性集合X唯一决定属性集合Y,记为X —> Y

定义:若关系R的两个元组在属性A1, A2, ..., An上一致,则它们必定在B1, B2, ... , Bn上也一致,记为

A1, A2, ..., An —> B1, B2, ... , Bn

示例:如表4中若学号number确定,则S.name和age也能根据number确定下来,若number为c012,虽然有两条记录,但是S.name只能是小红,age也必定是14。

平凡函数依赖——子集与原集有函数依赖关系

A1, A2, ..., An —> B1, B2, ... , Bn ,其中{B1, B2, ... , Bn } 是{A1, A2, ..., An}的子集。

示例:表1为例,{number, name} —> {name},知道学号和名字,肯定能确定名字,而名字(右属性集)是左属性集的子集,这种依赖称作平凡函数依赖。

非平凡函数依赖——不是子集,但是有函数依赖关系

A1, A2, ..., An —> B1, B2, ... , Bn ,其中{B1, B2, ... , Bn } 不是{A1, A2, ..., An}的子集。

最常见的依赖关系,如{number} —> {name, age}

完全函数依赖——可理解为最小函数依赖

属性集合Y完全依赖于X,属性集X刚好能完全确定Y的所有属性,X少一个属性就不能确定Y的所有属性。

如在表4里,所有属性的集合完全依赖于{number,C.name}。number和C.name能确定所有属性,但是只有一个number的时候只能确定前面列的S.name和age,不能确定后面的city和grade,而只有一个C.name时也不能确定前面的age。

传递函数依赖——X—>Y,Y—>Z,则有X—>Z


三 、 属性集的闭包

个人理解:属性集的闭包就是由该属性集合能确定的所有属性的集合

eg:考虑属性A,B,C,D,E,F的关系,假设此关系有函数依赖:AB -> C, BC -> AD, D -> E, CF -> B, 那么{A, B}的闭包{A, B}+为?
步骤:BC -> AD 分解为 BC -> A 和 BC -> D,从X = {A, B}出发,AB -> C,把C加入X,得到{A, B, C},再由 BC -> D,加入D,由D -> E,加入E,得到X为{A, B, C, D, E},F确定不了,终止。得到闭包为{A, B, C, D, E}。

闭包的作用----能判断(属性集A与属性集B是否含依赖关系){A1, A2 ... An} -> {B1, B2 ... Bm}是否成立,若B是A的闭包的子集,则推断成立。

求闭包的算法:

输入:属性集合{A1, A2 ... An},函数依赖(FD)的集合S

输出:闭包{A1, A2 ... An}+

  1. 分解S中的FD,使每个FD的右边只有一个属性;
  2. 设X为闭包结果,将X初始化为{A1, A2 ... An};
  3. 重复过程:寻找FD:B1, B2, ...Bn —> C,使得{B1, B2, ...Bn}是{A1, A2 ... An}的子集,且C不在{A1, A2 ... An}中。若找到把C加入X。直到找不到这样的FD。最终没有任何属性能加入到X,步骤结束;
  4. 步骤3结束时,得到的X即为闭包{A1, A2 ... An}+。
分享到 :
0 人收藏
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:7942463
帖子:1588486
精华:0
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP