Impact analysis of database schema changes

ABSTRACT

We propose static program analysis techniques for identifying the impact of relational database schema changes upon object-oriented applications. We use dataflow analysis to extract all possible database interactions that an application may make. We then use this information to predict the effects of schema change. We evaluate our approach with a case-study of a commercially available content management system, where we investigated 62 versions of between 70k-127k LoC and a schema size of up to 101 tables and 568 stored procedures. We demonstrate that the program analysis must be more precise, in terms of context-sensitivity than related work. However, increasing the precision of this analysis increases the computational cost. We use program slicing to reduce the size of the program that needs to be analyzed. Using this approach, we are able to analyse the case study in under 2 minutes on a standard desktop machine, with no false negatives and a low level of false positives.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Scott W. Ambler , Pramodkumar J. Sadalage, Refactoring Databases: Evolutionary Database Design, Addison-Wesley Professional, 2006
• 3: Robert S. Arnold, Software Change Impact Analysis, IEEE Computer Society Press, Los Alamitos, CA, 1996
• 4: Dirk Beyer , Andreas Noack , Claus Lewerentz, Efficient Relational Calculation for Software Analysis, IEEE Transactions on Software Engineering, v.31 n.2, p.137-149, February 2005 [doi>10.1109/TSE.2005.23]
• 5: David Binkley , Nicolas Gold , Mark Harman, An empirical study of static program slice size, ACM Transactions on Software Engineering and Methodology (TOSEM), v.16 n.2, p.8-es, April 2007 [doi>10.1145/1217295.1217297]
• 6: F. Biscotti, C. Graham, and D. Sommer. Market Share: Database Management Systems Software, EMEA, 2005. Technical report, Gartner, June 2006.
• 7: T.-H. Choi, O. Lee, H. Kim, and K.-G. Doh. A practical string analyzer by the widening approach. In N. Kobayashi, editor, APLAS, volume 4279 of LNCS, pages 374--388. Springer, 2006.
• 8: A. S. Christensen, A. Møller, and M. I. Schwartzbach. Precise analysis of string expressions. In Proc. 10th International Static Analysis Symposium, SAS ?03, volume 2694 of LNCS, pages 1--18. Springer-Verlag, June 2003.
• 9: Yossi Cohen , Yishai A. Feldman, Automatic high-quality reengineering of database programs by abstraction, transformation and reimplementation, ACM Transactions on Software Engineering and Methodology (TOSEM), v.12 n.3, p.285-316, July 2003 [doi>10.1145/958961.958962]
• 10: Martin Fowler, Patterns of Enterprise Application Architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 11: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 12: Carl Gould , Zhendong Su , Premkumar Devanbu, Static Checking of Dynamically Generated Queries in Database Applications, Proceedings of the 26th International Conference on Software Engineering, p.645-654, May 23-28, 2004
• 13: Susan Horwitz , Thomas Reps , Mooly Sagiv, Demand interprocedural dataflow analysis, ACM SIGSOFT Software Engineering Notes, v.20 n.4, p.104-115, Oct. 1995
• 14: Suresh Jagannathan , Stephen Weeks, A unified treatment of flow analysis in higher-order languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.393-407, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199536]
• 15: Gregory M. Kapfhammer , Mary Lou Soffa, A family of test adequacy criteria for database-driven applications, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 16: A. Karahasanovic. Supporting Application Consistency in Evolving Object-Oriented Systems by Impact Analysis and Visualisation. PhD thesis, University of Oslo, 2002.
• 17: James Law , Gregg Rothermel, Whole program Path-Based dynamic impact analysis, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 18: O. Lhoták and L. Hendren. Context-sensitive points-to analysis: is it worth it? In A. Mycroft and A. Zeller, editors, 15th Int. Conference on Compiler Construction, volume 3923 of LNCS, pages 47--64, Vienna, 2006. Springer.
• 19: D. Liang , M. J. Harrold, Slicing Objects Using System Dependence Graphs, Proceedings of the International Conference on Software Maintenance, p.358, March 16-19, 1998
• 20: Mikael Lindvall , Kristian Sandahl, How well do experienced software developers predict software change?, Journal of Systems and Software, v.43 n.1, p.19-27, Oct. 1998 [doi>10.1016/S0164-1212(98)10019-5 ]
• 21: Phoenix Framework. http://research.microsoft.com/phoenix, 2007.
• 22: Shari Lawrence Pfleeger, Software engineering: theory and practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 23: Xiaoxia Ren , Fenil Shah , Frank Tip , Barbara G. Ryder , Ophelia Chesley, Chianti: a tool for change impact analysis of java programs, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 24: Thomas Reps , Susan Horwitz , Mooly Sagiv , Genevieve Rosay, Speeding up slicing, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.11-20, December 06-09, 1994, New Orleans, Louisiana, United States
• 25: B. Ryder. Dimensions of precision in reference analysis of object-oriented programming languages. Lecture Notes of Computer Science, 137:126--137, 2003.
• 26: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 27: D. I. Sjoberg. Quantifying schema evolution. IST, 35(1):35--44, 1993.
• 28: Frank Tip, A Survey of Program Slicing Techniques., CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1994
• 29: Ben Wiedermann , William R. Cook, Extracting queries by static analysis of transparent persistence, ACM SIGPLAN Notices, v.42 n.1, January 2007
• 30: K. Wong. Rigi Users?s manual, Version 5.4.4. Technical report, University of Victoria, Dept of Computer Science, ftp://ftp.rigi.csc.uvic.ca/pub/rigi/doc, 1998.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design

General Terms:
Algorithms, Design, Management

Keywords:
impact analysis