An algebraic framework for the study of recursion has been developed. For immediate linear recursion, a Horn clause is represented by a relational algebra operator. It is shown that the set of all such operators forms a closed semiring. In this formalism, query answering corresponds to solving a linear equation. For the first time, the query answer is able to be expressed in an explicit algebraic form within an algebraic structure. The manipulative power thus afforded has several implications on the implementation of recursive query processing algorithms. Several possible decompositions of a given operator are presented that improve the performance of the algorithms, as well as several transformations that give the ability to take into account any selections or projections that are present in a givin query. In addition, it is shown that mutual linear recursion can also be studied within a closed semiring, by using relation vectors and operator matrices. Regarding nonlinear recursion, it is first shown that Horn clauses always give rise to multilinear recursion, which can always be reduced to bilinear recursion. Bilinear recursion is then shown to form a nonassociative closed semiring. Finally, several sufficient and necessary-and-sufficient conditions for bilinear recursion to be equivalent to a linear one of a specific form are given. One of the sufficient conditions is derived by embedding to bilinear recursion in an algebra.

Query optimizers of future database management systems are likely to face large access plan spaces in their task. Exhaustively searching such access plan spaces is unacceptable. We propose a query optimization algorithm based on simulated annealing, which is a probabilistic hill climbing algorithm. We show the specific formulation of the algorithm for the case of optimizing complex non-recursive queries that arise in the study of linear recursion. The query answer is explicitly represented and manipulated within the closed semiring of linear relational operators. The optimization algorithm is applied to a state space that is constructed from the equivalent algebraic forms of the query answer. A prototype of the simulated annealing algorithm has been built and few experiments have been performed for a limited class of relational operators. Our initial experience is that, in general, the algorithm converges to processing strategies that are very close to the optimal. Moreover, the traditional processing strategies (e.g., the semi-naive evaluation) have been found to be, in general, suboptimal.

A state transition model for the optimization of query processing in a distributed database system is presented. The problem is parameterized by means of a state describing the amount of processing that has been performed at each site where the database is located. A state transition occurs each time a new join or semijoin is executed. Dynamic programming is used to compute recursively the costs of the states and the globally optimal solution, taking into account communication and local processing costs. The state transition model is general enough to account for the possibility of parallel processing among the various sites, as well as for redundancy in the database. The model also permits significant reductions of the necessary computations by taking advantage of simple additivity and site-uniformity properties of a cost model, and of clever strategies that improve on the basic dynamic programming algorithm.

In this paper we treat the problem of subdividing a database and allocating the fragments to the sites in a distributed database system in order to maximize non-duplicative parallelism. Our goal is to establish a conceptual framework for distributing data without being committed to specific cost models.We introduce the concept of "local sufficiency" as a measure of parallelism, and show how certain classes of queries lead naturally to irredundant partitions of a database that are locally sufficient. For classes of queries for which no irredundant distribution is locally sufficient, we offer ways to introduce redundancy in achieving local sufficiency

We present a conceptual framework in which a database's intra- and interrecord set access requirements are specified as a constrained assignment of abstract characteristics (“evaluated,” “indexed,” “clustered,” “well-placed”) to logical access paths. We derive a physical schema by choosing an available storage structure that most closely provides the desired access characteristics. We use explicit replication of schema objects to reduce the access cost along certain paths, and analyze the trade-offs between increased update overhead and improved retrieval access. Finally, we given an algorithm to select storage structures for a CODASYL 78 DBTG schema, given its access requirements specification.

In this paper an approach to processing distributed queries that makes explicit use of redundant data is proposed. The basic idea is to focus on the dynamics of materialization, defined as the collection of data and partial results available for processing at any given time, as query processing proceeds. In this framework the role of data redudancy in maximizing parallelism and minimizing data movement is clarified. What results is not only the discovery of new algorithms but an improved framework for their evaluation.

A “decompilation” algorithm is developed to transform a program written with the procedural operations of CODASYL DML into one which interacts with a relational system via a nonprocedural query specification. An Access Path Model is introduced to interpret the semantic accesses performed by the program. Data flow analysis is used to determine how FIND operations implement semantic accesses. A sequence of these is mapped into a relational query and embedded into the original program. The class of programs for which the algorithm succeeds is characterized.

There are numerous situations in which a database cannot provide a precise answer to some of the questions that are posed. Sources of imprecision vary and include examples such as recording errors, incompatible scaling, and obsolete data. In many such situations, considerable prior information concerning the imprecision exists and can be exploited to provide valuable information for queries to which no exact answer can be given. The objective of this paper is to provide a framework for doing so.

Because it is more intuitively understandable than the previously existing convolution algorithms, Mean Value Analysis (MVA) has gained great popularity as an exact solution technique for separable queueing networks. However, the derivations of MVA presented to date apply only to closed queueing network models. Additionally, the problem of the storage requirement of MVA has not been dealt with satisfactorily. In this paper we address both these problems, presenting MVA solutions for open and mixed load independent networks, and a storage maintenance technique that we postulate is the minimum possible of any “reasonable” MVA technique.

In an earlier paper, recursive formulas for the causal filtering of two-dimensional random fields were developed. "Causality" in two dimensions is not a physical constraint but rather an artifact introduced to generate recursion, which in turn is motivated by computational efficiency. The earlier results are extended here in order to derive some recursive formulas for "smoothing" estimators which use all the data rather than just the data in the "past".

