When Semantics

Meets Syntax

  • Instructors:

Phokion G. Kolaitis

Andreas Pieris


  • Category: Introductory Course

  • Area: Logic and Computation

Course Description

The study of model theory typically proceeds from syntax to semantics, that is, the syntax of a logical formalism is introduced first and then the properties of the mathematical structures that satisfy sentences of that formalism are explored. There is, however, a mature and growing body of research in the reverse direction aiming, among other goals, to characterize definability in some logical formalism in terms of model-theoretic or structural properties. The origins of this line of work can be traced to Tarski's program whose main objective was to characterize metamathematical notions in "purely mathematical terms".

This course will present a comprehensive overview of model-theoretic and structural characterizations of definability in first-order logic and in fragments of first-order logic that have found numerous applications to databases and related areas of computer science.

Main Themes

Theme 1: First-Order Logic: Definability and Rewritability

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.

Theme 2: Tuple-Generating Dependencies: Definability and Rewritability

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.

Slides of Lectures and References

Slides

References

  • General References

    • A list of textbooks, monographs, and handbooks for background reading and reference.

  • Articles

    • A list of research articles and survey papers referenced in the course.

Phokion Kolaitis is a Distinguished Research Professor at the University of California Santa Cruz and a Principal Research Staff Member at the IBM Almaden Research Center. His research interests include principles of database systems, logic in computer science, and computational complexity. For additional information, please visit his personal website.



Andreas Pieris is an Assistant Professor at the University of Cyprus and an Associate Professor at the University of Edinburgh. His research interests are database theory with emphasis on knowledge-enriched and uncertain data, knowledge representation and reasoning, and logic in computer science. For additional information, please visit his personal website.