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