The parameterized complexity of dependency detection in relational databases

DOI10.4230/LIPICS.IPEC.2016.6MaRDI QIDQ4634389zbMATH OpenFDO

Authors Thomas Bläsius, Tobias Friedrich, Martin Schirneck

Publication date 10 April 2018

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2016.6

zbMATH Keywords

parameterized complexityfunctional dependencyinclusion dependencyunique column combinationprofiling relational data

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

Recommendations

• The complexity of dependency detection and discovery in relational databases
• scientific article; zbMATH DE number 1222098
• On the complexity of database queries
• A survey of some combinatorial results concerning functional dependencies in database relations.
• On the complexity of inferring functional dependencies

Cited in

(9)

• Average-case complexity for the execution of recursive definitions on relational databases (paper no 50-95 accepted for publication in ACTA INFORMATICA)
• Possibilistic keys
• The complexity of dependency detection and discovery in relational databases
• Parameterised complexity of model checking and satisfiability in propositional dependence logic
• On the Complexity of Insertion Propagation with Functional Dependency Constraints
• A double exponential lower bound for the distinct vectors problem
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Controlling entity integrity with key sets
• scientific article; zbMATH DE number 7651160 (Why is no real title available?)

This page was built for publication: The parameterized complexity of dependency detection in relational databases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4634389)