QAGen: generating query-aware test databases

ABSTRACT

Today, a common methodology for testing a database management system (DBMS) is to generate a set of test databases and then execute queries on top of them. However, for DBMS testing, it would be a big advantage if we can control the input and/or the output (e.g., the cardinality) of each individual operator of a test query for a particular test case. Unfortunately, current database generators generate databases independent of queries. As a result, it is hard to guarantee that executing the test query on the generated test databases can obtain the desired (intermediate) query results that match the test case. In this paper, we propose a novel way for DBMS testing. Instead of first generating a test database and then seeing how well it matches a particular test case (or otherwise use a trial-and-error approach to generate another test database), we propose to generate a query-aware database for each test case. To that end, we designed a query-aware test database generator called QAGen. In addition to the database schema and the set of basic constraints defined on the base tables, QAGen takes the query and the set of constraints defined on the query as input, and generates a query-aware test database as output. The generated database guarantees that the test query can get the desired (intermediate) query results as defined in the test case. This approach of testing facilitates a wide range of DBMS testing tasks such as testing of memory managers and testing the cardinality estimation components of query optimizers.

REFERENCES

• 1: DTM Data Generator. http://www.sqledit.com/dg/.
• 2: IBM DB2 Test Database Generator. http://www-306.ibm.com/software/data/db2imstools/db2tools/db2tdbg/.
• 3: International Organization for Standardization (ISO). Information Technology-Database Language SQL, 1999.
• 4: TPC benchmark H. http://www.tpc.org/tpch.
• 5: C. Binnig, D. Kossmann, and E. Lo. Reverse query processing. In ICDE, 2007.
• 6: C. Binnig, D. Kossmann, E. Lo, and M. T. Özsu. QAGen: Generating Query-Aware Test Databases. ETH Zurich Technical Report, 2007.
• 7: Nicolas Bruno , Surajit Chaudhuri, Flexible database generators, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 8: N. Bruno, S. Chaudhuri, and D. Thomas. Generating Queries with Cardinality Constraints for DBMS Testing. TKDE, 2006.
• 9: S. Chaudhuri and V. Narasayya. TPC-D data generation with skew.
• 10: E. M. Clarke, O. Grumberg, and D. A. Peled. Model Checking. 2000.
• 11: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 12: B. Cook, D. Kroening, and N. Sharygina. Cogent: Accurate theorem proving for program verification. In CAV, pages 296--300, 2005.
• 13: R. A. Ganski and H. K. T. Wong. Optimization of nested SQL queries revisited. In SIGMOD, pages 23--33, 1987.
• 14: M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. 1990.
• 15: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 16: J. Gray, P. Sundaresan, S. Englert, K. Baclawski, and P. J. Weinberger. Quickly generating billion-record synthetic databases. In SIGMOD, pages 243--252, 1994.
• 17: Kenneth Houkjær , Kristian Torp , Rico Wind, Simple and realistic data generation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 18: James C. King, Symbolic execution and program testing, Communications of the ACM, v.19 n.7, p.385-394, July 1976 [doi>10.1145/360248.360252]
• 19: A. Klug, Calculating constraints on relational expression, ACM Transactions on Database Systems (TODS), v.5 n.3, p.260-290, Sept. 1980 [doi>10.1145/320613.320615]
• 20: Bart Kuijpers, Introduction to constraint databases, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601866]
• 21: G. N. Paulley , Per-Åke Larson, Exploiting Uniqueness in Query Optimization, Proceedings of the Tenth International Conference on Data Engineering, p.68-79, February 14-18, 1994
• 22: M. Poess and J. M. Stephens. Generating thousand benchmark queries in seconds. In VLDB, pages 1045--1053, 2004.
• 23: Donald R. Slutz, Massive Stochastic Testing of SQL, Proceedings of the 24rd International Conference on Very Large Data Bases, p.618-622, August 24-27, 1998
• 24: J. M. Stephens and M. Poess. Mudd: a multi-dimensional data generator. In WOSP, pages 104--109, 2004.
• 25: G. Zipf. Human Behaviour and the Principle of Least Effort. 1949.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Experimentation, Performance, Reliability

Keywords:
database, query processing, symbolic database, symbolic execution, symbolic query processing, testing