|
Logic & Semantics |
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