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.