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: when can a given CQ be uniquely characterized by a small number of data examples, and, conversely, how to construct, from a given set of data examples, a “good” fitting CQ (for various notions of goodness). The answers to these questions draw on techniques from the literature on combinatorial graph theory and constraint satisfaction problems.