Since the development of the relational data model in the early 1970s, the interaction between logic and databases has been extensive and fruitful. The aim of this course is to highlight some aspects of this interaction with emphasis on the interplay between logic, databases, and computational complexity along three main themes.

Theme 1: Database Query Languages and Computational Complexity
The relational data model; first-order logic as a database query language; Datalog; the query evaluation problem and the query containment problem; data complexity and combined complexity. Data complexity and combined complexity of conjunctive queries, unions of conjunctive queries, monotone queries, and Datalog.

Theme 2: Aspects of Conjunctive Query Evaluation
Conjunctive queries and and constraint satisfaction; acyclic joins; treewidth and conjunctive queries with a bounded number of variables, query width and hyper-treewidth; estimates on the size of relational joins and the connection to fractional edge covers.

Theme 3: Query Evaluation and Containment under Alternative Semantics

The first session of this mini course will take place on Monday, August 29th, 2016 3:00 pm – 4:00 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 1:30 pm – 2:30 pm; the fourth session of this mini course will take place on Thursday, September 1st, 2016 1:30 pm – 2:30 pm; the fifth session of this mini course will take place on Friday, September 2nd, 2016 1:30 pm – 2:30 pm.