next up previous contents
Next: Tuple Relational Calculus Up: Stages of Translation Previous: Formal Definition of

First Optimisation (OP1)


The first stage of optimisation is carried out once the query has been translated into DRC. This stage of optimisation is concerned with the removal of tuple membership clauses which have been made redundant by the explicit association of domains with variables. For example, if we consider the DRC query corresponding to the question ``who works in toys'':

can see that the variable fv is associated with the domain which is the projection on the name attribute of the emp relation. Now, however, we can see that the tuple membership clause which states that the tuple is a member of emp is redundant, since it merely reinforces the information given by the domain declaration. Our system performs this optimisation by converting the DRC expression into clausal form (see [Bundy, 1983]) and removing the redundant clauses. Our example above would therefore produce the following clause set

Removing the redundant clause produces the single clause:

which can be reconstructed to form the query:

Clearly, this represents an improvement.

Chris Fox, September 1995