@article{BlaesiusFriedrichLischeidetal.2022,
  author    = {Bl{\"a}sius, Thomas and Friedrich, Tobias and Lischeid, Julius and Meeks, Kitty and Schirneck, Friedrich Martin},
  title     = {Efficiently enumerating hitting sets of hypergraphs arising in data profiling},
  series = {Journal of computer and system sciences : JCSS},
  volume    = {124},
  journal   = {Journal of computer and system sciences : JCSS},
  publisher = {Elsevier},
  address   = {San Diego},
  issn      = {0022-0000},
  doi       = {10.1016/j.jcss.2021.10.002},
  pages     = {192 -- 213},
  year      = {2022},
  abstract  = {The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an algorithm running in output-polynomial time, but whose space requirement also scales with the output. We improve this to polynomial delay and space. Central to our approach is the extension problem, deciding for a set X of vertices whether it is contained in any minimal hitting set. We show that this is one of the first natural problems to be W[3]-complete. We give an algorithm for the extension problem running in time O(m(vertical bar X vertical bar+1) n) and prove a SETH-lower bound showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases.},
  language  = {en}
}
@article{KossmannPapenbrockNaumann2021,
  author    = {Koßmann, Jan and Papenbrock, Thorsten and Naumann, Felix},
  title     = {Data dependencies for query optimization},
  series = {The VLDB journal : the international journal on very large data bases / publ. on behalf of the VLDB Endowment},
  volume    = {31},
  journal   = {The VLDB journal : the international journal on very large data bases / publ. on behalf of the VLDB Endowment},
  number    = {1},
  publisher = {Springer},
  address   = {Berlin ; Heidelberg ; New York},
  issn      = {1066-8888},
  doi       = {10.1007/s00778-021-00676-3},
  pages     = {1 -- 22},
  year      = {2021},
  abstract  = {Effective query optimization is a core feature of any database management system. While most query optimization techniques make use of simple metadata, such as cardinalities and other basic statistics, other optimization techniques are based on more advanced metadata including data dependencies, such as functional, uniqueness, order, or inclusion dependencies. This survey provides an overview, intuitive descriptions, and classifications of query optimization and execution strategies that are enabled by data dependencies. We consider the most popular types of data dependencies and focus on optimization strategies that target the optimization of relational database queries. The survey supports database vendors to identify optimization opportunities as well as DBMS researchers to find related work and open research questions.},
  language  = {en}
}
@article{SchmidlPapenbrock2022,
  author    = {Schmidl, Sebastian and Papenbrock, Thorsten},
  title     = {Efficient distributed discovery of bidirectional order dependencies},
  series = {The VLDB journal},
  volume    = {31},
  journal   = {The VLDB journal},
  number    = {1},
  publisher = {Springer},
  address   = {Berlin ; Heidelberg ; New York},
  issn      = {1066-8888},
  doi       = {10.1007/s00778-021-00683-4},
  pages     = {49 -- 74},
  year      = {2022},
  abstract  = {Bidirectional order dependencies (bODs) capture order relationships between lists of attributes in a relational table. They can express that, for example, sorting books by publication date in ascending order also sorts them by age in descending order. The knowledge about order relationships is useful for many data management tasks, such as query optimization, data cleaning, or consistency checking. Because the bODs of a specific dataset are usually not explicitly given, they need to be discovered. The discovery of all minimal bODs (in set-based canonical form) is a task with exponential complexity in the number of attributes, though, which is why existing bOD discovery algorithms cannot process datasets of practically relevant size in a reasonable time. In this paper, we propose the distributed bOD discovery algorithm DISTOD, whose execution time scales with the available hardware. DISTOD is a scalable, robust, and elastic bOD discovery approach that combines efficient pruning techniques for bOD candidates in set-based canonical form with a novel, reactive, and distributed search strategy. Our evaluation on various datasets shows that DISTOD outperforms both single-threaded and distributed state-of-the-art bOD discovery algorithms by up to orders of magnitude; it can, in particular, process much larger datasets.},
  language  = {en}
}