DB-KEY

关系代数

关系代数的应用解过程

关系代数:

1. 确定查询目标
2. 明确查询条件
3. 选择查找路径， 确定操作对象
4. 关系的合并: 据3, 联结
5. 元组的选择: 据2, 条件
6. 属性的指定: 据1, 投影

第八章

概述

• 关系模式设计: 同一个关系数据库系统 有 多种不同的关系模式设计方案
• 好的设计方案: 既有合理的数据冗余度, 又没有插入和删除操作异常
• 不同设计结果有区别的原因: 函数依赖(属性间的语义相关性)不同
• 关系的规范化
  • 按照给定范式要求设计关系模式
  • 范式: 对一个关系中允许存在的函数依赖的要求

    规范化理论

    函数依赖

• 函数依赖: 一个关系中 两组属性之间的 取值约束
  • 表示: $X\to Y$: $Y$函数依赖于$X$
  • 直观: 在关系$R$中, 每个$X$的值都有唯一的一个$Y$值与之对应
  • 定义: 关系模式$R(U)$中, 关系$r$中元组$r_i$在$X$中的取值确定后, $Y$中取值必被确定, 则$X\to Y$
  • $X$决定因素, $Y$依赖因素
• 发现函数依赖
  • 直接根据语义
  • 根据取值对应关系
    • 一一对应: $X\to Y$, $Y\to X$
    • 一多对应/多一对应: $Y\to X$, $X\to Y$
    • 多多对应: 没有
• 平凡函数依赖
  • 非平凡函数依赖: $X\to Y, Y\not\subseteq X$, 默认是这个
  • 平凡函数依赖: 反之
• 完全函数依赖
  • 完全函数依赖: $X\to Y, \forall X’\subset X, X’\not\to Y$, 则$X\overset{f}{\to}Y$
  • 部分函数依赖: $X\to Y, \exists X’\subset X, X’\to Y$, 则$X\overset{p}{\to}Y$
• 传递函数依赖
  • $X\to Y, Y\not\subset X, Y\not\to X, Y\to Z$, 则 $X\to Z$为传递函数依赖
• Armstrong公理系统
  • 基本规则
    • 自反规则: $Y\subseteq X$, 则$X\to Y$
    • 增广规则: $X\to Y$, 则$XZ\to YZ$
    • 传递规则: $X\to Y\wedge Y\to Z$, 则$X\to Z$
  • 扩充规则
    • 分解规则: $X\to YZ$, 则$X\to Y\wedge X\to Z$
    • 合并规则: $X\to Y\wedge X\to Z$则$X\to YZ$
    • 伪传递规则: $X\to Y\wedge WY\to Z$, 则$WX\to Z$
• 函数依赖的逻辑蕴含概念
  • $F$为关系模式$R(U)$的一个函数依赖集
  • 从已有的函数依赖出发, 利用公理系统可以推导出$X\to Y$, 则$F\vDash X\to Y$
• 函数依赖集$F$的闭包$F^+$: $F^+=\{X\to Y|F\vDash X\to Y\}$
• 函数依赖集的等价
  • 可以互相推导出其中的函数依赖
• 最小函数依赖集
  • 与$F$等价的, 最小的集合
  • [解题] 寻找最小依赖集
    • 首先得到题目中的所有函数依赖, 分解成右端只有一个的依赖
    • 画箭头图, 用那堆公理尽可能减少集合大小
    • 合并依赖
• 属性集$X$在函数依赖集$F^+$上的闭包$X_F^+$: $X_F^+=\{A|F\vDash X\to A\}$
  • [解题] 计算闭包
    • $X^+=X$
    • 不断重复: 对每一个$F$中的依赖$Y\to Z$, 若$Y\subseteq X^+$, 则$X^+ = X^+ \cup Z$
    • 直到不再变化
• 关键字
  • 若$K\subseteq U, K\overset{f}{\to}U$, 则$K$是$R$的关键字
  • 主属性集: 所有关键字中的属性构成的集合
  • 非主属性集: 不属于任何一个关键字的属性构成的集合
  • 关键字与闭包: $K_F^+=U$, $\forall Z\subset F, Z_F^+\ne U$
  • [解题] 寻找关键字
    • 计算最小依赖集
    • 不断重复从$U$中删除属性, 直到其闭包不等X于$U$
    • 将得到一个关键字
    • 技巧
      • 只在左边出现过的属性 属于 每一个关键字
      • 只在右边出现过的属性 不属于 任何一个关键字
      • 只需要对两边都有的属性尝试删除即可

        与函数依赖有关的范式

