Luận văn Ứng dụng phân hạng tổng hợp cho bài toán so khớp lược đồ

1 Chương 1 Dẫn nhập 1.1. Giới thiệu về so khớp lược đồ Những năm gần đây, cơ sở dữ liệu trên Web phát triển rất nhanh chóng, nghiên cứu vào tháng 4/2004 của K. C.-C. Chang và các đồng sự [3] cho biết có 450000 cơ sở dữ liệu trực tuyến. Nguồn thông tin web càng phát triển thì nhu cầu tích hợp dữ liệu càng tăng lên nhanh chóng. So khớp lược đồ là thao tác cơ sở của quá trình tích hợp dữ liệu, nó đóng vai trò trung tâm trong nhiều lĩnh vực ứng dụng khác nhau như: tích hợp lược đồ (Schema integration), kho dữ liệu (Data warehouses), thương mại điện tử (E-commerce), xử lý truy vấn ngữ nghĩa (Semantic query processing),… So khớp lược đồ xác định sự tương ứng hoặc so khớp về ngữ nghĩa giữa các khái niệm mô tả ý nghĩa của dữ liệu trong những nguồn dữ liệu phân tán không đồng nhất (như các lược đồ cơ sở dữ liệu, XML DTD, các HTML form tags,…). Kết quả so khớp lược đồ hay ánh xạ lược đồ bao gồm tập tất cả các so khớp có thể có giữa các phần tử của hai lược đồ. So khớp lược đồ được xác định là một trong những thao tác cơ bản trong nhiều xử lý tích hợp dữ liệu [2], vì vậy kết quả so khớp ảnh hưởng rất lớn đến kết quả tích hợp dữ liệu. Ánh xạ lược đồ (kết quả của quá trình so khớp) có thể ứng dụng trong quá trình phát sinh lược đồ toàn cục, viết lại câu truy vấn trên các nguồn không đồng nhất, loại bỏ dữ liệu trùng lắp,… Bài toán so khớp lược đồ phát sinh khi giải quyết bài toán tích hợp lược đồ, và trong quá trình nghiên cứu, so khớp lược đồ còn là giải pháp cho những vấn đề liên quan đến sự không đồng nhất về ngữ nghĩa mà các hệ thống máy tính đang phải đối mặt. Chẳng hạn, hai doanh nghiệp muốn thực hiện việc sáp nhập với nhau thành một doanh nghiệp có quy mô lớn hơn. Về mặt kỹ thuật, những doanh nghiệp này phải tích hợp các cơ sở dữ liệu của họ. Để tích hợp cơ sở dữ liệu, các xử lý kỹ thuật 2 thường thực hiện theo hai bước (1) xác định những phần tử (như các thuộc tính, kiểu dữ liệu,…) tương ứng ngữ nghĩa giữa các thực thể có liên quan với nhau của hai lược đồ, đây là quá trình so khớp lược đồ, (2) tích hợp hai cơ sở dữ liệu ban đầu dựa vào kết quả xử lý ở bước 1. Vậy, so khớp lược đồ là quá trình xác định các cặp phần tử tương ứng ngữ nghĩa giữa các thực thể có liên quan với nhau của hai lược đồ, các phần tử này được gọi là so khớp với nhau. Ví dụ 1.1 Cho hai lược đồ, mỗi lược đồ có một quan hệ chứa thông tin về khách hàng, ví dụ về so khớp hai lược đồ này được mô tả ở Hình 1.1. So khớp lược đồ là xác định tập các ánh xạ thể hiện sự so khớp giữa các phần tử của hai lược đồ. Thuộc tính Mã KH trong lược đồ thứ nhất so khớp với thuộc tính Mã Khách hàng trong lược đồ thứ hai, tập thuộc tính {Họ, Tên lót, Tên} trong lược đồ thứ nhất so khớp với thuộc tính Họ tên trong lược đồ thứ hai, thuộc tính Ngày sinh so khớp với Năm sinh và hai thuộc tính địa chỉ trong hai lược đồ so khớp với nhau. Hình 1.1- Ví dụ về so khớp lược đồ So khớp lược đồ là thao tác cơ bản trong nhiều ứng dụng khác nhau như tích hợp lược đồ, kho dữ liệu (Data warehouses), thương mại điện tử (E-commerce), xử 3 lý truy vấn ngữ nghĩa (Semantic query processing),… Vì vậy trong hai thập kỷ qua đã có nhiều nghiên cứu về so khớp lược đồ. 1.2. Một số ứng dụng của bài toán so khớp lược đồ 1.2.1. Tích hợp lược đồ Nhóm tác giả J. Euzenat và P.Shvaiko[12] đưa ra một kịch bản tích hợp lược đồ như sau: Cho hai cơ sở dữ liệu CSDL1 và CSDL2 lưu trữ dữ liệu về các đầu sách của hai thư viện. Khi hai thư viện này được sáp nhập lại với nhau, yêu cầu được đặt ra là phải xây dựng một lược đồ toàn cục cung cấp giao diện thống nhất và trong suốt với người dùng khi truy cập hai cơ sở dữ liệu cục bộ CSDL1 và CSDL2. Quá trình xử lý tích hợp lược đồ được minh họa trong Hình 1.2 Hình 1.2 – Ví dụ ứng dụng so khớp lược đồ trong lĩnh vực tích hợp lược đồ Khi người dùng tìm kiếm thông tin về một quyển sách, câu truy vấn được viết trên lược đồ toàn cục. Câu truy vấn toàn cục này được gởi đến bộ xử lý trung 4 gian, bộ xử lý trung gian lại chuyển cho bộ so khớp lược đồ để tìm các phần tử trong lược đồ cục bộ tương ứng với các phần tử trong câu truy vấn toàn cục, khi nhận được kết quả so khớp, bộ xử lý trung gian biến đổi câu truy vấn toàn cục thành câu truy vấn cục bộ và gởi đến cơ sở dữ liệu cục bộ. Kết quả truy vấn trên cơ sở dữ liệu lại được trả về bộ so khớp trung gian, thực hiện so khớp lược đồ và biến đổi kết quả truy vấn cục bộ thành kết quả toàn cục và gởi kết quả lại cho lược đồ toàn cục tổng hợp kết quả và trả về cho người dùng. 1.2.2. Kho dữ liệu Một biến thể của bài toán tích hợp lược đồ đã trở nên phổ biến từ những năm 1990 là tích hợp các nguồn dữ liệu vào một kho dữ liệu. Kho dữ liệu là một cơ sở dữ liệu hỗ trợ ra quyết định được rút trích từ một tập nguồn dữ liệu. Quá trình rút trích đòi hỏi phải biến đổi dữ liệu từ định dạng nguồn sang định dạng của kho dữ liệu. Thao tác so khớp được ứng dụng trong việc thiết kế các phép biến đổi. Cho một nguồn dữ liệu, việc tạo ra những phép biến đổi thích hợp bắt đầu bằng cách tìm những phần tử của nguồn dữ liệu có trong kho dữ liệu, đây là một thao tác so khớp. Sau khi thực hiện so khớp lược đồ, với mỗi cặp phần tử tương ứng, người thiết kế kho dữ liệu xác định ngữ nghĩa của mỗi phần tử của nguồn dữ liệu và biến đổi tương ứng với ngữ nghĩa của phần tử của kho dữ liệu tương ứng. 1.2.3. Thương mại điện tử Thương mại điện tử ứng dụng so khớp lược đồ trong quá trình dịch thông điệp. Các đối tác kinh doanh thường xuyên trao đổi thông điệp mô tả các giao dịch kinh doanh. Thông thường, mỗi đối tác sử dụng một định dạng thông điệp riêng, định dạng của mỗi thông điệp có thể khác nhau về cấu trúc, như cấu trúc EDI (electronic data interchange – trao đổi dữ liệu điện tử), XML, … Họ cũng có thể sử dụng những lược đồ thông điệp khác nhau. Khi doanh nghiệp cần chuyển một thông điệp cho đối tác của họ, vì hai doanh nghiệp sử dụng định dạng thông điệp khác nhau nên cần phải xây dựng một 5 bộ dịch thông điệp để giúp các đối tác hiểu được thông điệp của nhau. Mô hình dịch thông điệp được minh họa trong Hình 1.3. Hình 1.3 -Ví dụ ứng dụng so khớp lược đồ trong lĩnh vực thương mại điện tử Khi doanh nghiệp cần chuyển một thông điệp cho đối tác, doanh nghiệp sẽ gởi thông điệp đến bộ dịch thông điệp. Bộ dịch thông điệp chuyển thông điệp cho bộ so khớp lược đồ để thực hiện việc so khớp các phần tử trong định dạng thông điệp của doanh nghiệp và đối tác. Khi có kết quả so khớp lược đồ, bộ dịch thông điệp biến đổi định dạng của thông điệp ban đầu thành định dạng thông điệp của đối tác. 1.3. Một số thách thức của bài toán so khớp lược đồ So khớp lược đồ là công việc xác định những tương ứng ngữ nghĩa giữa các phần tử trong hai lược đồ và là thao tác cơ bản trong nhiều lĩnh vực dữ liệu khác nhau như tích hợp dữ liệu, kho dữ liệu,….Tuy nhiên cho đến nay, so khớp lược đồ chủ yếu được thực hiện thủ công và là một xử lý rất khó. Khó khăn nảy sinh do những nguyên nhân sau: 6 • Vấn đề biểu diễn: các cơ sở dữ liệu được thiết kế bởi những người khác nhau, vì vậy thậm chí những lược đồ của những khái niệm giống nhau có mô hình biểu diễn khác nhau, tên và cấu trúc cũng khác nhau. Ngược lại, những lược đồ có thể có mô hình tương tự nhau nhưng nội dung lại khác nhau. Chúng có thể được biểu diễn bởi những mô hình dữ liệu khác nhau, chúng có thể sử dụng những từ tương tự nhau để mô tả những ý nghĩa khác nhau,… • Vấn đề ngữ nghĩa: ngữ nghĩa của những phần tử liên quan có thể được suy diễn từ một vài nguồn thông tin như từ điển, WordNet,…. • Vấn đề chi phí tính toán: khi xác định một phần tử s của lược đồ S1 so khớp với phần tử s’ của lược đồ S2, phải kiểm tra tất cả những phần tử khác của S2 để chắc rằng không có phần tử nào khác của S2 so khớp với s hơn s’. 1.4. Giải pháp cho bài toán so khớp lược đồ Trong hai thập kỷ qua, có rất nhiều công trình nghiên cứu tập trung nghiên cứu để tìm giải pháp cho bài toán so khớp lược đồ. Nhiều giải pháp so khớp khác nhau đã được đề xuất theo nhiều hướng tiếp cận khác nhau, chúng khai thác những đặc trưng của lược đồ như cấu trúc, thể hiện dữ liệu, ràng buộc, …sử dụng các kỹ thuật từ các lĩnh vực khác như tìm kiếm thông tin, trí tuệ nhân tạo,… Ban đầu, các công trình nghiên cứu chỉ tập trung nghiên cứu theo hướng cải thiện các kỹ thuật so khớp lược đồ cơ bản như kỹ thuật so khớp chuỗi, so khớp ngôn ngữ, so khớp dựa vào ràng buộc,…Sau đó, các nhóm nghiên cứu tập trung nghiên cứu theo nhiều hướng khác nhau. Một trong những hướng tiếp cận được tập trung nghiên cứu là tìm các chiến lược kết hợp các kỹ thuật so khớp cơ bản nhằm khai thác các ưu điểm và khắc phục những hạn chế của từng kỹ thuật, qua đó có thể tăng độ chính xác và độ phủ của kết quả trả về. Một hướng tiếp cận khác cũng được tập trung nghiên cứu là tìm top-k ánh xạ trả về thay vì trả về chỉ một ánh xạ lược đồ như các hướng tiếp cận khác. 7 Tuy nhiên cho đến nay vẫn chưa có giải pháp nào đáp ứng được yêu cầu của người dùng. Vì vậy, bài toán so khớp lược đồ vẫn đang là vấn đề được tập trung nghiên cứu theo nhiều hướng khác nhau. Do đó luận văn đã đề ra các mục tiêu sau: (1) tìm hiểu một số thành tựu đạt được trong lĩnh vực so khớp lược đồ (2) cài đặt thử nghiệm một số thuật toán phân hạng tổng hợp đã được phát triển trong lĩnh vực tìm kiếm thông tin cho bài toán so khớp lược đồ với mong muốn có thể nâng chất lượng của kết quả so khớp. Chất lượng kết quả sẽ được đánh giá tương tự như trong lĩnh vực tìm kiếm thông tin: đó là độ chính xác và độ phủ của kết quả trả về. 1.5. Cấu trúc luận văn Bố cục của luận văn được chia thành năm chương như sau: Chương 1: Giới thiệu tổng quan về bài toán so khớp lược đồ, các lĩnh vực ứng dụng, thao tác so khớp và những thách thức gặp phải trong quá trình so khớp lược đồ; và giới thiệu về luận văn. Chương 2: Trình bày chi tiết một số thành tựu đạt được theo hướng tiếp cận trả về một ánh xạ lược đồ trong lĩnh vực so khớp lược đồ. Chương 3: Trình bày một thành tựu mới theo hướng tiếp cận phân hạng top-k ánh xạ lược đồ. Chương 4: Trình bày một số thuật toán phân hạng tổng hợp trong các máy tìm kiếm liên hợp (metasearch engine) trong lĩnh vực tìm kiếm thông tin (Information Retriaval), đề xuất áp dụng các thuật toán này cho bài toán so khớp lược đồ, thử nghiệm phần cài đặt trên bộ số liệu thử nghiệm và đánh giá kết quả. Chương 5: Kết luận và hướng phát triển.