本节内容

  • 关系模式
  • 函数依赖
  • 范式
  • 逻辑蕴含与armstrong公理
  • 属性集闭包
  • 函数依赖的最小覆盖
  • 无损连接分解与保持函数依赖的分解

关系模式

关系模式:关系模式是一个五元组 R(U,D,DOM,F),简记为 R<U, F>。

  • R:关系名
  • U:组成该关系的属性名集合
  • D:属性组U中属性所来自的域
  • DOM:属性到域的映射
  • F:属性间的依赖集合。它限定了组成关系的各个元组必须满足的完整性约束条件

当且仅当U上的一个关系r满足F,r称为关系模式R<U, F>的一个关系

关系模式的设计问题

  1. 信息的不可表示问题:插入异常、删除异常
  2. 信息的冗余问题:数据冗余、更新异常

函数依赖 ★

设R(U)是属性集U上的关系模式,X , Y 为 U 的子集,r是R(U)上的任意一个关系,如果总有:

 t,sr, t[X]=s[X] t[Y]=s[Y]\forall \ t,s \in r, \ t[X] = s[X] \Rightarrow \ t[Y] = s[Y]

那么称“X函数决定Y”,或“Y函数依赖于X”,记作

XYX \rightarrow Y

说明

  • 任意两元组,若在X属性上取值相同,则Y属性上取值也一定相同。
  • 不存在两个X属性值相同但Y属性值不同的两个元组。

平凡函数依赖

在R(U)中,若

XY,YXX \rightarrow Y, Y \subseteq X

则称Y平凡函数依赖于X

部分函数依赖

在R(U)中,若

XY, XX (XX), XYX \rightarrow Y, \ \forall X' \subseteq X \ (X' \neq X), \ X' \nrightarrow Y

则称Y完全函数依赖于X,记为

XfYX \stackrel{f}{\longrightarrow} Y

否则称Y部分函数依赖于X,记为

XpYX \stackrel{p}{\longrightarrow} Y

传递函数依赖

在R(U)中,若

XY,YZ,YX,Z⊄YX \rightarrow Y, Y \rightarrow Z, Y \nrightarrow X, Z \not\sub Y

则称Z传递函数依赖于X

  • 候选码:K为 R<U, F> 的属性组,若 ,则称K为R的候选码
  • 超码:K为 R<U, F> 的候选码,X为 R<U, F> 的属性组,若 ,则称X为R的超码
  • 主码:选定的候选码
  • 主属性:包含在每一个候选码中的属性
  • 全码:整个属性组U

范式 ★

1NF:关系中每一分量不可再分

不良特性

