关系代数

关系代数的应用解过程

关系代数:

  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$