|
|
Bertinoro International Spring School 2009 |
Structural Methods in Database
Theory (SM)
- Course summary
The main focus of this Database Theory course is on the
evaluation and optimization of Database queries. We start by recalling some
useful notions of Database Theory and First Order Logic. It will be shown that
perfect optimization is impossible, because even some easier related problems
are undecidable. Then, we recall the definitions of some complexity classes,
both above NP and inside P. The latter classes are interesting, because
problems therein can be solved efficiently by parallel algorithms. Moreover, we present some results about the
complexity and the expressive power of query languages. These results are based
on nice technical gadgets, such as the Ehrenfeucht-Fraisse games.
The central part of the course is about Conjunctive
queries, equivalent in expressive power to Select-Project-Join queries, which
constitute the most basic, most important, and best-studied type of database
queries. The problem of evaluating a conjunctive query over a relational
database is a fundamental problem in the field of database systems. This
problem is NP-hard in general. However, it was shown that there are large
classes of queries, called islands of tractability, that can be identified and
answered efficiently, that is, in polynomial-time with standard machines, or
even better with parallel machines. The idea is to exploit the structural
properties of query hypergraphs, generalizing a classical result by Yannakakis
[1981] on the tractability of acyclic queries. This line of research led to a
number of techniques, usually called structural methods, which extend the nice
properties of acyclic queries to more general classes of queries whose
associated hypergraphs have a "low degree of cyclicity". Notable
examples are the techniques based on the notions of tree-width and
hypertree-width. They find applications also in other fields of computer
science, such as constraint satisfaction in AI, theorem proving, game theory,
and so on. This course presents an overview of the main results about
structural methods, starting from the theoretical basis, and ending with recent
practical applications to query optimization in real DBMS. In particular, a
number of technical tools will be presented (e.g., alternating Turing machines,
parallel complexity classes, and graph games) that can be useful to students
even in very different settings and for completely different problems, besides
providing a deep-understanding of the main subjects of the course.
Prerequisites: Classical notions of computational complexity theory and of algorithms
and data structures, such as Turing machine, reducibility and algorithm
analysis. Basic
notions of Database Theory.
- Examination (new)
- Slides
Slides
for the class are now available in the following table. You can print
out a copy and bring it with you at the school.
|
Name |
4slides/page |
|
Presentation of the course |
|
|
Introduction to Databases and FO Logic |
|
|
The Impossibility of Perfect Query Optimization |
|
|
Complexity of Query Languages |
|
|
Conjunctive Queries and Structural Methods |
|
|
Hypertree Decompositions: Characterizations, |
|
|
Parallel Algorithms |
|
|
FO Expressiveness and EF Games |
- Further Material
-
any database book, such as Foundations of Databases, by Serge
Abiteboul, Richard Hull, and Victor Vianu;
-
a computational complexity book,
such as Computational Complexity, by
C.H. Papadimitriou;
-
papers about structural methods,
e.g., the JACM paper and the JCSSs papers available at the Hypertree Decompositions
home page;
-
a paper by Ph. Kolaitis, available here;