``Scalable satisfiability checking and test data generation from modeling diagrams''
by
Yannis Smaragdakis,
Christoph Csallner,
and Ranjith Subramanian.
Automated Software Engineering, vol. 16, no. 1, Mar. 2009.
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 modeling language, primarily targeting database applications,
with significant uses in practice. The general problem of even checking
whether an ORM diagram is satisfiable is quite hard: restricted forms are
easily NP-hard and the problem is undecidable for some expressive
formulations of ORM. Brute-force mapping to input for constraint and SAT
solvers does 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.
@article{smaragdakis09scalable,
author = {Yannis Smaragdakis and Christoph Csallner and Ranjith
Subramanian},
title = {Scalable satisfiability checking and test data generation from
modeling diagrams},
journal = {Automated Software Engineering},
volume = {16},
number = {1},
month = mar,
year = {2009}
}
Copyright notice:
This material is presented to ensure timely dissemination of scholarly and
technical work. Copyright and all rights therein are retained by authors or
by other copyright holders. All persons copying this information are
expected to adhere to the terms and constraints invoked by each author s
copyright. In most cases, these works may not be reposted without the
explicit permission of the copyright holder.