Foundations of Graph Data Management

Wim Martens (University of Bayreuth).

Course Summary | About the lecturer | Location and schedule | Materials | Videos | Assignment

Course summary:

Graph-structured data has become very popular recently, because they it is both very flexible and allows to model information closely to how we think about it, i.e., in terms of entities and connections between them. These lectures will touch upon some classical results on graph data management, after which we will discuss current research challenges.

After giving a motivation of graph databases and an overview of the main data models, we will dive into foundational aspects of graph database query languages, with a strong focus on regular path queries (RPQs) and conjunctive regular path queries (CRPQs). We will consider the different semantics that graph database systems use for such queries (every path, simple path, trail), and we will look into the computational complexities of query evaluation and query containment.

After having gone through these foundations, we plan to do some excursions into connections between tree-structured and graph-structured data, adding data value comparisons, and aspects of real-life queries.

About the lecturer:

Wim Martens is a professor for Theoretical Computer Science at the University of Bayreuth. He is interested in theoretical aspects of data management, formal language theory, logic, and complexity. He was an invited speaker at STOC 2017 and his research received several awards (e.g., two ACM SIGMOD research highlight awards, an ICDT best paper award, and the Belgian dissertation award for computer science). Currently, he is on the editorial board of ACM TODS and he is chairing the ICDT Council.

Location and schedule:

MIMUW, room 5440. schedule updated:

Thursday, March 5
14:15 - 15:45 lecture
15:45 - 16:00coffee and cake
16:00 - 17:20 lecture
Friday, March 6
14:15 - 15:45 lecture
15:45 - 16:00 coffee and cake
16:00 - 17:20 lecture


Videos: The video recordings of the lectures are now available here.

Assignment: problem set. Please submit the solutions to wim dot martens at uni-bayreuth dot de by 30 April 17 May.