** Data examples for conjunctive queries **
Data 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 the interactive design of schema mappings, as well as query synthesis, and query refinement and debugging. In knowledge representation, data examples arise, for instance, in the context of algorithms for learning concept expressions and ontologies. The talk will be about data examples for conjunctive queries, and we will cover some fundamental questions, such as: (a) when can a given query be uniquely characterized by a small number of data examples (where a data example is a database instance satisfying given integrity constraints), and (b) how to construct, from a given set of data examples, a "good" fitting query (for various notions of goodness). To answer these questions, we draw on, and refine, techniques from the literature on combinatorial graph theory and constraint satisfaction problems.