BIBLIOGRAPHIC ENTRIES Abrial74 Abrial, J. R. Data semantics. In Klimbie, J. W. and Koffeman, K. L. (Eds.), Database Management, North-Holland, 1974, pp. 1-59. The author discusses the semantics of databases and presents a functional data model for their description. The work draws on research in generalized DBMSes, relational databases, and artificial intelligence. In the data model, the description of an object is given by the connections it has with other objects. Each connection is a pair of possibly multivalued access functions, one for each direction along the connection. Hence, the data model is based on binary relations. The data model is defined informally using examples. The author discusses missing values (nothing, unknown), naming, side effects, standard or generic functions, and the writing of algorithms and programs within the model. The data model is formally defined in terms of mathematics and the basic concepts of the model (the model is used to define itself). Finally, physical implementation considerations are given. This paper was perhaps the first extensive investigation of data semantics and the first description of the functional approach to data semantics. Allman76 Allman, E., Stonebraker, M., and Held, G. Embedding a relational data sublanguage in a general purpose programming language. In Utah76. Ambler77 Ambler, A. L., Good, D. I., Browne, C., Burger, W. F., Cohen, R. M., Hoch, C. G., and Wells, R. E. GYPSY: A language for specification and verification of verifiable programs. SIGPLAN Notices 12, 3(March 1977), pp. 1-10. An introduction to the Gypsy programming and specification language is given. Gypsy is a high-level programming language with facilities for general programming and also for systems programming that is oriented toward communications processing. This includes facilities for concurrent processes and process synchronization. Gypsy also contains facilities for detecting and processing errors that are due to he actual running of the program in an imperfect environment. The specification facilities give a precise way of expressing the desired properties of the Gypsy programs. All of the features of Gypsy are fully verifiable, either by formal proof or by validation at run time. An overview of the language design and a letailed example program are given. (authors' abstract) Ardis79 Ardis, M. A. and Hamlet, R. G. Structure of specifications and implementations of data abstractions. Computer Science TR-801, University of Maryland, Sept. 1979. A data abstraction is a collection of sets together with a collection of functions. An intuitive bstraction is unconnected with formalism: the sets and functions are supposed to be known ab initio. ormal ideas enter when the abstraction is (i) implemented, a conventional program written to carry out the perations on actual data; and (ii) specified, a mathematical characterization given to precisely describe its ets and functions. The intuitive abstraction, an implementation, and a specification share a syntax that imes the sets and functions, and gives the function domains and ranges (as set names). The central estion for any particular example of syntax is whether the semantics of the three ideas correspond: does e collection of objects and operations a human being was thinking of behave in the way the plementation's data and procedures behave? Do the mathematical entities behave as imagined? The questions can never be answered precisely, because the intuitive abstraction is imprecise. On the other hand, precise comparison of specification and implementation is possible. This paper presents an algebraic comparison of specifications with implementations. It is shown that these abstractions always overlap, and have a common (lattice) structure that is valuable in understanding the modification of code or specification. However, in dealing with the precise entities subject to formal analysis, we must not lose sight of the intuition behind them. Therefore, our definitions are framed in terms of the intuitive abstraction a person attempted to specify or implement, and we refer the algebraic ideas to this standard whenever possible. Section 1 presents the intuitive ideas of an abstraction, its implementation, and specification. The ideas are essentially those of Hoare and Guttag. Section 2 gives the common formalism to be used, the constant word algebra. In Sections 3 and 4, this is applied to ideas, and suggests that the precise connection can shed light on the imprecise one that is really of interest: the intuitive abstraction in a person's mind. (authors' abstract) Astrahan76 Astrahan, M. M., et al. System R: Relational approach to database management. ACM TODS 1, 2 (June 1976). Atkinson78a Atkinson, M., Martin, J. and Jordon, M. A uniform, modular structure for databases and programs. CSR-33-78, U. Edinburgh, Oct. 1978. This paper discusses the relationship of a modular database description and the modular structure of programs over the database. It presents an approach to the design of large software systems that store data in a set of shared databases. The objective is to minimize the difference in treatment between data and programs. The authors investigate the relationship between abstract data types and database systems. The result is a modular structure in the data description which is refined in parallel with the program development. The approach is aimed at a top-down design of a database. The authors claim improvements for design quality, consistency, and completeness. Atkinson78b Atkinson, M. P. Programming languages and data bases. In VLDB78. Research work in programming languages and database systems is combating the same problems of scale, change, and complexity. This paper looks at the present difficulties of relating persistent data with changing programs. It argues that there is a discontinuity between the data types and programming structures in existing programming languages and database systems. This discontinuity results in problems of programming methodology, translation, algorithm design, and implementation. The paper illustrates this discontinuity at the database interface by means of examples. The author proposes the need for new language primitives to encapsulate database concepts. Several such primitives are examined. It is suggested that these primitives could simplify the use of databases by programmers. ALGOL68 is used as a base language which is extended to accommodate high level access to databases via the mode control. The author proposes that all data be treated alike but that some data can be declared as persistent. He proposes that research in this direction should look for the simplest set of primitives to achieve the integration of databases and programming languages. Atkinson78c Atkinson, R. R., Liskov, B. H. and Scheifler, R. W. Aspects of implementing CLU. Proc. 1978 ACM Annual Conf., Washington, D. C., Dec. 1978. CLU is a programming language/system that supports procedural, data, and control abstractions. This paper reviews linguistic mechanisms in CLU which support structured exception handling, iteration over abstract objects, and parameterized abstractions. The implementation of these features is also discussed. In CLU, a routine (procedure or iterator) can be programmed to terminate normally by executing a return statement or terminate in an exceptional condition by executing a signal statement. The exception is handled by the calling routine which must provide a handler a list of exceptions and code to handle them. If an exception has no appropriate action associated, a failure exception is raised. Iterators, a type of control abstraction, permit iteration over a collection of data items without knowing how they are obtained. A for statement is used to generate items one at a time and maintain the current state of the collection while routines use the current item. Procedures, iterators, and clusters can all be parameterized. This supports abstraction by permitting one module declaration to be used for a class of related abstractions. Parameters are limited to a few types, however, size parameters are not needed since CLU objects can change size dynamically. Although the module does not know what the actual parameters will be, information about operations on the actual type may have to be provided in a where clause. Bachman77 Bachman, C. W. and Daya, M. The role concept in data models. In VLDB77. The authors present a new data model which is a direct extension of the network model, but is claimed to be a complete conceputal data model. The basic premise of the model is that database applications are collections of entities that are characterized by their behavior. An entity is defined as having a certain structure (as represented in traditional record types) and may play one or more roles. For example, a person or a corporation may be entities while a stockholder and a customer are roles that those entities may assume. The authors introduce role-segments and operations over roles to extend the CODASYL system to support roles. It is argued that the role model supports meta entities that are not supported in other models and therefore the role model is a good basis for conceptual schemas. The role model provides solutions to existing CODASYL problems: multiple member set types can be expressed using sharable member roles, alternate owner set types can be expressed using sharable owner roles, recursive and "sometimes" sets are expressible. The authors claim that the role model will: facilitate schema mapping and the movement of data throughout an information system; provide greater semantic (integrity) power; and be compatible with high level programming languages. The main points of the paper (in terms of data abstraction) are: emphasis on behavioral properties, inclusion of behavior in the data model and schema; semantic integrity; improved application semantics; the concept of "sub-entity" or shared roles; and the need for integrating data models with high level programming languages. Bachman78a Bachman, C. W. and Daya, M. Additional comments on the role model. Honeywell Information Systems Inc., Billerica, Mass., May 1978. Bachman78b Bachman, C. W. and Daya, M. The database manipulation primitives of the role model. Honeywell Information Systems Inc., Billerica, Mass., Oct. 1978. Badal79 Badal, D. Z. and Popek, G. J. Cost and performance analysis of semantic integrity validation methods. In SIGMOD79. Baker79 Baker, A.L. and Zweben, S.H. The use of software science in evaluating modularity concepts. IEEE Trans. Soft. Eng. SE-5, 2 (March 1979). Baldissera79 Baldissera, C., Ceri, S., Pelagatti, G., and Bracchi, G. Interactive specification and formal verification of user's views in database design. In VLDB79. Among the different phases of the database design process, the phase of modelling user's views has a particular relevance. This paper describes an interactive methodology for designing the views starting from the elementary sentences that specify the requirements of the application. The methodology generates a canonical representation, and provides verification algorithms for detecting inconsistencies, redundancies and ambiguities, and for restructuring and optimizing the model. (authors' abstract). Balzer67 Balzer, R.M. Dataless programming. Proc. 1967 FJCC, pp. 535-544. Balzer 73 Balzer, R.M. A global view of automatic programming. Proc International Joint Conf. on AI, 1973. Balzer76 Balzer, R.M., Goldman, N. and Wile, D. On the transformational approach to programming. In PSE76. This paper discusses various approaches to programming, it defines and highlights Transformational Implementation. It then examines the basic causes of software problems and their resolution with the Transformational Implementation approach. Finally, an example illustrating the approach is given. (authors' abstract) Balzer78 Balzer, R.M., Goldman, N. and Wile, D. Informality in program specifications. IEEE Trans. on Software Engineering SE-4, 2(March 1978). This paper is concerned with the need for computer-based tools which help designers formulate formal process-oriented specifications. It first determines some attributes of a suitable process-oriented specification language, then examines the reasons why specifications would still be difficult to write in such a language in the absence of formulation tools. The key to overcoming these difficulties seems to be the careful introduction of informality based on partial, rather than complete, descriptions and the use of a computer-based tool that uses context extensively to complete these descriptions during the process of constructing a well-formed specification. Some results obtained by a running prototype of such a computer-based tool on a few informal example specifications are presented and, finally, some of the techniques used by this prototype system are discussed. (authors' abstract) Balzer 79a Balzer, R. and Goldman, N. Principles of good software specification and their implications for specification language. In PSRS79. This paper examines the uses of and criteria for software specifications, which are then used to develop design principles for "good" specifications. These principles, in turn, imply a number of requirements for specification languages that strongly constrain the set of adequate specification languages and identify the need for several capabilities that are novel in the programming language area. The constraints imply the need for an ultra-high-level language which combines the database concept of a global data model containing alternate viewpoints with the control structures of programming languages. The eight design principles are: 1) separate functionality from implementation; 2) process-oriented systems specification language; 3) a specification must encompass the system containing the software; 4) a specification must encompass the environment in which the system operates; 5) a system specification must be a cognitive model; 6) a specification must be operational; 7) a system specification must be tolerant of incompleteness and must be augmentable; 8) a specification must be localized and loosely coupled. The resulting 17 implications for specification languages include: a global model; a high level relational database; uniform data specification; global database with inference; descriptive, historical, and future references; demons; logical aggregation; and the elimination of variables. Balzer79b Balzer,R. An implementation methodology for semantic data base models. In Chen79. The Data Base community faces the same software crisis as the rest of the programming community as the gap between conceptual semantic data base models, such as Entity-Relationsip models, and the underlying physical representation of these data base models rapidly widens. This trend is expected to continue as the semantic models become increasingly abstract and as more sophisticated concrete data structures and search techniques are utilized. Among the various approaches to resolving the software problem, one seems particularly relevant to the data base community. Its relevance arises from the fact that the language with which it deals includes semantic data models. This particular approach is based on a more general methodology for systematically transforming conceptual specifications into efficient implementations that are guaranteed to be valid and for easily maintaining these implementations. This paper describes this general implementation methodology, its specific application to a specification language which spans semantic data models, an example of the implementation of a specification in this language, and the extension of the approach required for data base applications. (author's abstract) Bartussek77 Bartussek, W. and Parnas, D. Using traces to write abstract specifications for software modules. UNC Report 77-012, University of North Carolina at Chapel Hill, Dec. 1977. must meet. A specification for a software module is a statement of the requirements that the final programs |