关系数据库中函数依赖和近似函数依赖的发现
【网学提醒】：本文主要为网上学习者提供关系数据库中函数依赖和近似函数依赖的发现，希望对需要关系数据库中函数依赖和近似函数依赖的发现网友有所帮助，学习一下吧!
资料包括： 论文(67页44191字) 图纸
说明：
摘要
逆向工程是为实现遗留系统的软件理解而提出来的。不仅如此，当今软件开发的特点决定了逆向工程必将有较大的用武之地。然而，在实践中逆向工程却是一个很复杂的过程。对于一个以数据库为中心的系统来说，先对数据库进行逆向工程然后再对过程进行逆向工程可以降低工程的复杂度。前者我们称其为数据库逆向工程。
数据库逆向工程从理论角度可以看作为数据库设计过程的逆。但在实际应用中，数据库逆向工程不仅借助逆向工程的一些特有的技术比如模式转换技术，语义丰富技术，有时还要用到数据库设计中的一些技巧和方法。
考虑到数据库逆向工程面对的可能不是一个设计良好的数据库，而是有着种种设计问题的数据库，本文分析了数据库设计中可能出现的问题，指出这些问题对于数据库逆向工程的影响。
目前关于关系数据库逆向工程的研究提出很多解决方法。在比较一些常用方法的基础上我们发现各个方法要求条件不同而且高，因而很难在实践中得到推广和应用。考虑到ER图在表述概念上的缺点，我们采用数据源向图作为静态概念的描述工具，并且提出了基于数据的数据库逆向工程解决方法。该方法弥补了现有算法对于条件要求过高的不足，能够满足实际中的需要。
本文在研究数据挖掘技术的基础上提出了基于分类思想的多策略函数依赖发现算法并对近似函数依赖关系发现进行了研究。这是数据为本数据库逆向工程的基础。
关键字：数据库设计,逆向工程,数据库逆向工程,遗留数据库,数据挖掘,函数依赖,
近似函数依赖
Abstract
Reverse engineering is put forward in order to understand software.And the characteristics of software developing destine that Reverse engineering has an open field.However,Reverse engineering is a complex process in the practice.But in term of the data-centered system，it will deduce the complexity through separating data and procedure.
In the theory,database reverse engineering(DBRE) can be regard as the reverse of database design process.But in the practice,DBRE may use not only some technique of reverse engineering,such as
Schema transform and semantic rich,but also some technique of forward engineering.
Some ill-designed database may be found in the database reverse engineering.The problem in database design is analyzed and some effects on DBRE are also pointed out in this article .
A lot of methods are presented in the research of DBRE.We compared some usual methods and presented the method based on data analysis and We replace the Entity –Relationship Diagram with Data_Source_Direction Diagram as the ouput of DBRE.Our method can make up for the shortage of highly condition and satisfy the practice.
A new method of mining the functional dependency is presented based on analysising Data mining technique and the approximative functional dependency is researched in the article .It is base to get the result of DBRE.
Keywords: database design , reverse engineering,database reverse engineering,legacy database,
Data mining ,funcational dependency ,approximative funcational dependency
目录：
摘要4
Abstract5
致谢6
第一章 前言7
1.1 简介7
1.1.1问题的提出7
1.1.2研究的意义8
1.1.3本文的工作9
1.2文章的安排10
第二章 关系数据库设计11
2.1 数据库设计在软件工程中的地位11
2.2 关系数据库设计理论12
2.2.1 函数依赖12
2.2.2关系模式的规范化15
2.3 设计过程分析16
2.3.1概念设计17
2.3.2逻辑设计18
2.3.3物理设计19
2.4数据库设计中常见的问题20
第三章 数据库的逆向工程24
3.1 数据库逆向工程的产生和含义24
3.1.1 遗留信息系统和遗留数据库24
3.1.2 逆向工程24
3.1.3 数据库的逆向工程25
3.2 关系数据库逆向工程的研究状况27
3.2.1 基本框架27
3.2.2 常见方法的比较30
3.2.3存在的问题33
3.3 解决方法34
第四章函数依赖和近似函数依赖关系的发现36
4.1 数据挖掘和知识发现36
4.1.1什么是数据挖掘36
4.1.2 数据挖掘中常用的方法和技术38
4.1.3 Levelwise 算法40
4.1.4效率问题41
4.2函数依赖的发现42
4.2.1什么是数据库中函数依赖的发现42
4.2.2 函数依赖提取研究背景及现状44
4.2.3 基于分类思想的多策略函数依赖发现算法45
4.2.4算法比较与评述50
4.3关系中近似函数依赖关系的发现50
4.3.1 近似函数依赖50
4.3.2近似函数依赖的发现53
4.4 实验分析57
4.4.1 实现57
4.4.2实验58
第五章 总结62
5.1总结62
5.2进一步的工作63
参考文献64
参考文献：
H.Briand,C.Ducateau,From Minimal Cover to Entity-Relationship Diagram.Proceedings of the International Conference on the Entity Relationship Approch,1987.
H.K.Davis,A.K.Arora:Converting a Relational Database Model into an Entity-Relationship model.Proceedings of the 7th International Conference on the Entity Relationship Approch,1988
P.Johannesson,K.Kalman,A Method for Translating Relational Schemas into Conceptual Schemas .Proceedings of the 8th International Conference on the Entity Relationship Approch,1989
M.M.Fonkam,W.A.Gray :An Approach to Eliciting the Semantics of Relational Databases.Proceedings of the 4th International Conference on Computer Aided software Engineering 1992
V.M.Markowitz,J.A.Makowsky:Identifying Extended Entity-Relationship Object Structures in Relational Schemas.IEEE Transactions on Software Engineering,1994.
W.J.Premerlani,M.R.Blaha:An Approach for Reverse Engineering of Relational Databases Proceedings of the IEEE Working Conference on Reverse Engineering ,1993
Martin Andersson. Extracting an entity relationhip schema from a relational database through reverse engineering. In 13th Int. Conf. on ER Approach, 1994.
Roger S.Pressman ，Software engineering，机械工业出版社 1999
姚卿达 数据库设计 高等教育出版社 1987
施伯乐等 数据库系统导论 高等教育出版社 1994
Abraham Silberschatz ,Database System Concepts, China Machine Press 1999
N.Rishe.”A Methodology and Tool for Top-down Relational Database Design”,Data and Knowledge Engineering 10(1993)259-291
K.Bennett,”legacy System”,IEEE software Jan 1995.pp,19-73
M.Brodie and M.Stonebraker,Migrating Legacy System:Gateway,interface and Incremental Appoch ,Morgan Kaufmann ,SanFancisca,1995
[15] 王睿 关系数据库逆向工程方法的设计和评价 计算机工程 1998
[16] J-L Hainaut, C. Tonneau, M. Joris, M. Chandelon ,Transformation-based Database Reverse Engineering,in Proc. of the 12th Int. Conf. on ER Approach, Arlington-Dallas, LNCS 823, Springer-Verlag, 1994
[17] J. Henrard, J.-L. Hainaut, J.-M. Hick, D. Roland, V. Englebert ,Data structure extraction in database reverse engineering,REIS''99, Paris, November 1999
[18] Hainaut, J.-L., Database Reverse Engineering, Research Publication, Namur, 1999, 133 pp.
[19]Roger H.L.Chiang,”A Knowledge-based system for performing reverse engineering of relational databases”,Decision Support Systems 13,pp 295-312,North-Holland,1995.
[20] Roger H.L.Chiang,Terrence M.Barron ,Veda C.Storey,”Reverse engineering of relational databases:Extraction of an EER model from a relational database”,Data &Knowledge Engineering 12,pp107-142,Elsevier Science 1994
[21] Paul Johannesson,” A Method for transforming Relational Schemas into Conceptual Schemas”,in Proc,.of the 10th International Conference on Data Engineering,Rusinkiewicz(Ed.),pp 115-122,Houston ,IEEE Press,1994.
[22] Victor Markowitz and Johann A.Makowsky ,”Identifying Extented Entity-Relationship Object Structures in Relational Schemas”,IEEE Transactions on Software Engineering,Vol 16,N.8,August 1990.
[23] Carlo Batini,Stefano Ceri,Shamkant B.Navathe,”Conceptual Database Design-An Entity-RelationShip Approach”,Benjamin/Cummings ,1992.
[24] J-M.Petit,F.Toumani,J-F.Boulicaut,J.Kouloumdjian,”Towards the Reverse Engineering of Denormalized Relational Database “,in Proc,of the 12th International Conference on Data Engineering ,New Orleans,Louisiana,USA,IEEE Press,Feb.96
[25] M.Blaha and W.Premerlani,”Object-Oriented Modelling and Design for Database Applications “,Prentice-Hall,1998.
[26]Oreste Signore,Mario Loffredo,Mauro Gregori,Marco Cima,”Using Procedural Patterns in Abstracting Relational Schemata “,in Proc.of the 13 th International Conference on Entity-Relationship Approach,Lecture Notes in Computer Science,Volume 881,Dec.1994
[27]李必信、郑国梁，软件理解研究与进展，计算机研究与发展，1999.8
[28] Heikki Mannila: Inductive databases and condensed representations for data mining, International Logic Programming Symposium, 1997
[29] Heikki Mannila and Hannu Toivonen: Levelwise search and borders of theories in knowledge discovery Report C-1997-8, University of Helsinki, Department of Computer Science, January 1997
[30]李德毅.知识获取和数据库学习系统.计算机科学.1993
[31] John F.Elder .A Statistical Perspective on Knowledge Discovery in Databases
[32]U.Fayyad ,Gregory Piatetsky-Shapiro .From Data Mining to Knowledge Discovery in Database
[33]Bhavani Thuraisingham .Data mining :technologies,techniques,Tools,and Trends.1999 by CRC Press LLC
[34] Stephen Muggleton. Inductive logic programming:issues,results and the challedge of
Learning Language in logic.Artificial Intellegence 114(1999)283-296
[35]邵盛.数据采掘技术的研究.微机发展.1999.3
[36]Kankana Chakrabarty.Fuzziness in rough sets. Fuzzy sets and system 110(2000)247-251
[37] Mannila,H. and Raiha,K.-J.Algorithms for inferring functional dependencies.Data & Knowledge Engineering 12 (1994)
[38]Huhtala.y.,Karkkainen.J.,Porkka.Efficient Discovery of Functional and Approximate Dependencies using Partitions.In Proc.14th int.conf.on Data Engineering(ICDE ’98),pp.392-401.IEEE computer society Press.
[39] http://www.ics.uci.edu/~mlearn/MLSummary.html
[40]Heikki Mannila, Kari-Jouko Räihä: Dependency Inference.vldb 1987 155-158
[41]Heikki Mannila and Hannu Toivonen: Levelwise search and borders of theories in knowledge discovery Report C-1997-8, University of Helsinki, Department of Computer Science, January 1997.
[42] Savnik and P.A. Flach. Bottom-up induction of functional dependencies from relations. In Proceedings of the AAAI''93 Workshop on Knowledge Discovery in Databases, pages 174--185. AAAI Press, 1993. Washington DC.
[43] R. Agrawal, R. Srikant: "Fast Algorithms for Mining Association Rules", Proc. of the 20th Int''l Conference on Very Large Databases, Santiago, Chile, Sept. 1994.
[44]George H.John and Pat Langley.Static Versus dynamic sampling for data mining.In Proc.of the Second International Conference on Knowledge Discovery in Database ,page 367.AAAI/MIT press,1996
[45] F. Provost, D. Jensen, and Tim Oates. Efficient progressive sampling. In Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 15-18, 1999.
[46] J. Kivinen and H. Mannila. The power of sampling in knowledge discovery. Technical Report C-1993-66, University of Helsinki, Computer Science Department, 1993.
[47] Raju Addala .Sampling: An efficient, simple and robust technique for scaling up data mining Research paper, CISC 832 Advanced Topics in Database Management
[48] Raju Addala,Sampling:An efficient,simple and robust technique for scaling up data mining.
Reserch paper,CISC 832 Advanced Topics in Database Management
[49] Heikki Mannila, Hannu Toivonen, and A. Inkeri Verkamo: Discovery of frequent episodes in event sequences. Report C-1997-15, University of Helsinki, Department of Computer Science, February 1997. A revised version is to appear in Data Mining and Knowledge Discovery, 1997.
[50] K. Koperski and J. Han, Discovery of Spatial Association Rules in Geographic Information Databases, Proc. 4th Int''l Symp. on Large Spatial Databases (SSD95), Maine, Aug. 1995, pp. 47-66.
[51] Schlimmer,J.C(1993)Efficiently inducing determinations:A complete and systematic search algorithm that uses optimal pruning .In Piatetsky-Shapiro,G,Proc.!0th Int.Conf. on Machine Learning,Amhearst,MA,pp.184-290,Morgan Kaufmann.
[52] "Discovery of Constraints from Data for Information System Reverse Engineering" Australian Software Engineering Conference (ASWEC ''97), 29th Sep. - 2nd Oct., Sydney, Australia. Wie Ming LIM, John Harrison
[53] Pfahringer B., Kramer S.: Compression-Based Evaluation of Partial Determinations, KDD-95: Proceedings of the First International Conference on Knowledge Discovery & Data Mining, AAAI Press, 1995.
[54] 周概容 编.概率论与数理统计.高等教育出版社.1984
[55] 吴翊等编著.应用数理统计.国防科技大学出版社.1995
[56] Andrew McAllister,Reverse Engineering a Medical Database,Proceedings of WCRE 1996 IEEE
[57]《设计规范与应用实例》中山大学软件研究所 2000.8
[58] 郝忠孝，刘国华 基于属性相关表的关系模式全部候选关键字求法 计算机研究与发展
1994.6
[59] 唱江华，郝忠孝 基于逆向FD超图环的全部候选关键字求法 计算机研究与发展 1997.3
[60] 李恪 在关系模式中查找关键字的算法 计算机工程与应用 1994.5
作者点评：
本文第二章概述了传统的数据库设计过程，并对数据库设计中存在的问题进行研究。我们认为这是理解数据库逆向工程的基础。原因不仅仅在于数据库逆向工程是正向过程的逆过程，而且在于数据库逆向工程中要经常的使用到正向工程的一些技巧。从数据库的生存周期的角度来考虑它们也是不可以分割的，数据库逆向工程处理的数据库是数据库设计的结果。
第三章对数据库逆向工程进行了深入的研究，在比较常见的数据库逆向工程方法的基础上提出了以数据为基础的数据库逆向工程的研究方法。并且对原有数据库逆向工程的方法进行了改进，其改进主要表现在用数据源向图和状态转换图分别表示静态概念模型和动态概念模型来替代E_R图的概念表示方法。这样可以将两种概念模型的提取分开来，使得数据库逆向工程研究向形式化处理发展，更多的实现机器自动化。除此以外，我们还提出了构造数据库数据源向图的实现方案。
第四章我们从研究数据挖掘技术出发解决了数据库中函数依赖和近似函数依赖关系的发现问题。这是我们进行进一步研究的基础。对于后面的处理，我们作如下讨论：
在函数依赖关系已知的基础上发现关系模式的候选关键字是一个研究很成熟的问题。比如，[58][59][60]都对该问题进行了研究，提出了各自的算法。其中[58]提出属性相关表的方法，它首先在理论上对主属性和非主属性进行区分，然后结合属性相关表研究主属性和非主属性在属性相关表中的特征。对于主属性和非主属性的区分是分两步进行的，第一步识别那些仅出现在函数依赖左侧和不在函数依赖中出现的属性，第二步识别出现在函数依赖两侧的属性，在区分主属性和非主属性的基础上构造所有的候选关键字。由于属性相关表的本质是一个矩阵，因而该算法易于在计算机中实现。
键和外键的发现需要与人的交互或者通过代码分析的方法发现。在这里我们不作详细的探讨。在此基础上构造数据库的数据源向图需要有一个具体的实例作依托才有实际的意义。我们把它作为今后的研究问题。
该方法的特点是以数据为本重构数据库的设计规范。其优点是1)对于系统的要求低，容易满足实际的需要。2）求取的结果具有较高的稳定性和健壮性。当然，这样处理的缺点是对于大型的数据库还说效率是比较低的，但我们可以通过降低精确度抽样的方法获取近似函数依赖关系然后利用专家知识的方式来解决效率的问题。因此，效率也不是一个制约因素。
除此以外，我们还作了如下的研究工作：研究更新情况下数据库函数依赖关系的提取，提出了基于马尔可夫链的函数依赖关系预测模型和健壮度估计模型。
资料包括： 论文(67页44191字) 图纸
说明：
摘要
逆向工程是为实现遗留系统的软件理解而提出来的。不仅如此，当今软件开发的特点决定了逆向工程必将有较大的用武之地。然而，在实践中逆向工程却是一个很复杂的过程。对于一个以数据库为中心的系统来说，先对数据库进行逆向工程然后再对过程进行逆向工程可以降低工程的复杂度。前者我们称其为数据库逆向工程。
数据库逆向工程从理论角度可以看作为数据库设计过程的逆。但在实际应用中，数据库逆向工程不仅借助逆向工程的一些特有的技术比如模式转换技术，语义丰富技术，有时还要用到数据库设计中的一些技巧和方法。
考虑到数据库逆向工程面对的可能不是一个设计良好的数据库，而是有着种种设计问题的数据库，本文分析了数据库设计中可能出现的问题，指出这些问题对于数据库逆向工程的影响。
目前关于关系数据库逆向工程的研究提出很多解决方法。在比较一些常用方法的基础上我们发现各个方法要求条件不同而且高，因而很难在实践中得到推广和应用。考虑到ER图在表述概念上的缺点，我们采用数据源向图作为静态概念的描述工具，并且提出了基于数据的数据库逆向工程解决方法。该方法弥补了现有算法对于条件要求过高的不足，能够满足实际中的需要。
本文在研究数据挖掘技术的基础上提出了基于分类思想的多策略函数依赖发现算法并对近似函数依赖关系发现进行了研究。这是数据为本数据库逆向工程的基础。
关键字：数据库设计,逆向工程,数据库逆向工程,遗留数据库,数据挖掘,函数依赖,
近似函数依赖
Abstract
Reverse engineering is put forward in order to understand software.And the characteristics of software developing destine that Reverse engineering has an open field.However,Reverse engineering is a complex process in the practice.But in term of the data-centered system，it will deduce the complexity through separating data and procedure.
In the theory,database reverse engineering(DBRE) can be regard as the reverse of database design process.But in the practice,DBRE may use not only some technique of reverse engineering,such as
Schema transform and semantic rich,but also some technique of forward engineering.
Some ill-designed database may be found in the database reverse engineering.The problem in database design is analyzed and some effects on DBRE are also pointed out in this article .
A lot of methods are presented in the research of DBRE.We compared some usual methods and presented the method based on data analysis and We replace the Entity –Relationship Diagram with Data_Source_Direction Diagram as the ouput of DBRE.Our method can make up for the shortage of highly condition and satisfy the practice.
A new method of mining the functional dependency is presented based on analysising Data mining technique and the approximative functional dependency is researched in the article .It is base to get the result of DBRE.
Keywords: database design , reverse engineering,database reverse engineering,legacy database,
Data mining ,funcational dependency ,approximative funcational dependency
目录：
摘要4
Abstract5
致谢6
第一章 前言7
1.1 简介7
1.1.1问题的提出7
1.1.2研究的意义8
1.1.3本文的工作9
1.2文章的安排10
第二章 关系数据库设计11
2.1 数据库设计在软件工程中的地位11
2.2 关系数据库设计理论12
2.2.1 函数依赖12
2.2.2关系模式的规范化15
2.3 设计过程分析16
2.3.1概念设计17
2.3.2逻辑设计18
2.3.3物理设计19
2.4数据库设计中常见的问题20
第三章 数据库的逆向工程24
3.1 数据库逆向工程的产生和含义24
3.1.1 遗留信息系统和遗留数据库24
3.1.2 逆向工程24
3.1.3 数据库的逆向工程25
3.2 关系数据库逆向工程的研究状况27
3.2.1 基本框架27
3.2.2 常见方法的比较30
3.2.3存在的问题33
3.3 解决方法34
第四章函数依赖和近似函数依赖关系的发现36
4.1 数据挖掘和知识发现36
4.1.1什么是数据挖掘36
4.1.2 数据挖掘中常用的方法和技术38
4.1.3 Levelwise 算法40
4.1.4效率问题41
4.2函数依赖的发现42
4.2.1什么是数据库中函数依赖的发现42
4.2.2 函数依赖提取研究背景及现状44
4.2.3 基于分类思想的多策略函数依赖发现算法45
4.2.4算法比较与评述50
4.3关系中近似函数依赖关系的发现50
4.3.1 近似函数依赖50
4.3.2近似函数依赖的发现53
4.4 实验分析57
4.4.1 实现57
4.4.2实验58
第五章 总结62
5.1总结62
5.2进一步的工作63
参考文献64
参考文献：
H.Briand,C.Ducateau,From Minimal Cover to Entity-Relationship Diagram.Proceedings of the International Conference on the Entity Relationship Approch,1987.
H.K.Davis,A.K.Arora:Converting a Relational Database Model into an Entity-Relationship model.Proceedings of the 7th International Conference on the Entity Relationship Approch,1988
P.Johannesson,K.Kalman,A Method for Translating Relational Schemas into Conceptual Schemas .Proceedings of the 8th International Conference on the Entity Relationship Approch,1989
M.M.Fonkam,W.A.Gray :An Approach to Eliciting the Semantics of Relational Databases.Proceedings of the 4th International Conference on Computer Aided software Engineering 1992
V.M.Markowitz,J.A.Makowsky:Identifying Extended Entity-Relationship Object Structures in Relational Schemas.IEEE Transactions on Software Engineering,1994.
W.J.Premerlani,M.R.Blaha:An Approach for Reverse Engineering of Relational Databases Proceedings of the IEEE Working Conference on Reverse Engineering ,1993
Martin Andersson. Extracting an entity relationhip schema from a relational database through reverse engineering. In 13th Int. Conf. on ER Approach, 1994.
Roger S.Pressman ，Software engineering，机械工业出版社 1999
姚卿达 数据库设计 高等教育出版社 1987
施伯乐等 数据库系统导论 高等教育出版社 1994
Abraham Silberschatz ,Database System Concepts, China Machine Press 1999
N.Rishe.”A Methodology and Tool for Top-down Relational Database Design”,Data and Knowledge Engineering 10(1993)259-291
K.Bennett,”legacy System”,IEEE software Jan 1995.pp,19-73
M.Brodie and M.Stonebraker,Migrating Legacy System:Gateway,interface and Incremental Appoch ,Morgan Kaufmann ,SanFancisca,1995
[15] 王睿 关系数据库逆向工程方法的设计和评价 计算机工程 1998
[16] J-L Hainaut, C. Tonneau, M. Joris, M. Chandelon ,Transformation-based Database Reverse Engineering,in Proc. of the 12th Int. Conf. on ER Approach, Arlington-Dallas, LNCS 823, Springer-Verlag, 1994
[17] J. Henrard, J.-L. Hainaut, J.-M. Hick, D. Roland, V. Englebert ,Data structure extraction in database reverse engineering,REIS''99, Paris, November 1999
[18] Hainaut, J.-L., Database Reverse Engineering, Research Publication, Namur, 1999, 133 pp.
[19]Roger H.L.Chiang,”A Knowledge-based system for performing reverse engineering of relational databases”,Decision Support Systems 13,pp 295-312,North-Holland,1995.
[20] Roger H.L.Chiang,Terrence M.Barron ,Veda C.Storey,”Reverse engineering of relational databases:Extraction of an EER model from a relational database”,Data &Knowledge Engineering 12,pp107-142,Elsevier Science 1994
[21] Paul Johannesson,” A Method for transforming Relational Schemas into Conceptual Schemas”,in Proc,.of the 10th International Conference on Data Engineering,Rusinkiewicz(Ed.),pp 115-122,Houston ,IEEE Press,1994.
[22] Victor Markowitz and Johann A.Makowsky ,”Identifying Extented Entity-Relationship Object Structures in Relational Schemas”,IEEE Transactions on Software Engineering,Vol 16,N.8,August 1990.
[23] Carlo Batini,Stefano Ceri,Shamkant B.Navathe,”Conceptual Database Design-An Entity-RelationShip Approach”,Benjamin/Cummings ,1992.
[24] J-M.Petit,F.Toumani,J-F.Boulicaut,J.Kouloumdjian,”Towards the Reverse Engineering of Denormalized Relational Database “,in Proc,of the 12th International Conference on Data Engineering ,New Orleans,Louisiana,USA,IEEE Press,Feb.96
[25] M.Blaha and W.Premerlani,”Object-Oriented Modelling and Design for Database Applications “,Prentice-Hall,1998.
[26]Oreste Signore,Mario Loffredo,Mauro Gregori,Marco Cima,”Using Procedural Patterns in Abstracting Relational Schemata “,in Proc.of the 13 th International Conference on Entity-Relationship Approach,Lecture Notes in Computer Science,Volume 881,Dec.1994
[27]李必信、郑国梁，软件理解研究与进展，计算机研究与发展，1999.8
[28] Heikki Mannila: Inductive databases and condensed representations for data mining, International Logic Programming Symposium, 1997
[29] Heikki Mannila and Hannu Toivonen: Levelwise search and borders of theories in knowledge discovery Report C-1997-8, University of Helsinki, Department of Computer Science, January 1997
[30]李德毅.知识获取和数据库学习系统.计算机科学.1993
[31] John F.Elder .A Statistical Perspective on Knowledge Discovery in Databases
[32]U.Fayyad ,Gregory Piatetsky-Shapiro .From Data Mining to Knowledge Discovery in Database
[33]Bhavani Thuraisingham .Data mining :technologies,techniques,Tools,and Trends.1999 by CRC Press LLC
[34] Stephen Muggleton. Inductive logic programming:issues,results and the challedge of
Learning Language in logic.Artificial Intellegence 114(1999)283-296
[35]邵盛.数据采掘技术的研究.微机发展.1999.3
[36]Kankana Chakrabarty.Fuzziness in rough sets. Fuzzy sets and system 110(2000)247-251
[37] Mannila,H. and Raiha,K.-J.Algorithms for inferring functional dependencies.Data & Knowledge Engineering 12 (1994)
[38]Huhtala.y.,Karkkainen.J.,Porkka.Efficient Discovery of Functional and Approximate Dependencies using Partitions.In Proc.14th int.conf.on Data Engineering(ICDE ’98),pp.392-401.IEEE computer society Press.
[39] http://www.ics.uci.edu/~mlearn/MLSummary.html
[40]Heikki Mannila, Kari-Jouko Räihä: Dependency Inference.vldb 1987 155-158
[41]Heikki Mannila and Hannu Toivonen: Levelwise search and borders of theories in knowledge discovery Report C-1997-8, University of Helsinki, Department of Computer Science, January 1997.
[42] Savnik and P.A. Flach. Bottom-up induction of functional dependencies from relations. In Proceedings of the AAAI''93 Workshop on Knowledge Discovery in Databases, pages 174--185. AAAI Press, 1993. Washington DC.
[43] R. Agrawal, R. Srikant: "Fast Algorithms for Mining Association Rules", Proc. of the 20th Int''l Conference on Very Large Databases, Santiago, Chile, Sept. 1994.
[44]George H.John and Pat Langley.Static Versus dynamic sampling for data mining.In Proc.of the Second International Conference on Knowledge Discovery in Database ,page 367.AAAI/MIT press,1996
[45] F. Provost, D. Jensen, and Tim Oates. Efficient progressive sampling. In Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 15-18, 1999.
[46] J. Kivinen and H. Mannila. The power of sampling in knowledge discovery. Technical Report C-1993-66, University of Helsinki, Computer Science Department, 1993.
[47] Raju Addala .Sampling: An efficient, simple and robust technique for scaling up data mining Research paper, CISC 832 Advanced Topics in Database Management
[48] Raju Addala,Sampling:An efficient,simple and robust technique for scaling up data mining.
Reserch paper,CISC 832 Advanced Topics in Database Management
[49] Heikki Mannila, Hannu Toivonen, and A. Inkeri Verkamo: Discovery of frequent episodes in event sequences. Report C-1997-15, University of Helsinki, Department of Computer Science, February 1997. A revised version is to appear in Data Mining and Knowledge Discovery, 1997.
[50] K. Koperski and J. Han, Discovery of Spatial Association Rules in Geographic Information Databases, Proc. 4th Int''l Symp. on Large Spatial Databases (SSD95), Maine, Aug. 1995, pp. 47-66.
[51] Schlimmer,J.C(1993)Efficiently inducing determinations:A complete and systematic search algorithm that uses optimal pruning .In Piatetsky-Shapiro,G,Proc.!0th Int.Conf. on Machine Learning,Amhearst,MA,pp.184-290,Morgan Kaufmann.
[52] "Discovery of Constraints from Data for Information System Reverse Engineering" Australian Software Engineering Conference (ASWEC ''97), 29th Sep. - 2nd Oct., Sydney, Australia. Wie Ming LIM, John Harrison
[53] Pfahringer B., Kramer S.: Compression-Based Evaluation of Partial Determinations, KDD-95: Proceedings of the First International Conference on Knowledge Discovery & Data Mining, AAAI Press, 1995.
[54] 周概容 编.概率论与数理统计.高等教育出版社.1984
[55] 吴翊等编著.应用数理统计.国防科技大学出版社.1995
[56] Andrew McAllister,Reverse Engineering a Medical Database,Proceedings of WCRE 1996 IEEE
[57]《设计规范与应用实例》中山大学软件研究所 2000.8
[58] 郝忠孝，刘国华 基于属性相关表的关系模式全部候选关键字求法 计算机研究与发展
1994.6
[59] 唱江华，郝忠孝 基于逆向FD超图环的全部候选关键字求法 计算机研究与发展 1997.3
[60] 李恪 在关系模式中查找关键字的算法 计算机工程与应用 1994.5
作者点评：
本文第二章概述了传统的数据库设计过程，并对数据库设计中存在的问题进行研究。我们认为这是理解数据库逆向工程的基础。原因不仅仅在于数据库逆向工程是正向过程的逆过程，而且在于数据库逆向工程中要经常的使用到正向工程的一些技巧。从数据库的生存周期的角度来考虑它们也是不可以分割的，数据库逆向工程处理的数据库是数据库设计的结果。
第三章对数据库逆向工程进行了深入的研究，在比较常见的数据库逆向工程方法的基础上提出了以数据为基础的数据库逆向工程的研究方法。并且对原有数据库逆向工程的方法进行了改进，其改进主要表现在用数据源向图和状态转换图分别表示静态概念模型和动态概念模型来替代E_R图的概念表示方法。这样可以将两种概念模型的提取分开来，使得数据库逆向工程研究向形式化处理发展，更多的实现机器自动化。除此以外，我们还提出了构造数据库数据源向图的实现方案。
第四章我们从研究数据挖掘技术出发解决了数据库中函数依赖和近似函数依赖关系的发现问题。这是我们进行进一步研究的基础。对于后面的处理，我们作如下讨论：
在函数依赖关系已知的基础上发现关系模式的候选关键字是一个研究很成熟的问题。比如，[58][59][60]都对该问题进行了研究，提出了各自的算法。其中[58]提出属性相关表的方法，它首先在理论上对主属性和非主属性进行区分，然后结合属性相关表研究主属性和非主属性在属性相关表中的特征。对于主属性和非主属性的区分是分两步进行的，第一步识别那些仅出现在函数依赖左侧和不在函数依赖中出现的属性，第二步识别出现在函数依赖两侧的属性，在区分主属性和非主属性的基础上构造所有的候选关键字。由于属性相关表的本质是一个矩阵，因而该算法易于在计算机中实现。
键和外键的发现需要与人的交互或者通过代码分析的方法发现。在这里我们不作详细的探讨。在此基础上构造数据库的数据源向图需要有一个具体的实例作依托才有实际的意义。我们把它作为今后的研究问题。
该方法的特点是以数据为本重构数据库的设计规范。其优点是1)对于系统的要求低，容易满足实际的需要。2）求取的结果具有较高的稳定性和健壮性。当然，这样处理的缺点是对于大型的数据库还说效率是比较低的，但我们可以通过降低精确度抽样的方法获取近似函数依赖关系然后利用专家知识的方式来解决效率的问题。因此，效率也不是一个制约因素。
除此以外，我们还作了如下的研究工作：研究更新情况下数据库函数依赖关系的提取，提出了基于马尔可夫链的函数依赖关系预测模型和健壮度估计模型。