Transformation of data traversals and operations in application programs to account for semantic changes of databases

ABSTRACT

This paper addresses the problem of application program conversion to account for changes in database semantics that result in changes in the schema and database contents. With the observation that the existing data models can be viewed as alternative ways of modeling the same database semantics, a methodology of application program analysis and conversion based on an existing-DBMS-model-and schema-independent representation of both the database and programs is presented. In this methodology, the source and target databases are described in terms of the association types of a semantic association model. The structural properties, the integrity constraints, and the operational characteristics (storage operation behaviors) of the association types are more explicitly defined to reveal the semantics that is generally hidden in application programs. The explicit descriptions of the source and target databases are used as the basis for program analysis and conversion. Application programs are described in terms of a small number of “access patterns” which define the data traversals and operations of the programs. In addition to the methodology, this paper (1) describes a model of a generalized application program conversion system that serves as a framework for research, (2) presents an analysis of access patterns that serve as the primitives for program description, (3) delineates some meaningful semantic changes to databases and their corresponding transformation rules for program conversion, (4) illustrates the application of these rules to two different approaches to program conversion problems, and (5) reports on the development effort undertaken at the University of Florida.

REFERENCES

• 1: ANSI/X3/SPARC DBMS Framework Report of the Study Group on Data Base Management Systems, D. Tsichritzis and A. Klug (Eds.). Tech. Note 12, July 1977.
• 2: BACHMAN, C.W., AND DAYA, M. Role concept in data models. In Proc. 3rd Int. Conf. on Very Large Databases, Tokyo, Oct. 1977, pp. 464-476.
• 3: BIass, E.W., AND FRY, J.P. Generalized software for translating data. in Proc. 1976 Nat. Computer Conf., Vol. 15, AFIPS Press, Arlington, Va., pp. 889-899.
• 4: Donald D. Chamberlin , Raymond F. Boyce, SEQUEL: A structured English query language, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.249-264, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811515]
• 5: Peter Pin-Shan Chen, The entity-relationship model—toward a unified view of data, ACM Transactions on Database Systems (TODS), v.1 n.1, p.9-36, March 1976 [doi>10.1145/320434.320440]
• 6: CODD, E.F. A data base sublanguage founded on the relational calculus. Proc. 1971 A CM SIGFIDET Workshop on Data Description, Access, and Control, ACM, New York.
• 7: EDELMAN, J.A., JONES, E.E., LIAW, Y.S., NAZIF, Z.A., AND SCHE|DT, D.L. REORG--A data base reorganizer. Internal Tech. Rep., Bell Labs., Apr. 1976.
• 8: James P. Fry , Randall L. Frank , Ernest A. Hershey, III, A developmental model for data translation, Proceedings of 1972 ACM-SIGFIDET workshop on Data description, access and control, p.77-105, January 1972 [doi>10.1145/800295.811486]
• 9: James P. Fry , David W. Jeris, Towards a formulation and definition of data reorganization, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.83-100, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811506]
• 10: James P. Fry , Diane P. Smith , Robert W. Taylor, An approach to Stored Data Definition and Translation, Proceedings of 1972 ACM-SIGFIDET workshop on Data description, access and control, p.13-55, January 1972 [doi>10.1145/800295.811483]
• 11: FRY, J.P., AND SCHINDLER, S. Assessment of the effect of restructuring on database application programs. DPCTG Working Paper, May 9, 1977.
• 12: FRY, J.P., ET AL. An assessment of the technology for data and program-related conversion. In Proc. 1978 Nat. Computer Conf., Vol. 47, AFIPS Press, Arlington, Va., pp. 887-907.
• 13: GOCUEN, N.H., AND KAPLEN, M.M. An approach to generalized data translation: The ADAPT system. Internal Rep., Bell Labs., Oct. 5, 1977.
• 14: Michael Hammer , Dennis McLeod, The semantic data model: a modelling mechanism for data base applications, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509264]
• 15: HIRANI, H. The migration analyzer for an application program conversion system. CIS Rep. 7879-5, Database Systems Research and Development Center, Computer and Information Science Dep., Univ. Florida, June 1979.
• 16: Honeywell Information Systems Functional specification task 609 database interface package. Defense Communications Agency Contract DCA 100 73-c 0055.
• 17: HousEL, B.C. A unified approach to program and data conversion. In Proc. 3rd Int. Conf. on Very Large Databases, ACM, New York, 1977, pp. 327-335.
• 18: Barron C. Housel , Vincent Y. Lum , Nan Shu, Architecture to an interactive migration system (AIMS), Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.157-169, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811510]
• 19: Barron C. Housel , Maurice H. Halstead, A methodology for machine language decompilation, Proceedings of the 1974 annual conference, p.254-260, January 1974 [doi>10.1145/800182.810410]
• 20: HOUSEL, B., SMITH, D., SHU, N., AND LUM, V. DEFINE: A non-procedural data description language for defining information easily. In Proc. 1975, A CM Pacific Conf., San Francisco, Calif., Apr. 1975, pp. 62-70.
• 21: LAM, H. A generalized system for application program conversion to account for database semantic changes--Design and prototype implementation. CIS Rep. 7879-6, Database Systems Research and Development Center, Computer and Information Science Dep., Univ. Florida, June 1979.
• 22: LAM, H., AND Su, S.Y.W. A semi-automatic data base translation system. ACM Pacific Regional Conf., San Francisco, Calif., 1975, pp. 71-79.
• 23: LUM, V.~., SHU, N.C., AND HOUSEL, B.C. A general methodology for data conversion and restructuring. IBM J. Res. Dev. 20, 5 (1976), 483-497.
• 24: MARION, R. Host/DML language application program conversion as a result of data conversion. DPCTG Working Paper, Nov. 21, 1977.
• 25: J. W. Mehl , C. P. Wang, A study of order transformations of hierarchical structures in IMS data bases, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.125-139, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811508]
• 26: Alan G. Merten , James P. Fry, A data description language approach to file translation, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.191-205, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811512]
• 27: MooRE, L. The implementation of a COBOL/DML analyzer for an application program conversion system. Master's Thesis, in preparation, 1979.
• 28: 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]
• 29: Shamkant B. Navathe , James P. Fry, Restructuring for large databases: three levels of abstraction, ACM Transactions on Database Systems (TODS), v.1 n.2, p.138-158, June 1976 [doi>10.1145/320455.320461]
• 30: Shamkant B. Navathe , Mario Schkolnick, View representation in logical database design, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509286]
• 31: PALMER, i. Record subtype facilities in database systems. In Proc. Int. Conf. Very Large Data Bases, West Berlin, W. Germany, Sept. 1978, pp. 148-155.
• 32: J. A. Ramirez , N. A. Rin , N. S. Prywes, “Automatic generation of data conversion programs using a data description language”, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.207-225, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811513]
• 33: ROTUN~E, J.B. Evaluating inter-entry retrieval expressions in a relational data base management system. In Proc. AFIPS 1975 Nat. Computer Conf., Vol. 44, AFIPS Press, Arlington, Va., pp. 417-423.
• 34: RoussoPouLos, N., AND MYLOPOULOS, j. Using semantic networks for database management. In Proc. Very Large Database Conf., Framingham, Mass., Sept. 1975, pp. 144-172.
• 35: SCHINDLER, S. An approach to database application restructuring. Working Paper 76 ST 2.3, Database Systems Research Group, Univ. Michigan, Ann Arbor, 1976.
• 36: SCHINDLER, S. Templates for structured DML programs. Working Paper ST 2.1 Data Translation Project, Business Administration Dep., Univ. Michigan, Ann Arbor, Dec. 1976, pp. 1-31.
• 37: SCHKOLNICK, M. The optimal selection of secondary indices for files. Inf. Syst. 1 (1975), 141-146.
• 38: Hans Albrecht Schmid , J. Richard Swenson, On the semantics of the relational data model, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500110]
• 39: SENKO, M.E. Specification of stored data structures and desired output results in DIAM iI with FORAL. In Proc. 1st Int. Conf. on Very Large Databases, Framingham, Mass., Sept. 1975, pp. 557-571.
• 40: Arie Shoshani, A logical-level approach to data base conversion, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500097]
• 41: SHNEDIERMAN, B. A framework for automatic conversion of network database programs under schema transformation. In Proc. Jerusalem Conf. In{ormation Technology, North-Holland Publishing Co., Amsterdam, The Netherlands, 1978.
• 42: SHNEIDERMAN, B., AND COOK, C. Enumerating logical database designs. DPCTG Working Paper, Jan. 21, 1978.
• 43: Nan C. Shu , Barron C. Housel , Vincent Y. Lum, CONVERT: a high level translation definition language for data conversion, Communications of the ACM, v.18 n.10, p.557-567, Oct. 1975 [doi>10.1145/361020.361023]
• 44: N. C. Shu , B. C. Housel , R. W. Taylor , S. P. Ghosh , V. Y. Lum, EXPRESS: a data EXtraction, Processing, and Restructuring System, ACM Transactions on Database Systems (TODS), v.2 n.2, p.134-174, June 1977 [doi>10.1145/320544.320549]
• 45: SIBLEY, E.B., AND MERTEN, A.G. Transferability and translation of programs and data. In Information Systems, CONINS IV, Plenum Press, N.Y., 1972, pp. 291-301.
• 46: SMITH, D. The use of abstraction hierarchies in the study of database program conversion. DPCTG Working Paper, Jan. 21, 1978.
• 47: Diane C. P. Smith, A method for data translation using the Stored-Data Definition and Translation Task Group languages, Proceedings of 1972 ACM-SIGFIDET workshop on Data description, access and control, p.107-124, January 1972 [doi>10.1145/800295.811487]
• 48: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation and generalization, ACM Transactions on Database Systems (TODS), v.2 n.2, p.105-133, June 1977 [doi>10.1145/320544.320546]
• 49: John Miles Smith , Philip Yen-Tang Chang, Optimizing the performance of a relational algebra database interface, Communications of the ACM, v.18 n.10, p.568-579, Oct. 1975 [doi>10.1145/361020.361025]
• 50: Stanley Y. W. Su, Application Program Conversion due to Data Base Changes, Systems for Large Data Bases, p.143-157, September 08-10, 1976
• 51: 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]
• 52: Stanley Y. W. Su , Der Her Lo, A Semantic Association Model for Conceptual Design, Proceedings of the 1st International Conference on the Entity-Relationship Approach to Systems Analysis and Design, p.169-192, January 1980
• 53: Sv, S.Y.W., AND REYNOLDS, M.J. Conversion of high level sublanguage queries to account for database changes. Tech. Rep. PC7701, Electrical Engineering Dep., Univ. of Florida, May 1977.
• 54: Su, S.Y.W., AND REYNOLDS, M.J. Conversion of high-level sublanguage queries to account for database changes. In Proc. Nat. Computer Conf., Vol. 47, AFIPS Press, Arlington, Va., 1978, pp. 857-875.
• 55: Su, S.Y.W., Lo, D.H., AND LAM, H. Application program conversion due to semantic changes. Unpublished manuscript, 1978.
• 56: TAYLOR, R., FRY, J., SCHNEIDERMAN, B., SMITH, D., AND Su, S. Database program conversion: A framework for research. Database Program Conversion Task Group of the COSASYL Systems Committee. In Proc. Fifth Int. Conf. on Very Large Data Bases, Rio de Janeiro, Brazil, Oct. 3-5, I979.
• 57: UNIVAC, UNIVAC I100 Series Data File Converter, Programmer Reference UP-8070, Sperry Rand Corporation, March 1974.
• 58: VASSILIOU, Y. DBMS transaction translation. Unpublished paper, Dep. Computer Science, Univ. Toronto, Canada, 1978.
• 59: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
• 60: Koichi Yamaguchi , Alan G. Merten, Methodology for transferring programs and data, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.141-155, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811509]
• 61: S. B. Yao, An attribute based model for database access cost analysis, ACM Transactions on Database Systems (TODS), v.2 n.1, p.45-67, March 1977 [doi>10.1145/320521.320535]
• 62: YAO, S.B. Optimal evaluation of two-variable queries. Unpublished manuscript, 1978.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms, Design

Keywords:
access pattern, application program conversion, database changes, semantic data model, transformation rules