tailieunhanh - Keyword Search in Databases- P15

Keyword Search in Databases- P15: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 | . DISTINCT ROOT-BASED KEYWORD SEARCH 69 DISTINCT ROOT-BASED KEYWORD SEARCH In this section we show approaches to find Q-subtrees using the distinct root semantics where the weight of a tree is defined as the sum of the shortest distance from the root to each keyword node. As shown in the previous section the problem of keyword search under the directed steiner tree is in general a hard problem. Using the distinct root semantics there can be at most n Q-subtrees for a keyword query and in the worst case all the Q-subtrees can be found in time O l n log n m . The approaches introduced in this section deal with very large graphs in general and they propose search strategies or indexing schemes to reduce the search time for an online keyword query. BIDIRECTIONAL SEARCH BackwardSearch algorithm as proposed in the previous section can be directly applied to the distinct root semantics by modifying Line 3 to iterate over the l keyword nodes . ki ki . It would explore an unnecessarily large number of nodes in the following scenarios The query contains a frequently occurring keyword. In BackwardSearch one iterator is associated with each keyword node. The algorithm would generate a large number of iterators if a keyword matches a large number of nodes. An iterator reaches a node with large fan-in incoming edges . An iterator may need to explore a large number of nodes if it hits a node with a very large fan-in. Bidirectional search Kacholia et al. 2005 can be used to overcome the drawbacks of BackwardSearch. The main idea of bidirectional search is to start forward searches from potential roots. The main difference of bidirectional search from BackwardSearch are as follows All the single source shortest path iterators from the BackwardSearch algorithm are merged into a single iterator called the incoming iterator. An outgoing iterator runs concurrently which follows forwarding edges starting from all the nodes explored by the incoming iterator. A spreading .