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: |
Sebastian Rudolph: Query Answering over Existential Rules |
Social Event | Andreas Maletti: Applications of Weighted Tree Automata and Tree Transducers in Natural Language Processing |
|
Abstracts
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.
