Abstract
In this paper the various tactics for query processing in INGRESS are empirically evaluated on a test bed of sample queries.
1. Introduction
In Ref. 5 we presented a general strategy for query processing known as decomposition, which had been designed for the nonprocedural query language QUEL2 and was in the process of being implemented in the relational database management system INGRESS. 4 In this approach the problem of dealing with a multi-relational query is separated into two
stages. First, a query which references several relations is decomposed into simpler components, the main objective at this point being to minimize
the combinatorial growth that multirelational ' queries entail. The information used to achieve this minimization consists mainly of the structure of the query and size statistics of the relations used. ciently simple" components, the focus of the strategy shifts from one of the structural simplification to that of minimizing data access, and in this
"end game" phase of query processing the information associated with storage structure plays a dominant role. Once the query is decomposed into "suffi- One of the principal tactics that we proposed for breaking up a query into simple pieces was reduction, a process which might be described as separating a query at its natural joints. On both intuitive and theoretical grounds reduction appeared to be a highly advantageous tactic. However, the overall procedure of decomposition was too complex to permit a complete theoretical analysis, and the efficacy of reduction required confirmation by an empirical study. now been undertaken,8 and a summary of its major findings will be reported in this paper.
Such a study has A second issue to be addressed in this paper is the strategy of the "end game." decomposition, a considerable amount of work has already been published on strategies for processing two-variable queries. Our work differs from these both in the way the problem is abstracted and in the specific assumptions concerning the costs that the implementation environment imposes. In contrast to In section 2 we shall review the principal 409 features of the decomposition procedures with an emphasis on the tactic of reduction. In section 3 the results of our experiments concerning reduction will be summarized. In section 4 details of the "end game'' strategy together with a summary of some empirical studies will be presented.

Download full report
http://googleurl?sa=t&source=web&cd=1&ve...718156.pdf%3Farnumber%3D718156&ei=rHcyTrqRGsnRrQf--7XMCw&usg=AFQjCNHAhbRQAL24uvIlop2m8hRtaC6iYw&sig2=n3Z-3I9p7_HekOjwZr4NGw