模式分解这边主要包括无损分解和保持函数依赖的分解两种形式,简单整理一下。
无损分解
把一个 R R R 分成 ρ = { R 1 , R 2 , ⋯ , R k } \rho =\{R_1,R_2,\cdots,R_k\} ρ={R1,R2,⋯,Rk},然后通过自然连接 R 1 ⋈ R 2 ⋈ ⋯ ⋈ R k R_1\bowtie R_2\bowtie \cdots\bowtie R_k R1⋈R2⋈⋯⋈Rk,如果连回来了就是无损分解,如果多出了一些冗余元组就是有损分解。
这个定义很难直接用来判定,下面介绍一个判定算法。
判定算法
术语描述
ρ = { R 1 < U 1 , F 1 > , ⋯ , R k < U k , F k > } \rho = \{R_1<U_1,F_1>,\cdots,R_k<U_k,F_k>\} ρ={R1<U1,F1>,⋯,Rk<Uk,Fk>} 是 R < U , F > R<U,F> R<U,F> 的一个分解, U = { A 1 , ⋯ , A n } U=\{A_1,\cdots,A_n\} U={A1,⋯,An}, F = { F D 1 , ⋯ , F D ρ } F=\{\mathrm{FD_1,\cdots,FD}_\rho\} F={FD1,⋯,FDρ}(必须是极小依赖集),其中 F D i : = X i → A l i \mathrm{FD}_i:=X_i\rightarrow A_{li} FDi:=Xi→Ali。算法的过程:
( 1 ) (1) (1) 建立 k × n k\times n k×n 表 C = [ c i j ] k × n \boldsymbol C=[c_{ij}]_{k\times n} C=[cij]k×n,每列对应属性 A j ( j = 1 , ⋯ , n ) A_j(j=1,\cdots,n) Aj(j=1,⋯,n),每行对应一个分解的 U i U_i Ui。 c i j = { a j , A j ∈ U i , b i j , A j ∉ U i c_{ij}=\displaystyle\begin{cases}a_j,&A_j\in U_i,\\b_{ij},&A_j\notin U_i\end{cases} cij={aj,bij,Aj∈Ui,Aj∈/Ui。
( 2 ) (2) (2) 遍历 F D i \mathrm{FD}_i FDi,截取 C \boldsymbol C C 中对应 X i X_i Xi 的列,看看哪些行的内容是相同的。这些行在 l i li li 列若存在一个 a l i a_{li} ali,那么这些行在 l i li li 列的值全部改为 a l i a_{li} ali;否则全部改为 b m l i b_{mli} bmli,其中 m m m 为这些行的行号最小值。
一个符号被更改,表中其它所有相同的符号都应作相同的更改。
( 3 ) (3) (3) 重复 ( 2 ) (2) (2) 的操作,如果有一行全 a a a 说明 ρ \rho ρ 是无损连接分解,停止算法;否则表 C \boldsymbol C C 总会在某个时刻不再更新,停止算法并下结论 ρ \rho ρ 是有损连接分解。
案例描述(直接上图)
设有关系模式 R ( A , B , C , D , E ) R(A,B,C,D,E) R(A,B,C,D,E), R R R 的最小函数依赖集是 F = A → D , E → D , D → B , B C → D , D C → A \mathit{F={A→D,E →D,D →B,BC →D,DC →A}} F=A→D,E→D,D→B,BC→D,DC→A。判断 ρ = { A B , A E , E C , D B C , A C } \mathit{ρ=\{AB,AE,EC,DBC,AC\ \}} ρ={AB,AE,EC,DBC,AC } 是否为无损连接分解。
判定定理(分解为 2 个关系)
定理描述:对于 R < U , F > R<U,F> R<U,F> 的一个分解 ρ = { R 1 < U 1 , F 1 > , R 2 < U 2 , F 2 > } \rho = \{R_1<U_1,F_1>,R_2<U_2,F_2>\} ρ={R1<U1,F1>,R2<U2,F2>},如果 U 1 ∩ U 2 → U 1 − U 2 ∈ F + U_1\cap U_2\rightarrow U_1-U_2\in F^+ U1∩U2→U1−U2∈F+ 或 U 1 ∩ U 2 → U 2 − U 1 ∈ F + U_1\cap U_2\rightarrow U_2-U_1\in F^+ U1∩U2→U2−U1∈F+,则 ρ \rho ρ 具有无损连接性。
这个定理可以从上面的算法得出,具体证明看下图就知道了。
保持函数依赖的分解
把一个 R R R 分成 ρ = { R 1 , R 2 , ⋯ , R k } \rho =\{R_1,R_2,\cdots,R_k\} ρ={R1,R2,⋯,Rk},然后看看是否有 F 1 + ∪ F 2 + ∪ ⋯ ∪ F k + = F + F_1^+\cup F_2^+\cup\cdots\cup F_k^+=F^+ F1+∪F2+∪⋯∪Fk+=F+,如果相等就是保持函数依赖的分解,否则不是。
这个定义可以直接用来判定。
模式分解算法
保持函数依赖的 3NF 分解
描述
( 1 ) (1) (1) 对 R < U , F > R<U,F> R<U,F>中的 F F F进行极小化处理。处理后的函数依赖集仍用 F F F 表示。
( 2 ) (2) (2) 找出不在 F F F 中出现的属性,把这样的属性构成一个关系模式,并把这些属性从 U U U 中去掉。
( 3 ) (3) (3) 如果 F F F 中有一个函数依赖涉及 R R R 的全部属性,则 R R R 不能再分解。
( 4 ) (4) (4) 如果F中含有 X → A X→A X→A,则分解应包含模式 X A XA XA,如果 X → A 1 , X → A 2 , ⋯ , X → A n X→A_1,X→A_2,\cdots,X→A_n X→A1,X→A2,⋯,X→An 均属于 F F F,则分解应包含模式 X A 1 A 2 ⋯ A n \mathit{XA}_1A_2\cdots A_n XA1A2⋯An。
例子
设关系模式 R < U , F > R<U,F> R<U,F>, U = { C , T , H , R , S , G , X , Y , Z } U=\{C,T,H,R,S,G,X,Y, Z\} U={C,T,H,R,S,G,X,Y,Z}, F = { C → T , C S → G , H R → C , H S → R , T H → R , C → X } F=\mathit{\{C→T,CS→G,HR→C,HS→R,TH→R,C→X\}} F={C→T,CS→G,HR→C,HS→R,TH→R,C→X},将 R R R 分解为 3 N F \rm3NF 3NF,且保持函数依赖。
解:设该函数依赖集已经是最小化的,先对 F F F 中左边相同的进行合并 ( C → T + C → X = C → T X ) (C→T +C→X=C\rightarrow\mathit{TX}) (C→T+C→X=C→TX) 得 F = { C → T X , C S → G , H R → C , H S → R , T H → R } F=\mathit{\{C→TX,CS→G,HR→C,HS→R,TH→R\}} F={C→TX,CS→G,HR→C,HS→R,TH→R}。
因此 ρ = { Y Z , C T X , C S G , H R C , H S R , T H R } \mathit{\rho=\{YZ,CTX,CSG,HRC,HSR,THR\}} ρ={YZ,CTX,CSG,HRC,HSR,THR}。
Y Z \mathit{YZ} YZ 是 F F F 中没有出现的属性,单独拿出来。
保持函数依赖的无损 3NF 分解
在保持函数依赖的 3NF 分解基础上,尝试在 ρ \rho ρ 中加入 R R R 所有的码得 τ \tau τ。加入后可能会存在包含关系,保大去小。举个例子说明。
有关系模式 R < U , F > R<U,F> R<U,F>, U = { C , T , H , R , S , G } U=\{C,T,H,R,S,G\} U={C,T,H,R,S,G}, F = { C → T , C S → G , H R → C , H S → R , T H → R } \mathit{F=\{C→T,CS→G, HR→C,HS→R,TH→R\}} F={C→T,CS→G,HR→C,HS→R,TH→R},将 R R R 分解为 3 N F \rm3NF 3NF,且既具有无损连接性又能保持函数依赖。
解:求得关系模式 R R R 的码为 H S \mathit{HS} HS,它的一个保持函数依赖的 3 N F \rm3NF 3NF为: ρ = { C T , C S G , H R C , H S R , T H R } \mathit{\rho=\{CT,CSG,HRC,HSR,THR\}} ρ={CT,CSG,HRC,HSR,THR}。
因为码 H S ⊂ H S R \mathit{HS\subset HSR} HS⊂HSR,所以去掉 H S \mathit{HS} HS,保留 H S R \mathit{HSR} HSR。所以 τ = ρ = { C T , C S G , H R C , H S R , T H R } \mathit{\tau=\rho=\{CT,CSG,HRC,HSR,THR\}} τ=ρ={CT,CSG,HRC,HSR,THR}为满足要求的分解。