On the complexity of inferring functional dependencies

DOI10.1016/0166-218X(92)90031-5zbMath0767.68034WikidataQ61450080 ScholiaQ61450080MaRDI QIDQ1202891

Kari-Jouko Raeihae, Heikki Mannila

Publication date: 31 January 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

relational databaselower boundsfunctional dependenciesquery optimizationdependency inference problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Related Items (16)

Improved time complexities for learning Boolean networks ⋮ Performance analysis of a greedy algorithm for inferring Boolean functions ⋮ On the fixed-parameter tractability of the equivalence test of monotone normal forms ⋮ Mining approximate interval-based temporal dependencies ⋮ Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ Approximate inference of functional dependencies from relations ⋮ Decomposition-by-normalization (DBN): leveraging approximate functional dependencies for efficient CP and Tucker decompositions ⋮ Reducing one class of machine learning algorithms to logical operations of plausible reasoning ⋮ Functional and multivalued dependencies in nested databases generated by record and list constructor ⋮ Normal forms and syntactic completeness proofs for functional independencies ⋮ Algorithms for computing the Shapley value of cooperative games on lattices ⋮ Join on Closure Systems Using Direct Implicational Basis Representation ⋮ Lower bounds for three algorithms for transversal hypergraph generation ⋮ On the complexities of consistency checking for restricted UML class diagrams ⋮ A simple greedy algorithm for finding functional relations: Efficient implementation and average case analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Design by example: An application of Armstrong relations
• On the number of databases and closure operations
• On the Structure of Armstrong Relations for Functional Dependencies
• Algorithms for inferring functional dependencies from relations
• On the Optimality of Some Set Algorithms

This page was built for publication: On the complexity of inferring functional dependencies