• A regular expression (regex) is an elegant, standard, and informative description of the content of a database column to support various analytical tasks.
• Building a high-quality expression is a difficult and tedious process that needs human involvement in most cases.
• Automatic learning and inference of such expressions is a both relevant and challenging task.

The regular expression is a formal language consisting of meta-symbols to describe a pattern in a set of data values. A large class of data-driven tasks is based on using regular expressions, such as information retrieval, data validation, entity extraction, DNA string matching, etc. Under the umbrella of Data Profiling, a regular expression representation of the columns of a table are very interesting metadata. This metadata has many applications, such as (1) data format transformation and data preparation, (2) instance-based schema matching, (3) data validation and cleansing by enforcing the most frequent patterns in a column, and (4) data integration from different sources.

An optimal regex should be neither too specific nor too generic. For example, ^\d{4}$ and ^(19|20)\d{2}$ are regexes that can match a year column in the 20th or 21st centuries. But, which one is optimal and in which use case?

The main goal of this thesis is to design a scalable, precise and fully-automated algorithm to learn and infer optimal regular expressions of each column in a table. This includes the development of several use cases and corresponding quality measures to determine the quality of the results.

For more information please contact Prof. Felix Naumann or Hazar Harmouch.

An inclusion dependency between two attribute sets X1,...,Xn and Y1,...,Yn of two relations R and S is defined in the following: For each tuple of values appearing in columns X1,...,Xn of Relation R, there must be an equivalent tuple in columns Y1,...,Yn in relation S. In short this is denoted as R[X1,...,Xn] ⊆ S[Y1,...,Yn].

Inclusion dependencies are an important topic in the research area of data profiling, which aims to extract new metadata for tables. In particular, inclusion dependencies are a prerequisite for foreign keys and thus are a starting point to detect meaningful relationships between tables. Existing work has suggested algorithms for the discovery of inclusion dependencies in databases [1] and webtables [2].

While the discovery of inclusion dependencies has been researched for static databases or webtables, the discovery of inclusion dependencies in historical data remains an open problem. In particular, it should be discussed how the definition of inclusion dependencies for database snapshots (as explained in the first paragraph) should be generalized to table histories and whether the development of the database over time can be used to reduce the search space.

Tasks in this thesis include:

• Define temporal inclusion dependencies as candidates for foreign keys between two dynamic tables.

• Design of a scalable, distributed algorithm for the discovery of inclusion dependencies. Implementation of the Algorithm in Apache Spark

• Creation of a Gold-Standard on webtables

• Evaluation on real-world datasets, such as all relational tables in the History of Wikipedia (the dataset is already available)

For more information please contact Prof. Felix Naumann, Tobias Bleifuß or Leon Bornemann.

[1] Papenbrock, Thorsten, et al. "Divide & conquer-based inclusion dependency discovery." Proceedings of the VLDB Endowment 8.7 (2015): 774-785.

[2] Tschirschnitz, Fabian, Thorsten Papenbrock, and Felix Naumann. "Detecting inclusion dependencies on very many tables." ACM Transactions on Database Systems (TODS) 42.3 (2017): 18.

Further Related Work on adapting Dependencies to Temporal Databases:

[3] Jensen, Christian S., Richard T. Snodgrass, and Michael D. Soo. "Extending existing dependency theory to temporal databases." IEEE Transactions on Knowledge and Data Engineering 8.4 (1996): 563-582.

[4] Artale, Alessandro, and Enrico Franconi. "Temporal ER modeling with description logics." International Conference on Conceptual Modeling. Springer, Berlin, Heidelberg, 1999.

Data change, all the time. This undeniable fact has motivated the development of database management systems in the first place. While they are good at recording this change, and while much technology has emerged to retrieve and analyze this data, there is not yet much research to explore and understand the nature of such change, i.e., the behavior of a dataset over time. A large research undertaking in our group is dedicated to developing models, methods, and systems to systematically explore and analyze such changes [3].

The goal of this thesis is to develop a query language for changes in data. One of its key requirements is to support complex queries that involve (temporal) patterns. For example, we want to answer queries like:

• “For what percentage of cities that underwent a change of government between 1990 and 2000, was there a reversal of that change within the next decade?”

• “Which countries recorded population growth for at least 10 years and then shrank by at least the same amount within 5 years?”.

• “How often do employees get salary increases compared to the average number of salary increases of all people who have ever been their supervisor? How high are these?”

The task is not only to design the language and demonstrate its usefulness, but also to develop a prototypical implementation. It could draw inspiration from related temporal query languages such as TSQL2 [1] or T-SPARQL [2], but should distinguish from them by focusing on the change and not on temporal data. The focus of the new language should be on state transitions and not on states at certain times in the past, which is why these state changes should be the atomic units of its result sets.

