草稿:追逐測試

Chase算法用於測試數據庫之數據依賴。最基本的Chase算法可檢測對有函數依賴關係模式的分解是否具有無損連接,即任一元組拆分後自然連接與原元組相同。

示例

R(A, B, C, D) 為已知關係模式,服從函數依賴集F = {AB, BC, CD→A}。若R分解為三個關係模式S1 = {A, D}、S2 = {A, C}、S3 = {B, C, D},現用chase算法確定分解是否無損。

起初構建一個表:

A B C D
a b1 c1 d
a b2 c d2
a3 b c d

三行分別代表S1、S2、S3。分解所含屬性無下標,其他屬性有下標。此後使用各函數依賴。

考慮A→B。第一行與第二行均為無下標a,由該依賴可得B相同。故改b2b1

A B C D
a b1 c1 d
a b1 c d2
a3 b c d

考慮B→C,同理改c1c

A B C D
a b1 c d
a b1 c d2
a3 b c d

考慮CD→A,同理改a3a

A B C D
a b1 c d
a b1 c d2
a b c d

此時第三行 (a, b, c, d) 均無下標,即與 t 相同,可知該分解具有無損連接。特別地,所得元組與投影至 {B, C, D} 的元組相同。