Modeling and analysis of data base organization: The doubly chained tree structure

The doubly-chained tree data base (file) organization is modeled and analyzed to obtain estimates of average access time (read-only) and total storage requirements. Macroscopic expressions are derived relating such performance measures to characteristic parameters of the specific data base, query or transaction traffic, storage devices and particular doubly-chained storage structure chosen. Important and generally applicable implementation-oriented aspects are considered. The model forms part of a prototype system for automatically analyzing and evaluating various data base organizations. The methodology and system are briefly outlined. Results for the doubly-chained structure using several real data bases are summarized, showing the rather large variability of performance as a function of both data base contents and complexity of queries.     

An approach to testing specifications

An approach to testing the consistency of specifications is explored, which is applicable to the design validation of communication protocols and other cases of step-wise refinement. In this approach, a testing module compares a trace of interactions obtained from an execution of the refined specification (e.g., the protocol specification) with the reference specification (e.g., the communication service specification). Nondeterminism in reference specifications presents certain problems. Using an extended finite state transition model for the specifications, a strategy for limiting the amount of nondeterminacy is presented. An automated method for constructing a testing module for a given reference specification is discussed. Experience with the application of this testing approach to the design of a transport protocol and a distributed mutual exclusion algorithm is described.     

Pattern matching and pattern-directed invocation in systems programming languages

Pattern recognition systems in the artificial intelligence field have been based on the assumption that components of the system should be invoked not by directly calling them, but by running data across their sensors and having the invocation take place when a defined pattern is found. Most systems programming, however, has taken a completely different route; the emphasis there is on structures of execution and data types. A new approach to systems programming languages where a bridge is made between structure and pattern-directed invocation is described. The syntax of pattern-directed invocation, along with the semantics of a support structure for message receiving and sending necessary for pattern-directed invocation of routines is presented. Finally, some conclusions are made about pattern-directed invocation, and further areas of work are stated.     

The functional life cycle model and its automation: USE.IT

Recently there has been an accelerated awareness of the urgent need for effective system development tools and techniques. Towards this end attempts have been made to develop standard languages for programming and standard techniques for the front end of the development process. Further, there has even been talk of integrating the various processes within a system life cycle. Our thesis, here, is that although these are steps leading in the right direction, they are simply not enough. What we suggest is needed, rather, is a totally new life cycle model; it is based on pure functional needs. This is in contrast to the “event” driven model that has been forced into being based on constraints which are often unnecessary, wasteful, and error prone. The functional model, itself formally defined, not only includes formal techniques for defining the front end, but it also includes techniques which integrate by means of formal methods and automation that front end to the rest of the life cycle of a system. A functional life cycle model has been defined. USE.IT, an implementation of this model, provides for an integrated and automated development process of a system. We discuss, here, the HOS functional model, USE.IT, and the implications of their use.     

Interoperability through effective information exchange standards

The objective of this paper is to develop an awareness of the existence of, the need for, and the emphasis currently being placed on Interoperability, with an understanding of the derivation of Interoperability Standards to make effective use of advancing hardware and software system technology. To accomplish this objective, the paper discusses the definition of specific terms related to Interoperability, some of the Interoperability problem areas, a walk through of current standards derivations methodology being used in the Program, and consideration of the standards validation process. The paper also contains a brief analysis of lessons learned from past Interoperability programs and an assessment of how Interoperability considerations affect a participating project.     

The external structure: Experience with an automated module interconnection language

To study the problems of modifiable software, the Software Technology project has investigated approaches and methodologies that could improve modifiability. To test our approaches tools based on data abstraction—a design and programming language and a module interconnection language—were built and used. The incorporation of the module interconnection language into design altered the traditional model of system building. Introducing novices to our approach led to the formalization of new models of program design, development, and evaluation.     

Ada programming language standardization

The need for software management and standardization of programming languages used in military systems was first identified by DoD in 1975. DoD at that time supported many limited use languages for what are now called embedded computer applications. This diversity of languages contributed to high software costs. In November 1976, DoD first established seven approved , , , -J3, -J73, , -2, -1. Eventually the number of approved DoD languages may be reduced to three, Ada, , and . Ada was established as Military Standard 1815, on 10 December 1980. The ANSI standardization process for Ada is in progress. The Ada concept places restrictions on what may be called an Ada compiler. Compilers may not be called Ada compilers until they have passed validation tests. Up to 80% of software costs are incurred after the software has been put into service. Ada can promote a programming style that leads to maintainable software. It is in the program maintenance phase of the software life cycle where large savings will be achieved through the use of Ada.     

A model of the software development process

