INFO:

For testing the correctness of SQL queries, 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 understand where the inequivalence arises. Therefore, in this paper, given a known counterexample D for Q_1 and Q_2, we aim to find the smallest counterexample D