臺灣博碩士論文加值系統

本研究之目的在於探討如何有效率的發掘動態關聯式資料庫及動態模糊關聯式資料庫中之功能相依性(functional dependency; FD)。功能相依是描述資料庫關聯中屬性之間的一種函數關係。從關聯式資料庫中發掘功能相依性可以應用於資料庫設計、查詢最佳化及資料庫安全上。因此功能相依性之探勘技術已被視為一項重要的資料庫分析工具，最近幾年更受到相當多的重視。然而多數的研究著重在靜態的資料庫上發掘功能相依性，只有少數研究考慮到動態資料庫之探勘技術。若能進一步改善動態資料庫功能相依性之探勘技術，則可使其更具實用價值。
因此我們針對一般之關聯式資料庫及以類似關係為主之模糊關聯式資料庫，在資料庫有所變動時（新增資料），提出三個有效率的功能相依性之漸增式探勘方法。第一個方法是在一般之關聯式資料庫上,提出一個以分割(partition)為主之功能相依性漸增式探勘演算法。第二個方法是在以類似關係為主之模糊關聯式資料庫上，提出一個以逐對比較(pair-wise comparison)之功能相依性漸增式探勘演算法。第三個方法亦是在以類似關係為主之模糊關聯式資料庫上，提出一個以分割為主之功能相依性漸增式探勘演算法。同時我們並對三個方法之計算複雜度提出分析比較及實驗。結果顯示，三個方法皆能相當有效地找出一組最小的功能相依性組合。

The goal of this research is to study how to improve the incremental discoveries of functional dependencies (FD) from crisp and fuzzy relational databases. Functional dependencies are relationship between attributes of a database relation. Discovery of FD’s from relational databases can be applied to database design, database reverse engineering, query optimization, and database security. It has been identified as an important database analysis technique and received considerable research interests in recent years. However, most studies emphasize on non-incremental searching techniques of FD’s from static databases. Few have considered the incremental searching techniques that are required when the database is updated incrementally. More researches are needed to improve current incremental searching techniques to deal with dynamic database behaviors in the real world.
In this research, we proposed three efficient incremental searching algorithms of functional dependencies for crisp relational databases and similarity-based fuzzy relational databases, when a set of tuples is added to the database. Algorithm I is a partition-based incremental searching algorithm on crisp relational database. Algorithm II is a pairwise-comparison-based incremental searching algorithm on similarity-based fuzzy relational database. Algorithm III is a partition-based incremental searching algorithm on similarity-based fuzzy relational database. We also present the complexity analysis and experimental results of these three algorithms. The results show that the proposed algorithms could find the minimal cover of functional dependencies efficiently.

摘要 II
ABSTRACT III
ACKNOWLEDGEMENTS V
LIST OF FIGURES VIII
LIST OF TABLES IX
CHAPTER 1 INTRODUCTION 1
1.1 Background 1
1.2 Motivation 3
1.3 Thesis Organization 4
CHAPTER 2 LITERATURE SURVEY 5
2.1 Discovery of Functional Dependencies from Relational Databases 5
2.2 Incremental Discovery of FD’s from Relational Databases 8
2.3 The Similarity-based Fuzzy Data Model 10
2.3.1 Similarity Relation and Domain Partitions 10
2.3.2 The Similarity-based Fuzzy Relational Data Model 12
2.3.3 Functional Dependencies on the Similarity-based Data Model 14
CHAPTER 3 INCREMENTAL SEARCHING ALGORITHM OF FD’s FROM RELATIONAL DATABASES 19
3.1 Notation 19
3.2 Algorithm I 20
3.3 Example 23
CHAPTER 4 INCREMENTAL SEARCHING ALGORITHMS OF FD’s FROM SIMILARITY-BASED FUZZY RELATIONAL DATABASES 28
4.1 Validation of FD’s by Fuzzy Relational Operations 28
4.2 Monotonicity of FD’s 31
4.3 Notation 33
4.4 Algorithm II 34
4.5 Algorithm III 36
4.6 Example 41
CHAPTER 5 ANALYSIS 45
CHAPTER 6 EXPERIMENTS 49
CHAPTER 7 CONCLUSION AND FUTURE WORK 54
REFERENCES 55
PUBLICATION LIST 59

