FastFDs

FastFDs: A heuristic-driven, depth-first algorithm for mining functional dependencies from relation instances. 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</font size=-1>. Our experimental results indicate that DFHD search is more efficient than Dep-Miner’s levelwise search or TANE</font size=-1>’s partitioning approach for many of these benchmark instances.


References in zbMATH (referenced in 10 articles , 1 standard article )

Showing results 1 to 10 of 10.
Sorted by year (citations)

  1. Kim, Mijung; Candan, K. Selçuk: Decomposition-by-normalization (DBN): leveraging approximate functional dependencies for efficient CP and Tucker decompositions (2016)
  2. Baixeries, Jaume; Kaytoue, Mehdi; Napoli, Amedeo: Characterizing functional dependencies in formal concept analysis with pattern structures (2014)
  3. Wolf, Garrett; Kalavagattu, Aravind; Khatri, Hemal; Balakrishnan, Raju; Chokshi, Bhaumik; Fan, Jianchun; Chen, Yi; Kambhampati; Subbarao: Query processing over incomplete autonomous databases: query rewriting using learned data dependencies (2009) ioport
  4. Trinh, Thu: Using transversals for discovering XML functional dependencies (2008)
  5. Wei, Qiang; Chen, Guoqing: Efficient discovery of functional dependencies with degrees of satisfaction (2004)
  6. Giannella, Chris; Robertson, Edward: A note on approximation measures for multi-valued dependencies in relational databases (2003)
  7. De Marchi, Fabien; Lopes, Stéphane; Petit, Jean-Marc: Efficient algorithms for mining inclusion dependencies (2002)
  8. Giannella, Chris M.; Dalkilic, Mehmet M.; Groth, Dennis P.; Robertson, Edward L.: Improving query evaluation with approximate functional dependency based decompositions (2002)
  9. Lopes, Stéphane; Petit, Jean-Marc; Lakhal, Lotfi: Functional and approximate dependency mining: Database and FCA points of view (2002)
  10. Wyss, Catharine; Giannella, Chris; Robertson, Edward: FastFDs: A heuristic-driven, depth-first algorithm for mining functional dependencies from relation instances. extended abstract (2001)