In the first part of the course, we will focus on some classical results from the model theory of first-order logic, and provide answers to the following central questions:

Question 1: When is a collection of structures (finite or infinite) definable by a set of first-order sentences?

Question 2: When is a collection of structures (finite or infinite) definable by a finite set of first-order sentences?

Question 3: Let C be a class of structures definable by a set of first-order sentences, and let D be a collection of first-order sentences. When is C definable by a set of sentences in D?

Question 4: Let C be a class of structures definable by a finite set of first-order sentences, and let D be a collection of first-order sentences. When is C definable by a finite set of sentences in D?

The compactness theorem of first-order logic will be the main tool for obtaining answers to these questions. We will give a self-contained proof of the compactness theorem using ultraproducts. The answers to the last two questions involve some of the classical preservation theorems for first-order logic. We will also examine whether or not these classical preservation theorems survive the passage to the finite, i.e., whether or not they hold when only finite structures are considered.

In the second part of the course, we will concentrate on a key fragment of first-order logic, called tuple-generating dependencies (tgds), that has numerous applications to databases. Tgds have been originally introduced as a unifying framework for database integrity constraints, and later on have been used in data exchange and integration, and for modeling ontologies that are intended for data-intensive tasks. The focus will be on finite structures and on finite sets of tgds. We will provide answers to the following central questions:

Question 1: When is a class of finite structures definable by a finite set of tgds?

Question 2: When is a class of finite structures definable by a finite set of tgds from a restricted class (full tgds, linear tgds, guarded tgds)?

Question 3: Let C be a class of finite structures definable by a finite set of tgds. When is C definable by a finite set of tgds from a restricted class (full tgds, linear tgds, guarded tgds)?

The answers to the above questions will exploit standard model-theoretic properties such as criticality and closure under direct products, as well as a recent notion of locality specifically defined for dealing with tgds (and subclasses thereof).

We will finally study analogous questions for source-to-target (s-t) tgds (aka GLAV constraints), linear s-t tgds (aka LAV constraints), and full s-t tgds (aka GAV constraints) that have been heavily used in data exchange and integration.