连接依赖子类可满足性的多项式测试

测试一个关系是否满足所给的依赖,这在关系数据库设计中是很重要的。本文定义了一些连接依赖子类:顺序连接依赖,广义顺序连接依赖,环形连接依赖,广义环形连接依赖和梯形连接依赖,前二类依赖可满足性测试算法时间复杂性是O(n~2logn),后三类依赖可满足性测试算法时间复杂性是O(n~4)。目前所定义的应用范围比连接依赖小的所有依赖都包含在这里所定义的连接依赖子类中。