AN APPROACH TO INCREASE THE PERFORMANCE OF FUNCTIONAL DEPENDECY FINDING ALGORITHM

Abstract

Relational database model is the most common database model in current information
systems to keep the transaction data. The basis of the relational database design process is
Functional Dependencies (FDs). Moreover, FDs in the existing database can be used to
discover new knowledge and to do data mining; therefore various researches have been
carried out to develop algorithms to discover the hidden FDs in the existing data sets. These
findings help to database designers too in various ways: to database design verifications, to
database management, to reverse engineering, and to query optimization. We could find four
popular functional dependencies in the literature. They are TANE, FD_Mine, FastFD, and
Dep_Miner. The literature says that the performance of FastFD is better for large number of
attributes with lesser number of records, while the performance of the FD_Mine is better for
large number of records with lesser number of attributes. We could find an improvement for
FD_Mine algorithm, but nothing for FastFD. We suggested an approach to increase the
performance of FastFD algorithm using equivalence attributes. The paper concluded that the
equivalence sets helps to reduce the time complexity of the FastFD algorithm some extend,
by reducing the number of records to be checked.