Miika Hannula

Associate Professor at University of Tartu, Estonia

Conjunctive query evaluation

 

Abstract

Query evaluation is one of the most central problem in databases. Given a query q, a value c, and a database D, this problem is to determine whether c belongs to the output q(D) of the query q on the database D. Remarkably, this problem is NP-complete even for conjunctive queries, which correspond to the most basic kind of SQL queries. What explains, then, that databases are so successful in practice? This course explores the theoretical foundations and techniques that make efficient query evaluation possible.

The first half of the course examines how concepts and tools from logic, graph theory, and information theory are applied to analyze and optimize conjunctive query evaluation. The second half addresses conjunctive query evaluation in the presence of uncertainty, focusing on consistent query answering—a framework designed for querying databases with inconsistent information. By the end of the course, students will understand how theoretical principles underpin the possibilities and limitations of query evaluation in database systems.

Course materials

• Slides from Lecture 1 [pdf]
• Slides from Lecture 2 [pdf]
• Exercises 1 [pdf]
• Slides from Lecture 3 [pdf]
• Exercises 2 [pdf]
• Slides from Lecture 4 [pdf]

---