Most algorithms for determining query processing strategies in distributed databases are static in nature; that is, the strategy is completely determined on the basis of a priori estimates of the size of intermediate results, and it remains unchanged throughout its execution. The static approach may be far from optimal because it denies the opportunity to reschedule operations if size estimates are found to be inaccurate. Adaptive query execution may be used to alleviate this problem. A low overhead delay method is proposed to decide when to correct a strategy. Sampling is used to estimate the size of relations, and alternative heuristic strategies prepared in a background mode are used to decide when to correct. Evaluation using a model of a distributed database indicates that the heuristic strategies are near optimal. Moreover, it also suggests that it is usually correct to abort creation of an intermediate relation which is much larger than predicted.>

A strategy to process a distributed query is formed using estimates of intermediate result sizes and delays due to network data transfer and CPU processing. Strategy execution is monitored, and corrected if observed parameter values differ substantially from their estimates. This paper presents and compares two methods which can be used to decide when to correct a strategy. In the reformulation method, a new strategy is formulated following each relational operation. The threshold method, on the other hand, is based on the fact that some intermediate results are more ‘critical’ than others. The query-processing strategy is represented as a network of activities, and the critical path method is used to determine threshold values for intermediate results. If an intermediate result is delayed beyond its threshold value, the strategy is corrected. The reformulation and threshold methods are evaluated on a test-bed of queries for a modelled application of a distributed database.

Several issues that arise in processing distributed queries dynamically are investigated. The effect of inaccuracies in estimation on the cost/delay of strategies is considered. Two methods than can be used to decide whether or not to correct a strategy are examined and compared. The problem of aborting operations in process is also examined, i.e. whether operations which are in progress should be aborted or whether they should be permitted to complete.>

The authors examine objectives, or measures of cost, which can be used in optimizing queries in a distributed database (DDB). They include the delay and dollar cost due to the network data transfer, CPU processing or a combination of both, and cost measures in terms of the size of partial results. These measures are used in distributed query processing modeling on a testbed of queries to examine the effect of choosing one measure of cost in optimizing strategies on their cost expressed in other measures and the cost of strategies generated by a two-phased approach. Results indicate that best strategies are generated when optimization considers cost measured in terms of both CPU processing and a network data transfer. They also confirm that the two-phased optimization yields close to optimal strategies.>

This paper presents the basic architecture and performance of a mobile radio multiaccess voice/data system. Natural pauses in conversational speech allow bandwidth saving through interleaving of data packets and talkspurts from different voice sources. A speech detector designed specifically for the mobile environment is presented. Blocking and delay performance of the multiaccess uplink is analyzed for voice traffic, assuming no traffic effects from the low priority data packets. Performance results from simulation are then presented for two downlink strategies in a two-hop virtual circuit in which a base station acts as a relay. The results verify also that the uplink analysis is valid for low voice traffic. For the data traffic, simulation results are presented in terms of data packet transmission delay and probability of collision with talkspurts. The results indicate that data flow may be limited by the collision factor. This work concludes that relative to conventional radio telephoning in which two channels are dedicated to each transmitter/receiver pair, a bandwidth reduction of 30-35 percent can be achieved.

Access control to shared files in a distributed computing environment requires an efficient method of allocating file resources with local and remote user processes. While software controlled access methods are convenient from the user's point of view, they give rise to serious operational problems such as job interferences (deadlock situations) and critical race conditions. Two software controlled access schemes, one centralized and one distributed are described in this paper. A basic set of protocols is derived to illustrate the implementation aspects of each scheme in a given network environment. The two approaches are then evaluated in the light of several performance criteria.

The problems of file allocation and capacity assignment in a fixed topology distributed computer network are examined. These two aspects of the design are tightly coupled by means of an average message delay constraint. The objective is to allocate copies of information files to network nodes and capacities to network links so that a minimum cost is achieved subject to network delay and file availability constraints. A model for solving the problem is formulated and the resulting optimization problem is shown to fall into a class of nonlinear integer programming problems. Deterministic techniques for solving this class of problems are computationally cumbersome, even for small size problems. A new heuristic algorithm is developed, which is based on a decomposition technique that greatly reduces the computational complexity of the problem. Numerical results for a variety of network configurations indicate that the heuristic algorithm, while not theoretically convergent, yields practicable low cost solutions with substantial savings in computer processing time and storage requirements. Moreover, it is shown that this algorithm is capable of solving realistic network problems whose solutions using deterministic techniques are computationally intractable.