Approximate Queries with Adaptive Processing

The traditional query processing approach, by which queries are executed exactly according to a query execution plan selected before query execution starts, breaks down in heterogeneous and dynamic processing environments that are becoming more and more common as query processing contexts. In such environments, queries are often relaxed and query processing is forced to be adaptive and approximate, either to cope with limited processing resources or with limited data knowledge and data heterogeneity.When approximation and adaptivity are applied in order to cope with limited processing resources, possibly sacrificing result quality, we refer to as Quality of Service (QoS)-oriented techniques. On the other hand, when they are a means to improve the quality of results, in presence of limited data knowledge and data heterogeneity, we refer to as Quality of Data (QoD)-oriented techniques. While both kinds of approximation techniques have been proposed, most adaptive solutions are QoS-oriented. In this chapter, we first survey both kinds of approximation and introduce adaptive query processing techniques; then, we show that techniques which apply a QoD-oriented approximation in a QoD-oriented adaptive way, though demonstrated potentially useful on some examples, are still largely neglected.