CASDAL: CASSM's DAta Language

ABSTRACT

CASDAL is a high level data language designed and implemented for the database machine CASSM. The language is used for the manipulation and maintenance of a database using an unnormalized (hierarchically structured) relational data model. It also has facilities to define, modify, and maintain the data model definition. The uniqueness of CASDAL lies in its power to specify complex operations in terms of several new language constructs and its concepts of tagging or marking tuples and of matching values when walking from relation to relation. The language is a result of a top-down design and development effort for a database machine in which high level language constructs are directly supported by the hardware. This paper (1) gives justifications for the use of an unnormalized relational model on which the language is based, (2) presents the CASDAL language constructs with examples, and (3) describes CASSM's architecture and hardware primitives which match closely with the high level language constructs and facilitate the translation process. This paper also attempts to show how the efficiency of the language and the translation task can be achieved and simplified in a system in which the language is the result of a top-down system design and development.

REFERENCES

• 1: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 2: M. M. Astrahan , D. D. Chamberlin, Implementation of a structured English query language, Communications of the ACM, v.18 n.10, p.580-588, Oct. 1975 [doi>10.1145/361020.361215]
• 3: BOYCE, R.F., AND CHAMBERLIN, D.D. Using a structured English query language as a data definition facility. Res. Rep. RJ1318, IBM Res. Lab., San Jose, Calif., Dec. 1973.
• 4: BOYCE, R.F., CHAMBERLIN, D.D., KING, W.F. III, AND HAMMER, M.M. Specifying queries as relational expressions: SQUARE. In Database Management (Proc. IFIP Working Conf. Corsica, April 1974), North-Holland, Amsterdam, 1974, pp. 169-177.
• 5: BRACCHI, G., FEDILI, A., AND PASLINI, P. A language for a relational database management system. Proc. Sixth Annual Princeton Conf. on Inform. Sci. and Syst., March 1972, pp. 84-92.
• 6: J. A. Bush , G. J. Lipovski , S. Y. W. su , J. K. Watson , S. J. Ackerman, Some implementations of segment sequential functions, Proceedings of the 3rd annual symposium on Computer architecture, p.178-185, January 19-21, 1976
• 7: 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]
• 8: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 9: CODD, E.F. A data base sublanguage founded on the relational calculus. Proc. 1971 ACM- SIGFIDET Workshop on Data Description, Access, and Control, San Diego, Calif., Nov. 1971, p. 35-68.
• 10: CODD, E.F. Further normalization of the database relational model. In Coourunt Computer Science Symposia 6: Database Systems, Prentice-Hall, Englewood Cliffs, N.J., 1971, pp. 33-64.
• 11: CODD, E.P. Relational completeness of database sublanguages. In Courant Computer Science Symposia 6: D&abase Systems, Prentice-Hall, Englewood Cliffs, N.J., 1971, pp. 65-98.
• 12: CODD, E.F. Seven steps to rendezvous with the casual user. Proc. IFIP TC-2 Working Conf. on Database Manage. Syst., Corsica, April 1974, pp. 179-200.
• 13: George P. Copeland, Jr. , G. J. Lipovski , Stanley Y.W. Su, The architecture of CASSM: A cellular system for non-numeric processing, Proceedings of the 1st annual symposium on Computer architecture, p.121-128, December 09-11, 1973
• 14: George P. Copeland , Stanley Y. W. Su, A high level data sublanguage for a context-addressed segment-sequential memory, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.265-276, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811516]
• 15: DATE, C.J. Relational database systems: A tutorial. In Information Systems COINS IV, T. Tou, Ed., Plenum Press, New York, 1974, pp. 37-54.
• 16: C. J. Date, An architecture for high-level language database extensions, Proceedings of the 1976 ACM SIGMOD international conference on Management of data, June 02-04, 1976, Washington, D.C.
• 17: DAVIS, E.W. STARAN parallel processor system software. Proc. AFIPS 1974 NCC, Vol. 43, AFIPS Press, Montvale, N.J., pp. 16-22.
• 18: DEFIORE, C.R., AND BERRA, P.B. A data management system utilizing an associative memory. Proc. AFIPS 1973 NCC, Vol. 42, AFIPS Press, Montvale, N.J., pp. 181-185.
• 19: EMAM, A. A data language and its compiler for the CASSM system. Master's Th., Dept. EE, U. of Florida, Gainesville, Fla., 1976.
• 20: GOLDSTEIN, RX?., AND STRNAD, A.J. The MacAIMS data management system. Proc. 1970 ACM SIGFIDET Workshop on Data Description and Access, Houston, Tex., pp. 201- 209.
• 21: HARDGRAVE, W.T. BOLT: A retrieval language for tree structured database systems. In Information Systems COINS IV, T. Tou, Ed., Plenum Press, New York, 1974, pp. 137- 158.
• 22: HEALY, L.D., LIPOVSKI, G.J., AND DOTY, K.L. The architecture of a context addressed segment-sequential storage. Proc. AFIPS 1972 FJCC, AFIPS Press, Montvale, N.J., pp. 691-701.
• 23: HELD, G.D., STONEBRAKER, M.R., AND WONG, E. INGRES-a relational database system. Proc. AFIPS 1975 NCC, Vol. 44, AFIPS Press, Montvale, N.J., pp. 409416.
• 24: Barron C. Housel , Nan C. Shu, A high-level data manipulation language for hierarchical data structures, Proceedings of the 1976 conference on Data : Abstraction, definition and structure, p.155-169, March 22-24, 1976, Salt Lake City, Utah, United States
• 25: KARLOWSKY, I., LEILICH, H.O., AND ZEIDLER, H.C. Content addressing in data bases by special peripheral hardware: A proposal called Search Processor. Institut ftir Datenverarbeitungsanlagen der Tehnischen U., Braunschweig, 1975.
• 26: Charles Kellogg , John Burger , Timothy Diller , Kenneth Fogt, The converse natural language data management system: current status and plans, Proceedings of the 1971 international ACM SIGIR conference on Information storage and retrieval, April 01-02, 1971, College Park, Maryland [doi>10.1145/511285.511290]
• 27: Chyuan Shiun Lin , Diane C. P. Smith , John Miles Smith, The design of a rotating associative memory for relational database applications, ACM Transactions on Database Systems (TODS), v.1 n.1, p.53-65, March 1976 [doi>10.1145/320434.320447]
• 28: LINDE, R.R., GATES, R., AND PENG, T. Associative processor applications to real-time data management. Proc. AFIPS 1973 NCC, Vol. 42, AFIPS Press, Montvale, N.J., pp. 187-195.
• 29: LORIE, R.A. XRM-an extended (n-ary) relational memory. Rep. G320-2096, IBM Scientific Ctr., Cambridge, Mass., Jan. 1974.
• 30: MADISON, D.H., AND CHEN, W.F. CASSMBLR: A cross assembler for CASSM. In a collected description of CASSM: A context addressed segment-sequential memory. Tech. Rep. No. 5, Dept. of EE, U. of Florida, Gainesville, Fla., 1975.
• 31: MINSKY, N. Rotating storage devices as partially associative memories. Proc. 1972 AFIPS FJCC, Vol. 41, Pt. I, AFIPS Press, Montvale, N.J., pp. 587-596.
• 32: MOULDER, R. An implementation of a data management system on an associative processor. Proc. AFIPS 1973 NCC, Vol. 42, AFIPS Press, Montvale, N.J., pp. 171-176.
• 33: OMIIZCINSKI, E.R. The source program analysis phase of compilation for the data sublanguage SLICK II. Master's Th., Dept. of EE, U. of Florida, Gainesville, Fla., 1974.
• 34: OZKARAHAN, E.A., SCHUSTER, S.A., AND SMITH, K.C. RAP-an associative processor for data base management. Proc. AFIPS 1975 NCC, Vol. 44, AFIPS Press, Montvale, N.J., pp. 370-387.
• 35: PARHAMI, B. A highly parallel computing system for information retrieval. Proc. AFIPS 1972 FJCC, Vol. 41, Pt. II, AFIPS Press, Montvale, N.J., pp. GSl-690.
• 36: RUDOLPH, J.A. A production implementation of an associative processor: STARAN. Proc. AFIPS 1972 FJCC, Vol. 41, Pt. I, AFIPS Press, Montvale, N.J., pp. 229-241.
• 37: SAVITT, D.A., LOVE, H.H., AND TROOP, R.E. ASP: A new concept in language and machine organization. Proc. AFIPS 1967 SJCC, Vol. 30, AFIPS Press, Montvale, N.J., pp. 87-102.
• 38: SCHUSTER, S.A., OZKARAHAN, E.A., AND SMITH, K.C. A virtual memory system for a relational associative processor. Proc. 1976 NCC, Vol. 45, AFIPS Press, Montvale, N.J., pp. 855-862.
• 39: Su, S.Y.W. Associative programming in CASSM and its applications. Proc. Int. Conf. on Very Large Data Bases, Tokyo, Japan, Oct. 1977, pp. 213-228.
• 40: Stanley Y. W. Su , George P. Copeland , G. Jack Lipovski, Retrieval operations and data representations in a context-addressed disc system, Proceedings of the 1973 meeting on Programming languages and information retrieval, p.144-160, November 04-06, 1973, Gaithersburg, Maryland
• 41: Su, S.Y.W., EMAM, A., AND CHEN, W.E. CASAL: CASSM's assembly language. Tech. Rep. #7, CASSM Proj., Dept. of EE, U. of Florida, Gainesville, Fla., 1976.
• 42: Su, S.Y.W., AND LIPOVSKI, G.J. CASSM: A cellular system for very large databases. Proc. Int. Conf. on Very Large Databases, Framingham, Mass., Sept. 1975, pp. 456472.
• 43: Su, S.Y.W., AND Lo, D.H. A multi-level semantic model and its integrity control. In preparation.
• 44: System 2006 Reference Manual. MRI Systems Corporation, Austin, Texas, August 1974.
• 45: F. B. Thompson , P. C. Lockemann , B. Dostert , R. S. Deverill, REL: A Rapidly Extensible Language system, Proceedings of the 1969 24th national conference, p.399-417, August 26-28, 1969 [doi>10.1145/800195.805947]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Design, Languages

Keywords:
associative memory, database, nonprocedural language, query language, relational model