The third QuantLA spring school will take place from March 25 to March 29, 2019, at the Hotel Erbgericht Krippen (Bächelweg 4, 01848 Bad Schandau - Krippen).

The hotel is reachable by public transport via Dresden main station: Take the S1 in the direction of Schöna to Krippen. From the station in Krippen, it is a short walk in the direction of travel to the hotel on the right hand side.

Our invited speakers are Dr. Antoine Mottet and Prof. Dr. Joachim Niehren.

Some additional information can be found in the internal material.

Time Table

  Monday, March 25 Tuesday, March 26 Wednesday, March 27 Thursday, March 28 Friday, March 29
09:00 - 10:30

Arrival at the hotel

Joachim Niehren:
Querying Complex Event Streams
Joachim Niehren:
Efficient Aggregation for Database Queries 
Christel Baier:
Formal Analysis of Markovian Models 
Heiko Vogler:
Principle Abstract Families of Weighted Tree Languages
10:30 - 11:00  Coffee break
11:00 - 12:30 Manfred Droste:
Weighted First-Order Logic 
Antoine Mottet:
Introduction to Constraint Satisfaction Problems 
Manuel Bodirsky:
The Connection between Stochastic Games and Constraint Satisfaction
Antoine Mottet:
Introduction to Constraint Satisfaction Problems  
12:30 - 14:00 Lunch break
14:00 - 15:30 Anni-Yasmin Turhan:
Introduction to Description Logics
Karin Quaas:
Minsky Machines
Franz Baader:
Tricks of the Trade 
Gerd Brewka:
Handling Exceptions in Knowledge Representation: A Brief Introduction to Nonmonotonic Reasoning 
15:30 - 16:00  Coffee break
16:00 - 17:30

Karin Quaas:
Minsky Machines 

Sebastian Rudolph:
Query Answering over Existential Rules 
Social Event  Andreas Maletti:
Applications of Weighted Tree Automata and Tree Transducers in Natural Language Processing



Joachim Niehren: Efficient Aggregation Algorithms for Database Queries

We will study aggregation problems for database queries such as counting the number of query answers. While aggregation problems are generally computationally hard, they become feasible when restricting the query language so that Yannakakis' famous algorithm [3] can be applied. We will start with a tutorial on a recent generalization of this algorithm [4], which permits to convert any acyclic conjunctive queries on a relational database in polynomial time into a Boolean circuit called DDNF. The computed DDNF represents the whole answer set in a concise manner, even though it may be huge (exponential in the database). Therefore, efficient aggregation algorithms can and should be based on DDNFs.  This holds in particular for dependency weighted aggregation [1] as needed for computing statistics in data mining [2].  

[1] Florent Capelli, Nicolas Crosetti, Joachim Niehren, Jan Ramon: Dependency Weighted Aggregation on Factorized Databases, 2019.  

[2] Yuyi Wang, Jan Ramon, and Thomas Fannes. An efficiently computable subgraph pattern support measure: counting independent observations. Data Mining and Knowledge Discovery, 27(3). 2013.    

[3] Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981, 1981  

[4] Arnaud Durand and Stefan Mengel. Structural tractability of counting of solutions to conjunctive queries. Theory Comput. Syst., 57(4):1202–1249, 2015.


Antoine Mottet: Introduction to Constraint Satisfaction Problems 

Constraint satisfaction problems (CSPs) form a large class of decision problems whose complexity is well behaved. In these lectures, I will introduce the basic formalisms of CSPs and the tools that were developped in the past 30 years to study the complexity of these problems. The goal of the lectures is to provide the audience with an intuition for the so-called algebraic approach, that was the central approach allowing for the recent proofs of the famous dichotomy conjecture for finite-domain CSPs by Feder and Vardi. Time permitting, I will then give a very rough idea of recent research themes in the area of constraint satisfaction, including infinite-domain CSPs and the pursuit of a solution to the new dichotomy conjecture by Bodirsky and Pinsker.