SDM is a high-level semantics-based database description and structuring formalism (database model) for databases. This database model is designed to capture more of the meaning of an application environment than is possible with contemporary database models. An SDM specification describes a database in terms of the kinds of entities that exist in the application environment, the classifications and groupings of those entities, and the structural interconnections among them. SDM provides a collection of high-level modeling primitives to capture the semantics of an application environment. By accommodating derived information in a database structural specification, SDM allows the same information to be viewed in several ways; this makes it possible to directly accommodate the variety of needs and processing requirements typically present in database applications. The design of the present SDM is based on our experience in using a preliminary version of it. SDM is designed to enhance the effectiveness and usability of database systems. An SDM database description can serve as a formal specification and documentation tool for a database; it can provide a basis for supporting a variety of powerful user interface facilities, it can serve as a conceptual database model in the database design process; and, it can be used as the database model for a new kind of database management system.

DIAL is a problem-oriented and high-level programming language oriented towards database applications. It integrates into a unified framework database primitives and computational facilities, so that an application programmer will deal with a single coherent language. The design of DIAL is based on the premise that in order to have a meaningful impact on the construction of application software, a database programming language should eschew generality and focus on what is unique about the application domain in question. To that end, DIAL seeks to embody features that naturally express the most common and frequently recurring patterns encountered in database applications programs.A number of its features distinguish DIAL from other contemporary related efforts. Data description plays a primary role in DIAL, in that a substantial amount of application semantics is expressed in the database schema rather than in procedure definitions; to achieve this end, DIAL employs a higher-level data model (the SDM) as its data description mechanism. Facilities for conducting user-system dialogues are also embedded in the language. Specialized control structures are provided to allow for succinct and direct expression of the algorithmic structure of procedures that utilize the database. High-level mechanisms (called controllers) are used to specify an application system's required behavior in the face of multiple concurrent users and aborted transactions.DIAL has been applied to two realistic and substantial systems, a purchasing application and a job-shop scheduler. Continued validation studies of the language are underway, as are an implementation effort and the design of an allied program development system.

This paper presents the reliability mechanisms of SDD-1, a prototype distributed database system being developed by the Computer Corporation of America. Reliability algorithms in SDD-1 center around the concept of the Reliable Network (RelNet). The RelNet is a communications medium incorporating facilities for site status monitoring, event timestamping, multiply buffered message delivery, and the atomic control of distributed transactions. This paper is one of a series of companion papers on SDD-1 [3, 4, 6, 13].

The declining cost of computer hardware and the increasing data processing needs of geographically dispersed organizations have led to substantial interest in distributed data management. SDD-1 is a distributed database management system currently being developed by Computer Corporation of America. Users interact with SDD-1 precisely as if it were a nondistributed database system because SDD-1 handles all issues arising from the distribution of data. These issues include distributed concurrency control, distributed query processing, resiliency to component failure, and distributed directory management. This paper presents an overview of the SDD-1 design and its solutions to the above problems. This paper is the first of a series of companion papers on SDD-1 (Bernstein and Shipman [2], Bernstein et al. [4], and Hammer and Shipman [14]).

One technique that is sometimes employed to enhance the performance of a database management system is known as attribute partitioning. This is the process of dividing the attributes of a file into separately stored subfiles. By storing together those attributes that are frequently requested together by transactions, and by separating those that are not, attribute partitioning can reduce the number of pages that are transferred from secondary storage to primary memory in the processing of a transaction.The goal of this work is to design mechanisms that can automatically select a near-optimal attribute partition of a file's attributes, based on the usage pattern of the file and on the characteristics of the data in the file. The approach taken to this problem is based on the use of an accurate partition evaluator and of a heuristic that guides a search through the large space of possible partitions. The heuristics propose a small set of promising partitions to submit for detailed analysis. The evaluator assigns a figure of merit to any proposed partition that reflects the cost that would be incurred in processing the transactions in the usage pattern if the file were partitioned in the proposed way.We have implemented an evaluator for a particular model database system and have developed a heuristic search technique. A series of experiments has demonstrated the accuracy and efficiency of this heuristic.

