Database Support for Weighted Match Joins

As relational database management systems are applied to non-traditional domains such as scientific data management, there is an increasing need to support queries with semantics that differ from those appropriate for traditional RDBMS applications. Two interesting ideas currently being explored in the DBMS community are ranking query results (e.g., top-k computations) and, more recently, "match joins." In this paper we combine these two ideas and study weighted match joins, in which (a) like match joins, each tuple joins with at most one matching tuple, and (b) like top-k joins, the system attempts to provide a set of answer tuples that maximizes a weight function. We explore exact and approximate strategies for evaluating weighted match joins. Using a prototype implementation in PostgreSQL, we explore the performance characteristics of these strategies. Our results suggest that the DBMS optimization-based approach of providing several implementations of an operator and then choosing an appropriate one at run time can be useful in computing weighted match joins.