TAILIEUCHUNG - Database Support for Matching: Limitations and Opportunities

Part of feeling secure is knowing that capture is automatic. While browser web capture at first struck us as somewhat trivial, this essential feature has changed our behavior. The failure of Gemmell’s hard drive resulted in losing four months of captured web pages and was an emotional and productivity blow – perhaps like having one’s memories taken away. Even months later, he searches for information expected to be in the web archive, only to realize that it was lost. Bell had a similar experience when he inadvertently deleted an email folder that while backed up was not properly synchronized (see. | Database Support for Matching Limitations and Opportunities Ameet Kini Srinath Shankar Jeffrey F. Naughton David J. Dewitt Department of Computer Sciences University of Wisconsin - Madison 1210 W. Dayton Street Madison WI 53706 akini srinath naughton dewitt @ ABSTRACT We define a match join of R and S with predicate 6 to be a subset of the 6-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 6-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. 1. INTRODUCTION As more and more diverse applications seek to use RDBMSs as their primary storage the question frequently arises as to whether we can exploit the query capabilities of the RDBMS to support these applications. Some recent examples of this include OPAC queries 9 preference queries 2 5 and top- selection 8 and join queries 12 20 . Here we consider the problem of supporting matching operations. In mathematical terms a matching problem can be expressed as follows given a bipartite graph G with edge set E find a subset of E denoted E such that for each e u v eE neither u nor v

• Cơ sở dữ liệu
• Terpenoids and Gibberellic
• Acids Interaction
• Diabetes Mellitus Type
• Hematologic Manifestations
• Multiple Sclerosis
• Laboratory Method
• Developing Olive
• Olive Inflorescence
• Regulatory Mechanism
• Asexual Cycles
• medicine availability
• private sector
• private pharmacies
• electrical signal
• shrimp trawler