Shrinking test databases to speed up query containment checks
How Can We Shrink the Family of Test Databases? Query Containment with Nulls and Comparisons
Databases
Summary
Figuring out if one database question always gives results inside another is a key way to speed up data searches. Common tests use big sets of example databases, which are too large to check quickly when databases have null values or special order tests. The authors found ways to make these example sets smaller by focusing on important variables and breaking down hard parts, making some checks easier and more practical. This helps database systems quickly confirm when two questions actually mean the same thing or one is inside the other.
What this means in practice
- •For database developers: Simplify and speed up query optimization by using smaller test cases to confirm query containment under conditions with nulls and order comparisons.
- •For software engineers working on query planners: Improve query rewriting tools by applying decomposed and parameterized test families that handle real-world query features efficiently.
Authors
Helen Sternbach, Sara Cohen
Abstract
Query containment and equivalence drive database query optimization and rewriting. For plain conjunctive queries, both are decided by evaluating one query over a single canonical database of the other. This classical test breaks down in two settings that pervade real queries: databases with null values under SQL's three-valued semantics, and queries with order comparisons. In both, deciding containment is $Π_2^p$-complete, and the known characterizations replace it by an exponential family of test databases, leaving no practical route to certifying equivalence. We ask how the family of test databases can be shrunk. For conjunctive queries over databases with nulls, we shrink the family to one that is exponential only in a special set of variables, and place containment in NP when that set has constant size. For queries with comparisons, we construct canonical values that decide containment, and then shrink the family by decomposing the test into independent components and by splitting it along the order conflicts. Finally, we combine the two features, and prove that the number of test databases is fixed-parameter tractable in three local parameters of the two queries, with the null-only and comparison-only tests as special cases. Each test evaluates the containing query over a family of databases, an operation native to any database system.