Efficient join processing over uncertain data

ABSTRACT

In many applications data values are inherently uncertain. This includes moving-objects, sensors and biological databases. There has been recent interest in the development of database management systems that can handle uncertain data. Some proposals for such systems include attribute values that are uncertain. In particular, an attribute value can be modeled as a range of possible values, associated with a probability density function. Previous efforts for this type of data have only addressed simple queries such as range and nearest-neighbor queries. Queries that join multiple relations have not been addressed in earlier work despite the significance of joins in databases. In this paper we address join queries over uncertain data. We propose a semantics for the join operation, define probabilistic operators over uncertain data, and propose join algorithms that provide efficient execution of probabilistic joins. The paper focuses on an important class of joins termed probabilistic threshold joins that avoid some of the semantic complexities of dealing with uncertain data. For this class of joins we develop three sets of optimization techniques: item-level, page-level, and index-level pruning. These techniques facilitate pruning with little space and time overhead, and are easily adapted to most join algorithms. We verify the performance of these techniques experimentally.

REFERENCES

• 1: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluating probabilistic queries over imprecise data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872823]
• 2: R. Cheng, Y. Xia, S. Prabhakar, R. Shah, and J. Vitter. Efficient indexing methods for probabilistic threshold queries over uncertain data. In Proc. VLDB, 2004.
• 3: R. Cheng, Y. Xia, S. Prabhakar, R. Shah, and J. S. Vitter. Efficient join processing over uncertain data. Technical Report CSD TR#05-004, Dept. of CS, Purdue University, 2005.
• 4: N. Dalvi and D. Suciu. Efficient query evaluation on probabilistic databases. In Proc. VLDB, 2004.
• 5: A. Deshpande, C. Guestrin, S. Madden, J. Hellerstein, and W. Hong. Model-driven data acquisition in sensor networks. In Proc. VLDB, 2004.
• 6: D. Pfoser and C. Jensen. Capturing the uncertainty of moving-objects representations. In Proc. SSDBM, 1999.
• 7: Jost Enderle , Matthias Hampel , Thomas Seidl, Joining interval data in relational databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007645]
• 8: Himawan Gunadhi , Arie Segev, Query Processing Algorithms for Temporal Intersection Joins, Proceedings of the Seventh International Conference on Data Engineering, p.336-344, April 08-12, 1991
• 9: E. Hung, L. Getoor, and V. S. Subrahmanian. PXML: A probabilistic semistructured data model and algebra. In ICDE, 2003.
• 10: The Lowell Database Research Self-Assessment Meeting. Lowell Massachusetts. May 2003.
• 11: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 12: A. Nierman and H. V. Jagadish. ProTDB: Probabilistic Data in XML. In VLDB, 2002.
• 13: Michael D. Soo , Richard Thomas Snodgrass , Christian S. Jensen, Efficient Evaluation of the Valid-Time Natural Join, Proceedings of the Tenth International Conference on Data Engineering, p.282-292, February 14-18, 1994
• 14: J. Widom. Trio: A system for integrated management of data, accuracy, and lineage. In Proc. CIDR, 2005.
• 15: Ouri Wolfson , A. Prasad Sistla , Sam Chamberlain , Yelena Yesha, Updating and Querying Databases that Track Mobile Units, Distributed and Parallel Databases, v.7 n.3, p.257-387, July 1999 [doi>10.1023/A:1008782710752]
• 16: Adnan Yazici , Alper Soysal , Bill P. Buckles , Fred E. Petry, Uncertainty in a nested relational database model, Data & Knowledge Engineering, v.30 n.3, p.275-301, July 1999 [doi>10.1016/S0169-023X(99)00010-5]
• 17: Efficient Temporal Join Processing Using Indices, Proceedings of the 18th International Conference on Data Engineering, p.103, February 26-March 01, 2002

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Performance

Keywords:
imprecise data, joins, uncertainty management