[1] Snodgrass, Richard T., ed. The TSQL2 temporal query language. Vol. 330. Springer Science & Business Media, 2012.

[2] Fabio Grandi. T-SPARQL: A TSQL2-like Temporal Query Language for RDF. In ADBIS (Local Proceedings), pp. 21-30. 2010.

[3] https://hpi.de/naumann/projects/data-profiling-and-analytics/data-change-exploration.html

For more information please contact Prof. Felix Naumann or Tobias Bleifuß.

The maintenance of many data sources takes place in laborious detail work by individual users. For example, the infoboxes on Wikipedia, which many search engines use as a source of factual knowledge, are maintained in this way. A user might update the number of inhabitants for all counties in Mississippi or update their mayors after a local election. For this purpose, (s)he searches for all articles for the individual counties and changes the semi-structured data of infoboxes there. However, different types of errors occur: the user may have forgotten counties or might confuse a county with an identical county in another state or use too many or too few trailing zeros.

In the Janus project [1], we are currently examining how this type of systematic change can follow a concise, logical description. For this purpose, we are translating a set of these changes into an update-query similar to SQL. But to do this, we first need to identify that set of changes that belongs to a systematic change. The recognition of the limits of systematic changes (i.e. when did the user start, when was (s)he finished, did (s)he stop the work and do something else in the meantime?) is a non-trivial matter, which shall be solved by this master thesis.

The work will develop a clustering procedure that considers both the temporal distribution of changes and the semantics of the changes. The resulting clusters should have a clearly recognizable systematic aspect and be complete with respect to this aspect (the user has not made any further changes that correspond to this aspect). Possibly the clusters could be organized hierarchically. Part of the work is the comparison against a baseline and selecting a suitable methodology for this comparison.

[1] https://IANVS.org/

For more information please contact Prof. Felix Naumann or Tobias Bleifuß.

Web tables constitute a rich and often free source of information. Unfortunately, not all information contained in them is always trustworthy and up-to-date. However, the table's change-history can help assess the trustworthiness and timeliness of its information: Who has authored the table? When was the table last updated? How much was changed? This analysis can, of course, be performed at table-level, but it is much more valuable if done on a cell- or value-level. Only then there is a chance to recognize quality discrepancies within a table.

Tracing the change history by hand is a very tedious task. Tables often change their layout and schema over the course of their lifetime, making it difficult to track which cells are predecessors or successors to each other. In addition, individual cells can be split into multiple cells and, vice-versa, merged into one. The goal of this thesis is to develop an algorithm that automatically constructs the edit history of individual cells in web tables as a graph. Each node in this graph represents one version of one cell at a particular point in time and each edge represents the relationship of these cell versions.

In the context of the Janus project [1] we have already developed an algorithm for matching tables over time and also a baseline algorithm that matches cells (with some constraints) over time. The master's thesis can build on this work and in particular overcome its limitations. For example, the work can focus on improved semantic interpretation of the tables and on scaling aspects. There is already a small gold standard for cell matching, but part of the task is to extend and possibly adapt it. The previous implementation is available in Java, so knowledge of this programming language is beneficial.

[1] https://www.IANVS.org

For more information please contact Prof. Felix Naumann or Tobias Bleifuß.

Machine learning and deep learning are increasingly seen as silver bullets for many difficult knowledge mining tasks. Stanford’s InfoLab has proposed and provides the novel Snorkel platform (http://hazyresearch.github.io/snorkel/), which alleviates many of the difficult preparatory tasks involved in applying learning methods to real-world problems. In particular, it significantly reduces the painful work of creating training data by reducing the task to the creation of a few simple tagging functions in lieu of manually tagging actual data.

We propose to apply this technique to the notoriously difficult problems of named entity recognition (NER) and relationship extraction (RE). One particular goal is to find out with how few and how simple tagging functions one can get away with.

For more information please contact Prof. Felix Naumann or Michael Loster.

Duplicate Detection is a crucial part of data cleansing, as duplicate entries cause a number of issues in data analytics and business operations. A typical process flow includes (1) normalizing the data, (2) retrieving candidates, (3) candidate comparison, (4) classification, and (5) evaluation. The 2nd and 3rd steps require record pair comparisons, which use similarity measures, such as Levenshtein and Jaro-Winkler. In this thesis we will implement or imitate such measures, in the GPU environment, and systematically evaluate the advantages of migrating from CPU to the graphical equivalent. 

A record could be represented as a vector of string or numerical values. Numerical values are more suitable for GPUs, since GPU vector comparisons are very fast, and orders of magnitude faster than in CPU. Therefore we want to examine the benefits of using such vectors, with manually crafted features, in comparison with the similarity measures.

For more information please contact Prof. Felix Naumann or Ioannis Koumarelas.