Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Programs that can assist in the creation or automatically create trip diaries and stories will considerably increase use, especially for future viewers who have no idea of the content. For example, a fishing trip diary with a timeline, animated maps and annotations is substantially more valuable to us and our progeny than a collection of unlabelled photos in a labeled folder. New capture devices vastly broaden the nature of personal recording. Passive picture taking using the sensor-enhanced (Figure 6a) SenseCam is also very promising [2] whereby a camera captures several thousand photos a day (Figure 6b) complete with voice comments,. | Database Support for Matching Limitations and Opportunities Ameet M. Kini Srinath Shankar David J. Dewitt and Jeffrey F. Naughton Technical Report TR 1545 University of Wisconsin-Madison Computer Sciences Department 1210 West Dayton Street Madison WI 53706 USA akini srinath dewitt naughton @cs.wisc.edu 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. 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 or enhance the query capabilities of the RDBMS to support these applications. Some recent examples of this include OPAC queries 8 preference queries 1 4 and top-k selection 7 and join queries 10 13 17 . 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 appear in any other edge in E . Intuitively this says that each node in the graph is matched with at most one other node in the graph. Many versions of this problem can be defined by requiring different