LFCS Seminar: Tuesday, 14 March - Michael Benedikt

Speaker:       Michael Benedikt

Title:               Nested Relations, Views, and Implicit Definability

Abstract:

The first part of this talk will be about databases. It will give a quick

overview of the nested relational data model and the nested relational

calculus (NRC), the standard query model for defining

transformations on nested relations. It will then introduce views and

view rewriting problems, a fundamental computational question in

data management -- for any data model -- and more broadly in CS. The first

part will close with a statement of new results about answering queries

using views in the setting of nested relations.

The second part will give a flavor of some ingredients in the proofs of

the main results. This will be -- perhaps surprisingly --

database-free. It will connect to a number of topics in computational

logic: implicit vs explicit definability, Gaifman's coordinisation

theorem, and the theorems of Chang and Makkai.

This is joint work with Pierre Pradic and Christoph Wernhard (POPL 21

and PODS 23).