四、关系数据理论

4.1 规范化理论

  • 关系的规范化：按照一定的规范设计的关系模式，将结构复杂的关系分解成结构简单的关系，从而把不好的关系数据库模式转变成为好的关系数据库模式
  • 简化的关系模式：$ R(U,F) $，其中$ U $为组成该关系的属性名集合，$ F $为属性间数据的依赖关系集合

4.2 函数依赖（FD）

  • 设$ R(U) $是属性集$ U $上的关系模式，$ X $, $ Y\subseteq U $， $ r $是$ R(U) $上的任意一个关系，如果有对$ \forall t,s\in r $，若$ t[X] = s[X] $，则$ t[Y] = s[Y] $，那么称X函数决定Y，或Y函数依赖于X，记作$ X\rightarrow Y $，并称$ X $为决定因素

  • 函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件

  • 若$ X\rightarrow Y $且$ Y\rightarrow X $，则$ X\leftrightarrow Y $

  • 若$ Y $不函数依赖于$ X $，则$ X\nrightarrow Y $

  • 平凡函数依赖：如果$ X\rightarrow Y $且$ Y\subset X $，则称为平凡函数依赖

  • 非平凡函数依赖：如果$ X\rightarrow Y $且$ Y\nsubseteq X $，则称为非平凡函数依赖

  • 若不特别声明，我们讨论的都是非平凡的函数依赖

  • 部分函数依赖：如果$ X\rightarrow Y $，且对于任意$ X $的真子集$ X' $，有$ X'\nrightarrow Y $，则称$ Y $对$ X $完全函数依赖，记作$ X{\stackrel{f}\rightarrow}Y $，否则称$ Y $对$ X $部分函数依赖，记作$ X{\stackrel{p}\rightarrow}Y $

    只有当决定因素是组合属性时，讨论部分函数依赖才有意义

    当决定因素是单属性时，只能是完全函数依赖

    例如，在关系模式$ S(SNO,SN,AGE,DEPT) $，决定因素为单属性$ SNO $，有$ SNO (SN,AGE,DEPT) $，不存在部分函数依赖

  • 传递函数依赖：如果$ X\rightarrow Y $，$ Y\rightarrow Z $，$ Y\nrightarrow X $，$ Y\nsubseteq X $，则称$ Z $对$ X $传递函数依赖

  • 候选码：设$ K $为$ R(U,F) $的属性或属性组合，若$ K\stackrel{f}\rightarrow U $，则称$ K $为$ R $的候选码

  • 主属性：任何一个候选码中的属性称作主属性

  • 主码：从一个关系的多个候选码中选定一个作为主码

  • 超码：某个属性组合，其存在一个子集是候选码

4.3 范式

  • $ 1NF $
    • 关系中每一分量在语义上不可再分
    • 即不能以集合、数组、序列、结构体等作为属性值
  • $ 2NF $
    • 若$ R\in 1NF $，且每个非主属性完全依赖于码，则称$ R\in 2NF $
    • 该范式消除了非主属性对码的部分依赖
    • 采用投影分解法将一个$ 1NF $的关系分解为多个$ 2NF $的关系
    • 将一个$ 1NF $关系分解为多个$ 2NF $的关系，并不能完全消除关系模式中的各种异常情况和数据冗余
  • $ 3NF $
    • 关系模式$ R(U,F) $中，若不存在这样的码$ X $、属性组$ Y $及非主属性$ Z $（$ Z\nsubseteq Y $），使得$ X\rightarrow Y $，$ Y\nrightarrow X $，$ Y\rightarrow Z $成立，称$ R\in 3NF $
    • 每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码
    • 该范式消除了非主属性对码的传递依赖
  • $ BCNF $
    • 设$ R\in 1NF $，若对于$ R $的每个函数依赖$ X\rightarrow Y $，若$ Y $不属于$ X $，则$ X $必包含候选码，那么$ R\in BCNF $
    • 该范式消除了主属性对码的传递依赖或部分依赖
    • 如果$ R\in 3NF $，且$ R $只有一个候选码，则$ R\in BCNF $

