Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Keyword Search in Databases- P7:Conceptually, a database can be viewed as a data graph GD(V ,E), where V represents a set of objects, and E represents a set of connections between objects. In this book, we concentrate on two kinds of databases, a relational database (RDB) and an XML database. In an RDB, an object is a tuple that consists of many attribute values where some attribute values are strings or full-text; there is a connection between two objects if there exists at least one reference from one to the other | 2.3. CANDIDATE NETWORK EVALUATION 29 A Partial Lattice W C Wll A XML A MicjielleJ P XML P Michelle A XML W A Michelle P XML C P Michelle Inputs Figure 2.14 Lattice and Its Inputs from a Stream v in L on Rlist specified for Ri K . Each deletion may notify some father nodes of v to be moved from Rlist or Wlist to Slist and v may also be moved from Rlist to Wlist. 2.3.2 GETTING TOP- MTJNTS IN A RELATIONAL DATABASE We have discussed several effective ranking strategies in Section 2.1. In this section we discuss how to answer the top- keyword queries efficiently. A naive approach is to first generate all MTJNTs using the algorithms proposed in Section 2.3.1 and then calculate the score for each MTJNT and finally output the top- MTJNTs with the highest scores. In DISCOVER-II Hristidis et al. 2003a and SPARK Luo et al. 2007 several algorithms are proposed to get top- MTJNTs efficiently. The aim of all the algorithms is to find a proper order of generating MTJNT s in order to stop early before all MTJNTs are generated. In DISCOVER-II three algorithms are proposed to get top- MTJNTs namely the Sparse algorithm the Single-Pipelined algorithm and the Global-Pipelined algorithm. All algorithms are based on the attribute level ranking function given in Eq. 2.1. Given a keyword query Q for any tuple t let the tuple score be score t Q 2aet score a Q where score a Q is the score for attribute a of t as defined in Eq. 2.2. The score function in Eq. 2.1 has the property of tuple monotonicity defined as follows. For any two MTJNTs T ti N t2 N . N ti and T tj N t N . N t generated from the same CN C if for any 1 i l score ti Q score t- Q then we have score T Q score T Q . For a keyword query Q given a CN C let the set of keyword relations that contain at least one keyword in C be C.M Mi M2 . Ms . Suppose tuples in each Mi 1 i s are sorted in non-increasing order of their scores. Let Mi.tj be the j-th tuple in Mi. In each Mi we use Mi.cur to denote the current tuple such that the .
