Properties and pre-processing strategies to enhance the discovery of functional dependency with degree of satisfaction

• Autorzy: Wei Q. , Chen G. , Zhou X.
• Języki publikacji: EN

Abstrakty

EN

Functional dependency with degree of satisfaction (FDd) is an extended notion in data modeling, and reflects a type of integrity constraints and business rules on attributes, mainly for massive databases, in which incomplete data such as noise, null and imprecision may exist. While existing approaches are considered effective in general, attempts for further improvement in efficiency are deemed meaningful and desirable as far as knowledge discovery is concerned. This paper focuses on discovering (FDd)s as a form of useful semantic knowledge, aiming at providing an enhancement to the FDd mining process in a more efficient manner. In doing so, properties of FDd are in-depth investigated along with a measure for degree of distinctness. Subsequently, a number of optimization strategies are developed for pre-processing, which are then incorporated into the mining process, giving rise to an enhanced approach for mining functional dependency with degree of satisfaction, namely e-MFDD. Finally, data experiments revealed that e-MFDD significantly outperformed the original approach without pre-processing.

Słowa kluczowe

EN

functional dependency; incomplete data; degree of distinctness; data mining

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2009
• Tom: Vol. 38, no 2
• Strony: 367--394
• Opis fizyczny: Bibliogr. 51 poz., wykr.

Twórcy

autor

Wei Q.

autor

Chen G.

autor

Zhou X.

• Department of Management Science and Engineering, School of Economics and Management, Tsinghua University, Beijing 100084, China,

Bibliografia

