Generating Queries with Cardinality Constraints for DBMS Testing - Bruno, Nicolas; Chaudhuri, Surajit; Thomas, Dilys (Transactions on Knowledge and Data Engineering, 2006)
Good testing coverage of novel database techniques, such as multidimensional histograms or changes in the execution engine, is a complex problem. In this work, we argue that this task requires generating query instances, not randomly, but based on a given set of constraints. Specifically, obtaining query instances that satisfy cardinality constraints on their sub-expressions is an important challenge. We show that this problem is inherently hard, and develop heuristics that effectively find approximate solutions.