"Example-Driven Interactive Specification of Database Queries"
A distinguished lecture by Balder ten Cate (University of Amsterdam)
Main content
The talk starts at 13:00, coffee will be served from 12:45. Please help us cut down waste by bringing your own mug.
Abstract: Examples can be a useful tool when a formal specification must be synthesized or communicated. They sometimes provide a more convenient medium for communication than the formal specification itself. We all know this from daily life: think about teaching someone a card game. Simply reading out loud the rules of the game is not an effective way of doing this. Instead, what works best in practice is to give examples of valid and invalid game plays.
In data management, data examples have been proposed and used in the context of schema design and the interactive specification of schema mappings, as well as database query synthesis, refinement and debugging.
In the talk, we will discuss some of these use cases, and we will discuss some fundamental algorithmic problems, focusing on the specific case of conjunctive queries (CQs, or equivalently, existential-conjunctive first-order formulas). These fundamental problems include: generating a small set of "good" data examples that showcase the behavior of a query; and, conversely, constructing, from a given set of data examples, a “good” fitting CQ. We will discuss solutions to these problems that draw on techniques from the literature on computational learning theory, combinatorial graph theory and the study of constraint satisfaction problems.