Journal of Applied Mathematics and Decision Sciences
Volume 7 (2003), Issue 1, Pages 49-59
doi:10.1155/S117391260300004X
Discovery of functional and approximate functional dependencies in relational databases
1Computer Science Department, The University of Texas at Tyler, Tyler 75799, Texas, USA
2Marathon Oil, Houston, Texas, USA
Copyright © 2003 Ronald S. King and James J. Legendre. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
This study develops the foundation for a simple, yet efficient method for uncovering functional and approximate functional dependencies in relational databases. The technique is based upon the mathematical theory of partitions defined over a relation's row identifiers. Using a levelwise algorithm the minimal non-trivial functional dependencies can be found using computations conducted on integers. Therefore, the required operations on partitions are both simple and fast. Additionally, the row identifiers provide the added advantage of nominally identifying the exceptions to approximate functional dependencies, which can be used effectively in practical data mining applications.