Explaining Wrong Queries Using Small Examples.

Journal Article (Journal Article)

For testing the correctness of SQL queries, e.g., evaluating student submissions in a database course, a standard practice is to execute the query in question on some test database instance and compare its result with that of the correct query. Given two queries Q 1 and Q 2 , we say that a database instance D is a counterexample (for Q 1 and Q 2 ) if Q 1 (D ) differs from Q 2 (D ); such a counterexample can serve as an explanation of why Q 1 and Q 2 are not equivalent. While the test database instance may serve as a counterexample, it may be too large or complex to read and understand where the inequivalence comes from. Therefore, in this paper, given a known counterexample D for Q 1 and Q 2 , we aim to find the smallest counterexample D'D where Q 1 (D' ) ≠ Q 2 (D' ). The problem in general is NP-hard. We give a suite of algorithms for finding the smallest counterexample for different classes of queries, some more tractable than others. We also present an efficient provenance-based algorithm for SPJUD queries that uses a constraint solver, and extend it to more complex queries with aggregation, group-by, and nested queries. We perform extensive experiments indicating the effectiveness and scalability of our solution on student queries from an undergraduate database course and on queries from the TPC-H benchmark. We also report a user study from the course where we deployed our tool to help students with an assignment on relational algebra.

Full Text

Duke Authors

Cited Authors

  • Miao, Z; Roy, S; Yang, J

Published Date

  • June 2019

Published In

Volume / Issue

  • 2019 /

Start / End Page

  • 503 - 520

PubMed ID

  • 31439982

Pubmed Central ID

  • PMC6705612

International Standard Serial Number (ISSN)

  • 0730-8078

Digital Object Identifier (DOI)

  • 10.1145/3299869.3319866


  • eng