Account
Edit tools
Internal
SucheSearch
Deutsch

Database Theory

From International Center for Computational Logic

Database Theory

Course with SWS 2/2/0 (lecture/exercise/practical) in SS 2016

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.

Prerequisites

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 Thursday in DS4 (13:00–14:30)
  • Exercises: each Monday in DS3 (11:10–12:40)

However, there will be some exceptions that will be announced in the lecture:

  • The first lecture is on Monday, 04 April 2016.
  • The lecture on Thursday, 9 June, will be in DS3 (from 11:10) in room APB 3027, since the afternoon is reserved for OUTPUT.DD 2016.
  • The lecture on Thursday, 16 June, will be held by Sebastian Rudolph.
  • The exercise session on Monday, 4 July, will be held by Tomáš Masopust.

Legacy

This course has first been taught at TU Dresden in the form of the 2015 lecture Foundations of Databases and Query Languages. The plan for this year's course will be very similar.

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 4, 2016 in APB E005 File 1,  File 2
Lecture First-Order Queries DS4, April 7, 2016 in APB E005 File 1,  File 2
Exercise Relational Algebra DS3, April 11, 2016 in APB E005 File
Lecture Query Answering Complexity DS4, April 14, 2016 in APB E005 File 1,  File 2
Exercise First-Order Queries DS3, April 18, 2016 in APB E005 File
Lecture FO Query Answering Complexity DS4, April 21, 2016 in APB E005 File 1,  File 2
Exercise FO Query Answering Complexity DS3, April 25, 2016 in APB E005 File
Lecture Conjunctive Queries DS4, April 28, 2016 in APB E005 File 1,  File 2
Exercise Conjunctive Queries, CSP, and Hypergraphs DS3, May 2, 2016 in APB E005 File
Exercise Conjunctive Queries, CSP, and Hypergraphs DS3, May 9, 2016 in APB E005 File
Lecture Tree-Like Conjunctive Queries DS4, May 12, 2016 in APB E005 File 1,  File 2
Exercise Treewidth and Hypertree Width DS3, May 23, 2016 in APB E005 File
Lecture Query Optimisation DS4, May 26, 2016 in APB E005 File 1,  File 2
Exercise FO Query Optimisation and Trakhenbrot's Theorem DS3, May 30, 2016 in APB E005 File
Lecture CQ Optimisation and FO Expressivity DS4, June 2, 2016 in APB E005 File 1,  File 2
Exercise CQ Optimisation and FO Expressivity DS3, June 6, 2016 in APB E005 File
Lecture FO Expressivity and Introduction to Datalog DS3, June 9, 2016 in APB 3027 File 1,  File 2
Exercise FO Expressivity and Introduction to Datalog DS3, June 13, 2016 in APB E005 File
Lecture Expressive Power and Complexity of Datalog DS4, June 16, 2016 in APB E005 File 1,  File 2
Exercise Datalog DS3, June 20, 2016 in APB E005 File
Lecture Datalog Optimisation and Evaluation DS4, June 23, 2016 in APB E005 File 1,  File 2
Exercise Datalog / Q&A DS3, June 27, 2016 in APB E005 File
Lecture Datalog Evaluation DS4, June 30, 2016 in APB E005 File 1,  File 2
Exercise Datalog Evaluation DS3, July 4, 2016 in APB E005 File
Lecture Graph Databases and Path Queries DS4, July 7, 2016 in APB E005 File 1,  File 2
Exercise Path Queries DS3, July 11, 2016 in APB E005 File
Lecture Database Theory in Practice DS4, July 14, 2016 in APB E005 File 1,  File 2


Calendar


Retrieved from "https://iccl.inf.tu-dresden.de/w/index.php?title=Database_Theory_(SS2016)/en&oldid=18343"