强偏序时态模式中混合依赖集的成员籍问题

Membership of mixed dependency set in strong partial ordered temporal scheme

有效的模式分解算法设计中应着重考虑和解决成员籍问题,时态类型间偏序关系在强偏序时态模式中的存在给解决成员籍问题带来了困难。为了有效解决强偏序时态模式中混合依赖集的成员籍问题,提出了给定时态类型上的偏序混合依赖基、强偏序模式混合依赖基、偏序时态函数依赖和偏序时态多值依赖的混合集闭包、强偏序模式混合闭包等概念,给出了求混合依赖集中属性的依赖基、属性集的闭包的算法,并在此基础上给出了强偏序模式混合依赖集成员籍问题的算法,证明了其正确性及可终止性,对该算法的时间复杂度进行了分析。应用实例表明相关理论和算法能解决强偏序混合依赖集中成员籍问题的判定问题,为解决强偏序时态模式规范化问题以及时态数据库设计提供了理论基础。

The solution of membership problem is essential to design an available algorithm of scheme decomposition. Because of the partial order among temporal types in strong partial ordered temporal scheme, it is difficult to solve its membership problem. The concepts of mixed dependency base on given temporal type, mixed dependency base in strong partial ordered scheme, mixed set closure of partial temporal functional dependency and temporal multi-valued dependency and mixed closure of strong partial ordered scheme were given. The algorithms of dependency base of attribution and closure of attribution sets were also given. On this basis, the algorithm of membership problem of mixed dependency set in strong partial ordered scheme was put forward. The proof for its termination, correction and time complexity were presented. Application examples show that the research on related theory and algorithm solves determination of the membership problem in strong partial ordered mixed dependencies, and provides a theoretical basis for solving the strong partial order temporal scheme and the design of temporal database standardization.