Conventional data models are not satisfactory for modelling data base application systems. The features that they provide are too low level and representational to allow the semantics of a data base to be directly expressed in the schema. The semantic data model (SDM) has been designed as a natural application modelling mechanism that can capture and express the structure of an application environment. The features of the SDM correspond to the principal intensional structures naturally occurring in contemporary data base applications. Furthermore, facilities for expressing derived (redundant) information are an essential part of the SDM; derived information is as prominent in an SDM schema as is primitive data. The SDM is designed to enhance the effectiveness and usability of computerized data bases. It can serve as a formal specification and documentation mechanism for a data base, can support a variety of powerful user interface facilities, and can be used as a tool in the data base design process.

A principal impediment to the use of declarative assertions for monitoring the state of a dynamic database is the high cost of conventional implementation techniques for such a facility. This paper presents a means of efficiently detecting violations of assertions caused by updates to a database. Our technique is based on the premise that the structure of updates to a database can generally be anticipated, and that an analysis of the potential effect that an update may have on an assertion can enable the assertion to be efficiently tested when the update is performed.This analysis is performed by a compile-time assertion processor; for each type of update operation defined on the database, the assertion processor synthesizes a procedure that will be used to evaluate a set of given assertions whenever an operation of the given type is performed on the database. For each assertion and operation, the assertion processor performs a detailed logical analysis, called perturbation analysis, of the effect that the operation may have on the assertion. Perturbation analysis identifies conditions that can be efficiently tested at run-time (when an operation of the given type is performed) and that minimize the extent to which the assertion must be fully reevaluated; the identified conditions also enable the assertion to be tested before the update is actually performed, thereby avoiding the need for expensive back-out procedures in the case that the assertion is found to be violated. Based on this analysis, the assertion processor generates a set of alternative efficient means of determining whether or not execution of the operation causes the assertion to be violated. A database transaction processor, which estimates the performance cost of each of the alternatives in the context of the physical representation and access methods of the database, can then be used to identify the least expensive means of testing the assertion.This work has been done in the particular context of semantic integrity assertions, but it readily extends to related problems of database monitoring. The efficiency of testing that can be achieved through the use of our assertion processing technique in comparable with that attainable through the use of hand-coded procedures. The technique therefore supports all the advantages of the declarative approach to database assertion-monitoring, while retaining the level of efficiency that is usually associated with procedural methods.

We address the problem of automatically adjusting the physical organization of a data base to optimize its performance as its access requirements change. We describe the principles of the automatic index selection facility of a prototype self-adaptive data base management system that is currently under development. The importance of accurate usage model acquisition and data characteristics estimation is stressed. The statistics gathering mechanisms that are being incorporated into our prototype system are discussed. Exponential smoothing techniques are used for averaging statistics observed over different periods of time in order to predict future characteristics. An heuristic algorithm for selecting indices to match projected access requirements is presented. The cost model on which the decision procedure is based is flexible enough to incorporate the overhead costs of index creation, index storage and application program recompilation.

As a model of some aspect(s) of the real world, the data in a data base must be accurate. In the context of a relational data base system, a facility to allow the expression and enforcement of a set of semantic integrity constraints is discussed. Semantic integrity constraints may describe properties of and relationships between data objects (in a relational data base) that are to hold (state snapshot constraints). Constraints may also place limitations on permissible data base operations (state transition constraints).

For some time, it has been recognized that left-to-right deterministic top-down parsing has a number of features to recommend it. The logic of such a parser is easily expressed as a one-state pushdown machine, and very flexible translations can readily be performed in conjunction with top-down processing. The major difficulty with this style of parsing is that there are relatively few grammars which satisfy the rather restrictive requirements to admit of top-down parsing (the LL(k) grammars), in comparsion with grammars that can be parsed deterministically bottom-up (the LR(k) grammars). There has been some research along the lines of trying to apply transformations to non-LL(k) grammars in order to convert them into equivalent LL(k) form [1,2,3]; the most successful approach has been that of Rosenkrantz and Lewis [4]. They define class of grammars, the LC(k) grammars, which can be parsed in a mixed hybrid of top-down bottom-up techniques; this class strictly includes the LL(k) grammars, as well as many interesting but non-LL(k) grammars. They then provide a deterministic algorithm for converting any LC(k) grammar into an equivalent LL(k) grammar.