Database support for matching: limitations and opportunities

ABSTRACT

We define a match join of R and S with predicate θ to be a subset of the θ-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 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 resource allocation scenarios. To the best of our knowledge no one uses an RDBMS as a tool to help solve these problems; our goal in this paper is to explore whether or not this needs to be the case. We show that the simple approach of computing the full θ-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 related problems beyond merely serving as expensive file systems exporting data sets to external user programs.

REFERENCES

• 1: Rakesh Agrawal , H. V. Jagadish, Materialization and Incremental Update of Path Information, Proceedings of the Fifth International Conference on Data Engineering, p.374-383, February 06-10, 1989
• 2: Rakesh Agrawal , Edward L. Wimmers, A framework for expressing and combining preferences, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.297-306, May 15-18, 2000, Dallas, Texas, United States
• 3: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 4: C. Berge, "Two Theorems in Graph Theory" Proceedings of the National Academy of Science USA, 1957, p. 842--844.
• 5: Yuan-Chi Chang , Lawrence Bergman , Vittorio Castelli , Chung-Sheng Li , Ming-Ling Lo , John R. Smith, The onion technique: indexing for linear optimization queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.391-402, May 15-18, 2000, Dallas, Texas, United States
• 6: J. Feigenbaum et al., "On Graph Problems in a Semi-Streaming Model", Proceedings of ICALP 2004, p. 531--543
• 7: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 8: Surajit Chaudhuri , Luis Gravano, Evaluating Top-k Selection Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.397-410, September 07-10, 1999
• 9: S. Guha et al. "Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints", Proceedings of VLDB 2003, p. 778--789
• 10: S. Guha et al. "Merging the Results of Approximate Match Operations", Proceedings of VLDB 2004, p. 636--647.
• 11: J. Hopcroft and R. Karp. "An n5/2 Algorithm for Maximum Matching in Bipartite Graphs", SIAM Journal of Computing, 1975, p. 225--231.
• 12: F. Ilyas , G. Aref , K. Elmagarmid, Supporting top-k join queries in relational databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.3, p.207-221, September 2004 [doi>10.1007/s00778-004-0128-2]
• 13: R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100262]
• 14: J. Magun. "Greedy Matching Algorithms: An experimental study", Proceedings of the 1st Workshop on Algorithm Engineering, p. 22--31, 1997.
• 15: Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and Generalized On-line Matching, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.264-273, October 23-25, 2005 [doi>10.1109/SFCS.2005.12]
• 16: Predator Project. http://www.distlab.dk/predator/
• 17: R. Raman , M. Livny , M. Solomon, Matchmaking: Distributed Resource Management for High Throughput Computing, Proceedings of the The Seventh IEEE International Symposium on High Performance Distributed Computing, p.140, July 28-31, 1998
• 18: C. Schlup. "Automatic Game Matching", http://dcg.ethz.ch/theses/ws0203/OnlineMatching_abstract.pdf
• 19: Todd Tannenbaum , Derek Wright , Karen Miller , Miron Livny, Condor: a distributed job scheduler, Beowulf cluster computing with Linux, MIT Press, Cambridge, MA, 2001
• 20: P. Tsaparas et al. "Ranked Join Indices", Proceedings of IEEE ICDE 2003, p. 277--288.
• 21: http://www.research.microsoft.com/mlp/trueskill/default.aspx

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
advanced query types, join, matching