Abstract
To address the problem of generating test data for a set of general consistency constraints, we propose a new two-step approach: First the interdepen-dencies between consistency constraints are explored and a generator formula is derived on their basis. During its creation, the user may exert control. In essence, the generator formula contains information to restrict the search for consistent test databases. In the second step, the test database is generated. Here, two different approaches are proposed. The first adapts an already published approach to generating finite models by enhancing it with requirements imposed by test data generation. The second, a new approach, operationalizes the generator formula by translating it into a sequence of operators, and then executes it to construct the test database. For this purpose, we introduce two powerful operators: the generation operator and the test-and-repair operator. This approach also allows for enhancing the generation operators with heuristics for generating facts in a goal-directed fashion. It avoids the generation of test data that may contradict the consistency constraints, and limits the search space for the test data. This article concludes with a careful evaluation and comparison of the performance of the two approaches and their variants by describing a number of benchmarks and their results.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alavi, M. An assessment of the prototyping approach to information systems development.Communications of the ACM, 27:556–563, 1984.
Bitton, D., De Witt, D.J., and Turbyfill, C. Benchmarking database systems—A systematic approach.Proceedings of the International Conference on VLDB, Florence, 1983.
Brodie, M.L. and Ridjanovic, D. On the design and specification of database transactions. In: Brodie, M.L., Mylopoulos, J., and Schmidt, J.W., eds.,On Conceptual Modelling. Perspectives from Artifical Intelligence, Databases, and Programming Languages, Springer-Verlag: New York, 1984, pp. 277–306.
Bry, F. and Manthey, R. Checking consistency of database constraints: A logical basis.Proceedings of the International Conference on VLDB, Kyoto, 1986.
Bry, F., Decker, H., and Manthey, R. A uniform approach to constraint satisflability and constraint satisfiability in deductive databases.Proceedings of the International Conference on Extending Database Technology, Venice, 1988.
Budde, R., Kuhlenkamp, K., Mathiassen, L., and Züllighoven, H., eds.Approaches to Prototyping. Springer-Verlag: New York, 1984.
Cosmadakis, C.C. and Papadmitriou, C.H. Updates of relational views.Journal of the ACM, 31(4):742–760, 1984.
De Witt, D.J. Benchmarking database systems: Past efforts and future directions.IEEE Database Engineering, 8(1):2–9, 1985.
Fagin, R. Horn clauses and database dependencies.Journal of the ACM, 28(4):952–985, 1982.
Fagin, R. and Vardi, M. Armstrong databases for functional and inclusion dependencies.Information Processing Letters, 16:13–19, 1983.
Geibel, P. Entwicklung und bewertung von strategien zur testdatengenerierung. In German.Master's thesis, Fakultät für Informatik, Universität Karlsruhe, April, 1991.
Guessoum, A. and Lloyd, J.W. Updating knowledge bases.New Generation Computing, 8(1):71–89, 1990.
Guessoum, A. and Lloyd, J.W. Updating knowledge bases II.New Generation Computing 10(1):73–100, 1991.
Kung, C.H. A tableaux approach for consistency checking. In: Sernadas, A., Bubenko, J., Jr., and Olive, A., eds.,Proceedings of IFIP Conference on Theoretical and Formal Aspects of Information Systems, Amsterdam: North-Holland Publishing Company, 1985, pp. 191–210.
Lockemann, P.C., Moerkotte, G., Neufeld, A., Radermacher, K., and Runge, N. Database design with user-definable modelling concepts,Data and Knowledge Engineering (submitted).
Manchanda, S. and Warren, D.S., Towards a logical theory of database view up-dates.Proceedings of the Workshop on Foundations of Deductive Databases and Logic Programming, Washington, DC, 1986.
Mannila, H. and Räihä, K.-J. Automatic generation of test data for relational queries.Journal of Computer and System Sciences, 38(2):240–258, 1989.
Manthey, R. and Bry, F. A hyperresolution-based proof procedure and its implementation in PROLOG. In: Morik, K., ed.,German Workshop on Artificial Intelligence, Berlin Heidelberg: Springer-Verlag, Informatik-Fachberichte 152, 1987, pp. 221–230.
Manthey, R. and Bry. SATCHMO: A theorem prover implemented in PROLOG. In: Lusk, E. and Overbeck, R., eds.,Ninth International Conference on Automated Deduction, Argonne, IL, Berlin Heidelberg: Springer-Verlag, 1988, pp. 415–434.
Moerkotte, G. and Lockemann, P.C. Reactive consistency control in deductive databases.ACM Transactions on Database Systems, 16(4):670–702, 1991.
Moerkotte, G. and Schmitt, P.H. Analysis and repair of inconsistencies in deductive databases.Journal of Logic Programming (submitted).
Neugebauer, L. and Neumann, K. Schema-driven test data generation for relational database systems. Informatik-Bericht 8502, TU Braunschweig, Institut für Informatik, Abtl. Datenbanken und Informationssysteme, 1985.
Ngu, A.H. Conceptual transaction modeling.IEEE Transactions on Knowledge and Data Engineering, 1(4):508–518, 1989.
Nicolas, J.-M. Logic for improving integrity checking in relational data Bases.Acta Informatica, 18:227–253, 1982.
Noble, H. The automatic generation of test data for a relational database.Information Systems, 8(2):79–86, 1983.
Oberweis, A. Schönthaler, F., Lausen, G., and Stucky, W. Net-based conceptual modelling and rapid prototyping with INCOME.Proceedings of the Third Conference on Software Engineering, Paris, 1986.
Reiter, R. On closed world data bases. Gallaire, H. and Minker, J., eds.,Logic and Data Bases, Plenum Publishing: New York, 1978, pp. 55–76.
Röhrle, J. Dynamic test data generation for the evaluation of database prototypes.Informatik Forschung und Entwicklung, 4:139–148, 1989.
Rossi, F. and Naqvi, S.A. Contributions to the view update problem.Proceedings of the Sixth International Conference on Logic Programming, Lisbon, 1989.
Schönthaler, F. Rapid prototyping to support the conceptual design of information systems.Ph.D. thesis, Universität Fridericiana Karsruhe, 1989.
Silva, A.M. and Melkanoff, M.A. A method for helping discover the dependencies of a relation. In: Gallaire, H., Minker, J., and Nicolas, J.-M., eds.,Advances in Data Base Theory, Vol. 1. Plenum Publishing: New York, 1981.
Stonebraker, M. Tips on benchmarking data base systems.IEEE Database Engineering, 8(1):10–18, 1985.
Tomasic, A. View update translation via deduction and annotation.Proceedings of the International Conference on Database Theory, Bruges, 1988.
Ullman, J.D.Principles of Database and Knowledge-Based Systems, Vol. 1. Rockville, MD: Computer Science Press, 1988.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Neufeld, A., Moerkotte, G. & Loekemann, P.C. Generating consistent test data: Restricting the search space by a generator formula. VLDB Journal 2, 173–213 (1993). https://doi.org/10.1007/BF01232186
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01232186