# Enumeration in Data Profiling

This is a platform for the research project on enumeration problems in data profiling of the HPI Algorithm Engineering group lead by Tobias Friedrich. The research is conducted in close collaboration with our colleagues at the neighboring Information Systems group of Felix Naumann as well as with Kitty Meeks at the University of Glasgow.

## Description

Data profiling is the gathering of metadata from databases. In relational data dependencies among different attributes are of particular importance, e.g., unique column combinations (UCCs, a.k.a. candidate keys), functional dependencies, inclusion dependencies, and denial constraints. Usually it is not enough to detect the existence of a single such dependency in a database, instead one is interested in a comprehensive list of all occurrences. This naturally leads to several interesting enumeration problems.

Many discovery algorithms in data profiling use a reduction to the hitting set problem in hypergraphs. In the case of UCCs, we showed that their enumeration is in fact equivalent to the famous transversal hypergraph problem, i.e., computing all minimal hitting sets. While the computational complexity of the transversal hypergraph problem is a major open question, this equivalence opens intriguing new perspectives and in turn facilitates new algorithms for data profiling.

The results of this project are continuously published at the leading scientific conferences, including at IPEC 2016, ALENEX 2019, VLDB 2020, and ESA 2020. Additionally, the late-breaking developments are presented at workshops like the 2018 Dagstuhl Seminar on Algorithmic Enumeration and WEPA 2019.

The project includes research conducted together with our students. Julius Lischeid wrote his bachelor's thesis on * Lexicographic Enumeration of Hitting Sets in Hypergraphs* and Benjamin Feldmann wrote his master's thesis on

*Distributed Unique Column Combinations Discovery*. Johann Birnick contributed to the development and implementation of the

*HPIValid*algorithm as part of this project.

## HPIValid

The most recent algorithm developed in this project is *HPIValid, *it enumerates all inclusion-wise minimal unique column combinations of a given database. The code of a C++ implementation can be found in this GitLab repository. A ZIP-file with the data used for testing can be downloaded here (3.5GB).

2020 [ to top ]

- Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery. Proceedings of the VLDB Endowment 2020: 2270 - 2283
- The Minimization of Random Hypergraphs. European Symposium on Algorithms (ESA) 2020: 21:1-21:15

2019 [ to top ]

- Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling. Algorithm Engineering and Experiments (ALENEX) 2019: 130-143

2016 [ to top ]

- The Parameterized Complexity of Dependency Detection in Relational Databases. International Symposium on Parameterized and Exact Computation (IPEC) 2016: 6:1-6:13

Additionally, several full versions are available as a preprint on ArXiv.

## Code

A C++ implementation of the UCC enumeration algorithm described in the ALENEX paper is available at GitHub. Special thanks go to Julius Lischeid for authoring and maintaining the code. An implementation of *HPIValid *can be found in at our GitLab.

## Data

Some hypergraphs together with their respective databases can be found here (ZIP, 39.1MB). The data samples with 100,000 records were used for testing in the extended version of the paper * Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling.* The data we used for testing *HPIValid *can be downloaded here (ZIP, 3.5GB).

## Additional Resources

- This survey article gives an overview of problems and techniques in data profiling.
- The slides of the talk at the Dagstuhl seminar on Algorithmic Enumeration can be found here.
- The Information Systems group maintains another GitHub repository containing different data profiling tools, including their Metanome suite.