有关系模式 S(S# , SN , SD , DEAN , C# , G)

  • 插入异常:如果学生没有选课,关于他的个人信息及所在系的信息就无法插入
  • 删除异常:如果删除学生的选课信息,则有关他的个人信息及所在系的信息也随之删除了
  • 更新异常:如果学生转系,若他选修了k门课,则需要修改k次
  • 数据冗余:如果一个学生选修了k门课,则有关他的所在系的信息重复

2NF:R属于1NF,且每个非主属性完全依赖于码

2NF消除了非主属性对码的部分依赖

单主属性不存在部分函数依赖,即一个属性组成的属性集X,若Y依赖于X,则一定为完全函数依赖

不良特性

有关系模式 S_SD(S# , SN , SD , DEAN)

  • 插入异常:若系中没有学生,则与系有关的信息就无法插入
  • 删除异常:如果学生全部毕业了,则在删除学生信息的同时与系有关的信息也随之删除了
  • 更新异常:如果学生转系,不但要修改SD,还要修改DEAN,如果换系主任,则该系每个学生元组都要做相应修改
  • 数据冗余:每个学生都存储了所在系的系主任的信息

3NF:在满足2NF的条件下消除非主属性对码的传递函数依赖

不良特性

STC(S# , T# , C#),T# -> C#,每位老师只教授一门课;
(S#,C#)-> T#, 某学生选定一门课,就对应一位老师;
(S#,T#)-> C#;
(S#,T#),(S#,C#)为候选码。

  • 插入异常:如果没有学生选修某位老师的任课,则该老师担任课程的信息就无法插入
  • 删除异常:删除学生选课信息,会删除掉老师的任课信息
  • 更新异常:如果老师所教授的课程有所改动,则所有选修该老师课程的学生元组都要做改动
  • 数据冗余:每位学生都存储了有关老师所教授的课程的信息

BCNF:关系模式R<U, F>中,对于属性组X、Y,当

XY, Y⊄XX \to Y, \ Y \not\sub X

时(即存在X到Y的非平凡函数依赖),X 必含有码(即X是超码)。

属于BCNF的关系一定属于3NF,反之不一定成立;若R属于3NF,且R只有一个候选码,则R属于BCNF

Armstrong 公理系统

逻辑蕴含

关系模式R,F是其函数依赖,X,Y是其属性子集,如果从F的函数依赖能够推出X -> Y,则称F逻辑蕴涵X -> Y,记作F├ X -> Y 。

F的闭包:被F所逻辑蕴涵函数依赖的全体所构成的集合称作F的闭包,记作F+ = {X -> Y | F├ X -> Y}

Armstrong 公理

若X,Y,Z是属性集,则下列规则成立:

自反律(reflexivity):

YXXYY \sube X \Rightarrow X \to Y

增广律(augmentation):

XYXZYZX \to Y \Rightarrow XZ \to YZ

传递律(transitivity):

XY, YZXZX \to Y, \ Y \to Z \Rightarrow X \to Z

推理规则:

合并律

XY, YZXYZX \to Y, \ Y \to Z \Rightarrow X \to YZ

分解律

XYZXY, YZX \to YZ \Rightarrow X \to Y, \ Y \to Z

伪传递律

XY, WYZWXZX \to Y, \ WY \to Z \Rightarrow WX \to Z

引理一

XA1A2AkXAi (i=1,2,,k)X \to A_1A_2\cdots A_k \Rightarrow X\to A_i \ (i=1, 2,\cdots ,k)

属性集的闭包★:XF+ 为属性集X关于F函数依赖集的闭包

XF+={AXA Armstrong}X^+_F = \{ A | X \to A \ 能由 Armstrong 公理导出 \}

计算属性集的闭包:
image-20210703182809986

引理二★:

XA Armstrong    AXF+X \to A \ 能由 Armstrong 公理导出 \iff A \sube X_F^+

用途

  • 判断X是否为超码/候选码:X->U是否成立(超码),X的真子集是否决定U(候选码)
  • ★ 判断 F是否逻辑蕴涵 X->Y :即判断 Y 是否包含于 XF+

函数依赖的等价与最小覆盖 ▲

等价性:函数依赖集F,G,若F+=G+,则称F和G等价。

最小覆盖Fmin:

  1. (右侧)单属性化
  2. (左侧)既约化
  3. 无冗余化

模式分解

关系模式R<U , F>的一个分解是指

ρ={R1<U1,F1>,R2<U2,F2>,,Rn<Un,Fn>}\rho = \{ R_1<U_1, F_1>, R_2<U_2, F_2>, \cdots, R_n<U_n, F_n> \}

其中:

U=i=1nUi ,  UiUj (1i,jn)U=\bigcup_{i=1}^n U_i \ , \ 没有 \ U_i \sube U_j \ (1 \leq i,j \leq n)

Fi是F在Ui上的投影

分解的基本代数运算:投影,自然连接

分解的目标:无损连接分解,保持函数依赖,达到更高级范式

无损连接分解

无损连接分解的充要条件

ρ={R1,R2}     R1R2R1R2 or R2R1\rho = \{R_1, R_2\} \ 为无损连接分解 \iff R_1 \cap R2 \to R_1 - R_2 \ or \ R_2 - R_1

保持函数依赖的分解

ρ={R1,R2,,Rn} \rho = \{R_1, R_2, \cdots , R_n\} \ 为保持函数依赖的分解

    F+=(i=1nΠRi(F))+\iff F^+ = (\bigcup_{i=1}^n \Pi_{R_i} (F))^+

    F(i=1nFi)+\iff F \sube (\bigcup_{i=1}^n F_i)^+

判定方法:如果没有给定F1,F2,……,Fn,先求之。求所有模式的依赖集的并集

G=i=1nFiG = \bigcup_{i=1}^n F_i

对F中所有函数依赖X -> Y,检查是否在G+中,即判断Y是否在XG+中。


[例] 设关系模式R(ABCD),在R上有两个相应的函数依赖集及分解:F ={A→B,B→C, C→D},ρ={AB,ACD}回答下列问题:

  1. 确定R的码
  2. ρ是否无损分解;
  3. ρ是否保持函数依赖;
  4. 确定ρ中每一模式的范式级别

[解]

(1) AF+=ABCD, BF+=CD, CF+=BCD, DF+=D。故A是码。

(2)ρ是无损分解

ABACD=A, ABACD=B,ABAB \cap ACD = A,\ AB-ACD = B, A\to B 成立

(3)ρ不保持函数依赖

F1={AB}, F2={AC,AD,CD}, G=F1F2F_1 = \{ A\to B \}, \ F_2 = \{ A\to C, A\to D, C\to D \}, \ G = F_1 \cup F_2

BCF,BG+=B,C∉BG+, BC∉G\because B\to C \in F, B_G^+=B, C\not\in B_G^+, \ \therefore B\to C \not\in G

(4)

R1BCNF, R22NFR_1 \in BCNF , \ R_2 \in 2NF

R2中 D 传递依赖于 A。


模式分解算法(略)