We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Explaining Wrong Queries Using Small Examples

00:00

Formal Metadata

Title
Explaining Wrong Queries Using Small Examples
Title of Series
Number of Parts
155
Author
License
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
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.
Customer relationship managementMagneto-optical driveQuery languageGoodness of fitTupleQuery languagePresentation of a groupLecture/ConferenceMeeting/InterviewComputer animation
DatabaseSocial classQuery languageStatistical hypothesis testingInstance (computer science)Student's t-testLinear regressionPiImage registrationGradientCounterexampleTupleCompilation albumComplex (psychology)Kolmogorov complexityTerm (mathematics)Boolean algebraBoolean satisfiability problemRelational databaseVariable (mathematics)MereologyMultiplicationResultantDirectory serviceProjective planeExpressionMathematical modelData storage deviceStudent's t-testDifferent (Kate Ryan album)CASE <Informatik>NumberSummierbarkeitWell-formed formulaObject (grammar)Statistical hypothesis testingLogical constantMultiplication signTable (information)outputInformation privacyWeightSocial classCellular automatonOcean current1 (number)Insertion lossSampling (statistics)Point (geometry)Interpreter (computing)Boolean satisfiability problemRelational databaseExistential quantificationVotingFocus (optics)Group actionSet (mathematics)Lattice (order)Event horizonTask (computing)Linear regressionInstance (computer science)Image registrationComplex (psychology)Personal digital assistantSimilarity (geometry)Closed setPlastikkarteQuery languageTupleDichotomyVariable (mathematics)DatabaseNP-hardQueue (abstract data type)Boolean algebraMathematical optimizationAddress spaceRow (database)Office suiteStandard deviation2 (number)CounterexamplePrimality testComputer animation
Motion captureTupleMathematical optimizationProcess (computing)Query languageImage registrationLocal GroupStudent's t-testParameter (computer programming)AnalogyExponential functionDatabaseAlgebraRelational databaseTwin primeInstance (computer science)Statistical hypothesis testingScale (map)Task (computing)AverageOverhead (computing)CounterexampleReduction of orderOrder of magnitudeOrder (biology)GradientConstraint (mathematics)Control flowSimilarity (geometry)Arithmetic meanFeedbackDependent and independent variablesPersonal digital assistantSample (statistics)Equivalence relationType theoryComputer programOperator (mathematics)Functional (mathematics)Context awarenessAlgorithmKolmogorov complexityStudent's t-testStatistical hypothesis testingExpressionSelectivity (electronic)Query languageResultantNumberDifferent (Kate Ryan album)BenchmarkKey (cryptography)Instance (computer science)Medical imagingMathematical optimizationProcess (computing)Predicate (grammar)State observerObservational studyMethodenbankAddress spaceGreatest elementFluktuations-Dissipations-TheoremMultiplication signDegree (graph theory)Machine visionLine (geometry)Cartesian coordinate systemSimilarity (geometry)Grand Unified TheoryAverageInformationLogical constantCASE <Informatik>WeightAdditionOverhead (computing)FlagRow (database)Shape (magazine)CountingParameter (computer programming)Social classScripting languagePerformance appraisalSinc functionMetreForestTupleOnline helpQueue (abstract data type)Demo (music)DialectDatabaseSet (mathematics)Relational databaseoutputFeedbackComplex (psychology)Software frameworkRun time (program lifecycle phase)AlgebraComputer animation
Lecture/ConferenceMeeting/Interview
Transcript: English(auto-generated)