Evaluation of Probabilistic Queries over Imprecise Data in Constantly-Evolving Environments. Information Systems Journal, 32(1), March 2007. Reynold Cheng, Dmitri V. Kalashnikov, and Sunil Prabhakar Department of Computer Sciences Purdue University Abstract Sensors are often employed to monitor continuously changing entities like locations of moving objects and temperature. The sensor readings are reported to a database system, and are subsequently used to answer queries. Due to continuous changes in these values and limited resources (e.g., network bandwidth and battery power), the database may not be able to keep track of the actual values of the entities. Queries that use these old values may produce incorrect answers. However, if the degree of uncertainty between the actual data value and the database value is limited, one can place more confidence in the answers to the queries. More generally, query answers can be augmented with probabilistic guarantees of the validity of the answers. In this paper, we study probabilistic query evaluation based on uncertain data. A classification of queries is made based upon the nature of the result set. For each class, we develop algorithms for computing probabilistic answers, and provide efficient indexing and numeric solutions. We address the important issue of measuring the quality of the answers to these queries, and provide algorithms for efficiently 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 effectiveness of several data update policies. Keywords: Sensor databases, querying imprecise data, uncertainty, uncertainty region, handling uncertainty, models of uncertainty, aggregate query, entity-based query, value-based query, probabilistic queries, quality of probabilistic answer, update heuristics, location-aware computing, Downloadable files: Paper: IS07_dvk_pqry.pdf See also a moving-object environment solution to a similar problem. BibTeX entry: @article{IS07::dvkPQ, author = {Reynold Cheng and Dmitri V.\ Kalashnikov and Sunil Prabhakar}, title = {Evaluation of Probabilistic Queries over Imprecise Data in Constantly-Evolving Environments}, journal = IS, volume = 32, number = 1, pages = {104--130}, month = mar, year = 2007 } Back to Kalashnikov's homepage