Introducing dynamic invariant detection for relational databases

Introduction

Have you ever wondered how to extend the concept of dynamic invariant detection from software programs to relational databases? In a recent research paper (Cobb et al. 2011) , my co-authors and I introduced a novel approach that makes this extension. The presented method significantly enhances the detection of meaningful invariants in both fixed data sets and subject programs. Keep reading to learn more about this research!

Contributions

The paper presents several key contributions, summarized in the following list:

• Technique: A new method that extends the notion of dynamic invariant detection to structured query language (SQL)-based databases and the applications that employ them.

• Tool: An implementation that analyzes existing MySQL databases and the Java applications that use these databases to automatically produce files for input to Daikon, a popular dynamic invariant detection tool commonly applied to Java applications.

• Experiments: Two empirical studies using seven subjects, one of which analyzes the quality of invariant detection and the other of which examines a database-specific application for schema constraint modification. An insight from these experiments is that the tool can automatically detect that programs are enforcing constraints on their data that are not — but could be! — encoded in the relational database’s schema.

Overall, this paper’s results demonstrate the feasibility of collecting meaningful invariants for four fixed data sets and three subject programs. Furthermore, the paper shows that dynamic invariants for relational databases can be effectively used to identify areas where the relational database schema constraints could be tightened to protect data integrity.

Future

This research opens up several exciting avenues for future work. For instance, the mapping of the database structure could be extended to allow for additional invariant detection on relationships between columns in different tables or for the results of JOINs executed by a program. Along with ensuring that it works for a wide variety of relational database management systems, we plan to use the approach to support other testing tasks for database schemas.

Return to Blog Post Listing