Name
Abstract | ||
|---|---|---|
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' \subseteq D$ where $Q_1(D') \neq Q_2(D')$. The problem in general is NP-hard. Drawing techniques from provenance and constraint solving, we develop a suite of algorithms for finding small counterexamples for different classes of queries, including those involving negation and aggregation. We evaluate the effectiveness and scalability of our algorithms 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.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3299869.3319866 | Proceedings of the 2019 International Conference on Management of Data |
Keywords | Field | DocType |
data provenance, explanations, relational query grading | SQL,Data mining,Suite,Computer science,Correctness,Constraint satisfaction problem,Theoretical computer science,Relational algebra,Counterexample,Scalability | Journal |
Volume | ISSN | ISBN |
abs/1904.04467 | 0730-8078 | 978-1-4503-5643-5 |
Citations | PageRank | References |
1 | 0.35 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhengjie Miao | 1 | 11 | 6.61 |
| Sudeepa Roy | 2 | 268 | 30.95 |
| Jun Yang | 3 | 2762 | 241.66 |