Decompiling CODASYL DML into retional queries

ABSTRACT

A “decompilation” algorithm is developed to transform a program written with the procedural operations of CODASYL DML into one which interacts with a relational system via a nonprocedural query specification. An Access Path Model is introduced to interpret the semantic accesses performed by the program. Data flow analysis is used to determine how FIND operations implement semantic accesses. A sequence of these is mapped into a relational query and embedded into the original program. The class of programs for which the algorithm succeeds is characterized.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: BLASGEN, M.W., ET AL. "System R: An architectural update," IBM Res. Rep. RJ2581(33481), IBM Research Laboratory, San Jose, Calif., July 1979.
• 3: CODASYL COBOL COMMITTEE. J. Dev., 1978.
• 4: CODD~ E.F. Further normalization of the data base relational model. In Courant Computer Science Symposia 6, Data Base Systems, Prentice-Hall, New York, 1971.
• 5: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 6: HOUSEL, B.C. A unified approach to program and data conversion. In Proc. Int. Conf. Very Large Data Bases (Tokyo, Japan, Oct. 1977), pp. 327-335.
• 7: Randy Howard Katz, Database design and translation for multiple data models, 1980
• 8: R. H. Katz , E. Wong, An access path model for physical database design, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582254]
• 9: John Nations , Stanley Y. W. Su, Some DML instruction sequences for application program analysis and conversion, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509284]
• 10: SCHINDLER, S.J. Templates for structured DML Programs. Working Paper ST 2.2, Data Translation Project, Graduate School of Business Administration, Univ. Michigan, Ann Arbor, Feb. 1977.
• 11: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 12: Stanley Y. W. Su, Application Program Conversion due to Data Base Changes, Systems for Large Data Bases, p.143-157, September 08-10, 1976
• 13: Stanley Y. W. Su , B. J. Liu, A methodology of application program analysis and conversion based on database semantics, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509417]
• 14: Su, S.Y.W., AND REYNOLDS, M.J. Conversion of high-level sublanguage queries to account for database changes. In Proc. 1978 AFIPS Nat. Computer Conf. AFIPS Press, Arlington, Va.
• 15: SU, S.Y.W., ET AL. Application program conversion due to semantic changes. CIS Rep. 7879-2, Dep. Computer and Information Sciences, March 1978.
• 16: TAYLOR, R.W., ET AL. Database program conversion: A framework for research. In Proc 5th Int. Conf. on Very Large Data Bases, 1979.
• 17: D. Tsichritzis, LSL: a Link and Selector Language, Proceedings of the 1976 ACM SIGMOD international conference on Management of data, June 02-04, 1976, Washington, D.C.
• 18: Eugene Wong , Randy H. Katz, Logical Design and Schema Conversion for Relational and DBTG Databases, Proceedings of the 1st International Conference on the Entity-Relationship Approach to Systems Analysis and Design, p.311-322, January 1980

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Data manipulation languages (DML); Query languages
      H.2.5 Heterogeneous Databases
          Subjects: Program translation**

General Terms:
Algorithms

Keywords:
decompilation, semantic data models