Bottom-up Induction of Functional Dependencies from Relations

Discovery of Dependencies and Models

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.