Representative Functional Dependencies

Functional dependencies (FDs) have been extensively employed in many applications, including query optimization, data cleaning, data obfuscation, and schema normalization. However, the number of FDs grows drastically as the dimensionality of datasets expands, making it impractical for large-scale applications operating on the complete set of FDs to utilize every FD. In this paper, we formulate the problem of representative FD discovery as obtaining a subset of FDs that effectively represents the complete set. Representativeness is measured by the pairwise similarity of FDs because similar FDs often convey duplicative information. In contrast to selecting a representative subset from the complete set after FD discovery, we extract it directly during the discovery process for superior efficiency. Specifically, our algorithm integrates the representativeness verification into the lattice traversal strategy (a prominent method in FD discovery) to significantly reduce the costly validation of FD candidates by only validating representative ones. Furthermore, we enhance our algorithm with three sophisticated designs: nearest indexes to prune the search space, dynamic stripped partitions to accelerate the FD validation, and a compressed FD-tree to guarantee the FD minimality, respectively. Experimental results on real-world and synthetic datasets justify the design of representative FDs and verify the efficiency and effectiveness of the proposed algorithms.