Foundations of Databases and Query Languages
Foundations of Databases and Query Languages
Course with SWS 2/2/0 (lecture/exercise/practical) in SS 2015
Lecturer
Tutor
SWS
- 2/2/0
Modules
Examination method
- Oral exam
Lecture series
Databases are a key technology in computer science that brings together fascinating theoretical topics and highly relevant practical applications. The goal of this lecture is to give an extended introduction to this interesting field, with a special focus on database query languages, their expressive power, and computational complexity. The lecture will introduce the relational datamodel, and then discuss theoretical and practical aspects of a variety of query languages:
- first-order logic as a query language and the relational algebra
- conjunctive queries and their unions
- navigational queries: path queries
- Datalog and its relatives
The lecture focuses on core principles that apply to many types of databases alike (relational, graph-based, semantic web). Some important query answering algorithms are presented, too, but otherwise the details of database implementation and administration are not covered.
Prerequistes
An undergraduate-level knowledge of predicate logic, regular languages, and algorithmic and computational complexity is required. The lecture will connect with other topics in the Computer Science and Computational Logic curriculum, such as relational databases, logic programming, and Semantic Web technologies – familiarity with these topics is not required to follow the lecture.
Time plan
The general time plan is as follows:
- Lectures: each Monday in DS3 (11:10–12:40)
- Exercises: each Friday in DS4 (13:00–14:30)
However, there will be some exceptions that will be announced in the lecture. The first lecture is on Monday, 13 April 2015.
Legacy
The structure of some of the lectures of this course is inspired by the course Theory of Data and Knowledge Bases in the version given by Georg Gottlob and Thomas Lukasiewicz at the University of Oxford.The main reference textbook for the lecture is:
- Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley. 1994.
- The book is available for free from its webpage, but there are also copies in the library.
Further texts might be consulted for background information and additional details:
- Michael Sipser: Introduction to the Theory of Computation. 2005
- Accessible introduction to complexity theory that covers all topics of computational complexity that the lecture touches upon.
- Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov: Complexity and expressive power of logic programming. ACM Computing Surveys, 33:3, pp 374-425, 2001.
- Covers all Datalog complexity results mentioned in the lecture. Available at http://dx.doi.org/10.1145/502807.502810 (may require access from within a university network)
- additional references will be added in the course of the lecture
Subscribe to events of this course (icalendar)
| Lecture | Introduction/Relational data model | DS3, April 13, 2015 in APB E005 | File 1, File 2 |
| Exercise | Relational algebra | DS4, April 17, 2015 in APB E005 | File |
| Lecture | First-Order Queries | DS3, April 20, 2015 in APB E005 | File 1, File 2 |
| Exercise | First-Order Queries | DS4, April 24, 2015 in APB E005 | File |
| Lecture | Query Answering Complexity | DS3, April 27, 2015 in APB E005 | File 1, File 2 |
| Lecture | FO Query Answering Complexity | DS3, May 4, 2015 in APB E005 | File 1, File 2 |
| Exercise | FO Query Answering Complexity | DS4, May 8, 2015 in APB E005 | File |
| Lecture | Conjunctive Queries | DS3, May 11, 2015 in APB E005 | File 1, File 2 |
| Exercise | Conjunctive Queries, CSP, and Hypergraphs | DS4, May 15, 2015 in APB E005 | File |
| Lecture | Tree-Like Conjunctive Queries | DS3, May 18, 2015 in APB E005 | File 1, File 2 |
| Exercise | Treewidth and Hypertree Width | DS4, May 22, 2015 in APB E005 | File |
| Lecture | Query Optimisation | DS3, June 1, 2015 in APB E005 | File 1, File 2 |
| Exercise | FO Query Optimisation and Trakhenbrot's Theorem | DS4, June 5, 2015 in APB E005 | File |
| Lecture | CQ Optimisation and FO Expressivity | DS3, June 8, 2015 in APB E005 | File 1, File 2 |
| Exercise | CQ Optimisation and FO Expressivity | DS4, June 12, 2015 in APB E005 | File |
| Lecture | FO Expressivity and Introduction to Datalog | DS3, June 15, 2015 in APB E005 | File 1, File 2 |
| Exercise | FO Expressivity and Introduction to Datalog | DS4, June 19, 2015 in APB E005 | File |
| Lecture | Expressive Power and Complexity of Datalog | DS3, June 22, 2015 in APB E005 | File 1, File 2 |
| Exercise | Datalog | DS4, June 26, 2015 in APB E005 | File |
| Lecture | Datalog Optimisation and Evaluation | DS3, June 29, 2015 in APB E005 | File 1, File 2 |
| Exercise | Datalog (part 2 of previous exercise) | DS4, July 3, 2015 in APB 2026 | |
| Lecture | Datalog Evaluation | DS3, July 6, 2015 in APB E005 | File 1, File 2 |
| Exercise | Datalog Evaluation | DS4, July 10, 2015 in APB E005 | File |
| Lecture | Graph Databases and Path Queries | DS3, July 13, 2015 in APB E005 | File 1, File 2 |
| Exercise | Path Queries | DS4, July 17, 2015 in APB E005 | File |
| Lecture | Database Theory in Practice | DS3, July 20, 2015 in APB E005 | File 1, File 2 |
| Exercise | General Q&A Session | DS4, July 24, 2015 in APB E005 |
Calendar
