草稿:追逐測試
Chase算法用於測試資料庫之數據依賴。最基本的Chase算法可檢測對有函數依賴關係模式的分解是否具有無損連接,即任一元組拆分後自然連接與原元組相同。
示例
令R(A, B, C, D) 為已知關係模式,服從函數依賴集F = {A→B, B→C, 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相同。故改b2為b1。
A | B | C | D |
---|---|---|---|
a | b1 | c1 | d |
a | b1 | c | d2 |
a3 | b | c | d |
考慮B→C,同理改c1為c。
A | B | C | D |
---|---|---|---|
a | b1 | c | d |
a | b1 | c | d2 |
a3 | b | c | d |
考慮CD→A,同理改a3為a。
A | B | C | D |
---|---|---|---|
a | b1 | c | d |
a | b1 | c | d2 |
a | b | c | d |
此時第三行 (a, b, c, d) 均無下標,即與 t 相同,可知該分解具有無損連接。特別地,所得元組與投影至 {B, C, D} 的元組相同。