Research Fields
- Foundations of Database Systems
- Information Integration and Data Exchange
- Logics and Foundations of Artificial Intelligence
- (Parameterized) Complexity Theory
- Constraint Satisfaction, Metaheuristics, Learning and Optimization
Foundations of Database Systems
Foundational questions on database systems cover a wide range of different aspects. They include, among others, topics like storing, querying, and processing data efficiently, the study of properties like expressibility and complexity of query languages, and of course query optimization. These issues are adressed for different database systems, data formats, and query languages.
In our group we especially focus on the tasks of query evaluation and optimization for the relatively new query language SPARQL. While looking for interesting fragments of the language, we also study basic problems like query containment and equivalence as well as efficient evaluation strategies for computing query answers. Lately, we also consider query answering in the presence of implicit information (provided e.g. by rule- or schema languages). In SPARQL, this feature is implemented in terms of the entailment regimes.
Information Integration and Data Exchange
In the last decade, work in this area has concentrated on the logic-based approach via schema mappings. Recently, research has focused on different languages for schema mappings (in particular their expressive power and computational complexity), on the optimization of schema mappings, on operators on schema mappings (in particular the composition and the inverse operator), and on notions of equivalence for schema mappings. While contributing to all these questions, a special focus of the work of our group is the optimization of schema mappings and different notions of equivalence for schema mappings.
So far, data integration and data exchange has been considered only for single data formats. Current research in our group thus focuses on extending the techniques for data integration and data exchange to a heterogenous setting. That is, the goal is to provide tools for integrating data which exists in different data formats or to migrate data from one format into another. Here we aim at developing tools that extend existing tools for these tasks on homogenous data.
Logics and Foundations of Artificial Intelligence
Work in this area has concentrated on logic based systems related to and with applications in Artificial Intelligence. Thereby we study a variety of different (nonmonotonic) reasoning formalisms, which include for example Answer Set Programming (ASP), Description Logics, Argumentation, Belief Revision, and Abductive Reasoning. Besides such reasoning methods we research questions from Social Choice, Planning, as well as Bioinformatics. The mainstay of our group's work in these area is the search for efficient algorithms. Besides the direct construction of algorithms, we are also interested in reduction-based approaches, where one translates the problem at hand into one that can be solved by SAT- (propositional satisfiability), QBF- (quantified Boolean formulas), or ASP-solvers. Another important aspect of our work is to study the effects of restricting the involved logic to, for example, Horn formulas or Kron formulas.
(Parameterized) Complexity Theory
Our work in this area mainly deals with the computational complexity of problems from Artificial Intelligence and database theory. Recent research focuses especially on the search for tractable fragments. Such fragments are either syntactical, like the restriction to certain logics, or structural, where we aim at finding problem specific parameters which are responsible for the computational hardness. One example of such a parameter is the treewidth of graph representations of the studied problems. Besides classical decision problems (e.g. does there exist a solution?), our group focuses on counting problems (e.g. counting the number of solutions) and enumeration problems (e.g. enumeration of all possible solutions). Additionally, we are interested in identifying parameters/features of typical real world instances that can be used in order to speed up the computation time.
Constraint Satisfaction, Metaheuristics, Learning and Optimization
In several cases the high computational complexity of the problems studied in our group prevents exact solutions. Therefore, work in this area focuses on methods that allow for fast computation of good solutions by omitting the requirement of optimality. Our aim is to provide new problem solving methods that use machine learning in search, and exploit structural decomposition techniques in metaheuristics. We investigate hybridization of Artificial Intelligence techniques, constraint programming and operational research methods. These techniques are applied in different domains including: Scheduling, Timetabling, and other combinatorial optimization problems.