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. 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. 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. 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. 4 CHAMBERLIN, D.D., AND BOYCE, R.F. SEQUEL: A structured English query language. In Proc. ACM/SIGMOD Workshop on Data Description, Access, and Control, Ann Arbor, Mich., 1974.
5. 5 CHEN, P.P.S. The entity-relationship model--Toward a unified view of data. A CM Trans. Database Syst. 1, 1 (March 1976}, 9-36.
6. 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. 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. 8 FRY, J.P., FRANK, R.L., AND HERSHEY, E.A., III A developmental model for translation. In Proc. 1972 ACM SIGFIDET Workshop on Data Description, Access, and Control, A.L. Dean (Ed.), ACM, New York, pp. 77-106.
9. 9 FRY, J.P., AND JERm, D. Towards a formulation of data reorganization. In Proc. 1974 ACM/ SIGMOD Workshop on Data Description, Access, and Control, R. Rustin (Ed.), ACM, New York, pp. 77-107.
10. 10 FRY, J.P., SMITH, D.C.P., AND TAYLOR, R.W. An approach to stored data definition and translation. In Proc. 1972 A CM/SIGFIDE T Workshop on Data Description, Access, and Control, A.L. Dean (Ed.), Denver, Colo., Nov. 1972, pp. I3-55.
11. 11 FRY, J.P., AND SCHINDLER, S. Assessment of the effect of restructuring on database application programs. DPCTG Working Paper, May 9, 1977.
12. 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. 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. 14 HAMMER, M., AND McLEOD, D. The semantic data model: A modelling mechanism for database applications. Proc. ACM S1GMOD "78, May 1978, pp. 26-34.
15. 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. 16 Honeywell Information Systems Functional specification task 609 database interface package. Defense Communications Agency Contract DCA 100 73-c 0055.
17. 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. 18 HOUSEL, B.C., LUM, V.Y., AND SHU, N. Architecture to an interactive migration system (AIMS). In Proc. 1974 ACM SIGIDET Workshop on Data Description, Access, and Control, ACM, New York, pp. 157-170.
19. 19 HousF.L, B.C., AND HALSTEAD, M.H. A methodology for machine language decompilation. In Proc. 1974 ACM Annu. Conf., ACM, New York, pp. 254-260.
20. 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. 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. 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. 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. 24 MARION, R. Host/DML language application program conversion as a result of data conversion. DPCTG Working Paper, Nov. 21, 1977.
25. 25 MEHL, J.W., AND WANG, C.P. A study of order transformation of hierarchical structures in IMS data bases. In Proc. ACM SIGF{DET Workshop on Data Description, Access, and Control, ACM, New York, May 1974, pp. 125-I40.
26. 26 MERTEN, A.G., AND FRY, J.P. A data description approach to file translation. In Proc. 1974 ACM SIGFIDET Workshop on Data Description, Access, and Control, ACM, New York, pp. 191-205.
27. 27 MooRE, L. The implementation of a COBOL/DML analyzer for an application program conversion system. Master's Thesis, in preparation, 1979.
28. 28 NATIONS, J., AND SU, S.Y.W. Some DML instruction sequences for application program analysis and conversion. In Proc. of the A CM SIGMOD Conf., Austin, Tex., 1978, pp. 120-131.
29. 29 NAVATHE, S.B., AND FRY, J.P. Restructuring for large data bases: Three levels of abstraction. ACM Trans. Database Syst. 1, 2 (June 1976), 138-158.
30. 30 NAVATHE, S.B., AND SCHKOLNICK, M. View representation in logical database designs. In Proc. ACM/SIGMOD rnt. Conf. Management of Data, Austin, Tex., May 1978, pp. 144-156.
31. 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. 32 RAMIREZ, J.A., RIN, N.A., AND PRYWES, N.S. Automatic conversion of data conversion programs using a data description language. In Proc. 1974 A CM SIGFIDET Workshop on Data Description, Access, and Control, ACM, New York, pp. 207-225.
33. 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. 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. 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. 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. 37 SCHKOLNICK, M. The optimal selection of secondary indices for files. Inf. Syst. 1 (1975), 141-146.
38. 38 SCHMID, H.A., AND SWF.NSON, J.E. On the semantics of the relational model. In Proc. A CM/ SIGMOD 1975 Conf., May 1975, pp. 211-233.
39. 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. 40 SHOSHANI, A. A logical-level approach to data base conversion. In Proc. 1975 ACM/SIGMOD int. Conf. Management ofData, ACM, New York, pp. 112--122.
41. 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. 42 SHNEIDERMAN, B., AND COOK, C. Enumerating logical database designs. DPCTG Working Paper, Jan. 21, 1978.
43. 43 Sau, N.C., HOUSEL, B.C., AND LUM, V.Y. CONVERT: A high level translation definition language for data conversion. Commun. ACM 18, 10 {Oct. 1975}, 557-567.
44. 44 SHU, N.C., HOUSEL, B.C., TAYLOR, R.W., GHOSH, S.P., AND LUM, V.Y. EXPRESS: A data extraction, processing, and restructuring system. A CM Tran. Database Syst. 2, 2 {June 1977), 134-174.
45. 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. 46 SMITH, D. The use of abstraction hierarchies in the study of database program conversion. DPCTG Working Paper, Jan. 21, 1978.
47. 47 SMITH, D.C.P. A method for data translation using the stored data and definition task group languages. Proc. 1972 ACM SIGEFIDET Workshop on Data Description, Access, and Control, ACM, N.Y., pp. I07-124.
48. 48 SMITH, J.M., AND SMITH, D.C.P. Database abstractions: Aggregation and generalization. A CM Trans. Database Syst. 2, 2 (June 1977), pp. 105-133.
49. 49 SMITH, J.M., AND CHANG, P.Y.T. Optimizing the performance of a relational algebra and database interface. Commun. ACM 18, 10 (Oct. 1975), 568-579.
50. 50 Su, S.Y.W. Application program conversion due to database changes. In Proc. of the Second Int. Conf. on Very Large Databases, Brussels, Belgium, Sept. 1976, pp. 143-158.
51. 51 SU, S.Y.W., AND LIU, B.J. A methodology of application program analysis and conversion based on database semantics. In Proc. 1977 Int. Conf. Management of Data, pp. 75-87.
52. 52 Su, S.Y.W., AND LO, D.H. A semantic association model for conceptual database design. In Proc. of the Int. Conf. Entity-Relationship Approach to Systems Analysis and Design, Los Angeles, Calif., Dec. 10-12, 1979.
53. 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. 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. 55 Su, S.Y.W., Lo, D.H., AND LAM, H. Application program conversion due to semantic changes. Unpublished manuscript, 1978.
56. 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. 57 UNIVAC, UNIVAC I100 Series Data File Converter, Programmer Reference UP-8070, Sperry Rand Corporation, March 1974.
58. 58 VASSILIOU, Y. DBMS transaction translation. Unpublished paper, Dep. Computer Science, Univ. Toronto, Canada, 1978.
59. 59 WONG, E., AND YOUSSEFI, K. Decomposition--A strategy for query processing. A CM Trans. Database Syst. 1, 3 (Sept. 1976), 233-241.
60. 60 YAMAGUCHI, K., AND MERTEN, A.G. Methodology for transferring programs and data. In Proc. 1974 ACM SIGFIDET Workshop on Data Description, Access, and Control, ACM, New York, pp. 141-156.
61. 61 YAO, S.B. An attribute based model for database access cost analysis. ACM Trans. Database Syst. 2, 1 (March 1977), 45-67.
62. 62 YAO, S.B. Optimal evaluation of two-variable queries. Unpublished manuscript, 1978.

Index Terms

• Information systems

  • Data management systems

    • Data structures

      • Data access methods

    • Database design and models

  • Information systems applications