[1] M. Anvari, and G.F. Rose, “Fuzzy Relational Databases,” in Bezdek, Ed., Analysis of Fuzzy Information, Vol. II (CRC Press, Boca Raton, FL, 1987).
[2] S. Bell and P. Brockhausen, “Discovery of Data Dependencies in Relational Databases,” Tech. Rep. LS-8, Report-14, University of Dortmund, Apr. 1995.
[3] P. Bosc, and O. Pivert, “Fuzzy Querying in Conventional Databases,” In Fuzzy Logic for the Management of Uncertainty, Zadeh, L. and Kacprzyk, J. Eds, John Wiley, New York, 1992, 645-671.
[4] P. Bosc, L. Lietard and O. Pivert, “Functional Dependencies Revisited Under Graduality and Imprecision,” NAFIPS, 1997, 57-62.
[5] B.P. Buckles and F.E. Petry, “A Fuzzy Representation of Data for Relational Databases,” Fuzzy Sets and Systems, 7, 1982, 213-226.
[6] G.Q. Chen, “Fuzzy Functional Dependencies and A Series of Design Issues of Fuzzy Relational Databases,” in Fuzziness in Database Management Systems, P. Bosc, J. Kacprzyk, eds, Physica Verlag, 1995, 166-185.
[7] G.Q. Chen, Fuzzy Logic in Data Modeling: Semantics, Constraints, and Database Design, Kluwer Academic Publishers, 1998.
[8] P.A. Flach, “Inductive Characterisation of Database Relations,” TIK Research Report, November, 1990.
[9] P.A. Flach and I. Savnik, “Database Dependency Discovery: A Machine Learning Approach,” AI Communications, 12(3), November 1999, 139-160
[10] R. Haux and U. Eckert, “Nondeterministic Dependencies in Relations: An Extension of The Concept of Functional Dependency,” Information Systems, 10 (2), 1985, 139-148.
[11] Y. Huhtala, J Karkkainen, P. Porkka, and H. Toivonen, “Efficient Discovery of Functional and Approximate Dependencies Using Partitions,” Proceedings of IEEE International Conference on Data Engineering, 1998, 392-410.
[12] M. Maddouri, S. Elloumi, and A. Jaoua, “An Incremental Learning System for Imprecise and Uncertain Knowledge Discovery,” Journal of Information Sciences, 1998, 109, 149-164.
[13] H. Mannila and K. J. Räihä, “Algorithms for Inferring Functional Dependencies,” Data & Knowledge Engineering, 12(1), 1994, 83-99.
[14] H. Mannila and H. Toivonen, “Levelwise Search and Borders of Theories in Knowledge Discovery,” Data Mining and Knowledge Discovery, 1 (3), 1997, 241-258.
[15] J.M. Medina, M.A. Vila, J.C. Cubero, and O. Pons, “Towards the Implementation of A Generalized Fuzzy Relational Database Model,” Fuzzy Sets and Systems, 75, 1995, 273-289.
[16] S. Parthasarathy, M. J. Zaki, M. Ogihara, and S. Dwarkadas, “Incremental and Interactive Sequence Mining,” ACM CIKM’99, 1999, 251-258.
[17] K.V.S.V.N. Raju and A.K. Majumdar, “Fuzzy Functional Dependencies and Lossless Join Decomposition of Fuzzy Relational Database Systems,” ACM Transactions on Database Systems, 13 (2), 1988, 129-166.
[18] H. Sachar, “Theoretical Aspects of Design of and Retrieval from Similarity-based Relational Database Systems,” Ph.D. Diss., 1986, Univ. of Texas at Arlington, TX, USA.
[19] I. Savnik, and P. Flach, “Bottom-up Induction of Functional Dependencies from Relations,” In Knowledge Discovery in Databases Workshop, G. Piatetsky-Shapiro, Editor, Paper from the 1993 AAAI Workshop, 174-185.
[20] A.N. Saharia, and T.M. Barron, “Approximate Dependencies in Database Systems,” Decision Support Systems, 13, 1995, 335-347.
[21] J.C. Schlimmer, “Efficiently Inducting Determinations: A Complete and Systematic Search Algorithm that Using Optimal Pruning,” In G. Piatetsky-Shapiro, Editor, Proceedings of the Tenth International Conference on Machine Learning, Morgan Kaufmann, 1993, 284-290.
[22] S. Shenoi, A. Melton, and L.T. Fan, “An Equivalence Class Model of Fuzzy Relational Databases,” Fuzzy Sets and Systems, 38, 1990, 153-170.
[23] S. Shenoi, and A. Melton, “Proximity Relations in The Fuzzy Relational Database Model,” Fuzzy Sets and System, 31, 1989, 285-296.
[24] Ning Shan, and Wojciech Ziarko, “Data-Based Acquisition and Incremental Modification of Classification Rules,” Computational Intelligence, Vol. 11, 2, 1995, 357-370.
[25] Jian Tang, “Using Incremental Pruning to Increase the Efficiency of Dynamic Itemset Counting for Mining Association Rules,” ACM 7th International Conference on Information and Knowledge Management, 1998, 273-280.
[26] M. Umano, “Freedom-O: A Fuzzy Database System, in Gupta-Sanchez,” Ed., Fuzzy Information and Decision Processes (North-Holland, Amsterdam, 1982).
[27] S.L. Wang, J.S. Tsai, and T.P. Hong, “Discovering Functional Dependencies from Similarity-based Fuzzy Relational Databases,” To Appear in Journal of Intelligent Data Analysis.
[28] A. Yazici, E. Gocmen, B.P. Buckles, and R. George, and F.E. Petry, “An Integrity Constraint for A Fuzzy Relational Database,” Proc. of Second IEEE Int. Conf. on Fuzzy Systems 1993, Vol: 1, 496-499.
[29] L.A. Zadeh, “Similarity Relations and Fuzzy Orderings,” Info. Sci., vol 3, no. 1, Mar. 1971, 177-200.
[30] M. Zemankova-Leech and A. Kandel, Fuzzy Relational Databases - A Key to Expert Systems, Verlag TUV Rheinland, Cologne, 1985.