Abstract syntax trees were devised as a compact alternative to parse trees, because parse trees are known to require excessive amounts of storage to represent parsed programs. However, the savings that abstract syntax trees actually achieve have never been precisely described because the necessary analysis has been missing. Without it, one can only measure particular cases that may not adequately represent all the possible behaviors. We introduce a data structure, production trees, that are more compact than either abstract syntax trees or parse trees. Further, we develop the necessary analysis to characterize the storage requirements of parse trees, abstract syntax trees, and production trees and relate the size of all three to the size of the program's text. The analysis yields the parameters needed to characterize these storage behaviors over their entire range. We flesh out the analysis by measuring these parameters for a sample of “C” programs. For these programs, production trees were from 1/15 to 1/23 the size of the corresponding parse tree, l/2.7 the size of a (minimal) abstract syntax tree, and averaged only 2.83 times the size of the program text.

Office-by-Example (OBE) is an integrated office information system that has been under development at IBM Research. OBE, an extension of Query-by-Example, supports various office features such as database tables, word processing, electronic mail, graphics, images, and so forth. These seemingly heterogeneous features are integrated through a language feature called example elements . Applications involving example elements are processed by the database manager, an integrated part of the OBE system. In this paper we describe the facilities and architecture of the OBE system and discuss the techniques for integrating heterogeneous objects.

Conventional database design techniques rely heavily on the designer's skill and experience, which are neither efficient nor effective for large, realistic design problems. A computer design aid can help by storing many design parameters and performing simple preprocessing before design decisions are made. In this paper, we report on the development of such a system.

This paper presents a semantic model and processing language upon which a logical database design tool can be based. The semantic model is invariant with respect to the placement of data items into records or relations. The processing language is based on the semantic model, so processing specifications are also invariant to these decisions. This allows a designer to specify the processing and semantics of small parts of a database (local views), and then to integrate these views into a global model of the database. We present operations to manipulate the model and processing specifications during the integration process. An algorithm, using these operations is given to perform the integration process.