Bottom-up Induction of Functional Dependencies from Relations

Iztok Savnik and Peter A. Flach

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.