Datenbanktheorie
VU 181.140 (2.0) SS 2009
Georg Gottlob
Ingo Feinerer
Nur für Magister- und Doktoratsstudien
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 06.03.2009. 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 Ingo Feinerer (please use the subject "[DBT]") in due time.
| Deadline | Exercises |
|---|---|
| 18.03.2009 | Relational algebra, first-order queries, and Datalog |
| 31.05.2009 | 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
Last modified: 2010-03-01 17:45