4.4 函数依赖的公理系统

  • 逻辑蕴涵：已知关系模式$ R $，$ U $是属性集全体，$ F $是其函数依赖，$ X $，$ Y $是其属性子集，对于任何一个关系$ r $，若函数依赖$ X\rightarrow Y $都成立，则称$ F $逻辑蕴涵$ X\rightarrow Y $

  • 依赖闭包：在关系模式$ R $中，为$ F $所逻辑蕴涵的函数依赖的全体叫做$ F $的闭包，记作$ F^{+} $

  • $ X $关于$ F $的闭包$ X_{F^+} $
    • $ X_{F^+}=\{A\vert X\rightarrow A\} $可由$ F $根据$ Armstrong $公理系统导出
  • $ Armstrong $公理系统
    • 自反律：若$ Y\subseteq X\subseteq U $，则$ X\rightarrow Y $为$ F $所蕴含
    • 增广律：若$ X\rightarrow Y $为$ F $所蕴含，且$ Z\subseteq U $，则$ XZ\rightarrow YZ $为$ F $所蕴含
    • 传递律：若$ X\rightarrow Y $和$ Y\rightarrow Z $为$ F $所蕴含，则$ X\rightarrow Z $为$ F $所蕴含
    • 合并规则：由$ X\rightarrow Y $，$ X\rightarrow Z $，则$ X\rightarrow YZ $
    • 伪传递规则：由$ X\rightarrow Y $，$ WY\rightarrow Z $，则$ XW\rightarrow Z $
    • 分解规则：由$ X\rightarrow Y $，$ Z\subseteq Y $，则$ X\rightarrow Z $
    • $ X\rightarrow A_1A_2\cdots A_k $成立的充要条件是$ X\rightarrow A_i $成立
  • $ X\rightarrow Y $能由$ F $根据$ Armstrong $导出的充要条件是$ Y\subseteq X_{F^+} $
    • 判定$ X\rightarrow Y $能否由$ F $根据$ Armstrong $导出转化为先求$ X_{F^+} $，然后判断$ Y $是否为其子集
    • 如果$ X_{F^+}=U $，则$ X $是$ R $的候选码

  • $ X_{F^+} $的计算

    • 寻找$ F $中决定因素为$ X $或$ X $子集的函数依赖，得到这些函数依赖的右部，与$ X $合并得到新的$ X $
    • 继续以上步骤，直至合并前后的属性集相同或合并后的属性集为$ U $

  • 候选码的计算

    • 基本定义
      • 左部属性：只出现在$ F $左边的属性
      • 右部属性：只出现在$ F $右边的属性
      • 双部属性：出现在$ F $两边的属性
      • 外部属性：不出现在$ F $的属性
    • 基本规则
      • 左部属性一定出现在任何候选码中/一定是主属性
      • 右部属性一定不出现在任何候选码中/一定是非主属性
      • 外部属性一定出现在任何候选码中/一定是主属性
    • 求解过程
      • 求已经确定的主属性集关于函数依赖的闭包
      • 如果该闭包为属性全集$ U $，则已经确定的主属性集为唯一候选码
      • 如果该闭包不为属性全集$ U $，则依次取左部属性和双部属性中的一个组成临时候选码，求其闭包，如果该闭包为属性全集$ U $，则该临时候选码为候选码
      • 如果第三步中仍未得到候选码，则依次取左部属性和双部属性中的2~n个组成临时候选码，求其闭包，如果该闭包为属性全集$ U $，则该临时候选码为候选码

  • 函数依赖的等价/覆盖：如果$ G^+=F^+ $，则$ F $覆盖$ G $

  • 最小覆盖/极小函数依赖集：满足如下条件的函数依赖集

    • $ F $中任一函数依赖的右部仅含有一个属性
    • $ F $中不存在这样的函数依赖$ X\rightarrow A $，使得$ F $与$ F-\{X\rightarrow A\} $等价，即$ F $中的函数依赖不能被其他函数依赖导出
    • $ F $中不存在这样的函数依赖$ X\rightarrow A $，$ X $有真子集$ Z $使得$ F $与$ F-\{X\rightarrow A\}\cup\{Z\rightarrow A\} $等价，即$ F $中各函数依赖左部均为最小属性集，均不存在冗余属性

  • 最小覆盖的计算

    • 将$ F $中所有函数依赖的右边化为单一属性
      • 使用合并规则
      • 逐一检查$ F $中各函数依赖$ F_i:X\rightarrow Y $
      • 若$ Y=A_1A_2\cdots A_k,k\geq2 $，则使用$ \{X\rightarrow A_j\vert j=1,2,\cdots,k\} $代替$ X\rightarrow Y $
    • 去掉$ F $中所有冗余的函数依赖
      • 逐一检查$ F $中各函数依赖$ F_i:X\rightarrow Y $
      • 若$ Y\in X_{(F-F_i)^+} $，则去掉该函数依赖
    • 去掉$ F $中所有函数依赖的左边的冗余属性
      • 逐一检查$ F $中各函数依赖$ F_i:X\rightarrow Y $
      • 若$ X=B_1B_2\cdots B_m $
        • 考察$ B_i $，$ Y\in(X-B_i)_{F^+} $则以$ X-B_i $代替$ X $

