Prof. Dr. Felix Naumann

Advanced Data Profiling

Efficient membership tests for order dependencies


If you are interested in participating, please attend the initial session and reach out to sebastian.schmidl(at)hpi.de until October 22.

Please do not hesitate to contact us if you are interested, but the current time slot does not fit your schedule. In this case, please include a note that the current time does not fit you well. We would try to reschedule our meetings to allow more students to participate.


Data profiling is the process of extracting metadata from datasets. One important task is the discovery of order dependencies (ODs), which capture the order relationship among attributes in a relational table. There are two prominent ways to express ODs: The list-based form and the set-based canonical form. Current state-of-the-art algorithms for the automatic discovery of order dependencies use the set-based form to benefit from the increased efficiency of a smaller search space. However, most OD usage scenarios require ODs in their list-based form. One example for the application of ODs is query optimization: If a user requests a relation to be ordered by multiple columns, the optimizer can reduce the number of performed sort operations if an OD holds. Notice that the SQL ORDER BY-statement uses lists of attributes. While the discovery algorithms output a complete set of minimal set-based ODs, we need to know if a certain, potentially non-minimal, list-based OD holds to perform the query rewrite. How do we efficiently check whether a given list-based OD can be derived from the set of minimal set-based ODs?

Finding a solution to the task is non-trivial due to the following three technical challenges:

  • the complex transformation between list-based and set-based forms (factorial complexity)
  • implementation of the known OD inference axioms for a membership test algorithm
  • requirement of an efficient data structure to access potentially large collection of valid ODs (hundreds of thousands)


  • Learn about the research area of data profiling
  • Read and understand scientific papers
  • Craft a novel solution to the problem of efficient OD membership tests
  • Run experiments and evaluate results
  • Present results in written and oral form



  • Project seminar for master students 
  • Language: English
  • Maximum number of participants: 8

We will form teams of two in the first session and each team develops their own approach.


  • Prior knowledge in data profiling (preferably completed Data Profiling lecture)
  • Good programming skills in a major programming language


In the seminar, each team will develop an approach and write a short report. The final grade consists of the following three parts:

  • Approach (35%)
  • Written report (35%)
  • Midterm and final presentations (30%)