Skip to content

Database design

概念复习:

  • Relation Schema 关系模式 \(R=(A_1,A_2\dots A_n)\) \(A_i\)是属性 关系模式是对关系的一种抽象
  • 关系 \(r(R)\) \(R\)上的具体关系(一系列满足R的元素组成的集合)
  • super key超键 定义：
    • 超键可以是多个属性的组合
    • 如果A是关系R的一个超键，那么(A, B)也是关系R的一个超键
  • candidate key候选键：如果K是R的一个超键，而任何K的真子集不是R的一个超键，那么K就是R的一个候选键

函数依赖

考虑这个表inst_dept(ID,name,dept_name,building)

需求:我们希望dept_name 能决定building (相同的系名，建筑名一定相同). 但是 dept_name不是表的主键，如何描述这种依赖关系?

定义: 对于一个关系模式 \(R\) 上属性的集合\(\alpha\) 和\(\beta\)

如果对于R的任意关系\(r(R)\)中的任意两行\(t_1,t_2\) \(t_1,t_2\)的\(\alpha\)属性值相同可以推出他们的\(\beta\) 属性值也相同,则称\(\alpha\to\beta\)是一个函数依赖

\(t_1[\alpha]=t_2[\alpha]\rightarrow t_1[\beta]=t_2[\beta]\)

显然若\(b \subseteq a\), 则\(a\to b\)

若\(a\to b\) 且\(b\subseteq a\),则称这个依赖是trivial的。否则是非trivial的

一般用\(R\)表示关系模式，用\(F\)表示\(R\)上所有函数依赖的集合。

注意箭头两边可以是多个属性的组合，如\(\{A,B\}\to C\) 可以简写为\(AB\to C\)

闭包

函数依赖的性质(Armstrong's axiom):

  • 若\(\beta \subseteq \alpha\) 则\(\alpha \to \beta\)
  • 若\(\alpha \to \beta\) 则\(\gamma\alpha \to \gamma \beta\)
  • 若\(\alpha \to \beta,\beta \to \gamma\), 则\(\alpha \to \gamma\)

F的闭包

函数依赖的集合F，通过运用上面的3条公理能够得到的所有函数依赖集合

属性集闭包

由属性集合a能够推出的所有 属性 的集合。a不一定是一个属性，可能是多个属性，如AB

result=a
while result is changed do
    for each b->c in F do
            if b is in result then
                result=result∪c

找超键和候选键

a是super key 当且仅当 \(R\subseteq a^+\) (等价于\(a\to R\))

\(a\to b\) 属于F: \(b\subseteq a^+\)

计算F的闭包: \(\forall a\subseteq R,\) 计算\(a^+\), 对所有\(S\subseteq a^+\), 则把\(a\to S\)加到结果例

找所有candidate key（重要!)

  • If attribute a only appears in left side of non trivial FDs in F, it should be part of a candidate key
  • If attribute a only appears in right side of non trivial FDs in F, it should not be part of a candidate key
  • If attribute a does not appear in any non trivial FDs of F, it should be part of a candidate key

例R=(A, B, C, D, E), F= {A B→C, B→D, AD→E}

A和B只出现左边，根据1,A,B一定是。C和E只在右边,一定不是。D可能是。

那么candidate key可能是AD,BD,AB

计算\((AD)^+,(BD)^+,(AB)^+\) , 发现$R\subseteq (AB)^+ $ 所以AB是candidate key

正则覆盖

函数依赖关系F中，是否有一些多余的依赖？

image-20240415223114415

法一(ppt 8.40)

image-20240415223202579

法二

画图法:

image-20240415223323444

image-20240415223611524

分解

分解: 把关系模式R的属性拆开，一部分属性组成R1,一部分组成R2, \(R=R_1\cup R_2\)

有损的分解(Lossy Decomposition)：不能用分解后的几个关系重建原本的关系

无损分解

定义 \(\forall r(R),r=\prod_{R_1}(r)\bowtie \prod_{R_2}(r)\)

验证: \(R=(R_1,R_2)\)是无损分解当且仅当 \(R_1\subseteq[R_1\cap R_2]^+\) 或 \(R_1\subseteq[R_1\cap R_2]^+\) (属性集闭包)

​ 用函数依赖的闭包,也可以等价写成 \((R_1\cap R_2)\to R_1\) 或 \((R_1\cap R_2)\to R_2\) 属于\(F^+\) 但是实际中用属性集闭包更好计算

依赖保持Dependency Preservation

定义：If it is sufficient to test only those dependencies on each individual relation of a decomposition in order to ensure that all functional dependencies hold, then that decomposition is dependency preserving.

验证方法1: 设\(R\)的分解为\(R=(R_1\dots R_n)\) \(F_i\)为\(F^+\) 上只包含\(R_i\)中属性的函数依赖构成的集合

若\((F_1\cup F_2\dots \cup F_n)^+=F^+\) 则是dependency preserving

验证方法2(ppt 8.45): (注意是在原来的函数依赖集合F上计算属性集闭包)

由于2只需要计算属性集的闭包，所以时间复杂度是多项式的

第一范式

一个关系模式R的所有属性都是不可拆分的(atomic).

BCNF

ppt 8.17,8.18

定义 \(F^+\)上的所有函数依赖\(a\to b\), 满足下面任意一条:

  • \(a\to b\)是trivial的
  • \(a\)是R的超键，即\(a\to R\) (但\(b\)可能是R的子集)

验证R满足BCNF

对于 F 上任意非平凡函数依赖\(\alpha \to \beta\) , \((\alpha)^+=R\) 则R满足BCNF

  • 注意只需要验证\(F\)而不是\(F^+\)

BCNF分解算法

思路: 如果\(a\to b\)是R上非平凡的函数依赖，则把R分解为\((a\cup b)\) 和\(R-(b-a)\)

tips: - 如果\(a\cap b=\emptyset\) 则\(b-a=b\) 分解为\(ab,R-b\) - 需要对R找到非平凡函数依赖，方法是对每个函数依赖的左边求闭包，看是否等于\(R\)

image-20240412200720497

性质: - 一定是无损分解 - 分解出的关系模式一定也是BCNF

问题: 不好检查关系是否满足函数依赖关系。因为\(AB\to C\)被拆掉了，要检查就要join \((A,B)\)和\((B,C)\) 。把BCNF的限制放松，得到3NF

3NF

\(R^+\)上的所有函数依赖\(a\to b\), 满足下面任意一条:

  • \(a\to b\)是trivial的
  • a是R的超键
  • 对于\(\forall A \in (b-a)\)中，都能找到R的一个候选主键K, \(A\in K\)

tradeoff: 有一些信息重复，但是检查函数依赖简单

3NF分解算法

  1. 计算Fc, 对于Fc中每个函数依赖\(a\to b\)，都生成

image-20240415223843944

性质 - 一定是无损分解 - 一定是依赖保持

Comments