The aim of this study is to present an algorithm which manipulates overlapping B-trees. The characteristic of the algorithm is that it uses a number of pointer manipulation routines which may replace pointer manipulations within an ordinary B-tree without sharing. The main advantages of the approach are (a) that any code operating on ordinary B-tree may be easily extended to cope with overlapping B-tree, and (b) that the pointer manipulation routines are general purpose in the sense that they may be applied to a broader family of tree structures

Disk drives with movable two-headed arms are now commercially available. The two heads are separated by a fixed number of cylinders. A major problem for optimizing disk head movement, when answering database requests, is the specification of the optimum number of cylinders separating the two heads. An earlier analytical study assumed a FCFS model and concluded that the optimum separation distance should be equal to 0.44657 of the number of cylinders N of the disk. This paper considers that the SCAN scheduling policy is used in file access, and it applies combinatorial analysis to derive exact formulas for the expected head movement. Furthermore, it is proven that the optimum separation distance is N/2 - 1 (⌈ N /2 - 1⌉ and ⌊ N /2 - 1⌋) if N is even (odd). In addition, a comparison with a single-headed disk system operating under the same scheduling policy shows that if the two heads are optimally spaced, then the mean seek distance is less than one-half of the value obtained with one head. In fact that the SCAN policy is used for many database applications (for example,batching and secondary key retrieval) demonstrates the potential of two-headed disk systems for improving the performance of database systems.

A number of previous studies derived expressions for batched searching of sequential and tree-structured files on the assumption that all the keys in the batch exist in the file, i.e., all the searches are successful. Formulas for batched searching of sequential and tree-structured files are derived, but the assumption made is that either all or part of the keys in the batch do not exist in the file, i.e., the batched search is completely or partly unsuccessful.>

A simple but general map overlay function is defined for quadtrees. It is shown that many common quadtree operations, including union, intersection, relative complement, masking, copy, complement and generalisation of quadtrees, can all be viewed as special cases of map overlay, depending on how pixel values of the result of an overlay are determined from the corresponding pixels of the maps being overlaid. It is shown that some operations, such as union, can be more efficiently performed by specialised algorithms. A more general overlay function is given, which is optimal (to within a constant factor) with respect to both time and space for all of the above operations. This overlay function requires two functions as parameters. One function determines when the quadtrees being overlaid are simple enough to be processed without further subdivision. The other performsthe overlay for simple cases.

In a previous study an ordered array of N keys was considered and the problem of locating a batch of M requested keys was investigated by assuming both batched sequential and batched binary searching. This paper introduces the idea of batched interpolation search, and two variations of the method are presented. Comparisons with the two previously defined methods are also made.

This study considers an ordered array of N keys and estimates the required number of key comparisons to locate M requested keys when a binary search is performed to find each key. The problem is analysed for the cases where the M requests (a) are performed individually on a First Come First Served basis, and (b) are treated as a batch. For the second case a break point is established which indicates whether it is preferable to apply binary or sequential search for a batch of M keys.

When repeatedly editing a text file, one is often faced with a choice of keeping previous generations for backup or deleting previous generations to reduce storage requirements. Since one generation of a text file is often very similar to the previous generation, the above conflict can often be resolved by sharing much of the common information. We propose using a tree structure to represent a text file. Common subtrees can be shared. Results of an experiment with one file are reported.

The secondary index selection problem (ISP) is known to be an NP-complete problem. The best possible known algorithm to find an exact solution of the ISP is the one developed by Schkolnick which utilizes the fact that the objective function of the problem satisfies the regularity condition. In a recent paper Ip et al presented a heuristic algorithm which solves the ISP with the added constraint that the creation and storage cost of the optimal selection must not exceed a certain specified cost. The current study observes that in practice this last problem can be translated to the classical ISP but requiring now that no more than k indexes may appear in the optimal set. It is shown that this new problem satisfies the regularity property. The study also presents the modifications needed to Schkolnick's algorithm for solving the problem considered.

