Bottom-up induction of functional dependencies from relations
Iztok Savnik, Peter A. Flach · 1993
Data dependencies express the presence of structure in database relations, that can be utilised in the database design process. The discovery of data dependencies can be viewed as an induction process. Like in induction, we can distinguish between topdown approaches and bottom-up approaches. In top-down approach, dependencies are generated and then tested against the given relation. Since each test requires O(n 2 ) comparisons, where n is the number of tuples in relation, this can be computationally costly. We propose an alternative approach which differs from the top-down approach in that it starts with an analysis of the tuples in the relation: a bottom-up approach. 1 Introduction Data dependencies are among the basic tools for modelling relational databases. They are used for the representation of constraints on the possible relations that can be instances of the relational scheme. Many types of data dependencies have been introduced and studied in the last two decades [8]. Of th...