This paper describes the techniques used to optimize relational queries in the SDD-1 distributed database system. Queries are submitted to SDD-1 in a high-level procedural language called Datalanguage. Optimization begins by translating each Datalanguage query into a relational calculus form called an envelope , which is essentially an aggregate-free QUEL query. This paper is primarily concerned with the optimization of envelopes. Envelopes are processed in two phases. The first phase executes relational operations at various sites of the distributed database in order to delimit a subset of the database that contains all data relevant to the envelope. This subset is called a reduction of the database. The second phase transmits the reduction to one designated site, and the query is executed locally at that site. The critical optimization problem is to perform the reduction phase efficiently. Success depends on designing a good repertoire of operators to use during this phase, and an effective algorithm for deciding which of these operators to use in processing a given envelope against a given database. The principal reduction operator that we employ is called a semijoin . In this paper we define the semijoin operator, explain why semijoin is an effective reduction operator, and present an algorithm that constructs a cost-effective program of semijoins, given an envelope and a database.

Design and Access Path Data Models are presented to form an integrated framework for logical and physical database design in a heterogeneous database environment. This paper focuses on the physical design process. First, a physical design is specified in terms of general properties of access paths, independent of implementation details. Then, a design is realized by mapping the specification into the storage structures of a particular database system. Algorithms for assigning the properties to logical access paths and for realizing a CODASYL 78 DBTG schema are given.

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]).

In this paper we present a new algorithm for retrieving and updating data from a distributed relational data base. Within such a data base, any number of relations can be distributed over any number of sites. Moreover, a user supplied distribution criteria can optionally be used to specify what site a tuple belongs to.The algorithm is an efficient way to process any query by "breaking" the qualification into separate "pieces" using a few simple heuristics. The cost criteria considered are minimum response time and minimum communications traffic. In addition, the algorithm can optimize separately for two models of a communication network representing respectively ARPANET and ETHERNET like networks. This algorithm is being implemented as part of the INGRES data base system.

The causal estimation of a two-parameter Gaussian random field in the presence of an additive, independent, white Gaussian noise is studied. The dynamics of this random field are modeled by partial differential equations from which the recursive filtering equations and the generalized Riccati equation are derived. A specific example is solved in detail.

The one-sided (or line-by-line) recursive filtering problem for a two-parameter Gaussian random signal in additive white Gaussian noise is considered. For a reasonably large class of models for the signal dynamics, both the filtering equation and the generalized Riccati equation explicitly obtained. As an example, the Riccati equation is solved to give the filter gain in a time-in-variant case and is compared with the infinite-time limiting solution to the Wiener filter solution obtained by spectral factorization techniques.

The currently operational (March 1976) version of the INGRES database management system is described. This multiuser system gives a relational view of data, supports two high level nonprocedural data sublanguages, and runs as a collection of user processes on top of the UNIX operating system for Digital Equipment Corporation PDP 11/40, 11/45, and 11/70 computers. Emphasis is on the design decisions and tradeoffs related to (1) structuring the system into processes, (2) embedding one command language in a general purpose programming language, (3) the algorithms implemented to process interactions, (4) the access methods implemented, (5) the concurrency and recovery control currently provided, and (6) the data structures used for system catalogs and the role of the database administrator. Also discussed are (1) support for integrity constraints (which is only partly operational), (2) the not yet supported features concerning views and protection, and (3) future plans concerning the system.

Strategy for processing multivariable queries in the database management system INGRES is considered. The general procedure is to decompose the query into a sequence of one-variable queries by alternating between (a) reduction: breaking off components of the query which are joined to it by a single variable, and (b) tuple substitution: substituting for one of the variables a tuple at a time. Algorithms for reduction and for choosing the variable to be substituted are given. In most cases the latter decision depends on estimation of costs; heuristic procedures for making such estimates are outlined.

Application of sequential testing to a Markovian model of cardiac rhythm intervals is investigated. An approximate expression for the expected number of observations is obtained for Wald's sequential test under dependent sampling. The interclass separability of three selected cardiac rhythms is then determined, and the results are used to evaluate the feasibility of an on-line implementation of a sequential classification procedure in a coronary care ward.

A class of recursive filtering problems for random fields with a two-dimensional parameter is considered. After a brief introduction of two-parameter stochastic calculus, a class of Markovian random fields generated by stochastic integral equations is defined and considered. It is then shown that the problem of estimating such a Markovian field in additive white Gaussian noise can be reduced to a recursive formalism. If the random field is itself Gaussian, the recursive formalism reduces to a finite set of stochastic integral equations involving the conditional mean and covariance.

This paper is concerned with the detection of a random signal in white Gaussian noise when both the signal and the noise are two-dimensional random fields. The principal result is the derivation of a recursive formula for the likelihood ratio relating it to certain conditional moments of the signal. It is also shown that, except for some relatively uninteresting cases, a simple exponential formula for the likelihood ratio, such as one has in one dimension, is not possible.

This paper surveys some of the literature on applications of stochastic processes published during the period 1968-1972. This survey highlights recent developments in the application of martingale theory. Because this subject is relatively new to the engineering community, a tutorial exposition of some aspects of the martingale calculus is also included.

The multidimensional demodulation problem is considered from the point of view of statistical estimation theory and a posteriori most probable signal estimates are derived. Correlated signals and noises are treated. This formulation yields a set of two matrix integral equations which must be solved for the optimum estimates. For amplitude modulation, the problem reduces to that of finding a set of time varying filters which are, again, solutions to a matrix integral equation. Special cases such as two-receiver systems, quadrature modulation, and single-sideband have particularly simple representations and are considered in some detail.