The complexity of dependency detection and discovery in relational databases
type: Item
instance of: scholarly article
title: The complexity of dependency detection and discovery in relational databases
author: Thomas Bläsius
author: Tobias Friedrich
author: Martin Schirneck
published in: Theoretical Computer Science
publication date: 2021-12-22T00:00:00Z
full work available at URL: https://arxiv.org/abs/2103.13331
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7450582
zbMATH Keywords: data profiling
zbMATH Keywords: enumeration complexity
zbMATH Keywords: functional dependency
zbMATH Keywords: inclusion dependency
zbMATH Keywords: parameterized complexity
zbMATH Keywords: parsimonious reduction
zbMATH Keywords: transversal hypergraph
zbMATH Keywords: unique column combination
zbMATH Keywords: W[3]-completeness
MaRDI profile type: Publication
OpenAlex ID: W3139384714
Wikidata QID: Q114129137
cites work: Molecular computing, bounded nondeterminism, and efficient recursion
cites work: Complexity of identification and dualization of positive Boolean functions
cites work: Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
cites work: Q4634389
cites work: Dual subimplicants of positive Boolean functions
cites work: Incremental delay enumeration: space and time
cites work: Extension of some edge graph problems: standard and parameterized complexity
cites work: Strong computational lower bounds via parameterized complexity
cites work: On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]
cites work: Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
cites work: The \(k\)-feature set problem is \(W[2]\)-complete
cites work: A complexity theory for hard enumeration problems
cites work: Parameterized Algorithms
cites work: Q4441489
cites work: Analytical approach to parallel repetition
cites work: Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
cites work: Fixed-Parameter Tractability and Completeness I: Basic Results
cites work: Fixed-parameter tractability and completeness II: On completeness for W[1]
cites work: Fundamentals of parameterized complexity
cites work: Identifying the Minimal Transversals of a Hypergraph and Related Problems
cites work: New Results on Monotone Dualization and Generating Hypergraph Transversals
cites work: Computational aspects of monotone dualization: a brief survey
cites work: Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
cites work: On the Complexity of Dualization of Monotone Disjunctive Normal Forms
cites work: Exploiting hidden structure in selecting dimensions that distinguish vectors
cites work: The Minimal Hitting Set Generation Problem: Algorithms and Computation
cites work: Q4804932
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: Discovering functional and inclusion dependencies in relational databases
cites work: Reducibility among Combinatorial Problems
cites work: Q3668890
cites work: Efficient algorithms for dualizing large-scale hypergraphs
cites work: Q5710169
cites work: An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
cites work: A theory of diagnosis from first principles
cites work: Q4024050
DOI: 10.1016/J.TCS.2021.11.020
description: scientific article; zbMATH DE number 7450582