University of Cambridge

Logic
&
Semantics

Logics with Aggregate Operators

By Lauri Hella (10th June 1999)
(University of Helsinki)

In this talk I give an overview of the study of logics with counting mechanisms and aggregate operators. The primary motivation comes from database applications, where aggregate operators, such as summing up elements of a column of a relation, are present in all real life query languages. The main result shows that all the standard aggregate constructs found in commercial query languages can be expressed in an infinitary aggregate logic. Since this aggregate logic can only express local properties, we obtain as a corollary a number of expressivity bounds for such query languages. For example, the transitive closure of a binary relation is not expresible in the usual commercial versions of SQL.

This is joint work with Leonid Libkin, Juha Nurmonen and Limsoon Wong

LS Home page or Talks in 1998/99