tailieunhanh - Keyword Search in Databases- P9

Keyword Search in Databases- P9: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 | . OTHER KEYWORD SEARCH SEMANTICS 39 certain keyword and its two attributes tidi and disi explicitly indicate that it is about keyword ki. The details of computing for Rj 1 j 4 are given below. F . nn d 1 di .ip .2 P A D R1 P1 2 nKl TiD tid . . Pm Dr-md U tidi .1 . p TID_R pID R- . 2PID R3 tid R3 U . p p _K pID R3 U nn J-TID di .4 Pii p d2_r t d R3 F. D- 4 U . p Tnf_R pID2R4 Here eachjoin project corresponds to a foreign key reference - an edge in schema graph Gs .The idea is to compute based on if there is an edge between Rj and Ri in Gs .Consider for R3 it computes P1 3 by union of three joins P - R3 U P 4 R3 U P 4 R3 because there is one foreign key reference between R3 Paper and R- Write and two foreign key references between R3 and R4 Cite . This ensures that all Rj tuples that are with distance d from a tuple containing a keyword ki can be computed. Continuing the example to compute for Rj 1 j 4 for keyword k1 we replace every in Eq. with Pd andreplace 1 dis1 with - dis1 . The process repeats Dmax times. Suppose that we have computed for 0 d Dmax and 1 j 4 for keyword k1 _ Michelle . We further compute the shortest distance between a Rj tuple and a tuple containing k1 using union group-by and SQL aggregate function min. First we perform project . Therefore every relation has the same tree attributes. Second for Rj we compute the shortest distance from a Rj tuple to a tuple containing keyword k1 using group-by T and SQL aggregate function min. Gj Fmin dis1 U U where the left side of group-by T is group-by attributes and the right side is the SQL aggregate function. Finally Pair1 G1 U G- U G3 U G4 Here Pair1 records all tuples that are shortest distance away from a tuple containing