Explaining Wrong Queries Using Small Examples

Area of Science:

• Computer Science
• Database Systems
• Artificial Intelligence

Background:

• Evaluating SQL query correctness is vital in database education and performance analysis.
• Standard methods involve comparing query outputs on test databases, but counterexamples can be overly complex.
• Identifying the root cause of query inequivalence requires understanding these counterexamples.

Purpose of the Study:

• To develop algorithms for finding the smallest database counterexample (D') given a larger counterexample (D) for two SQL queries (Q1 and Q2).
• To address the NP-hard problem of minimizing counterexamples for SQL query inequivalence.
• To provide practical tools for database education and query optimization.

Main Methods:

• Developed a suite of algorithms for finding minimal counterexamples across various query classes.
• Introduced a provenance-based algorithm utilizing constraint solvers for Select-Project-Join-Union-Difference (SPJUD) queries.
• Extended the approach to handle complex queries involving aggregation, group-by, and nested structures.

Main Results:

• Demonstrated effectiveness and scalability of the proposed algorithms on student assignments and TPC-H benchmark queries.
• Successfully reduced complex counterexamples to minimal, understandable instances.
• Validated the tool's utility in an undergraduate database course through a user study.

Conclusions:

• The developed algorithms efficiently find minimal counterexamples, aiding in understanding SQL query inequivalence.
• The provenance-based approach offers a scalable solution for complex query types.
• The tool effectively supports database education by clarifying query comparison and relational algebra concepts.