Evaluating probabilistic queries over imprecise data

Abstract

Many applications employ sensors for monitoring entities such as temperature and wind speed. A centralized database tracks these entities to enable query processing. Due to con-tinuous changes in these values and limited resources (e. g., network bandwidth and battery power), it is often infeasi-ble to store the exact values at all times. A similar situation exists for moving object environments that track the con-stantly changing locations of objects. In this environment, it is possible for database queries to produce incorrect or invalid results based upon old data. However, if the degree of error (or uncertainty) between the actual value and the database value is controlled, we can place more confidence in the answers to queries. More generally, query answers can be augmented with probabilistic estimates of the valid-ity of the answers. In this chapter we study probabilistic query evaluation based upon uncertain data. A classifica-tion of queries is made based upon the nature of the result set. For each class, we develop algorithms for computing probabilistic answers. We address the important issue of measuring the quality of the answers to these queries, and provide algorithms for e ciently pulling data from relevant sensors or moving objects in order to improve the quality of the executing queries. Extensive experiments are performed to examine the e ectiveness of several data update policies.