Semantic query optimisation is a comparatively recent approach for the transformation of a given query into equivalent alternative queries using matching rules in order to select an optimum query based on the costs of executing these alternative queries. The most important aspect of this optimisation approach is that this resultant query can be processed more efficiently than the original query. This paper describes how a near optimal alternative query may be found in far less time than existing approaches. The method uses the concept of a 'search ratio' associated with each matching rule. The search ratio of a matching rule is based on the cost of the antecedent and consequent conditions of the rule. This cost is related to the number of instances in the database determined by these conditions. This knowledge about the number of instances is available and can be recorded when the rules are first derived. We then compare search ratios of rules to select the most restrictive rules for the construction of a near optimum query. The technique works efficiently regardless of the number of matching rules, since resources are not used to construct all alternative queries. This means that transformation and selection costs are minimised in our system. It is hoped that this method will prove a viable alternative to the expensive optimisation process normally associated with semantic query optimisation.

We present a simple generalised technique, for sequencing a multi-attribute file, which can be used in a situation where the query pattern is unknown and the term content equiprobable. The method is based on constructing a short spanning path through the records thereby minimising the sum of the Hamming distances between them. Retrieval performance is simulated over a range of query expressions and results suggest a significant reduction in the number of block accesses, using this technique, as compared with records randomly distributed over the file space.

An introduction is given to the use of formal semantics as a means of both specifying relational query languages and of establishing a conceptual basis for their analysis. The approach is demonstrated with respect to the relational calculus and then extended to cope with the more advanced constructs of SEQUEL and QUEL.

The construction of both an optimal read-forward polyphase sort and a near optimal read-backward version is described. The former minimizes the merge volume, for a given distribution of strings, without the use of auxiliary data structures, and incorporates a new technique for computing the positions of dummy strings. In the case of the read-backward version, an approach is developed which achieves a merge volume nearest to the minimum, inasmuch as the theoretical optimal read-backward polyphase sort cannot be realized. A dispersion algorithm is also described which optimizes the distribution of strings so that minimum merge volume is assured.

It is a well known and accepted fact in systems design that once the basic objectives of a system have been met, the cost of further expansion frequently outweighs any increased benefits and so effectively deters development. In many large organisations the implementation of sophisticated data base technology can represent both a profitable and necessary investment which, amongst other things, provides a comprehensive solution to the above problem. In other, perhaps small, installations the more important processing requirements are simply those of flexibility in file design and ease of changing formats. This paper sets out a proposal for a modified COBOL implementation which, by providing a level of data independence adequate to most DP installations, may be seen to offer a viable alternative to a full data-base system. The approach is based on the transferral of the data division file definitions, from the COBOL program, to the head of the physical files to which they pertain. Only those data elements referred to in the application logic need then be declared in the program itself, and association between the two definition sets may be deferred until run time. This work is an extension of that being currently undertaken by MacCallum (1973) and MacCallum and Jones (1975) forming part of a research programme aimed at improving information processing techniques.