4.5 模式分解

  • 模式分解：将关系模式$R\langle U,V\rangle$分解为$\rho=\{R_1\langle U_1,F_1\rangle,\cdots,R_n\langle U_n,F_n\rangle\}$，且$ U=U_1\cup\cdots\cup U_n $，没有$ U_i\subseteq U_j,1\leq i,j\leq n $，$ F_i $是$ F $在$ U_i $上的投影
  • 正确的模式分解
    • 具有无损连接性：设$ \rho={R_1\langle U_1,F_1\rangle ,\cdots,R_n\langle U_n,F_n\rangle } $是$ R\langle U,V\rangle $的一个分解，若对$ R $上的任何一个关系$ r $均有$ r=r $在$ \rho $中个关系模式上投影的自然连接，则称$ \rho $具有无损连接性，简称$ \rho $为无损分解
    • 具有保持函数依赖性：设$ \rho={R_1\langle U_1,F_1\rangle ,\cdots,R_n\langle U_n,F_n\rangle } $是$ R\langle U,V\rangle $的一个分解，若$ F $所逻辑蕴涵的函数依赖一定为分解后所有的关系模式中的函数依赖$ F_i $所逻辑蕴涵，即$ F^+=(F_1\cup F_2\cup\cdots\cup F_n)^+ $，则称$ \rho $具有保持函数依赖性
    • 如果一个分解具有无损连接性，则它能够保证不丢失信息
    • 如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况

五、查询优化

6.1 查询处理

  • 查询处理流程

    • 操作算子以树的形式进行组织
    • 数据流从叶子结点流向根节点
    • 根节点的输出是查询的结构

  • 迭代模型

    • 每个算子执行$ Next $函数，调用得到一个下层提交的元组或一个空值标记NULL Maker

  • 物化模型

    • 每个算子一次性获取所有输出，传递元组列表给父节点

  • 向量模型

    • 基本框架同迭代模型，但是每次提交一批元组（Batch）

6.2 代数优化

6.2.1 代数优化的基本准则

  • 选择运算尽可能先做
  • 在执行连接操作前对关系适当进行预处理
  • 投影运算和选择运算同时做
  • 某些选择运算与在其前面执行的笛卡尔积合并为连接运算

6.2.2 关系代数等价变换规则

  • 连接、笛卡尔积交换律：$ E_1\times E_2=E_2\times E_1 $、$ E_1\Join E_2=E_2\Join E_1 $
  • 连接、笛卡尔积结合律：$ (E_1\times E_2)\times E_3=E_1\times(E_2\times E_3) $、$ (E_1\Join E_2)\Join E_3=E_1\Join(E_2\Join E_3) $
  • 投影的串接定律：$ \prod_{A_1,A_2,\cdots,A_n}(\prod_{B_1,B_2,\cdots,B_m}(E))=\prod_{A_1,A_2,\cdots,A_n}(E) $，其中$ \{A_1,A_2,\cdots,A_n\} $是$ \{B_1,B_2,\cdots,B_m\} $的子集
  • 连接的串接定律：$ \sigma_{F_1}(\sigma_{F_2}(E))=\sigma_{F_1\land F_2}(E) $
  • 选择与投影的交换律
    • 如果选择条件$ F $只涉及$ A_1,\cdots,A_n $，则$ \sigma_F(\prod_{A_1,A_2,\cdots,A_n}(E))=\prod_{A_1,A_2,\cdots,A_n}(\sigma_F(E)) $
    • 如果选择条件$ F $含有不属于$ A_1,\cdots,A_n $的属性$ B_1,\cdots,B_n $，则$ \sigma_F(\prod_{A_1,A_2,\cdots,A_n}(E))=\prod_{A_1,A_2,\cdots,A_n}(\sigma_F(\prod_{A_1,A_2,\cdots,A_n,B_1,B_2,\cdots,B_m}(E))) $
  • 选择、笛卡尔积交换律
    • 如果选择条件$ F $只涉及$ E_1 $，则$ \sigma_F(E_1\times E_2)=\sigma_F(E_1)\times E_2 $
    • 设$ F=F_1\land F_2 $，如果选择条件$ F_1 $只涉及$ E_1 $且选择条件$ F_2 $只涉及$ E_2 $，则$ \sigma_F(E_1\times E_2)=\sigma_{F_1}(E_1)\times \sigma_{F_2}(E_2) $
    • 设$ F=F_1\land F_2 $，如果选择条件$ F_1 $只涉及$ E_1 $且选择条件$ F_2 $涉及$ E_1 $和$ E_2 $两者的属性，则$ \sigma_F(E_1\times E_2)=\sigma_{F_1}(E_1)\times \sigma_{F_2}(E_2) $
  • 选择对自然连接的分配律：$ \sigma(E_1\times E_2)=\sigma(E_1)\times\sigma(E_2) $
  • 投影与笛卡尔积的交换：$ \prod_{A_1,A_2,\cdots,A_n,B_1,B_2,\cdots,B_m}(E_1\times E_2)=\prod_{A_1,A_2,\cdots,A_n}(E_1)\times \prod_{B_1,B_2,\cdots,B_m}(E_2) $

6.2.3 代数优化的步骤

  • 根据SQL语句画出语法树
  • 将语法树转换为关系代数语法树
  • 通过代数优化得到优化后的关系代数语法树