@article{BlaesiusFriedrichSchirneck2021,
  author    = {Blaesius, Thomas and Friedrich, Tobias and Schirneck, Friedrich Martin},
  title     = {The complexity of dependency detection and discovery in relational databases},
  series = {Theoretical computer science},
  volume    = {900},
  journal   = {Theoretical computer science},
  publisher = {Elsevier},
  address   = {Amsterdam},
  issn      = {0304-3975},
  doi       = {10.1016/j.tcs.2021.11.020},
  pages     = {79 -- 96},
  year      = {2021},
  abstract  = {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 maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas.},
  language  = {en}
}
@article{SchirmerPapenbrockKoumarelasetal.2020,
  author    = {Schirmer, Philipp and Papenbrock, Thorsten and Koumarelas, Ioannis and Naumann, Felix},
  title     = {Efficient discovery of matching dependencies},
  series = {ACM transactions on database systems : TODS},
  volume    = {45},
  journal   = {ACM transactions on database systems : TODS},
  number    = {3},
  publisher = {Association for Computing Machinery},
  address   = {New York},
  issn      = {0362-5915},
  doi       = {10.1145/3392778},
  pages     = {33},
  year      = {2020},
  abstract  = {Matching dependencies (MDs) are data profiling results that are often used for data integration, data cleaning, and entity matching. They are a generalization of functional dependencies (FDs) matching similar rather than same elements. As their discovery is very difficult, existing profiling algorithms find either only small subsets of all MDs or their scope is limited to only small datasets. We focus on the efficient discovery of all interesting MDs in real-world datasets. For this purpose, we propose HyMD, a novel MD discovery algorithm that finds all minimal, non-trivial MDs within given similarity boundaries. The algorithm extracts the exact similarity thresholds for the individual MDs from the data instead of using predefined similarity thresholds. For this reason, it is the first approach to solve the MD discovery problem in an exact and truly complete way. If needed, the algorithm can, however, enforce certain properties on the reported MDs, such as disjointness and minimum support, to focus the discovery on such results that are actually required by downstream use cases. HyMD is technically a hybrid approach that combines the two most popular dependency discovery strategies in related work: lattice traversal and inference from record pairs. Despite the additional effort of finding exact similarity thresholds for all MD candidates, the algorithm is still able to efficiently process large datasets, e.g., datasets larger than 3 GB.},
  language  = {en}
}
@article{CaruccioDeufemiaNaumannetal.2021,
  author    = {Caruccio, Loredana and Deufemia, Vincenzo and Naumann, Felix and Polese, Giuseppe},
  title     = {Discovering relaxed functional dependencies based on multi-attribute dominance},
  series = {IEEE transactions on knowledge and data engineering},
  volume    = {33},
  journal   = {IEEE transactions on knowledge and data engineering},
  number    = {9},
  publisher = {Institute of Electrical and Electronics Engineers},
  address   = {New York, NY},
  issn      = {1041-4347},
  doi       = {10.1109/TKDE.2020.2967722},
  pages     = {3212 -- 3228},
  year      = {2021},
  abstract  = {With the advent of big data and data lakes, data are often integrated from multiple sources. Such integrated data are often of poor quality, due to inconsistencies, errors, and so forth. One way to check the quality of data is to infer functional dependencies (fds). However, in many modern applications it might be necessary to extract properties and relationships that are not captured through fds, due to the necessity to admit exceptions, or to consider similarity rather than equality of data values. Relaxed fds (rfds) have been introduced to meet these needs, but their discovery from data adds further complexity to an already complex problem, also due to the necessity of specifying similarity and validity thresholds. We propose Domino, a new discovery algorithm for rfds that exploits the concept of dominance in order to derive similarity thresholds of attribute values while inferring rfds. An experimental evaluation on real datasets demonstrates the discovery performance and the effectiveness of the proposed algorithm.},
  language  = {en}
}