跳转到内容

草稿:追逐测试

维基百科,自由的百科全书

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} 的元组相同。