Automatically Evaluating the Efficiency of Search-Based Test Data Generation for Relational Database Schemas
Cody Kinneer, Gregory M. Kapfhammer, Phil McMinn, Chris J. Wright · Proceedings/Proceedings of the ... International Conference on Software Engineering and Knowledge Engineering · 2015
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 performing search-based test data generation-a theoretical analysis to determine worst-case time complexity is difficult to generalize and thus not often reported in the literature.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 configurations, the results of our study reveal performance tradeoffs in testing strategies for relational database schemas.