Scalable automatic test data generation from modeling diagrams

ABSTRACT

We explore the automatic generation of test data that respect constraints expressed in the Object-Role Modeling(ORM) language. ORM is a popular conceptual modelinglanguage, primarily targeting database applications, withsignificant uses in practice. The general problem of evenchecking whether an ORM diagram is satisfiable is quitehard: restricted forms are easily NP-hard and the problemis undecidable for some expressive formulations of ORM.Brute-force mapping to input for constraint and SAT solversdoes not scale: state-of-the-art solvers fail to find data to satisfy uniqueness and mandatory constraints in realistic time even for small examples. We instead define a restricted subset of ORM that allows efficient reasoning yet contains most constraints overwhelmingly used in practice. We show that the problem of deciding whether these constraints are consistent (i.e., whether we can generate appropriate test data) is solvable in polynomial time, and we produce a highly efficient (interactive speed) checker. Additionally, we analyze over 160 ORM diagrams that capture data models from industrial practice and demonstrate that our subset of ORM is expressive enough to handle their vast majority

REFERENCES

• 1: F. A. Aloul, A. Ramani, I. L. Markov, and K. A. Sakallah. PBS: A backtrack search pseudo-boolean solver and optimizer. In Proc. Int. Symp. on the Theory and Applications of Satisfiability Testing (SAT), 2002.
• 2: Diego Calvanese , Maurizio Lenzerini, On the Interaction Between ISA and Cardinality Constraints, Proceedings of the Tenth International Conference on Data Engineering, p.204-213, February 14-18, 1994
• 3: Yuetang Deng , Phyllis Frankl , David Chays, Testing database transactions with AGENDA, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062486]
• 4: Alexander Egyed, Instant consistency checking for the UML, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134339]
• 5: Alexander Egyed, Fixing Inconsistencies in UML Design Models, Proceedings of the 29th international conference on Software Engineering, p.292-301, May 20-26, 2007 [doi>10.1109/ICSE.2007.38]
• 6: Wenfei Fan , Leonid Libkin, On XML integrity constraints in the presence of DTDs, Journal of the ACM (JACM), v.49 n.3, p.368-406, May 2002 [doi>10.1145/567112.567117]
• 7: John Grant , Jack Minker, Inferences for numerical dependencies, Theoretical Computer Science, v.41 n.2-3, p.271-287, Dec. 1985
• 8: Terry Halpin, A fact-oriented approach to schema transformation, Proceedings of the 3rd symposium on Mathematical fundamentals of database and knowledge base systems, p.342-356, May 1991, Rostock, Germany
• 9: T. A. Halpin. Object-role modeling (ORM/NIAM). In Handbook on Architectures of Information Systems, 1998.
• 10: Terry Halpin, Information modeling and relational databases: from conceptual analysis to logical design, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 11: Terry A. Halpin , Henderik Alex Proper, Database Schema Transformation and Optimization, Proceedings of the 14th International Conference on Object-Oriented and Entity-Relationship Modelling, p.191-203, December 12-15, 1995
• 12: S. Heynmans. Decidable Open Answer Set Programming. PhD thesis, Vrije Universiteit Brussel, Department of Computer Science, 2006.
• 13: Daniel Jackson, Software Abstractions: Logic, Language, and Analysis, The MIT Press, 2006
• 14: M. Jarrar and S. Heymans. Unsatisfiability reasoning in ORM conceptual schemes. In Int. Conf. on Semantics of a Networked World (ICSNW), 2005.
• 15: C. M. Keet. Prospects for and issues with mapping the object-role modeling language into DLRifd. In Proc. Int. Workshop on Description Logics, 2007.
• 16: Sarfraz Khurshid , Daniel Jackson, Exploring the Design of an Intentional Naming Scheme with an Automatic Constraint Analyzer, Proceedings of the 15th IEEE international conference on Automated software engineering, p.13, September 11-15, 2000
• 17: Panagiotis Manolios , Daron Vroon , Gayatri Subramanian, Automating component-based system assembly, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273473]
• 18: Christian Nentwich , Wolfgang Emmerich , Anthony Finkelstein, Consistency management with repair actions, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 19: Andrea Neufeld , Guido Moerkotte , Peter C. Lockemann, Generating consistent test data: restricting the search space by a generator formula, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.2, April 1993
• 20: G. M. Nijssen , T. A. Halpin, Conceptual schema and relational database design: a fact oriented approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 21: I. Shlyakhter, R. Seater, D. Jackson, M. Sridharan, and M. Taghdiri. Debugging overconstrained declarative models using unsatisfiable cores. In Proc. Automated Software Engineering (ASE), 2003.
• 22: Mana Taghdiri, Inferring Specifications to Detect Errors in Code, Proceedings of the 19th IEEE international conference on Automated software engineering, p.144-153, September 20-24, 2004 [doi>10.1109/ASE.2004.42]
• 23: P. van Bommel, A. ter Hofstede, and T. van der Weide. Semantics and verification of object-role models. Information Systems, 16(5):471--495, 1991.
• 24: Ian Warren , Jing Sun , Sanjev Krishnamohan , Thiranjith Weerasinghe, An Automated Formal Approach to Managing Dynamic Reconfiguration, Proceedings of the 21st IEEE/ACM International Conference on Automated Software Engineering, p.37-46, September 18-22, 2006 [doi>10.1109/ASE.2006.12]
• 25: David Willmor , Suzanne M. Embury, An intensional approach to the specification of test cases for database applications, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134301]

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.3 Languages
          Subjects: Data description languages (DDL)

General Terms:
Design, Languages

Keywords:
NP-hardness, ORM, ORM-modeling, test databases