The problem of organising a secondary index (e.g. inverted, multilist, B-tree, etc.) and the problem of selecting the secondary attributes to be indexed by employing a particular organisation are among the two most debated problems in database technology. Related studies try to solve the two problems by studying them separately. This paper tries to combine previous results on the two problems and develops a model which selects the optimal set of secondary attributes to be indexed by allowing various organisations and implementations of secondary indexes to be decision variables in the selection process.

In many applications it is necessary to be able to determine if a point is contained in a polygon. If co-ordinate values are approximate, we may be happy to have borderline cases dealt with in an arbitrary manner. However, if two regions have a common border section, decisions should be consistent. A simple algorithm for determining containment consistently is given.

The optimal selection of secondary indexes asks for the quantitative evaluation of the performance of a number of candidate secondary indexes in order to determine the particular combination of indexes which satisfies the anticipated user transactions at a minimal cost. Previous studies determine the optimal selection by assuming that the cost of satisfying a query using a secondary index is not affected by the existence of other indexes in the database. This assumption is realistic when the inverted file organization is used to organize secondary indexes. The main reason is that inverted files do not alter the size of the file. However, the assumption is not valid when the next most popular method for structuring secondary indexes is used, namely, the multilist database structures. This is so, because each multilist increases the size of the file. This paper studies the secondary index selection problem by making the assumption that the multilist organization is utilized to structure secondary indexes and develops a dynamic programming algorithm to solve it. The practical significance of the study lies in the fact that multilists can be easily implemented on network databases.

The study concerns a particular class of EDP applications, namely accounting applications. A common characteristics of these applications is that they perform calculations to produce records which contain monetary data. Missing, retroactive, erroneous and/or late data, which we term MREL data, may harm the accuracy of the accounting records unless special consideration is given during the system design and implementation. Two possible designs are presented which cope with the problem. The first design is easy to reach by adding some new modules to an already operating accounting applications. The second design is more appropriate when new applications are to be implemented. The study is supported with examples from a payroll application.

The initial database search cost deteriorates due to record additions, deletions and updates performed during the system operation. Previous studies proposed strategies for selecting the optimum maintenance points by making various assumptions about the rate of database deterioration, the database planning period, the maintenance interval, etc. However, the studies did not express the optimum maintenance points as a function of the database physical structure. The paper assumes (a) that the rate of additions to the database equals the rate of deletions for each database record type, and (b) that maintenance is performed for the entire database at fixed time intervals and it shows how the maintenance points may be determined for various primitive physical database structures. The results are subsequently ultilized to select the optimum maintenance points for arbitrary database structures.

The paper presents three criteria which aid in solving the problem of allocating copies of a file in a computer network. The criteria simplify the problem because (a) they can be applied a priori to determine that certain sites will (or will not) be included in the optimal allocation, and (b) they can become an integral part and accelerate a search procedure for finding an optimal allocation.

A framework is developed which places in perspective with other approaches a model developed by Kollias (1976) for the selection of indexing paths in a primary file. The paper extends the model and proves a number of properties which characterise it. These properties not only simplify the solution of the model but they can also be used by file designers as rules when selecting indexing paths for their applications.

Schneiderman and Goodman (1976) considered queries based on primary key values and they argued that the process of batching may reduce their response time. This study considers the effect of batching queries based on secondary key values and proposes some means of scheduling the queries which substantially reduces the required disc head movements. The method is a variation of the SCAN disc scheduling policy and it can be applied to online retrieval systems because it works even for very small batch sizes and because it does not impose prohibitive overheads in evaluating/implementing it.

Schneiderman and Goodman (1976) derived a formula which estimates the portion of a sequential structured file which has to be searched to satisfy a batch of queries. This note addresses a similar problem by assuming that the file (a) is organised either randomly or indexed sequentially, and (b) is placed on a disc with movable read/write heads, and reports a formula which estimates the expected seek time.

The paper solves two of the problems concerned with improving the performance of a particular class of intelligent data management systems: the self organising system. A common characteristic of the problems solved is the introduction of solution spaces which can be searched by linear programming technique.