"Foundations" seminar

Within TEMTA119 and in collaboration with other research groups, we are organizing a "Foundations of CS" seminar series. It is meant for people who like the foundations of computer science and CS's various subfields and/or who like the mathematical part of computer science.

Talks

• December 16, 16:15, in room 2049, by Miika Hannula
  • Title: Query Evaluation: Basics and Recent Developments
  • Abstract: Query evaluation is perhaps the most central problem pertaining to databases. Given a query q, a value c, and a database D, this problem is to determine whether or not c belongs to the output q(D) of the query q on the database D. Unfortunately, this problem is NP-complete even if we restrict to conjunctive queries which correspond to the most basic kind of SQL queries. What explains, then, that databases are so successful in practice? In this talk we look how theoretical investigation has helped to tame the query evaluation problem leading to efficient algorithms. We also look into recent developments regarding (a) query evaluation over inconsistent databases, and (b) application of information theory to join queries.