Speaker: Azza Abouzeid
Title: Learning Database Queries with Membership Questions
Writing complex database queries in a query language like SQL can be challenging for casual and expert users alike. Of all query tasks, quantification --- specifying constraints over a set of tuples instead of individual tuples --- is the most challenging. We turn to examples to simplify quantified query specification. In an example-driven interaction model, users provide simple propositions, which serve as a query skeleton. We then learn the complete query by asking the user to classify specifically constructed sets of tuples as either answers or non-answers. We call such questions: membership questions. For this interaction model to work, we need to identify an expressive class of quantified queries that is exactly and efficiently learnable from membership questions. In this talk, I will describe one such class: qhorn. qhorn is the class of conjunctions of quantified Horn formulae on n boolean variables. We show that a subclass of qhorn is exactly and efficiently learnable with O(nk) membership questions, where k is the size of the query. We show that a slight relaxation on the properties of this subclass results in an intractable query class.