Department of Computer Science
University of Toronto
4pm 21 October 2003
Room 2511, JCMB, King's Buildings
In this talk I address one of the most basic questions of database theory: what can one express in a query language? The standard approach is to assume that items stored in a database are uninterpreted values that can only be compared for equality. However, in reality they are numbers, or strings, or even XML documents.
The exact expressiveness of a query language then becomes heavily dependent on some basic properties of the underlying data types, in fact, their model-theoretic properties. To address the problem of the expressiveness of querying, one has to understand definability in the structure that describes a given data type, and use a new type of results that "parameterize" such definability by a finite relational database. At the end we obtain results about expressiveness of database querying by using such techniques as o-minimality, finite VC dimension, quantifier elimination, string and tree automata, and many others.
If you are not interested in databases, you can view this talk as an overview of an emerging area of mathematical logic called "embedded finite models".