• 模式分解
  • 分解结果: 子关系模式, 满足
    • $\textrm{Head}(R)=\bigcup^n\textrm{Head}(R_i)$
    • $F_i=\{X\to Y|X\to Y\in F^+ \wedge (X\cup Y)\in \textrm{Head}(R_i)\}$
  • 分解方法
    • 找出所有不满足范式的依赖
    • 选择一个依赖, 设$X\overset{f}{\to}Y$为这个依赖, 则将这个依赖所在的关系$R$分解为
      • $R_1=\{X\cup Y, \{X\to Y\}\}$
      • $R_2=\{\textrm{Head}(R)-Y, F_2\}$
      • 其中$F_2=\{A\to B|A\to B\in F^+\wedge (A\cup B)\subseteq \textrm{Head}(R_2)\}$
• 1NF: 属性值不可分割, 全都满足
• 2NF: 满足1NF, 每个非主属性都完全依赖于关键字
  • 检查:
    • 找到所有非主属性 和 所有候选关键字
    • 检查每一个非主属性$A$和每一个候选关键字$K$之间的函数依赖, 看看有没有部分依赖
• 3NF: 满足2NF, 每个非主属性都不传递依赖于关键字
  • 检查: 不满足3NF, 则必然存在下列情况之一, 其中$X\overset{f}{\to} Y$
    • $X$是某个关键字的真子集
    • $X$不是关键字
• BCNF: 满足1NF, 若$X\to Y$则$X$必含有该模式的关键字
  • 检查: 每个函数依赖, 是否满足$X$是关键字
• BCNF -> 3NF

  多值依赖与第四范式

• 多值依赖: $X\to\to Y$
  • 定义: 对$X$的一个取值, 存在一组$Y$与其对应; $Y$的取值与$U-X-Y$不相关
  • 成因: 两个一对多关系$C\to T$, $C\to L$, 其合并后$T$与$L$就是多值依赖
  • 平凡多值依赖
    • 非平凡多值依赖: $U-X-Y$不为空集
    • 平凡多值依赖: 反之
• 多值依赖有关的推理规则(需要掌握)
  • 求补规则: 若$X\to Y$, 则$U-X-Y$
  • 转换规则: 若$X\to Y$, 则$X\to\to Y$
• 4NF
  • 定义: 若$X\to\to Y$是非平凡多值依赖, 则$X$必含有关键字
  • 特点: 函数依赖需要满足BCNF; 不是函数依赖的多值依赖只有平凡多值依赖

    模式分解的研究

• 无损联结性
  • 设$\rho=\{R_1,\cdots,R_k\}$是对$R$的一个分解
  • 如果对每个满足$F$的关系实例$r$都满足$r=\pi_{R_1}(r)\Join\cdots\Join\pi_{R_k}(r)$
  • 则$\rho$是无损联接分解
  • 充要条件($\rho=\{R_1,R_2\}$)
    • $R_1\cap R_2\to (R_1-R_2)$ 或 $R_1\cap R_2\to (R_2-R_1)$
• 依赖保持性
  • 表示$\pi_Z(F)=\{X\to Y|X\to Y\in F^+\wedge (X\cup Y)\subseteq Z\}$
  • $F^+=(\pi_{R_1}(F)\cup\cdots\cup\pi_{R_1}(F))^+$

    到3NF的分解方法

• 计算最小依赖集, 代替$F$进行分解
• $S=\emptyset$
• 对每一个函数$X\to Y$依赖进行
  • 若在$S$中找不到子关系模式$Z$, 使得$X\cup Y\subseteq\textrm{Head}(Z)$
  • $X$和$Y$合并成新的子关系模式, 加入$S$
• 如果$R$中的每个候选关键字$K$均不在$S$中, 则任选一个关键字, 其属性单独构成一个子关系模式, 加入$S$