The complexity of dependency detection and discovery in relational databases

DOI10.1016/j.tcs.2021.11.020OpenAlexW3139384714WikidataQ114129137 ScholiaQ114129137MaRDI QIDQ2062133

Tobias Friedrich, Martin Schirneck, Thomas Bläsius

Publication date: 22 December 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2103.13331

zbMATH Keywords

functional dependencyinclusion dependencyparameterized complexitytransversal hypergraphparsimonious reductionenumeration complexitydata profilingunique column combinationW[3-completeness]

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Controlling entity integrity with key sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Strong computational lower bounds via parameterized complexity
• On product covering in 3-tier supply chain models: natural complete problems for W[3 and W[4]]
• Exploiting hidden structure in selecting dimensions that distinguish vectors
• Computational aspects of monotone dualization: a brief survey
• A theory of diagnosis from first principles
• Molecular computing, bounded nondeterminism, and efficient recursion
• An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
• Which problems have strongly exponential complexity?
• The \(k\)-feature set problem is \(W[2\)-complete]
• Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
• Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
• Incremental delay enumeration: space and time
• A complexity theory for hard enumeration problems
• Extension of some edge graph problems: standard and parameterized complexity
• Efficient algorithms for dualizing large-scale hypergraphs
• Complexity of identification and dualization of positive Boolean functions
• The Minimal Hitting Set Generation Problem: Algorithms and Computation
• Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Discovering functional and inclusion dependencies in relational databases
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Dual subimplicants of positive Boolean functions
• Reducibility among Combinatorial Problems
• Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
• Analytical approach to parallel repetition
• Parameterized Algorithms
• On the complexity of \(k\)-SAT

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