Supporting match joins in relational database management systems
Jeffrey F. Naughton, Ameet Kini · 2007
As more and more diverse applications seek to use database management systems (DBMS) as their primary storage, the question frequently arises as to whether we can exploit the query capabilities of the DBMS to support these applications. This dissertation explores the use of DBMS technology to efficiently support joins. Match joins and their generalizations belong to a broad class of matching problems that have attracted a great deal of attention in disciplines including operations research and theoretical computer science. Instances of these problems arise in practice in a wide range of applications from resource allocation to bioinformatics. To the best of our knowledge, no one uses a DBMS as a tool to help solve these problems. Our goal is to explore whether or not this needs to be the case. In the first part of this dissertation, we introduce the match join operation as a one-to-one subset of the relational join. In general, there are many one-to-one subsets of the relational join; for the variant of match join discussed in this part, we seek the one that maximizes the cardinality of the result. Then we consider an extension of the match join that incorporates weights, the quality metric for the result being the one that maximizes the total weight of the result set. Finally, we consider a third extension to the match join wherein instead of there being a single match predicate for the entire problem instance, each tuple in either input is allowed to specify its own match predicate. Our work suggests that DBMSs can play a role in matching related problems beyond merely serving as expensive file systems exporting data sets to external user programs.