TAILIEUCHUNG - Keyword Search in Databases- P6

Keyword Search in Databases- P6: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 | 24 2. SCHEMA-BASED KEYWORD SEARCH ON RELATIONAL DATABASES A XML A Michelle P XML P Michelle a Structure L-Node Relation L-Edge Relation Vid Rname KSet l 1 . A . 10 2 . b Storage Fid Cid Attr 3 . 1 AID Figure E-Lattice a Semijoin b Join Figure Join vs Semijoin Join CN Ci we attempt to find the largest subtrees in E that Ci can share with using the index and we link to the roots of such subtrees. Figure a illustrates a partial lattice. The entire lattice E is maintained in two relations L-Node relation and L-Edge relation Figure b . Let a bit-string represent a set of keywords ki k2 ki . The L-Node relation maintains for any node in E a unique Vid in E the corresponding relation name Rname that appears in the given database schema Gs a bit-string KSet that indicates the keywords associated with the node in E and the size of the bit-string l . The L-Edge relation maintains the parent child relations among all the nodes in E with its parent Vid and child Vid Fid Cid plus its join attribute Attr either primary key or foreign key . The two relations can be maintained in memory or on disk. Several indexes are built on the relations to quickly search for given nodes in E. There are three main differences between the two execute graphs the Mesh and the E-Lattice. 1 The maximum depth of a Mesh is Tmax 1 and the maximum depth of an E-Lattice is LTmax 2 1_ . 2 In a mesh only the left part of two CN s can be shared except for the leaf nodes while in an E-Lattice multiple parts of two CNs can be shared. 3 The number of leaf nodes in a . CANDIDATE NETWORK EVALUATION 25 mesh is O V Gs 21 2 because there are O V Gs 2l clusters in a mesh and each cluster may contain O V Gs 2l leaf nodes. The number ofleaf nodes in an T-Lattice is O 2l . After sharing computational cost using either the Mesh or the T-Lattice all CNs are evaluated using joins in DISCOVER or S-KWS. A join plan is shown in Figure b to process the CN in Figure a using 5 projects and 4 .

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.