TAILIEUCHUNG - Keyword Search in Databases- P20

Keyword Search in Databases- P20: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 | 94 4. KEYWORD SEARCH IN XML DATABASES Algorithm 32 IndexedLookupEager S1 Si Input l lists of Dewey IDs Si is the list of Dewey IDs of the nodes containing keyword k . Output All the SLCAs 1 V 2 while there are more nodes in Si do 3 Read p nodes of Si into buffer B 4 for i 2 to l do 5 B getSLCA B Si 6 removeFirstNode B if v _ and getFirstNode B x v 7 output v as a SLCA if v _ B _ 0 and v getFirstNode B 8 if B _ 0 then 9 v removeLastNode B 10 output B as SLCA nodes 11 output v as a SLCA 12 Procedure getSLCA Si S2 13 Result 0 u root with Dewey ID 0 14 for each node v e Si in increasing Dewey ID order do 15 x lca v closest v S2 16 if pre u pre x then 17 Result Result U u if u x 18 u X 19 return Result U u ScanEager p at Line 3 must be no smaller than Si . it must first compute slca Si S2 then slca slca Si S2 S3 and continue. ScanEager directly follows from Property Property Property . ScanEager outputs all the SLCA nodes . slca Si Si in time O ld Si d y l_2 Si or O ld S Xu and Papakonstantinou 2005 . Although ScanEager has the same time complexity as StackAlgorithm it has two advantages. First ScanEager starts from the smallest keyword list and it does not have to scan to the end of every keyword list and may terminate much earlier. Second the number of lca operations of ScanEager is O l Si which is usually much less than that of the StackAlgorithm that has OQ2i_i Si lca operations. Multiway SLCA MultiwaySLCA Sun et al. 2007 further improves the performance of IndexedLookupEager but with the same worst case time complexity. The Motivation and general idea of MultiwaySLCA are shown by the following example. . SLCA-BASED SEMANTICS 95 Algorithm 33 ScanEager Si Si Input l lists of Dewey IDs Si is the list of Dewey IDs of the nodes containing keyword k . Output All the SLCAs 1 u root with Dewey ID 0 2 for each node Vi e Si in increasing Dewey ID order do 3 moving cursors in each list S to closest vi Si for 1 i l 4 V lca vi closest vi S2 closest vi Si 5

• Cơ sở dữ liệu
• cơ sở dữ liệu quan hệ
• database relationship
• thiết kế CSDL quan hệ
• CSDL quản lý khách sạn
• Kiến trúc hệ quản trị CSDL
• đặc tính cơ sở dữ liệu
• Hệ cơ sở dữ liệu
• Hệ quản trị cơ sở dữ liệu
• Chức năng hệ cơ sở dữ liệu
• Hoạt động hệ cơ sở dữ liệu
• Các hệ cơ sở dữ liệu
• Tìm hiểu hệ cơ sở dữ liệu
• Cơ sở dữ liệu
• Bài giảng Các hệ cơ sở dữ liệu
• Hệ quản trị cơ sở dữ liệu phân tán
• Cơ sở dữ liệu phân tán
• Cơ sở dữ liệu quan hệ và SQL
• Bài giảng cơ sở dữ liệu quan hệ
• Lý thuyết cơ sở dữ liệu
• Cơ sở dữ liệu SQL
• Kiến trúc hệ cơ sở dữ liệu
• Bài giảng Các hệ quản trị cơ sở dữ liệu
• Kỹ thuật phục hồi cơ sở dữ liệu
• Phục hồi cơ sở dữ liệu
• Giới thiệu hệ quản trị cơ sở dữ liệu
• Đề cương môn học
• Quản trị cơ sở dữ liệu
• Tổng quan hệ cơ sở dữ liệu
• Tài liệu cơ sở dữ liệu
• Phát triển cơ sở dữ liệu
• Bài giảng cơ sở dữ liệu chương 2
• Bài giảng Quản trị cơ sở dữ liệu
• Ngôn ngữ SQL
• Xây dựng cơ sở dữ liệu
• Khai thác cơ sở dữ liệu
• Hệ quản trị cơ sở dữ liệu quan hệ
• Bài giảng Hệ cơ sở dữ liệu
• Hệ thống xử lý tập tin truyền thống
• Tiếp cận cơ sở dữ liệu
• Môi trường hệ quản trị cơ sở dữ liệu
• Cơ sở dữ liệu ba lược đồ
• bài tập Hệ quản trị cơ sở dữ liệu
• Bài tập cơ sở dữ liệu
• Câu lệnh SQL
• Tổng quan các hàm trong SQL
• Các hàm trên kiểu số
• Bài giảng Cơ sở dữ liệu
• Bài giảng Cơ sở dữ liệu Chương 1
• Tổng quan về cơ sở dữ liệu
• An ninh cơ sở dữ liệu
• Dữ liệu trong cơ sở dữ liệu
• Bài giảng cơ sở dữ liệu chương 11
• Môn Hệ quản trị cơ sở dữ liệu
• Đề thi quản trị cơ sở dữ liệu
• Ôn tập quản trị cơ sở dữ liệu
• Bài thi quản trị cơ sở dữ liệu
• Mô hình quan hệ
• Relational model
• Quy luật bảo toàn dữ liệu
• Ngôn ngữ quan hệ
• Hệ quản trị cơ sở dữ liệu quan hệ
• Bài giảng Tin học cơ sở 3
• Tin học cơ sở 3
• Tổng quan cơ sở dữ liệu quan hệ
• Cách lưu trữ dữ liệu
• Cách truy xuất dữ liệu
• Định nghĩa cơ sở dữ liệu
• Hệ thống cơ sở dữ liệu
• Hệ thống hướng tệp tin
• Hệ thống hướng cơ sở dữ liệu
• Bài giảng cơ sở dữ liệu chương 8
• Mô hình dữ liệu quan hệ
• Lập trình cơ sở dữ liệu
• Thiết kế cơ sở dữ liệu
• Cơ sở dữ liệu nâng cao
• Bài giảng Cơ sở dữ liệu nâng cao
• Quản lý cơ sở dữ liệu
• Khôi phục cơ sở dữ liệu
• Cài đặt cơ sở dữ liệu
• Bài giảng Hệ quản trị cơ sở dữ liệu
• Siêu khóa
• Lược đồ quan hệ
• Đề cương Hệ quản trị cơ sở dữ liệu
• Học phần Hệ quản trị cơ sở dữ liệu
• Mục tiêu cơ sở dữ liệu
• Nội dung cơ sở dữ liệu
• Lưu trữ dữ liệu
• Mô hình quan hệ dữ liệu
• Mô hình dữ liệu
• Liên kế dữ liệu
• Khôi phục dữ liệu
• An toàn dữ liệu
• Cấu trúc dữ liệu