Content
- Querying databases in first-order logic
- Complexity of database querying
- Trakhtenbrot's theorem: the algorithmic impossibility of a perfect query optimizer
- Conjunctive queries
- Query containment and equivalence for conjunctive queries
- Conjunctive query minimization
- Acyclic queries
- Tree decompositions, query decompositions, and hypertree decompositions
- Expressive power of query languages
- Ehrenfeucht-Fraïssé games
- Recursive query languages (Datalog, fixpoint queries)
- Monadic logic for querying semi-structured data
- Additional topics time permitting
Registration
Join group A in TUWIS++ until 17.03.2010. It is also highly recommended to subscribe to the course in TUWIS++ to receive announcements, etc.
Dates
Exam
- Written exercises (homework)
- Presentation and discussion of exercises in class
- Active participation in class
Exercises
Send your homework solutions (PDFs) to feinerer@dbai.tuwien.ac.at (please use the subject "[DBT]") in due time.
| Deadline | Exercises |
|---|---|
| 21.04.2010 | Relational algebra, first-order queries, and Datalog |
| 30.05.2010 | The impossibility of perfect query optimization, complexity of query languages, conjunctive queries, and first-order expressiveness and Ehrenfeucht-Fraïssé games |
Literature
S. Abiteboul, R. Hull, and V. Vianu: Foundations
of Databases, Addison-Wesley, 1995
G. Gottlob, N. Leone, and
F. Scarcello: The
Complexity of Acyclic Conjunctive Queries
C. Chekuri, and
A. Rajaraman: Conjunctive
query containment revisited
G. Gottlob, N. Leone, and
F. Scarcello: Hypertree
Decompositions and Tractable Queries
G. Kolaitis: On
the Expressive Power of Logics on Finite
Models
G. Gottlob: Slides on additional topics