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