Patent ID: 7873628

Claim:
A method for discovering functional dependencies within a relation, the method comprising computer implemented steps of: a computer system generating a sample of tuples from the relation, said tuples including a plurality of attributes; wherein the sample of tuples includes data for some but not all tuples in the relation; determining whether a certain candidate dependency from a search space of candidate functional dependencies exists within the sample; wherein said certain candidate dependency is based on a certain determining set of one or more attributes that determines a given attribute; if said certain candidate dependency exists within the sample, then performing the steps of: determining whether the certain candidate dependency exists within the entire relation; removing from the search space candidate functional dependencies that: determine the given attribute, and have a determining set that determines said certain determining set; and foregoing determining whether a candidate functional dependency removed from the search space exists within the sample; and if said certain candidate dependency exists within the entire relation, storing data which indicates that said certain candidate dependency is a functional dependency that holds within the relation.