Đang chuẩn bị liên kết để tải về tài liệu:
Keyword Search in Databases- P14

Keyword Search in Databases- P14: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 | 64 3. GRAPH-BASED KEYWORD SEARCH Algorithm 21 MinWeightQSubtree G P Input a data graph G and a set of PT constraints P. Output a minimum weight Q-subtree under constraints P. 1 return T if P consists of a single RPT T 2 return A if P consists of a single NPT 3 let T be obtained from P by replacing each N e P npt with the PT consisting of only the node root N 4 Initialize Tmin A where A has a weight to 5 for all subsets Ttop of T such that Ttop 2 do 6 G 1 G - UtePV T UteTtOp root T 7 Ttop - MinWeightSuperTree G1 Ttop 8 if Ttop a then 9 Tt p - Ttop U Ttop 10 let G2 be obtained from G by removing all the incoming edges to root T p 11 T - MinWeightSuperTree G2 P Ttop U Tt p 12 Tmin - min Tmin T 13 return Tmin But this will take exponential time as line 5 in MinWeightQSubtree. In the following we introduce approaches to find a 0 1 -approximate minimum weight Q-subtree under constraints P. Algorithm 22 AppWeightQSubtree Kimelfeld and Sagiv 2006b finds a 0 1 -approximation of the minimum weight Q-subtree in polynomial time under data-and-query complexity. Recall that the number of NPTs of P is no more than 2. AppWeightQSubtree mainly consists of three steps. 1. A minimum weight Q-subtree is found by calling MinWeightQSubtree if there are no RPTs in P line 1 . Otherwise it finds a 0-approximation of minimum weight super tree of P Tapp by calling AppWeightSuperTree line 2 . Return Tapp if it is a Q-subtree or A line 3 . 2. Find a reduced tree Tmin lines 4-5 . The weight of Tmin is guaranteed to be smaller than the minimum weight Q-subtree under constraints P if one exists. Note that this step can be accomplished by a single call to procedure MinWeightQSubtree by adding to G a virtual node v and an edge to each root T for all T e P rpt and calling MinWeightQSubtree G P npt U v . If Tmin is A then there is no Q-subtree satisfying the constraints P line 6 . 3.3. STEINER TREE-BASED KEYWORD SEARCH 65 Algorithm 22 AppWeightQSubtree G P Input a data graph G and a set of PT .