A simple greedy algorithm for finding functional relations: efficient implementation and average case analysis
✍ Scribed by Tatsuya Akutsu; Satoru Miyano; Satoru Kuhara
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 186 KB
- Volume
- 292
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
Inferring functional relations from relational databases is important for the discovery of scientiÿc 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 e cient 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 artiÿcially generated data are presented to verify the approach.