强全序时态模式下函数依赖多值依赖混合集问题研究
|
摘要
与时间相关的数据库应用需求的不断增长,使得时态数据库设计成为非常重要的问题。在数据库的设计中,要充分考虑对数据依赖的处理,数据依赖是指数据之间存在的各种联系,数据冗余的产生和数据依赖有着密切的联系。数据依赖是数据库设计理论中的一个核心概念,通过它可以规范属性之间满足的固有的语义约束。
为了更有效的研究时态数据库中各种依赖以及各属性之间的关系,以便将关系进一步规范化,本文提出了时态左部属性、时态右部属性、时态双部属性、时态函数依赖图等概念。并分别利用图论法和吸收法给出了求时态候选关键字集的算法,并证明其正确性。
时态函数依赖(Temporal Functional Dependency, TFD)和时态多值依赖(Temporal Multi-valued Dependency, TMVD)是时态数据库中最重要的两种数据依赖。对于具有TFD和TMVD混合集约束的时态模式来说,由于多时间粒度的使用使成员籍问题的解决变得更加复杂。但成员籍问题的解决对设计有效的模式分解算法必不可少,本文基于强全序时态模式以及全序时态函数依赖和规则时态多值依赖(RTMVD)理论提出了给定时态类型上的混合依赖基、强全序模式混合依赖基、TFD和RTMVD混合集闭包、强全序模式混合闭包等概念,并给出了求混合混依赖集中属性的依赖基、属性集的闭包的算法,对算法的可终止性、正确性进行了证明,并对时间复杂度进行了分析。在此基础上,给出了解决强全序模式混合集成员籍问题的算法,并对算法的可终止性、正确性进行了证明,对时间复杂度进行了分析。
同时,本文提出了强全序时态模式中冗余依赖、混合无冗余覆盖、规范混合依赖集等概念,并给出了求强全序时态模式混合依赖集的无冗余覆盖和规范覆盖的算法。
以上理论和算法的研究,很好的解决了强全序混合依赖集中依赖的判定的处理问题,为解决强全序时态模式规范化问题以及时态数据库设计提供了理论基础。
The ever increasing of database related to time makes designing temporal database very important. In the design of temporal database, it is necessary to give full consideration to the data dependent treatment. Data dependency means all kinds of connections among data. The happening of data redundance is connected with data dependency. Data dependency is a central notion in database design theory through which we can normalize intrinsic semantic restrinction among attributes.
In order to make the study, the relation of all the dependences and all the attributes, more efficient, then normalize relational database one more step, in this paper, the notions of temporal left attributes, temporal right attributes, temporal both-rl attributes, temporal functional dependency graph are introduced. And the algorithms for temporal candidate keyword sets is given use graph theory method and absorption method respectively, its correction are given.
Temporal functional dependency (TFD) and temporal multi-valued dependency (TMVD) are the two most important data-dependent in temporal database. For temporal scheme with temporal functional dependencies and temporal multi-valued dependencies constrains, the usages of multiple time granularities make it more difficult to solve membership problem. However, the solution of membership problem is essential to design an available algorithm of scheme decomposition. On the base of the strong totally orderd temporal scheme and totally orderd temporal functional dependency and the theory of regular temporal multi-valued dependency (RTMVD) of relational database, in this paper, the concepts of mix dependency base on given temporal type, mix dependency base in strong totally orderd scheme, TFD and RTMVD mix close set of strong totally orderd scheme are given. And the algorithms of dependency base of attribution sets, closure of attribution sets are given, then the proof for its termination, correction and time complexity are given. On this base, the algorithm of membership problem of mix set in strong totally orderd is given, and the proof for its termination, correction and time complexity are given.
As well as, concepts of redundant dependency, mixed non-redundant cover and canonical mixed dependency set of strong-totally order temporal scheme are given. Corresponding algorithms, non-redundant cover and canonical cover, are proposed which can solve the cover problem of mixed dependency set in strong-totally orderd temporal scheme.
The above research of theory and algorithm is a good solution to the problem of dependency judgement in a strong-totally mix-set of dependency, as well as, it provide theory basement for resolving the problem of normalization which in strong-totally ordered temporal scheme and the design of temporal database.
为了更有效的研究时态数据库中各种依赖以及各属性之间的关系,以便将关系进一步规范化,本文提出了时态左部属性、时态右部属性、时态双部属性、时态函数依赖图等概念。并分别利用图论法和吸收法给出了求时态候选关键字集的算法,并证明其正确性。
时态函数依赖(Temporal Functional Dependency, TFD)和时态多值依赖(Temporal Multi-valued Dependency, TMVD)是时态数据库中最重要的两种数据依赖。对于具有TFD和TMVD混合集约束的时态模式来说,由于多时间粒度的使用使成员籍问题的解决变得更加复杂。但成员籍问题的解决对设计有效的模式分解算法必不可少,本文基于强全序时态模式以及全序时态函数依赖和规则时态多值依赖(RTMVD)理论提出了给定时态类型上的混合依赖基、强全序模式混合依赖基、TFD和RTMVD混合集闭包、强全序模式混合闭包等概念,并给出了求混合混依赖集中属性的依赖基、属性集的闭包的算法,对算法的可终止性、正确性进行了证明,并对时间复杂度进行了分析。在此基础上,给出了解决强全序模式混合集成员籍问题的算法,并对算法的可终止性、正确性进行了证明,对时间复杂度进行了分析。
同时,本文提出了强全序时态模式中冗余依赖、混合无冗余覆盖、规范混合依赖集等概念,并给出了求强全序时态模式混合依赖集的无冗余覆盖和规范覆盖的算法。
以上理论和算法的研究,很好的解决了强全序混合依赖集中依赖的判定的处理问题,为解决强全序时态模式规范化问题以及时态数据库设计提供了理论基础。
The ever increasing of database related to time makes designing temporal database very important. In the design of temporal database, it is necessary to give full consideration to the data dependent treatment. Data dependency means all kinds of connections among data. The happening of data redundance is connected with data dependency. Data dependency is a central notion in database design theory through which we can normalize intrinsic semantic restrinction among attributes.
In order to make the study, the relation of all the dependences and all the attributes, more efficient, then normalize relational database one more step, in this paper, the notions of temporal left attributes, temporal right attributes, temporal both-rl attributes, temporal functional dependency graph are introduced. And the algorithms for temporal candidate keyword sets is given use graph theory method and absorption method respectively, its correction are given.
Temporal functional dependency (TFD) and temporal multi-valued dependency (TMVD) are the two most important data-dependent in temporal database. For temporal scheme with temporal functional dependencies and temporal multi-valued dependencies constrains, the usages of multiple time granularities make it more difficult to solve membership problem. However, the solution of membership problem is essential to design an available algorithm of scheme decomposition. On the base of the strong totally orderd temporal scheme and totally orderd temporal functional dependency and the theory of regular temporal multi-valued dependency (RTMVD) of relational database, in this paper, the concepts of mix dependency base on given temporal type, mix dependency base in strong totally orderd scheme, TFD and RTMVD mix close set of strong totally orderd scheme are given. And the algorithms of dependency base of attribution sets, closure of attribution sets are given, then the proof for its termination, correction and time complexity are given. On this base, the algorithm of membership problem of mix set in strong totally orderd is given, and the proof for its termination, correction and time complexity are given.
As well as, concepts of redundant dependency, mixed non-redundant cover and canonical mixed dependency set of strong-totally order temporal scheme are given. Corresponding algorithms, non-redundant cover and canonical cover, are proposed which can solve the cover problem of mixed dependency set in strong-totally orderd temporal scheme.
The above research of theory and algorithm is a good solution to the problem of dependency judgement in a strong-totally mix-set of dependency, as well as, it provide theory basement for resolving the problem of normalization which in strong-totally ordered temporal scheme and the design of temporal database.
引文
[1]师胜利,董瑞卿,杨彦锡.时态数据库在电子商务中的应用[J].计算机与信息技术,2008,(3):73-74.
[2] JENSEN C S, CLIFFORD J. A Glossary of Temporal Database Concepts[J]. ACM SIGMOD Record, 1994, 23(1): 52-64.
[3] TANSEL A, CLIFFORD J, GADIA J S. Temporal Databases: Theory, Design and Implementation[J]. Database Systems and Applications Series, 1993, (5): 35-40.
[4]唐常杰.时态数据库的沿革、特色与代表人物—时态数据库二十年回顾之一[J].计算机科学1999,26(2):27-29.
[5]唐常杰.时态数据库的成果、缺陷与未来—时态数据库二十年回顾之二[J].计算机科学,1999,26(3):63-65.
[6]汤庸.时态知识和时态数据库的统一模型研究[J].软件学报,2003,(12):74-78.
[7]汤庸.时态信息处理技术研究综述[J].中山大学学报,2003,(4):58-65.
[8] EDELWEISS N, HUBLER P N, DEMARTINI G. A Temporal Database Management System Implemented on Top of a Conventional Database[J]. IEEE Computer Society, 2000, (11): 551-631.
[9] SHASHI K G, SEO Y N. Benchmarking Temporal Database Models with Interval-based and Temporal Element-based Timestamping[J]. Journal of Systems and Software, 2008, 81(11): 1931-1943.
[10]郝忠孝.关系数据库数据理论新进展[M].北京:机械工业出版社,1998:23-25.
[11] HADRIEN C, BARRY S. Reformulating Positive Table Constraints Using Functional Dependencies[J]. Principles and Practice of Constraint Programming, 2008, 2(52): 418-432.
[12] HARTMANN S, LINK S. On a Problem of Fagin Concerning Multivalued Fependencies in Relational Databases[J]. Theoretical Computer Science, 2006, 353 (1-3): 137-158.
[13]司徒国强.关系数据库中规范化理论的应用研究[J].兰州铁道学院学报,1999,(3):98-105.
[14]张旭.关系型数据库的规范化[J].武汉工程职业技术学院学报,2002,(4):98-105.
[15]万静,郝忠孝.全序时态模块模式的TO_TSNF分解问题研究[J].计算机科学,2007,34(3):35-39.
[16]万静,郝忠孝.具有多时间粒度的强全序时态模式中多值依赖问题研究[J].计算机研究与发展,2008,45(6):1064-1072.
[17]汤庸.时态数据库导论[M].北京:北京大学出版社,2004:7-32.
[18]马雪英,冯睿.基于函数依赖的模式分解方法[J].计算机应用与软件,2004,(4):123-130.
[19]安蓓,赵政.面向对象的时态数据库技术研究[D].天津:天津大学,2006:1-32.
[20]乔彦友.非第一范式历史数据库的代数结构[J].计算机学报,1998,8(21):190-194.
[21] VIANU V. Dynamic Functional Dependencies and Database Aging[J]. Journal of ACM, 1987, 34(1): 28-59.
[22] WIJSEN J. Trends in Databases: Reasoning and Mining[J]. IEEE Transactions on Knowledge and Data Engineering, 2001, (5): 78-93.
[23] WIJSEN J. Temporal FDs on complex objects[J]. ACM Transactions on Database System, 1999, 24(1): 127-176.
[24] WIJSEN J. Design of Temporal Relational Databases Based on Dynamic and Temporal Functional Dependencies[J]. In: Proc of the International Workshop on Recent Advances in Temporal Databases, 1995: 61-76.
[25] WIJSEN J, VANDENBULCKE J, OLIVE H. Functional Dependencies Generalized for Temporal Databases that Include object-identity[C]. Springer-Verlag GmbH & Company KG. Proceedings of the 12th International Conference on the Entity-Relationship Approach, Arlington, 1994: 99.
[26] JENSEN C S, SNODGRASS R T. Temporally Enhanced Database Design[M]. In: Advances in Object-Oriented Data Modeling. Cambridge, USA: MIT Press, 2000, 163-193.
[27] JENSEN C S, SNODGRASS R T, SOO M D. Extending Existing Dependency Theory to Temporal Databases[J]. IEEE Transactions onKnowledge and Data Engineering, 1996, 8(4): 563-582.
[28]赵磊,徐士华.具有多时间粒度的时态数据库规范化问题研究[J].哈尔滨师范大学学报:自然科学学报,2006,22(3):55-58.
[29] BETTINI G, WANG X S, JAJODIA S. A Generak Framework and Reasoning Models for Time Granularity[J]. Workshop on Temporal Representation and Reasoning, 1996, (5): 256-304.
[30] WANG X S, BETTINI C, JAJODIA S. Logical Design for Temporal Databases with Multiple Granularities[J]. ACM Transactions on Database System: 1997, 22(2): 115-170.
[31] WIJSEN J. Temporal FDs on Complex Objects[J]. ACM Transactions on Database System, 1999, 24(1): 127-176.
[32] LIU WEI YI. SONG NING. A Logical Design Method for Temporal Databases Based on the Stability Constraint and the Generatlization Semantics[J]. Information Sciences, 2000, 124(1-4): 153-171.
[33]姚春龙,郝忠孝.时态类型集的封闭集[J].计算机工程,2003,2:35-37.
[34]姚春龙,郝忠孝.多时间粒度下时态数据库设计中时态类型的外理[J].小型微型计算机系统,2006,27(11):2094-2099.
[35]姚春龙,郝忠孝.一个具有多时间粒度时态函数依赖集的成员籍算法[J].计算机研究与发展,2002,(3):342-347.
[36]姚春龙,郝忠孝.具有全序时态类型集时态函数依赖集的研究[J].软件学报,2003,14(2):247-252.
[37]姚春龙,郝忠孝.一个多时间粒度下时态模式的T3NF分解算法[J].小型微型计算机系统,2005,26(9):1530-1535.
[38]李艳娟,郝忠孝.属性集的有限闭包与有限依赖基算法[J].哈尔滨理工大学学报,2005,2(10):19-22.
[39]郝忠孝,李艳娟.时态函数依赖多值依赖混合集的成员籍问题研究[J].计算机研究与发展,2006,43(7):1267-1272.
[40]郝忠孝,李艳娟.具有多时间粒度的时态多值依赖及时态模式分解方法研究[J].计算机研究与发展,2007,44(5):853-859.
[41] DYRESON C E, EVANS W S. Efficiently Supporting Temporal Granularities[J]. IEEE Transactions on Knowledge and Data Engineering, 2000, 12(4): 568-586.
[42]刘宁.时态数据库多时间粒度问题的研究[D].哈尔滨:哈尔滨理工大学,2005:10-16.
[43]龚冰.多粒度双时态数据模型的研究与应用[D].河北:燕山大学,2005:8-9.
[44]刘宁,郝忠孝.时态数据库初等关键字范式问题的研究[J].哈尔滨理工大学学报,2005,10(3):80-86.
[45]姚春龙,多时间性粒度下时态数据库设计理论研究[D].哈尔滨:哈尔滨工业大学,2004,(4):34.
[2] JENSEN C S, CLIFFORD J. A Glossary of Temporal Database Concepts[J]. ACM SIGMOD Record, 1994, 23(1): 52-64.
[3] TANSEL A, CLIFFORD J, GADIA J S. Temporal Databases: Theory, Design and Implementation[J]. Database Systems and Applications Series, 1993, (5): 35-40.
[4]唐常杰.时态数据库的沿革、特色与代表人物—时态数据库二十年回顾之一[J].计算机科学1999,26(2):27-29.
[5]唐常杰.时态数据库的成果、缺陷与未来—时态数据库二十年回顾之二[J].计算机科学,1999,26(3):63-65.
[6]汤庸.时态知识和时态数据库的统一模型研究[J].软件学报,2003,(12):74-78.
[7]汤庸.时态信息处理技术研究综述[J].中山大学学报,2003,(4):58-65.
[8] EDELWEISS N, HUBLER P N, DEMARTINI G. A Temporal Database Management System Implemented on Top of a Conventional Database[J]. IEEE Computer Society, 2000, (11): 551-631.
[9] SHASHI K G, SEO Y N. Benchmarking Temporal Database Models with Interval-based and Temporal Element-based Timestamping[J]. Journal of Systems and Software, 2008, 81(11): 1931-1943.
[10]郝忠孝.关系数据库数据理论新进展[M].北京:机械工业出版社,1998:23-25.
[11] HADRIEN C, BARRY S. Reformulating Positive Table Constraints Using Functional Dependencies[J]. Principles and Practice of Constraint Programming, 2008, 2(52): 418-432.
[12] HARTMANN S, LINK S. On a Problem of Fagin Concerning Multivalued Fependencies in Relational Databases[J]. Theoretical Computer Science, 2006, 353 (1-3): 137-158.
[13]司徒国强.关系数据库中规范化理论的应用研究[J].兰州铁道学院学报,1999,(3):98-105.
[14]张旭.关系型数据库的规范化[J].武汉工程职业技术学院学报,2002,(4):98-105.
[15]万静,郝忠孝.全序时态模块模式的TO_TSNF分解问题研究[J].计算机科学,2007,34(3):35-39.
[16]万静,郝忠孝.具有多时间粒度的强全序时态模式中多值依赖问题研究[J].计算机研究与发展,2008,45(6):1064-1072.
[17]汤庸.时态数据库导论[M].北京:北京大学出版社,2004:7-32.
[18]马雪英,冯睿.基于函数依赖的模式分解方法[J].计算机应用与软件,2004,(4):123-130.
[19]安蓓,赵政.面向对象的时态数据库技术研究[D].天津:天津大学,2006:1-32.
[20]乔彦友.非第一范式历史数据库的代数结构[J].计算机学报,1998,8(21):190-194.
[21] VIANU V. Dynamic Functional Dependencies and Database Aging[J]. Journal of ACM, 1987, 34(1): 28-59.
[22] WIJSEN J. Trends in Databases: Reasoning and Mining[J]. IEEE Transactions on Knowledge and Data Engineering, 2001, (5): 78-93.
[23] WIJSEN J. Temporal FDs on complex objects[J]. ACM Transactions on Database System, 1999, 24(1): 127-176.
[24] WIJSEN J. Design of Temporal Relational Databases Based on Dynamic and Temporal Functional Dependencies[J]. In: Proc of the International Workshop on Recent Advances in Temporal Databases, 1995: 61-76.
[25] WIJSEN J, VANDENBULCKE J, OLIVE H. Functional Dependencies Generalized for Temporal Databases that Include object-identity[C]. Springer-Verlag GmbH & Company KG. Proceedings of the 12th International Conference on the Entity-Relationship Approach, Arlington, 1994: 99.
[26] JENSEN C S, SNODGRASS R T. Temporally Enhanced Database Design[M]. In: Advances in Object-Oriented Data Modeling. Cambridge, USA: MIT Press, 2000, 163-193.
[27] JENSEN C S, SNODGRASS R T, SOO M D. Extending Existing Dependency Theory to Temporal Databases[J]. IEEE Transactions onKnowledge and Data Engineering, 1996, 8(4): 563-582.
[28]赵磊,徐士华.具有多时间粒度的时态数据库规范化问题研究[J].哈尔滨师范大学学报:自然科学学报,2006,22(3):55-58.
[29] BETTINI G, WANG X S, JAJODIA S. A Generak Framework and Reasoning Models for Time Granularity[J]. Workshop on Temporal Representation and Reasoning, 1996, (5): 256-304.
[30] WANG X S, BETTINI C, JAJODIA S. Logical Design for Temporal Databases with Multiple Granularities[J]. ACM Transactions on Database System: 1997, 22(2): 115-170.
[31] WIJSEN J. Temporal FDs on Complex Objects[J]. ACM Transactions on Database System, 1999, 24(1): 127-176.
[32] LIU WEI YI. SONG NING. A Logical Design Method for Temporal Databases Based on the Stability Constraint and the Generatlization Semantics[J]. Information Sciences, 2000, 124(1-4): 153-171.
[33]姚春龙,郝忠孝.时态类型集的封闭集[J].计算机工程,2003,2:35-37.
[34]姚春龙,郝忠孝.多时间粒度下时态数据库设计中时态类型的外理[J].小型微型计算机系统,2006,27(11):2094-2099.
[35]姚春龙,郝忠孝.一个具有多时间粒度时态函数依赖集的成员籍算法[J].计算机研究与发展,2002,(3):342-347.
[36]姚春龙,郝忠孝.具有全序时态类型集时态函数依赖集的研究[J].软件学报,2003,14(2):247-252.
[37]姚春龙,郝忠孝.一个多时间粒度下时态模式的T3NF分解算法[J].小型微型计算机系统,2005,26(9):1530-1535.
[38]李艳娟,郝忠孝.属性集的有限闭包与有限依赖基算法[J].哈尔滨理工大学学报,2005,2(10):19-22.
[39]郝忠孝,李艳娟.时态函数依赖多值依赖混合集的成员籍问题研究[J].计算机研究与发展,2006,43(7):1267-1272.
[40]郝忠孝,李艳娟.具有多时间粒度的时态多值依赖及时态模式分解方法研究[J].计算机研究与发展,2007,44(5):853-859.
[41] DYRESON C E, EVANS W S. Efficiently Supporting Temporal Granularities[J]. IEEE Transactions on Knowledge and Data Engineering, 2000, 12(4): 568-586.
[42]刘宁.时态数据库多时间粒度问题的研究[D].哈尔滨:哈尔滨理工大学,2005:10-16.
[43]龚冰.多粒度双时态数据模型的研究与应用[D].河北:燕山大学,2005:8-9.
[44]刘宁,郝忠孝.时态数据库初等关键字范式问题的研究[J].哈尔滨理工大学学报,2005,10(3):80-86.
[45]姚春龙,多时间性粒度下时态数据库设计理论研究[D].哈尔滨:哈尔滨工业大学,2004,(4):34.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |