The discovery of functional dependencies from relations is an important database analysis technique. We present TANE, an efficient algorithm for finding functional dependencies from large databases. TANE is based on partitioning the set of rows with respect to their attribute values, which makes testing the validity of functional dependencies fast even for a large number of tuples. The use of partitions also makes the discovery of approximate functional dependencies easy and efficient and the erroneous or exceptional rows can be identified easily. Experiments show that TANE is fast in practice. For benchmark databases the running times are improved by several orders of magnitude over previously published results. The algorithm is also applicable to much larger datasets than the previous methods. Received September 17, 1998; revised March 31, 1999  Functional dependencies are relationships between attributes of a database relation: a functional dependency states that the value of an attribute is uniquely determined by the values of some other attributes. For example, in an address database, zip code is determined by city and street address. The discovery of functional dependencies from relations has received considerable interest (e.g. [1, 2, 3, 4, 5, 6, 7, 8] ). Automated database analysis is, of course, interesting for knowledge discovery and data mining (KDD) purposes. For instance, consider a database of chemical compounds and their outcomes on various bioassays. Discovering that an essential quality, such as carcinogenicity, of a compound depends functionally from certain structural attributes can be invaluable. Functional dependencies also have well-known applications in the areas of database management, reverse engineering [9] and query optimization [10] . Formally, a functional dependency over a relation schema R is an expression X → A, where X ⊆ R and A ∈ R. The dependency holds or is valid in a given relation r over R if for all pairs of tuples t, u ∈ r we have: (we also say that t and u agree on X and A). A functional dependency X → A is minimal (in r ) if A is not functionally dependent on any proper subset of X, i.e. if Y → A does not hold in r for any Y ⊂ X. The dependency X → A is trivial if A ∈ X. The central task we consider is the following: given a relation r , find all minimal non-trivial dependencies that hold in r . An approximate functional dependency is a functional dependency that almost holds. For example, gender is approximately determined by first name. Such dependencies arise in many databases when there is a natural dependency between attributes, but some tuples contain errors or represent exceptions to the rule. The discovery of unexpected but meaningful approximate dependencies seems to be an interesting and realistic goal in many data mining applications. Consider, again, a database of chemical compounds. An approximate dependency from a set of structural attributes to the carcinogenicity could be as valuable as a functional dependency: both could provide valuable hints to biochemists for potential causes of cancer but neither can be taken as a fact without further analysis by domain specialists. Approximate functional dependencies also have applications in database design [11] . There are many possible ways of defining the approximateness of a dependency X → A. The definition we use is based on the minimum number of tuples that need to be removed from the relation r for X → A to hold in r : the error e(X → A) is defined as e(X → A) = min{|s| | s ⊆ r and X → A holds in r \ s}/|r |. The measure e has a natural interpretation as the fraction of tuples with exceptions or errors affecting the dependency. Given an error threshold ε, 0 ≤ ε ≤ 1, we say that X → A is an approximate (functional) dependency if and only if e(X → A) is at most ε. In this paper, we also consider the approximate dependency inference task: given a relation r and a threshold ε, find all minimal non-trivial approximate dependencies.
A significant number of papers revolve around the discovery of functional dependencies, with the TANE algorithm as the most famous example REF .
TANE: An Efficient Algorithm for Discovering Functional and Approximate Dependencies
Comput. J.
Comput. J.
Computer Science