Supercharging the Testing of Database Software

What is it about?

Databases provide their clients with a variety of guarantees that everyday systems rely on to ensure correct operation. Unfortunately, research has shown that these guarantees are routinely broken by much of the most widely used database software, due to its complexity, which users experience as errors in the software they interact with. For this reason, researchers have developed techniques and algorithms for testing whether database software comply with stated guarantees. In this work, we develop AWDIT (pron. “audit”), a collection of algorithms and a software tool, which significantly improve the efficiency of running such tests compared to existing work. We also tackle the problem theoretically by proving that the algorithms of AWDIT are, in a mathematical sense, the fastest possible, using techniques from complexity theory.

Featured Image

Photo by Eric Mills on Unsplash

Photo by Eric Mills on Unsplash

Why is it important?

AWDIT allows developers to run tests at an unprecedented scale; where previous work could test thousands of database operations in seconds, AWDIT can test millions. We hope that such improvements can lead to more widespread adoption of database testing, making our everyday software more reliable. Lastly, our application of techniques from complexity theory are novel in the area of database testing, and we hope that other researchers will be inspired to employ similar techniques in the future.