This paper presents a model of the programming process. The model has four parts. A resources model specifies how many useful man-months of design effort are available from project team members after subtracting the time required for learning and team communications. A system design model specifies how many man-months of effort are required to derive program module specifications, as a function of the number of team members, program size, and number of modules. A coding model specifies how many man-months of effort are required for coding, as a function of team, module, and program size. Finally, a checkout model specifies how many man-months are required for checkout as a function of program size, error detection and correction rates, and a design-complete factor. The model as a whole predicts that programmer productivity will decrease as project team size is increased and that project duration will first decrease and then increase as team size is increased. It also shows that productivity and project duration vary enormously as a function of project management factors, even when project complexity and programming staff competence are held constant.     

High-level debugging of distributed systems: The behavioral abstraction approach

Most extant debugging aids force their users to think about errors in programs from a low-level, unit-at-a-time perspective. Such a perspective is inadequate for debugging large complex systems, particularly distributed systems. In this paper, we present a high-level approach to debugging that offers an alternative to the traditional techniques. We describe a language, edl, developed to support this high-level approach to debugging and outline a set of tools that has been constructed to effect this approach. The paper includes an example illustrating the approach and discusses a number of problems encountered while developing these debugging tools.     

Measuring the quality of structured designs

The purpose of this study is to investigate the possibility of providing some useful measures to aid in the evaluation of software designs. Such measurements should allow some degree of predictability in estimating the quality of a coded software product based upon its design and should allow identification and correction of deficient designs prior to the coding phase, thus providing lower software development costs. The study involves the identification of a set of hypothesized measures of design quality and the collection of these measures from a set of designs for a software system developed in industry. In addition, the number of modifications made to the coded software that resulted from these designs was collected. A data analysis was performed to identify relationships between the measures of design quality and the number of modifications made to the coded programs. The results indicated that module coupling was an important factor in determing the quality of the resulting product. The design metrics accounted for roughly 50–60% of the variability in the modification data, which supports the findings of previous studies. Finally, the weaknesses of the study are identified and proposed improvements are suggested.     

Generalized path expressions: A high-level debugging mechanism

This paper introduces a modified version of path expressions called Path Rules which can be used as a debugging mechanism to monitor the dynamic behavior of a computation. Path rules have been implemented in a remote symbolic debugger running on the Three Rivers Computer Corporation PERQ computer under the Accent operating system.     

A method for the analysis of Gaussian-like clusters

In this paper we are concerned with the analysis of Gaussian-like point clusters in an n-dimensional space. The method described uses the directed fuzzy graph obtained from the points by linking every point to its neighbors and assigning a measure of the local point density to each node of the graph. Next, the tops of the fuzzy graph are found and a subset of them selected as cluster centers. The rest of the points are then classified based on the selected tops.     

Correct: A simulated text editor

This paper describes a project to write a simulator for the native mode text editor of one computer, which could be run on a different computer. This was done to give a user of both computers a common editing language. The method of design and construction is presented together with brief details of the syntax and semantics of the editing language.     

The softest program test system

This paper reviews the current status of both research and commercial testing systems, and addresses the features necessary for a commercial test system. These include test case specification, test data generation, testbed generation, program instrumentation, automatic test execution and validation, as well as dynamic analysis of control and data flow. Of particular value is the linking of the details of the test to the program specification by means of an assertion language. These and other features are then described within the contest of , an integrated system for testing Assembler, , and / 1 programs in a simulated test environment. This system is now being used to validate programs in a test laboratory.     

Data and reports: Contents design and users allocation

When a common information system should supply data in a batch processing mode to many various users, the systems analyst is faced with the problem of allocating data among various reports and reports among different users. The traditional approach to that problem is very unstructured. Such a problem is formulated here in a nonlinear binary programming model. Four alternative techniques of solving the model are presented, followed by an example. The main contribution is a systematic and analytic approach toward a major problem in information systems design.     

Guest editor's introduction: Tool and methodology evaluation

The first ACM Sigsoft-sponsored Software Engineering Symposium focused on the issue of evaluating the effectiveness of software engineering tools, techniques, methods, and environments. In this paper we overview and summarize a collection of symposium papers that collectively indicate the state of development in the area of tool and methodology evaluation.     

The new software documentation standard: Report on the joint logistic commanders joint policy coordinating group on computer resource management, computer software management subgroup, software workshop

Under the aegis of the Joint Logistics Commanders, the Computer Software Management Subgroup organized two workshops of combined industry and military personnel to review, revise, and recommend new standards for the acquisition and documentation of embedded computer systems. This paper describes the superset of documents which will be required under the new MIL-STD-SDS. The relationship of each document to the acquisition cycle, particularly the design reviews, and to each other, is emphasized.