FastFDs: A Heuristic-Driven, Depth-First Algorithm for Mining Functional Dependencies from Relation Instances Extended Abstract

@incollection{citeulike:2269278, abstract = {The problem of discovering functional dependencies (FDs) from an existing relation instance has received considerable attention in the database research community. To date, even the most efficient solutions have exponential complexity in the number of attributes of the instance. We develop an algorithm, FastFDs, for solving this problem based on a depth-first, heuristic-driven (DFHD) search for finding minimal covers of hypergraphs. The technique of reducing the FD discovery problem to the problem of finding minimal covers of hypergraphs was applied previously by Lopes et al. in the algorithm Dep-Miner. Dep-Miner employs a levelwise search for minimal covers, whereas FastFDs uses DFHD search. We report several tests on distinct benchmark relation instances involving Dep-Miner, FastFDs, and Tane. Our experimental results indicate that DFHD search is more efficient than Dep-Miner’s levelwise search or Tane’s partitioning approach for many of these benchmark instances.}, author = {Wyss, Catharine and Giannella, Chris and Robertson, Edward }, citeulike-article-id = {2269278}, doi = {http://dx.doi.org/10.1007/3-540-44801-2\_11}, journal = {Data Warehousing and Knowledge Discovery}, keywords = {data-profiling}, pages = {101--110}, posted-at = {2008-01-21 16:19:54}, priority = {2}, title = {FastFDs: A Heuristic-Driven, Depth-First Algorithm for Mining Functional Dependencies from Relation Instances Extended Abstract}, url = {http://dx.doi.org/10.1007/3-540-44801-2\_11}, year = {2001} }

TY - CHAP ID - citeulike:2269278 L3 - citeulike-article-id:2269278 TI - FastFDs: A Heuristic-Driven, Depth-First Algorithm for Mining Functional Dependencies from Relation Instances Extended Abstract JF - Data Warehousing and Knowledge Discovery SP - 101 EP - 110 N2 - The problem of discovering functional dependencies (FDs) from an existing relation instance has received considerable attention in the database research community. To date, even the most efficient solutions have exponential complexity in the number of attributes of the instance. We develop an algorithm, FastFDs, for solving this problem based on a depth-first, heuristic-driven (DFHD) search for finding minimal covers of hypergraphs. The technique of reducing the FD discovery problem to the problem of finding minimal covers of hypergraphs was applied previously by Lopes et al. in the algorithm Dep-Miner. Dep-Miner employs a levelwise search for minimal covers, whereas FastFDs uses DFHD search. We report several tests on distinct benchmark relation instances involving Dep-Miner, FastFDs, and Tane. Our experimental results indicate that DFHD search is more efficient than Dep-Miner’s levelwise search or Tane’s partitioning approach for many of these benchmark instances. KW - data-profiling AU - Wyss, Catharine AU - Giannella, Chris AU - Robertson, Edward PY - 2001/// UR - http://dx.doi.org/10.1007/3-540-44801-2_11 ER -