Abstract
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
• (a) Bag Semantics: query evaluation and query containment under bag semantics; undecidability of query containment for unions of conjunctive queries and for conjunctive queries with inequalities; progress to date on the open problem: is conjunctive query containment under bag semantics decidable?
• (b) Inconsistent databases; database repairs;consistent answers of queries; dichotomy theorems for the complexity of the consistent answers of conjunctive queries; dichotomy theorems for the complexity of repair checking.
• (c) Probabilistic databases: the tuple-independence model; conjunctive query evaluation in probabilistic databases; dichotomy theorems for conjunctive-query evaluation in probabilistic databases.
The second session of this mini course will take place on Tuesday, August 30th, 2016 1:30 pm – 2:30 pm; the third session of this mini course will take place on Wednesday, August 31st, 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.