Denial constraints (DCs) are the de facto language to specify integrity constraints [1], which have various usages, such as database design, data integration, query optimization, or data cleaning. DCs generalize unique column combinations, functional dependencies, and order dependencies. Each DC defines a set of predicates for which its predicates cannot hold true simultaneously. This expressive power, however, comes with the cost of a very large search space. So, discovering denial constraints (DCs) is computationally expensive. Researchers have developed efficient algorithms to discovery DCs, such as FastDC [2], BFastDC [3], HYDRA [4], or DCFinder [1]. Their application is limited to rather small datasets, though, because executing those algorithms on datasets with around 1 mio. rows and 20 attributes already takes hours [1]. Research for other data dependencies has shown that dynamic parallelization and distribution techniques can decrease the algorithm runtimes enough to make the processing of larger datasets possible [5].

The goal of this master thesis is to develop a distributed algorithm to efficiently discover denial constraints in large datasets.

[1] Eduardo H. M. Pena, Eduardo C. de Almeida, and Felix Naumann. Discovery of Approximate (and Exact) Denial Constraints. PVLDB, 13 (3) (2019). DOI:10.14778/3368289.3368293
[2] Xu Chu, Ihab. F. Ilyas, and Paolo Papotti. Discovering denial constraints. PVLDB, 6 (13) (2013). DOI:10.14778/2536258.2536262
[3] Hai Liu, Dongqing Xiao, Pankaj Didwania, and Mohamed Y. Eltabakh. Exploiting soft and hard correlations in big data query optimization. PVLDB, 9 (12) (2016). DOI:10.14778/2994509.2994519
[4] Tobias Bleifuß, Sebastian Kruse, and Felix Naumann. Efficient denial constraint discovery with Hydra. PVLDB, 11(3) (2017). DOI:10.14778/3157794.3157800
[5] Sebastian Schmidl and Thorsten Papenbrock: Efficient Distributed Discovery of Bidirectional Order Dependencies. The VLDB Journal (2022). DOI:10.1007/s00778-021-00683-4

For more information please contact Youri Kaminsky. Supervision could be in cooperation with Eduardo Pena from Universidade Tecnológica Federal do Paraná (UTFPR) in Toledo, Brasil.

Data quality is a multidimensional concept that is characterized by different dimensions, such as accuracy, completeness, or consistency. Consistency captures the violation of semantic rules defined over data [1]. Especially when data is not stored in relational database, but CSV or other file formats, semantic rules such as functional dependencies are not always enforced. Here, mining partial functional dependencies can help to detect violations as potential data errors reducing the overall consistency of a dataset. 

The goal of this master thesis is to: 

• Extend the data profiling algorithm HyFD to efficiently mine partial FDs over time, based on [2] (see temporal inclusion dependencies [3] for the time aspect)
• Create a DQ metric for the consistency dimension (based on the results of the partial FD mining algorithm) and implement this within our existing data quality tool Metis
• Evaluate the efficiency of the mining approach and the accuracy of your consistency assessment results

[1] Batini, C., & Scannapieco, M. (2016). Data and information quality. Cham, Switzerland: Springer International Publishing, 63.
[2] Seeger, M., Papenbrock, T. (2025). Profiling of Partial Data Dependencies for Data Cleaning. (in preparation)
[3] Bornemann, L., Bleifuß, T., Kalashnikov, D. V., Nargesian, F., Naumann, F., & Srivastava, D. (2024, March). Efficient Discovery of Temporal Inclusion Dependencies in Wikipedia Tables. In Advances in database technology. OpenProceedings. org.

For more information please contact Lisa Ehrlinger. Supervision could be in cooperation with Marcian Seeger from Marburg University, Germany.

Data quality is a multidimensional concept that is characterized by different dimensions, such as accuracy, consistency, or readability [1]. Readability describes the degree to which data represents the modelled domain in a natural and clear way, with the aim of being self-explanatory to the user. Readability is one central, yet underexplored data quality metric. Based on our prior work (towards assessing the readability of single string values in table cells [2, 3]), we would like to deeper explore on how to aggregate these single readability scores to a comprehensive score within a table. Here, we want to specifically take into account the context in which a word appears. 

The goal of this master thesis is to: 

• Explore LLMs and a WordNet to assess the readability of textual data in tables
• Extend our existing DQ tool Metis with a metric that automatically assesses the readability of a CSV file
• Develop an approach on how to aggregate the single DQ assessment results to a single DQ measure for the readability of one table (e.g., CSV file)
• Perform a three-fold evaluation of your DQ metric: (1) evaluate the assessment results with polluted data and known ground truth, (2) test your DQ metric with dirty real-world data, and (3) compare the output of your metric to the assessment of humans (tiny user study sufficient)

[1] Batini, C., & Scannapieco, M. (2016). Data and information quality. Cham, Switzerland: Springer International Publishing, 63.
[2] Ehrlinger, L., Huszar, G., & Wöß, W. (2019). A schema readability metric for automated data quality measurement. DBKDA, 12.
[3] Porbeck, J., Riedel, T., & Debski, R. (2024). Automatic human readability assessment of tabular data. Seminar report, HPI.

For more information please contact Lisa Ehrlinger or Sedir Mohammed.