Pulling Conjunctive Query Equivalence out of the Bag
Stefan Böttcher, Sebastian Link, Lin Zhang · 2014
We present LECQTER, a tool for generating a 'perfect example' database, called exemplar, for a given conjunctive query. Indeed, exemplars separate the given query from any non-equivalent query. Therefore, LECQTER reduces the query equivalence problem to an evaluation of the queries on the exemplar. LECQTER can thus be used for applications ranging from testing coded conjunctive SQL queries to learning how to write sound conjunctive SQL queries, as it provides immediate feedback about the semantic correctness of a query, and not just the correctness of the query answer on some database as, e.g., other SQL tutoring systems. This key novelty of LECQTER relies on the bag semantics of SQL since exemplars do not always exist under set semantics. Detailed experiments show that our construction of exemplars is efficient in practice, and that they can separate a number of non-equivalent user queries that is exponential in the size of the exemplar for the target query. We identify natural parameters to control the time and size of the exemplars constructed. Finally, we offer a solution that overcomes the non-existence of exemplars under set semantics.