Saarland University Database Group
Lehrstuhl für Informationssysteme
Prof. Christoph Koch
Universität des Saarlandes
Fachrichtung 6.2 - Informatik
D-66041 Saarbrücken, Germany
Building 36.1, 2nd floor
Talk Announcement
Conjunctive Queries
Speaker: Christoph Koch
Abstract: The theory of Conjunctive Queries, that is, first-order database queries
that can be defined using existentially quantified conjunctions of
atomic formulae, is one of the greatest success stories in database
theory. This class subsumes the most widely used queries in database
practice -- e.g., SQL select-from-where queries. Still, such queries can
be evaluated rather efficiently, and all major decision problems related
to conjunctive queries are decidable. This talk will survey the classical
results on conjunctive queries such as data and query complexity
(model checking), containment, equivalence, and query minimization,
equivalence under various forms of data dependencies (the "chase"
procedure), as well as more recent results on acyclic and tree-like
queries, tree- and hypertree-decompositions and game-theoretic
characterizations of bounded (hyper)tree-width, and conjunctive queries on
tree-like data. We also point out applications of the theory of
conjunctive queries to areas such as logic programming, constraint
satisfaction, and computational linguistics.
Time and location:
In the Ringvorlesung of the graduate college
Leistungsgarantien für Rechnersysteme and the
International Max Planck Research School, Saarland University , May 12th,
1 p.m. (punctual/s.t.) in seminar room 16 (building 45).
For questions, contact scherzinger@cs.uni-sb.de.