Abstract

A basic distinction between logic in databases and “vanilla mathematical logic” is that in the former quantifiers range over the objects that are stored in finite relations — stuff in the database; while in the latter we quantify over the domain of the model, which can be infinite—all strings, all real numbers, all integers, etc. Once upon a time, researchers studied what happens when you mix these two kinds of quantification within the same logic. In the resulting formalism, “embedded finite model theory”, you can, for example, write a query asking whether there is a vector of real numbers which satisfy certain inequalities with respect to all rows in a database table.

The talk will revisit embedded finite model theory, arguing that it’s relevant to a number of recent develpments in data management, such as performing linear algebra and ML tasks within a DBMS . The talk focus will be on new connections to theoretical CS: spectrum problems, bounds in decision procedures, and Ramsey theory.

There will be some classical model theory in the lecture, but it should be accessible to a theory-leaning CS audience. The talk includes joint work with Ehud Hrushovski and joint work with Anthony Lin.