@phdthesis{Papenbrock2017,
  author    = {Papenbrock, Thorsten},
  title     = {Data profiling - efficient discovery of dependencies},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-406705},
  school      = {Universit{\"a}t Potsdam},
  pages     = {viii, ii, 141},
  year      = {2017},
  abstract  = {Data profiling is the computer science discipline of analyzing a given dataset for its metadata. The types of metadata range from basic statistics, such as tuple counts, column aggregations, and value distributions, to much more complex structures, in particular inclusion dependencies (INDs), unique column combinations (UCCs), and functional dependencies (FDs). If present, these statistics and structures serve to efficiently store, query, change, and understand the data. Most datasets, however, do not provide their metadata explicitly so that data scientists need to profile them. While basic statistics are relatively easy to calculate, more complex structures present difficult, mostly NP-complete discovery tasks; even with good domain knowledge, it is hardly possible to detect them manually. Therefore, various profiling algorithms have been developed to automate the discovery. None of them, however, can process datasets of typical real-world size, because their resource consumptions and/or execution times exceed effective limits. In this thesis, we propose novel profiling algorithms that automatically discover the three most popular types of complex metadata, namely INDs, UCCs, and FDs, which all describe different kinds of key dependencies. The task is to extract all valid occurrences from a given relational instance. The three algorithms build upon known techniques from related work and complement them with algorithmic paradigms, such as divide \& conquer, hybrid search, progressivity, memory sensitivity, parallelization, and additional pruning to greatly improve upon current limitations. Our experiments show that the proposed algorithms are orders of magnitude faster than related work. They are, in particular, now able to process datasets of real-world, i.e., multiple gigabytes size with reasonable memory and time consumption. Due to the importance of data profiling in practice, industry has built various profiling tools to support data scientists in their quest for metadata. These tools provide good support for basic statistics and they are also able to validate individual dependencies, but they lack real discovery features even though some fundamental discovery techniques are known for more than 15 years. To close this gap, we developed Metanome, an extensible profiling platform that incorporates not only our own algorithms but also many further algorithms from other researchers. With Metanome, we make our research accessible to all data scientists and IT-professionals that are tasked with data profiling. Besides the actual metadata discovery, the platform also offers support for the ranking and visualization of metadata result sets. Being able to discover the entire set of syntactically valid metadata naturally introduces the subsequent task of extracting only the semantically meaningful parts. This is challenge, because the complete metadata results are surprisingly large (sometimes larger than the datasets itself) and judging their use case dependent semantic relevance is difficult. To show that the completeness of these metadata sets is extremely valuable for their usage, we finally exemplify the efficient processing and effective assessment of functional dependencies for the use case of schema normalization.},
  language  = {en}
}
@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}
}
@incollection{Fuhr2022,
  author    = {Fuhr, Harald},
  title     = {Development thinking and practice},
  series = {Handbook on global governance and regionalism},
  booktitle = {Handbook on global governance and regionalism},
  editor    = {R{\"u}land, J{\"u}rgen and Carrapatoso, Astrid},
  publisher = {Edward Elgar Publishing},
  address   = {Cheltenham, UK},
  isbn      = {978-1-80037-755-4},
  doi       = {10.4337/9781800377561.00037},
  pages     = {365 -- 380},
  year      = {2022},
  abstract  = {After some seventy years of intensive debates, there is an increasingly strong consensus within the academic and practitioner communities that development is both an objective and a process towards improving the quality of people's lives in various societal dimensions - economic, social, environmental, cultural and political - and about how subjectively satisfied they are with it. Since 2015, the seventeen Sustainable Development Goals (SDGs) of the United Nations (UN) reflect such consensus. The sections behind this argument are based on a review of (i) three key theoretical contributions to development and different phases of development thinking; (ii) global and regional governance arrangements and institutions for development cooperation; (iii) upcoming challenges to development policy and practice stemming from a series of new global challenges; and, (iv) development policy as a long and steady, increasingly global and participatory learning process.},
  language  = {en}
}