A simple greedy algorithm for finding functional relations: efficient implementation and average case analysis
Inferring functional relations from relational databases is important for the discovery of scientific knowledge because many experimental data are represented in the form of tables and many rules are represented in the form of functions. A simple greedy algorithm has been known as an approximation algorithm for this problem. This paper presents an efficient implementation of the algorithm. This paper also shows that the algorithm can identify an exact solution for simple functions if input data for each function are generated uniformly at random and the size of the domain is bounded by a constant. Results of computational experiments using artificially generated data are presented to verify the approach. (C) 2002 Elsevier Science B.V. All rights reserved.
greedy algorithm average case analysis functional dependencies set cover knowledge discovery