Mathematische Logik und Anwendungen


Graduiertenkolloquium SS 2008

Zeit: Mo 14 - 16 Uhr
Ort: SR 01-016, Gebäude 101 Georges-Köhler-Allee



Taming the infinite chase: query answering under expressive relational constraints
An important task in Knowledge Representation is answering queries posed over a knowledge base, represented as a set of facts plus a set of rules. In this talk we address the problem of answering conjunctive queries posed over knowledge bases where rules are an extension of logic programming rules, that may have existentially quantified variables in the head; this kind of rules are traditionally called tuple-generating dependencies (TGDs) in the database literature, but they are broadly used in Description Logics and in ontological reasoning. In this setting, the chase is an important tool for query answering; so far, most of the research has concentrated on cases where the chase terminates. We define and study large classes of TGDs under which the query evaluation problems remain decidable even in case the chase does not terminate; we provide tight complexity bounds for such cases. Our results immediately extend to query containment.

Tutorial über Ontology-based Data Access
Many organizations nowadays face the problem of accessing existing data sources by means of mechanisms that are sufficiently expressive without compromising efficiency. Ontologies allow one to describe the domain of interest of an information system at a high level of abstraction, and are widely considered as a suitable formal tool for sophisticated data access.
In this tutorial we provide a comprehensive understanding of the problem of ontology-based data access, both from the theoretical and from the practical points of view. We address several problems that are crucial in this context:

We will present solutions to these problems based on recent research results in the area of tractable Description Logics.