Common expression analysis in database applications

Independent optimization of database requests overlooks potential savings which can be achieved when they are optimized collectively. An intuitive model for queries called the query graph supports common expression detection for optimization of a stream of requests. We describe how ad hoc query processing can be improved using intermediate results and answers produced from earlier queries, without significantly impacting processing costs when no common expressions are found. We have written a Pascal program, COMMON, which implements a variation of the algorithm which we describe.