Secondary storage adds the dimension of latency to memory organization. Programming structures, which seamlessly fuse secondary- and primary-memory data processing, are at a higher level than is conventional, and so simpler: data structures are based on bulk processing; programming language abstracts over looping. New abstractions give new ways of thinking and break old habits of programming. We illustrate these changes by integrating a number of areas hitherto thought separate and needing separate programming paradigms.

Tries offer text searches with costs which are independent of the size of the document being searched, and so are important for large documents requiring spelling checkers, case insensitivity, and limited approximate regular secondary storage. Approximate searches, in which the search pattern differs from the document by k substitutions, transpositions, insertions or deletions, have hitherto been carried out only at costs linear in the size of the document. We present a trie based method whose cost is independent of document size. Our experiments show that this new method significantly outperforms the nearest competitor for k=0 and k=1, which are arguably the most important cases. The linear cost (in k) of the other methods begins to catch up, for our small files, only at k=2. For larger files, complexity arguments indicate that tries will outperform the linear methods for larger values of k. The indexes combine suffixes and so are compact in storage. When the text itself does not need to be stored, as in a spelling checker, we even obtain negative overhead: 50% compression. We discuss a variety of applications and extensions, including best match (for spelling checkers), case insensitivity, and limited approximate regular expression matching.

The scoping of names in programming languages interacts adversely with first-class procedures if these carry their closures with them. In this paper it is suggested that, if scoping and privacy are regarded as separate concepts, it would provide a partial solution to the problem.

Scalars, arrays, and records, together with associated operations and syntax, have been introduced as special cases of relations into the relational programming system, relix. This permits all of these data types, as well as relations, to be stored persistently. The requirement in most languages that array elements and record fields can be assigned to leads in this case to the general implementation of QT-selectors as l-expressions, with, in particular, systematic interpretations of assignment to projections and selections of relations. The authors discuss the principles and the implementation of this extension to the relational algebra. They take advantage of the very specialized syntax of array access to build a tuned access method, using B-trees and Z-order. The performance results show the advantage of this implementation over the slower implementation required for general QT-selectors.>

Abstract We have built on the U.C.S.D. P‐system (running on an IBM Personal Computer) a relational algebra processor, MRDS/FS, which is extremely powerful and which supports a functional syntax for the programmer‐user. The relational algebra is provided in the extended operators μ‐join, σ‐join, project and select. The domain algebra is fully implemented for the first time, giving operations on attributes: arithmetic, logic, comparison and four different categories of aggregation of these. A strictly functional syntax is provided, permitting user‐defined functions using the relational and domain algebras as primitive operations. An interactive editor permits the creation, copying and changing of both relations and user‐defined functions.

By interleaving the bits of the binary representations of the attribute values in a tuple, an integer corresponding to the tuple is created. A set of these integers represents a relation. The usual ordering of these integers corresponds to an ordering of multidimensional data that allows the use of conventional file organizations, such as Btrees, in the efficient processing of multidimensional queries (e.g. range queries). The class of data structures generated by this scheme includes a type of kd tree whose balance can be efficiently maintained, a multidimensional Btree which is simpler than previously proposed generalizations, and some previously reported data structures for range searching. All of the data structures in this class also support the efficient implementation of the set operations.

A top-down approach is proposed for cost analysis for database and information system design. General principles are given which allow the analyst either to estimate rapidly the costs of a wide variety of alternatives or to investigate fewer possibilities in great detail. Techniques are developed which can be used at any level of the iterative design process - at the early stages or at the detailed phase of specific design. The paper applies the methods to the basic categories of file cost at the simpler levels of analysis and refers to the literature for more sophisticated analyses, which can be done within the framework provided here. Among the specific results developed are: the extension of a widely-used hit ratio formula to non-uniform usage distribution; the introduction of the "distribution of depths" for serial accesses; a general activity analysis and a volatility analysis for indexed sequential files.