函数依赖理论
-
逻辑蕴涵
-
定义：
- 存在如下条件
- 关系模式：r(R)
- 依赖集：F （由一个或多个依赖组成）
- 依赖：f
- 若r(R)满足F ==> r(R)满足f
- 我们称 F 逻辑蕴涵 f
ps: 其中f可由F通过Armstrong公理推得
- 存在如下条件
- 举个栗子：
给定关系模式 r(A, B, C, G, H, I)
-
F包含如下依赖
- A → B
- A → C
- CG → H
- CG → I
- B → H
函数依赖f : A → H
-
其中 f 被 F 逻辑蕴涵
- 由Amstrong传递公理可知：A → B, B → H ==> A → H
-
-
函数依赖集的闭包
- 令 F 为一个函数依赖集。则 F的闭包 是 被 F 逻辑蕴涵的所有函数依赖的集合
- 记作：F+
-
Armstrong公理（Armstrong's axiom）
公理是科学的客观规律，不需要自己证明，直接用就行
-
Armstrong 公理
- 自反律（reflexivity rule）。若α为一个属性集，且β⊆α， 则α→β
- 举个栗子：(A, B)→A
- 增补律（augmentation rule）。若α→β成立且γ为一属性集，则γα→γβ
- 举个栗子：(A, B)→C ==> (A, B, D, E)→(C, D, E)
- 传递律（transitivity rule）。若α→β和β→γ成立，则 α→γ 成立
- 举个栗子：A→B, B→C ==> A→C
- 自反律（reflexivity rule）。若α为一个属性集，且β⊆α， 则α→β
-
Armstrong公理是完备的，对于一个给定的函数依赖集F，通过Armstrong公理可以产生全部的F+
-
Armstrong公理的一些推论
可由Armstrong公理直接推得，也可以当做公理使用
- 合并律（union rule）。若α→β和α→γ成立，则α→βγ
- 举个栗子：A→B, A→C ==> A→(B, C)
- 分解律（decomposition rule）。若α→βγ成立，则α→β和α→γ成立
- 举个栗子：A→(B, C) ==> A→B, A→C
- 伪传递律（pseudotransitivity rule）。若α→β和γβ→δ成立，则αγ→δ成立
- 举个栗子：A→B, (B, C)→D ==> (A, C)→D
- 合并律（union rule）。若α→β和α→γ成立，则α→βγ
-
-
属性集的闭包
- 令α为一个属性集，我们将函数依赖集 F 下被α 函数确定的所有属性的额集合为称为F下α的闭包
- 记作：α+
- 伪代码如下：
result := α repeat for each 函数依赖 β→γ in F do begin if β ⊆ result then result := result ∪ γ end until(result 不变)
-
正则覆盖（极小函数依赖集）
- 如果去除函数依赖中的一个属性不改变函数依赖集的闭包，则称该属性是无关的
- F的正则覆盖 Fc 是一个依赖集，使得F逻辑蕴涵Fc 中的所有依赖，并且Fc 逻辑蕴涵F中的所有依赖。此外，Fc 必须具有如下性质 ：
- Fc 中任何函数依赖都不含无关属性
- Fc 中函数依赖的左半部都是唯一的。即Fc 中不存在两个依赖α1→β1和α2→β2， 满足α1=α2
-
无损分解
- 如果用两个关系模式r1(R)和r2(R)替代r(R)时没有信息损失，则我们称该分解时无损分解（lossless decomposition）
- SQL 表示
-- 下面查询的结果与r具有相同结果的元组集 SELECT * FROM r1 natural join r2 - 关系代数表示：
- ∏R1(r) ⋈ ∏R2(r) = r
分解算法=> 下回分解
