About This Item

Ask the MINDS@UW Librarian

Database Support for Matching: Limitations and Opportunities

Show full item record

File(s):

Author(s)
Kini, Ameet; Shankar, Srinath; DeWitt, David; Naughton, Jeffrey
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Citation
TR1545
Date
2005
Abstract
A match join of R and S with predicate theta is a subset of the theta join of R and S such that each tuple of R and S contributes to at most one result tuple. Match joins and their generalizations arise in many scenarios, including one that was our original motivation, assigning jobs to processors in the Condor distributed job scheduling system. We explore the use of RDBMS technology to compute match joins. We show that the simplest approach of computing the full theta join and then applying standard graph-matching algorithms to the result is ineffective for all but the smallest of problem instances. By contrast, a closer study shows that the DBMS primitives of grouping, sorting, and joining can be exploited to yield efficient match join operations. This suggests that RDBMSs can play a role in matching beyond merely serving as passive storage for external programs.
Permanent link
http://digital.library.wisc.edu/1793/60472 
Export
Export to RefWorks 
‚Äč

Part of

Show full item record

Search and browse




About MINDS@UW

Deposit materials

  1. Register to deposit in MINDS@UW
  2. Need deposit privileges? Contact us.
  3. Already registered? Have deposit privileges? Deposit materials.