Methods and Apparatus for Identifying Conditional Functional Dependencies
OwnerWenfei Fan, Ming Xionginventors
Life of this patent
Estimating the term…
Abstract
Methods and apparatus are provided for discovering minimal conditional functional dependencies (CFDs). CFDs extend functional dependencies by supporting patterns of semantically related constants, and can be used as rules for cleaning relational data. A disclosed CFDMiner algorithm, based on techniques for mining closed itemsets, discovers constant minimal CFDs. A disclosed CTANE algorithm discovers general minimal CFDs based on the levelwise approach. A disclosed FastCFD algorithm discovers general minimal CFDs based on a depth-first search strategy, and an optimization technique via closed-itemset mining to reduce search space.
Claims15
A method for identifying one or more constant conditional functional dependencies defined over a schema, R, given a sample relation, r, of said schema, R, and a support threshold, k, comprising:
- mining k-frequent closed itemsets and k-frequent free itemsets using a latest mining technique following a depth-first search scheme, wherein said one or more constant conditional functional dependencies comprise only constant patterns.
A method for identifying one or more conditional functional dependencies defined over a schema, R, given a sample relation, r, of said schema, R, and a support threshold, k, comprising:
- generating an attribute set/pattern lattice comprised of attribute/value pairs that appear at least k times, wherein each attribute occurs with an unnamed variable;
- and
- employing a levelwise approach to mine said conditional functional dependencies at each level k+1 of said lattice, wherein each set at said level k+1 consists of k+1 attributes;
- and
- pruning said lattice based on attributes at level k.
A method for identifying one or more conditional functional dependencies defined over a schema, R, given a sample relation, r, of said schema, R, and a support threshold, k, comprising:
- identifying a set of k-frequent patterns in said schema:
- for each identified k-frequent pattern, maintaining a set of minimal difference sets;
- identifying minimal covers of said minimal difference sets using a depth-first approach based on an ordering of attributes;
- producing a candidate conditional functional dependency if no variable in said patterns can be removed;
- and
- evaluating one or more minimality conditions for each identified k-frequent pattern.
Dependencies are inferred from the claim text.