Logic and Databases

Lecture 1: Logic and Databases I
Lecture 2: Logic and Databases II
Lecture 3: Logic and Databases III
Lecture 4: Logic and Databases IV
Lecture 5: Logic and Databases V


This series of talks is part of the Logical Structures in Computation Boot Camp. Videos for each talk area will be available through the links above.

Speaker: Phokion Kolaitis (UC Santa Cruz and IBM Research - Almaden)

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.