• AGRAWAL, R., IMIELINSKI, T. and SWARMI, A. (1993) Mining Association Rules between Sets of Items in Large Databases. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, Washington, DC, USA. ACM Press, 207-216.
• AGRAWAL, R., MANNILA, H., SRIKANT, R., TOIVONEN, H. and VERKAMO, A.I. (1996) Fast Discovery of Association Rules. In: U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, R. Uthurusamy, eds., Advances in Knowledge Discovery and Data Mining, AAAI Press/The MIT Press, MA, USA, 1-30.
• AGRAWAL, R. and SHAFER, J. (1996) Parallel Mining of Association Rules. IEEE Transactions on Knowledge and Data Engineering 8, 962-969.
• ANDERSSON, M. (1994) Extracting an Entity Relationship Schema from a Relational Database through Reverse Engineering. Lecture Notes in Computer Science 881, Proceedings of the 13th International Conference on the Entity-Relationship Approach. Springer Verlag, London, 403-419.
• BAUDINET, M., CHOMICKI, J. and WOLPER, P. (1999) Constraint-generating dependencies. Journal of Computer and System Science 59 (1), 94-115.
• BELL, S. and BROCKHAUSEN, P. (1995) Discovery of Data Dependencies in Relational Databases. University of Dortmund, Computer Science Department, LS-8 Report 14.
• BERZAL, F., CUBERO, J.C., CUENCA, F. and MEDINA, J.M. (2002) Relational decomposition through partial functional dependencies. Data & Knowledge Engineering 43 (2), 207-234.
• BHUNIYA, B. and NIYOGI, P. (1993) Lossless join property in fuzzy relational databases. Data & Knowledge Engineering 11 (22), 109-124.
• BOSC, P., DUBOIS, D. and PRADE, H. (1999) Fuzzy functional dependencies and redundancy elimination. Journal of the American Society for Information Science, 49 (3), Special Issue: Management of Imprecision and Uncertainty, Published Online, 217-235.
• CASTELLANOS, M. and SALTOR, F. (1993) Extraction of Data Dependencies. European-Japanese Conf on Information Modelling and Knowledge Bases, Budapest, Hungary, May 31-June 3. IOS Press, Amsterdam, 401-421.
• CHEN, G.Q. (1998) Fuzzy Logic in Data Modeling: Semantics, Constraints and Database Design. Kluwer Academic Publishers, Boston.
• CHEN, G.Q., KERRE, E.E. and VANDENBULCKE, J. (1994) A computational algorithm for the FFD closure and a complete axiomatization of fuzzy functional dependency (FFD). International Journal of Intelligent Systems 9, 421-439.
• CHEN, G.Q., KERRE, E.E. and VANDENBULCKE, J. (1996) Normalization Based on Fuzzy Functional Dependency in a Fuzzy Relational Data Model. Information Systems 21 (3), 299-310.
• CHEN, G.Q., VANDENBULCKE, J. and KERRE, E.E. (1991) A step towards the theory of fuzzy relational database design. In: B. Loewen, M. Roubens, eds., Proc. of the 4th IFSA World Congress, Brussels, 44-47.
• CODD, E.F. (1970) A Relational Model for Large Shared Data Banks. Communications of the ACM 13 (6), 377-387.
• CUBERO, J.C. et al. (1999) Data Summarization in Relational Databases through Fuzzy Dependencies, Information Sciences 121 (3-4), 233-270.
• CUBERO, J.C., MEDINA, J.M., PONS, O. and VILA, M.A. (1995) Rulesdis-covery in fuzzy relational databases. In: Conference of the North American Fuzzy Information Processing Society, NAFIPS’95. Maryland (USA). IEEE Computer Society Press, 414-419.
• FAYYAD, U., PIATETSKY-SHAPIRO, G. and SMYTH, P. (1996) From Data Mining to Knowledge Discovery: An Overview. In: U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, R. Uthurusamy, eds., Advances in Knowledge Discovery and Data Mining, Cambridge, MA: AAAI Press/The MIT Press, U.S.A., 1-30.
• FLACH, P.A. and SAVNIK, I. (1999) Database Dependency Discovery: A Machine Learning Approach. Al Communications 12 (3), 139-160.
• HICK, J.M. and HAINAUT, J.L. (2006) Database Application Evolution: A Transformational Approach. Data & Knowledge Engineering 59, 534-558.
• HUHTALA, Y., KARKKAINEN, J., PORKKA and P., TOIVONEN, H. (1999) TANE: An Efficient Algorithm for Discovering Functional and Approximate Dependencies. The Computer Journal 42 (2), 100-111.
• HUHTALA, Y., KARKKAINEN, J., PORKKA, P. and TOIVONEN, H. (1998) Efficient Discovery of Functional and Approximate Dependencies Using Partitions. Proc. 14th Int. Conf. on Data Engineering, IEEE Computer Society Press.
• ILYAS, I.F., MARKL, V., HAAS, P., BROWN, P. and ABOULNAGA, A. (2004) CORDS: automatic discovery of correlations and soft functional dependencies. International Conference on Management of Data. Proceedings of the 2004 ACM SIGMOD, Paris, France. ACM Press, 647-658.
• KING, R.S. and LEGENDRE, J.J. (2003) Discovery of functional and approximate functional dependencies in relational databases. Journal of Applied Mathematics and Decision Sciences 7 (1), 49-59.
• KISS, A. (1991) A-decomposition of fuzzy relational database. Annales Univ. Sci. Budapest., Sect. Comp.
• KRAMER, S. and PFAHRINGER, B. (1996) Efficient Search for Strong Partial Determinations. KDD 1996. AAAI Press, 371-374.
• KRUSE, R., NANCK, D. and BORGELT, C. (1999) Data Mining with Fuzzy Methods: Status and Perspectives. In: Proc. 7th European Congress on Intelligent Techniques and Soft Computing (EUFIT’99), Aachen, CD-ROM.
• LIAO, S.Y., WANG, H.Q. and LIU, W.Y. (1999) Functional Dependencies with Null Values, Fuzzy Values, and Crisp Values. IEEE Transactions on Fuzzy Systems 7 (1), 97-103.
• LIU, W. (1993) The fuzzy functional dependency on the basis of the semantic distance. Fuzzy Sets and Systems 59 (2), 173-179.
• MAIMON, O., KANDEL, A. and LAST, M. (2001) Information-Theoretic Fuzzy Approach to Knowledge-Discovery in Databases. In: R. Roy, T. Furuhashi and P.K. Chawdhry, eds., Advances in Soft Computing - Engineering Design and Manufacturing, Springer-Verlag, London, 315-326.
• MATOS, V. and CRASSER, B. (2004) SQL-based discovery of exact and approximate functional dependencies. A CM SIGCSE Bulletin 36 (4), 58-63.
• MERZ, C.J. and MURPHY, P. (1996) UCI repository of machine learning databases (http://www. cs. uci.edu/~mlearn/MLRepository.html)
• MITRA, S., PAL, S.K. and MITRA, P. (2002) Data Mining in Soft Computing Framework: A Survey. IEEE Transactions on Neural Networks 13 (1), 3-14.
• MOUADDIB, N. (1995) Fuzzy Integrity Constraints in Relational Databases. In: Proceedings of the 6th IPS A World Congress, Sao Paulo, Brazil, 389-392.
• PATIG, S. (2006) Evolution of Entity-Relationship Modeling. Data & Knowledge Engineering 56 (2), 122-138.
• RAJU, K.V.S.V.N. and MAJUMDAR, A.K. (1988) Fuzzy functional dependencies and lossless join decomposition of fuzzy relational database systems. ACM Transactions on Database Systems 13 (2), 129-166.
• SAVNIK, I. and FLACH, P.A. (2002) Discovery of Multi-valued Dependencies from Relations. Intelligent Data Analysis Journal 4 (3-4), 195-211.
• SAXENA, P.C. and TYAGU, B.K. (1995) Fuzzy functional dependencies and independencies in extended fuzzy relational database models. Fuzzy Sets and Systems 69 (1), 65-89.
• SHENOI, S., MELTON, A. and TAN, L.T. (1992) Functional dependencies and normal norms in the fuzzy relational database model. Information Sciences 60, 1-28.
• The Insurance Company (2000)© Sentient Machine Research, http://www.smr.nl.
• ULLMAN, J.D. and WIDOM, J. (1997) A First Course in Database Systems. Prentice Hall, Inc., a Simon & Schuster Company.
• ULLMAN, J.D. (1988) Principles of Database and Knowledge-Based Systems. Maryland, Computer Sciences Press Inc.
• WANG, S.L., SHEN, J.W. and HONG, T.P. (2002) Incremental discovery of functional dependencies based on partitions. Intelligent Data Analysis.
• WEI, Q. and CHEN, G.Q. (2003a) An Efficient Algorithm on Mining a Minimal Set of Functional Dependencies with Degrees of Satisfaction. International Conference of IFSA 2003, Istanbul, Turkey. Springer Verlag, Berlin.
• WEI, Q. and CHEN, G.Q. (2003b) Mining a Minimal Set of Functional Dependencies with Degrees of Satisfaction. International Conference FIP 2003, Beijing, China, March 1-4. Tsinghua University Press.
• WEI, Q. and CHEN, G.Q. (2004) Efficient Discovery of Functional Dependencies with Degrees of Satisfaction. J. of Intelligent Systems 19, 1089-1110.
• WEI, Q. and CHEN, G.Q. (2006) Optimized Algorithm of Discovering Functional Dependencies with Degrees of Satisfaction. In: D. Ruan, et al., eds., “Applied Artificial Intelligence”. Proceedings of the 7th International FLINS Conference, Word Scientific Press, 169-176.
• WEI, Q., CHEN, G.Q. and KERRE, E.E. (2002) Mining Functional Dependencies with Degrees of Satisfaction in Databases. In: Proceedings of Joint Conference on Information Sciences, Durham, NC, USA. Association for Intelligent Machinery, Inc.
• WIJSEN, J.NG.R.T. and CALDERS, T. (1999) Discovering Roll-Up Dependencies. Conference on Knowledge Discovery in Data. Proceedings of the fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, California, United States. ACM Press, 213-222.
• WYSS, C., GIANNELLA, C. and ROBERTSON, E. (2001) FastFDs: A heuristic-driven depth-first algorithm for mining functional dependencies from relation instances. Technical Report 551, CS Department, Indiana University, July.
• YANG, Y.P. and SINGHAL, M. (1999) Fuzzy Functional Dependencies and Fuzzy Association Rules. Proceedings of the First International Conference on Data Warehousing and Knowledge Discovery, LCNS 1676, Springer Verlag, Berlin, 229-240.