APPROXIMATE-a query processor that produces monotonically improving approximate answers

Abstract

APPROXIMATE, a query processor that makes approximate answers available if part of the database is unavailable, or if there is not enough time to produce an exact answer, is described. The processor implements approximate query processing, and the accuracy of the approximate result produced improves monotonically with the amount of data retrieved to produce the result. The monotone query processing algorithm of APPROXIMATE works within a standard relational algebra framework. APPROXIMATE maintains semantic information for approximate query processing at an underlying level, and can be implemented on a relational database system with little change to the relational architecture. It is shown how APPROXIMATE is implemented to make effective use of the semantic support. The additional overhead required by APPROXIMATE is described.