Tìm kiếm trong cơ sở dữ liệu dựa trên từ khóa

- Nguyễn Hoàng Điệp TÌM KIẾM TRONG CƠ SỞ DỮ LIỆU DỰA TRÊN TỪ KHÓA Chuyên ngành: Công nghệ thông tin LUẬN VĂN THẠC SĨ KHOA HỌC CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS.
- Tìm kiếm trong cơ sở dữ liệu.
- Tìm kiếm dựa trên từ khóa.
- Tìm kiếm dựa trên từ khoá trong cơ sở dữ liệu quan hệ.
- 3 Chương 2 TỔNG QUAN TÌM KIẾM TRONG CƠ SỞ DỮ LIỆU DỰA TRÊN TỪ KHÓA.
- Kiến trúc hệ quản trị cơ sở dữ liệu tìm kiếm dựa trên từ khóa.
- Tổ chức lưu trữ dữ liệu.
- Quy trình thực hiện truy vấn từ khóa trong cơ sở dữ liệu.
- 12 Chương 3 XỬ LÝ TRUY VẤN CƠ SỞ DỮ LIỆU DỰA TRÊN TỪ KHÓA.
- Bài toán truy vấn top-k trong cơ sở dữ liệu.
- Bài toán truy vấn top-k.
- Tính ñiểm dữ liệu văn bản theo mô hình vectơ.
- Tính ñiểm dữ liệu văn bản dựa vào trọng số.
- Thuật toán truy vấn top-k.
- Thiết kế cơ sở dữ liệu.
- Kết quả thực nghiệm.
- ếm trong cơ sở dữ liệu Tìm kiếm trong CSDL là tìm kiếm dựa vào cấu trúc của dữ liệu ñược lưu trữ, 1.2.
- Tìm kiếm dựa trên từ khóa Trong một cách tiếp cận khác ñể thực hiện tìm kiếm thông tin, người ta dựa vào việc sử dụng từ khóa và ñối sánh từ khóa với nội dung thông tin ñể ñưa ra các thông tin mà người dùng quan tâm.
- DANH MỤC CÁC HÌNH Hình 2.1 Kiến trúc hệ quản trị cơ sở dữ liệu.
- 11 Hình 2.5 Quy trình thực hiện truy vấn từ khóa trong cơ sở dữ liệu.
- 12 Hình 4.1 Quá trình tìm kiếm thông tin với từ khóa.
- 44 Hình 4.3 Thiết kế kiểu dữ liệu cho các thuộc tính của các bảng CSDL.
- 45 Hình 4.4 Kiến trúc tìm kiếm full-text trong SQL server.
- 46 DANH MỤC CÁC BẢNG Bảng 3.1 Dữ liệu ñầu vào cho ví dụ 3.1.
- 20 Bảng 3.4 Dữ liệu ñầu vào cho ví dụ 3.2.
- 24 Bảng 3.7 Dữ liệu lưu trong bộ nhớ ñệm (bước 1-FA.
- 25 Bảng 3.9 Dữ liệu lưu trong bộ nhớ ñệm (bước 3-FA.
- 26 Bảng 3.10 Dữ liệu sau khi truy cập tuần tự (lần 1-TA.
- 28 Bảng 3.12 Dữ liệu lưu trong bộ nhớ ñệm sau khi thực hiện lần 1.
- 28 Bảng 3.13 Dữ liệu sau khi truy cập tuần tự dữ liệu (lặp lần 1-TA.
- 29 Bảng 3.14 Minh họa truy cập ngẫu nhiên dữ liệu (lặp lần 1-TA.
- 29 Bảng 3.15 Dữ liệu lưu trong bộ nhớ ñệm (lặp lần lần 1-TA.
- 30 Bảng 3.16 Minh họa truy cập ngẫu nhiên dữ liệu (lặp lần 2-TA.
- 30 Bảng 3.17 Dữ liệu lưu trong bộ nhớ ñệm (lặp lần lần 2-TA.
- 31 Bảng 3.18 Minh họa truy cập dữ liệu (lặp lần 3-TA.
- 31 Bảng 3.19 Dữ liệu lưu trong bộ nhớ ñệm (lặp lần lần 3-TA.
- 32 Bảng 3.20 Minh họa truy cập dữ liệu (lặp lần 4-TA.
- 32 Bảng 3.21 Dữ liệu lưu trong bộ nhớ ñệm (lặp lần lần 4-TA.
- 33 Bảng 3.22 Minh họa truy cập dữ liệu (lặp lần 5-TA.
- 33 Bảng 3.23 Dữ liệu lưu trong bộ nhớ ñệm (lặp lần lần 5-TA.
- 34 Bảng 3.24 Dữ liệu lưu trong bộ nhớ ñệm (lần 1-BPA.
- 36 Bảng 3.25 Dữ liệu lưu trong bộ nhớ ñệm (lặp lần 1 BPA.
- 37 Bảng 3.26 Dữ liệu lưu trong bộ nhớ ñệm (lặp lần 2 BPA.
- 38 Bảng 4.1 Dữ liệu trong bảng DETAI.
- 47 Bảng 4.1.1 Kết quả truy vấn chính xác từ “tìm kiếm” trên cột TENDT.
- 48 Bảng 4.1.2 Kết quả truy vấn từ “tìm kiếm” với like trên cột TENDT.
- 48 Bảng 4.1.3 Kết quả truy vấn từ “tìm kiếm” trên cột TENDT.
- 49 Bảng 4.1.4 Kết quả truy vấn từ ‘tìm’ hoặc ‘kiếm’ trên cột TENDT.
- 53 Bảng 4.2.2 Kết quả truy vấn từ “tìm” hoặc “quản” trong bảng DETAI.
- 59 DANH MỤC CÁC KÝ HIỆU VIẾT TẮT Từ viết tắt Viết ñầy ñủ Ý nghĩa BA Basic Algorithm Thuật toán vét cạn BPA Best Position Algorithm Thuật toán vị trí tốt nhất CSDL Cơ sở dữ liệu CNTT Công nghệ thông tin CNPM Công nghệ Phần Mềm DATN ðồ án tốt nghiệp DB DataBase Cơ sở dữ liệu ðSQH ðại số quan hệ FA Fagin’s Algorithm Thuật toán Fagin GV Giáo viên GVHD Giáo viên hướng dẫn IR Information retrieval Hệ thống tìm kiếm thông tin KF Keyword Frequency Tần xuất từ khóa, là số lần 1 từ khóa ñơn xuất hiện trong văn bản KW Keyword Weight Trọng số từ khóa KWBS KeyWord Based Search Tìm kiếm dựa trên từ khóa RKW Relative Keywords Weight Trọng số từ khóa liên quan SQL Structured Query Language SV Sinh viên TA Threshold Algorithm Thuật toán cận 1 Chương 1 1.
- ðẶT VẤN ðỀ Dữ liệu ñược lưu trữ ngày càng nhiều, trong khi sử dụng lại thông tin ñã có là một nhu cầu tất yếu.
- Do ñó, tìm kiếm thông tin ngày càng trở nên quan trọng trong ñời sống nói chung và trong các ứng dụng nói riêng.
- Trong hệ thống thông tin, kết quả tìm kiếm ñược trả về cho người dùng, nên việc xác ñịnh kết quả truy vấn ñể ñảm bảo thông tin có ý nghĩa là một ñiều rất quan trọng.
- Có nhiều cách thức ñể thực hiện tìm kiếm thông tin, ta có thể phân biệt hai hướng tiếp cận chính ñể thực hiện tìm kiếm là tìm kiếm dựa trên cấu trúc của dữ liệu trong cơ sở dữ liệu (CSDL) và tìm kiếm trên nội dung của dữ liệu dựa trên các từ khóa như trong các văn bản, tài liệu, dữ liệu web, dữ liệu không có cấu trúc.
- Tìm kiếm trong cơ sở dữ liệu Tìm kiếm trong CSDL là tìm kiếm dựa vào cấu trúc của dữ liệu ñược lưu trữ, trong ñó sử dụng ngôn ngữ truy vấn.
- Kết quả tìm kiếm là ñầy ñủ và chính xác.
- Tất cả các dữ liệu thỏa mãn ñiều kiện tìm kiếm ñều ñược trả về cho người dùng.
- Trong một CSDL lớn, với một câu truy vấn chứa ít ñiều kiện tìm kiếm ñược thì kết quả trả lại có thể rất nhiều do nhiều dữ liệu cùng thỏa mãn ñiều kiện tìm kiếm (xem ví dụ 4.2.2).
- Ngược lại, với câu truy vấn chứa nhiều ñiều kiện tìm kiếm, số các bản ghi cùng thỏa mãn tất cả các ñiều kiện tìm kiếm là rất ít, thậm chí không có bản ghi nào ñược trả về (truy vấn rỗng) (xem ví dụ 4.1.1, ví dụ 4.2.1).
- Trong cả hai tình huống trên, người dùng ñều gặp khó khăn trong việc xử lý kết quả tìm kiếm.
- Từ khóa là từ hoặc cụm từ ñưa ra ñể thể hiện và phát biểu yêu cầu tìm kiếm.
- Quá trình thực hiện tìm kiếm dựa trên việc ñối sánh từ khóa tìm kiếm với nội dung thông tin lưu trữ.
- Cách tiếp cận này ñược áp dụng chủ yếu cho tìm kiếm trên các tài liệu không có cấu trúc.
- ðể ñảm bảo hiệu quả của phép ñối sánh, hệ thống sẽ khai thác các chỉ mục ñược lập trên dữ liệu ñầu vào lưu trữ trong hệ thống.
- Việc ñánh giá mức ñộ liên quan của một từ khóa tìm kiếm có thể dựa trên sự xuất hiện của một hay nhiều từ khóa tìm kiếm trong tài liệu như tần xuất và kích thước văn bản [5, 17].
- Do ñó việc thực hiện tìm kiếm thông tin dựa trên từ khóa sẽ cho kết quả tìm kiếm là có thứ tự.
- Tìm kiếm dựa trên từ khoá trong cơ sở dữ liệu quan hệ Thực hiện tìm kiếm trong CSDL có một vài hạn chế như kết quả trả về là rỗng hoặc quá nhiều mà kết quả lại không có thứ tự (xem mục 1.1).
- Nếu thực hiện tìm kiếm chính xác trên các trường dữ liệu văn bản dài trong CSDL thì kết quả sẽ thật tệ do việc ñối sánh từng từ truy vấn với xâu văn bản tương ứng với trường dữ liệu tìm kiếm.
- Các kỹ thuật tìm kiếm thông tin tập trung vào so sánh gần ñúng dựa trên từ khóa (kỹ thuật tìm kiếm gần ñúng) và xếp hạng kết quả (kỹ thuật xếp hạng) [17, 23].
- 3 Nếu áp dụng tìm kiếm dựa trên từ khóa (kỹ thuật xếp hạng) trong tìm kiếm thông tin cho tìm kiếm trong CSDL, sử dụng ñiểm ñánh giá cho mỗi ñối tượng có kiểu dữ liệu văn bản trong CSDL, thì kết quả trả lại sẽ là có thứ tự, kết quả tốt hơn sẽ ñược hiển thị trước và thông thường chúng ñược người dùng xem trước.
- Nếu sử dụng kỹ thuật tìm kiếm gần ñúng trong tìm kiếm thông tin cho tìm kiếm trong CSDL, cụ thể là giảm thiểu ñiều kiện truy vấn thì kết quả trả về hầu như chắc chắn sẽ tăng lên, trường hợp kết quả trả về rỗng hoặc quá ít (xem mục 1.1) sẽ ñược giải quyết.
- Mục ñích của luận văn Mục ñích của luận văn là tìm hiểu và tích hợp các kỹ thuật trong tìm kiếm dựa trên từ khóa trong CSDL.
- Việc kết hợp này sẽ giúp cho việc tìm kiếm trong CSDL trở nên linh hoạt hơn và các kết quả tìm kiếm có ”ý nghĩa” hơn với người dùng.
- Trong phạm vi của luận văn này chúng tôi tập trung tìm hiểu một số kỹ thuật hỗ trợ ñánh giá và xếp hạng kết quả tìm kiếm trong CSDL như là các truy vấn dạng top-k.
- Kết quả tìm hiểu về mặt lý thuyết ñược áp dụng vào bài toán quản lý ñồ án ñể minh họa khả năng tìm kiếm trong CSDL dựa vào từ khóa.
- Phần tiếp theo của luận văn ñược tổ chức như sau: Chương hai giới thiệu tổng quan về tìm kiếm trong CSDL dựa trên từ khóa.
- Phần này tập trung vào tổ chức lưu trữ và truy cập dữ liệu phục vụ cho việc tìm kiếm thông tin.
- Chương ba tập trung trình bày các kỹ thuật hỗ trợ việc tìm kiếm dựa vào từ khóa trong CSDL.
- Chương bốn phát biểu bài toán quản lý ñồ án, trong ñó phạm vi của ứng dụng tập trung chủ yếu vào việc sử dụng kỹ thuật tìm kiếm trong CSDL dựa vào từ khóa.
- TỔNG QUAN TÌM KIẾM TRONG CƠ SỞ DỮ LIỆU DỰA TRÊN TỪ KHÓA 2.1.
- Kiến trúc hệ quản trị cơ sở dữ liệu tìm kiếm dựa trên từ khóa Sử dụng triệt ñể hệ quản trị CSDL ñã có bằng cách biến ñổi từ khóa truy vấn ñầu vào thành câu truy vấn trong hệ thống, hay tích hợp thêm tìm kiếm dựa trên từ khóa trong một hệ quản trị CSDL.
- Tuy nhiên, về kiến trúc tổng thể, nhìn chung các modul chính trong hệ quản trị CSDL có tính năng tìm kiếm dựa trên từ khóa không khác gì so với hệ quản trị CSDL thông thường.
- Hình 2.1 Kiến trúc hệ quản trị cơ sở dữ liệu Bộ quản lý lưu trữ dữ liệu có nhiệm vụ lưu trữ và truy xuất dữ liệu trên các thiết bị nhớ ngoài, tổ chức tối ưu dữ liệu trên thiết bị nhớ và tương tác hiệu quả với bộ quản lý tệp trong quá trình ñiều khiển việc ñọc/ghi dữ liệu qua lại giữa bộ nhớ và thiết bị lưu trữ tương tác với bộ quản lý giao dịch [21].
- CSDL Xử lý Quản lý giao dịch Quản lý lưu trữ dữ liệu 6 ðể phục vụ hiệu quả yêu cầu tìm kiếm, bộ quản lý lưu trữ phải lựa chọn các cấu trúc lưu trữ phù hợp với các yêu cầu tìm kiếm.
- Các tổ chức vật lý thường dùng là tổ chức tệp chỉ dẫn trên các trường dữ liệu.
- Tuy nhiên, ñể phục vụ tìm kiếm trên từ khóa, ngoài các chỉ dẫn trên các trường dữ liệu thường phải tạo thêm chỉ mục term trên trường dữ liệu thực hiện tìm kiếm từ khóa [2, 19].
- Bộ quản lý giao dịch trong các hệ quản trị CSDL ñảm bảo tính nhất quán và tính ñúng ñắn của dữ liệu.
- Bộ này thực hiện công việc quản lý ñiều khiển tương tranh, phát hiện lỗi và phục hồi cơ sở dữ liệu.
- Bộ xử lý truy vấn hỗ trợ người dùng phát biểu yêu cầu tìm kiếm.
- Phân tích yêu cầu tìm kiếm, xử lý và tối ưu yêu cầu tìm kiếm, thực thi và trả lại kết quả cho người dùng tương ứng với yêu cầu tìm kiếm.
- Phần tiếp theo tập trung vào hai thành phần cần có những ñiều chỉnh cập nhật ñể phục vụ tìm kiếm với từ khóa trong CSDL.
- Tổ chức lưu trữ dữ liệu ðể lưu trữ dữ liệu trong bộ nhớ thì có nhiều cách lưu trữ, cũng như có thể lưu trữ nhiều nơi.
- Nếu xét cách lưu trữ dữ liệu theo cách phân chia dữ liệu trên bộ nhớ trong và bộ nhớ ngoài.
- Do một CSDL yêu cầu khối lượng lưu trữ lớn, nên ở ñây chỉ xét việc lưu trữ dữ liệu trong bộ nhớ ngoài.
- Lưu trữ và tìm kiếm thông tin ở bộ nhớ ngoài có một số kiểu dữ liệu cơ bản là: Tệp có chỉ mục, tệp băm và B-cây.
- Sau ñây là chi tiết về cấu trúc dữ liệu bộ nhớ ngoài, sau ñó là chi tiết về các kiểu lưu trữ về tệp và B-cây.
- B-cây Cây tìm kiếm m nhánh là sự tổng quát hoá của cây tìm kiếm nhị phân, trong ñó mỗi ñỉnh của cây có nhiều nhất m con.
- Các phép toán tìm kiếm, xen vào và loại bỏ trên cây tìm kiếm m nhánh ñược thực hiện bằng các kỹ thuật tương tự cây tìm kiếm nhị phân.
- B-cây là một loại ñặc biệt của cây tìm kiếm m nhánh cân bằng [3].
- B-cây cấp m là cây tìm kiếm m nhánh thoả mãn các tính chất: Nếu cây có nhiều hơn hai nút thì gốc có ít nhất hai con và nhiều nhất m con

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt