Automatically Evaluating the Efficiency of Search-Based Test Data Generation for Relational Database Schemas

The characterization of an algorithm’s worst-case time complexity is useful because it succinctly captures how its runtime will grow as the input size becomes arbitrarily large. However, for certain algorithms—such as those per-forming search-based test data generation—a theoretical analysis to determine worst-case time complexity is diffi-cult to generalize and thus not often reported in the liter-ature. This paper introduces a framework that empirically determines an algorithm’s worst-case time complexity by doubling the size of the input and observing the change in runtime. Since the relational database is a centerpiece of modern software and the database’s schema is frequently untested, we apply the doubling technique to the domain of data generation for relational database schemas, a field where worst-case time complexities are often unknown. In addition to demonstrating the feasibility of suggesting the worst-case runtimes of the chosen algorithms and configu-rations, the results of our study reveal performance trade-offs in testing strategies for relational database schemas.