The complexity of dependency detection and discovery in relational databases
- Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximalMulti-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas.…
Author details: | Thomas BlaesiusGND, Tobias FriedrichORCiDGND, Friedrich Martin SchirneckORCiDGND |
---|---|
DOI: | https://doi.org/10.1016/j.tcs.2021.11.020 |
ISSN: | 0304-3975 |
ISSN: | 1879-2294 |
Title of parent work (English): | Theoretical computer science |
Publisher: | Elsevier |
Place of publishing: | Amsterdam |
Publication type: | Article |
Language: | English |
Date of first publication: | 2021/12/02 |
Publication year: | 2021 |
Release date: | 2023/12/07 |
Tag: | Unique column combination; W[3]-completeness; data profiling; dependency; enumeration complexity; functional dependency; inclusion; parameterized complexity; parsimonious reduction; transversal hypergraph |
Volume: | 900 |
Number of pages: | 18 |
First page: | 79 |
Last Page: | 96 |
Organizational units: | An-Institute / Hasso-Plattner-Institut für Digital Engineering gGmbH |
DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
Peer review: | Referiert |