Luận văn Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng vnmatch

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ------------------------------------------ LUẬN VĂN THẠC SĨ KHOA HỌC TÌM HIỂU VỀ ĐỐI SÁNH LƯỢC ĐỒ VÀ XÂY DỰNG ỨNG DỤNG VNMATCH NGÀNH: CÔNG NGHỆ THÔNG TIN NGÔ VĂN QUÂN HÀ NỘI 2006 i Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 Lời cảm ơn Trong lời đầu tiên của báo cáo luận văn tốt nghiệp “Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch” này, tôi muốn gửi những lời cảm ơn và biết ơn chân thành của mình tới tất cả những người đã hỗ trợ, giúp đỡ tôi về chuyên môn, vật chất và tinh thần trong quá trình thực hiện Đồ án. Trước hết, tôi xin chân thành cảm ơn TS. Nguyễn Kim Anh, bộ môn Hệ thống thông tin, Khoa Công nghệ thông tin trường Đại học Bách khoa Hà Nội, người đã trực tiếp hướng dẫn, nhận xét, giúp đỡ tôi trong suốt quá trình thực hiện luận văn. Xin chân thành cảm ơn Khoa Công nghệ thông tin, Trung tâm Đào tạo và Bồi dưỡng sau đại học Trường Đại học Bách Khoa Hà Nội đã giúp đỡ tôi trong suốt quá trình học tập và nghiên cứu. Tôi cũng muốn gửi lời cảm ơn tới TS. Đỗ Hồng Hải1, tác giả của hệ thống COMA++; anh Lê Hồng Phương2 tác giả của vnTokenizer, vnLTag; Enrico May, sinh viên nghiên cứu về dự án Cupid. Tôi cũng xin bày tỏ lòng biết ơn đến gia đình và những người bạn thân đã giúp đỡ, động viên tôi rất nhiều trong suốt quá trình học tập và làm luân văn tốt nghiệp. Do thời gian thực hiện có hạn, kiến thức chuyên môn còn nhiều hạn chế nên đồ án tôi thực hiện chắc chắn không tránh khỏi những thiếu sót nhất định. Tôi rất mong nhận được ý kiến đóng góp của thầy, cô giáo và các bạn. Xin chân thành cảm ơn ! Hà Nội, ngày 09 tháng 10 năm 2006 1 2 Lê Hồng Phương, công tác tại trường Đại Học Quốc Gia Hà Nội, hiện đang làm nghiên cứu sinh tại Pháp ii Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 Chương 1 Mở đầu.............................................................................1 1 Đối sánh lược đồ..........................................................................2 2 Sự hỗn tạp ngữ nghĩa...................................................................3 3 Định nghĩa bài toán......................................................................6 3.1 Schemas..............................................................................6 3.2 Đầu vào bài toán (Input)........................................................7 3.3 Đầu ra bài toán (Output)........................................................7 3.4 Kiến trúc chung ....................................................................8 4 Ứng dụng của bài toán đối sánh lược đồ ..........................................9 4.1 Các ứng dụng tích hợp dữ liệu và data warehouse......................9 4.2 E-Business ......................................................................... 11 4.3 Semantic Web .................................................................... 12 5 Các vấn đề mở .......................................................................... 13 5.1 Khả năng biểu diễn của ngôn ngữ.......................................... 13 5.2 Làm việc với các lược đồ có kích thước lớn .............................. 13 5.3 Sự kết hợp của các phương pháp đối sánh .............................. 14 Chương 2 Các phương pháp tiếp cận................................................. 15 1 Các dự án liên quan ................................................................... 15 1.1 COMA++ ........................................................................... 15 1.2 SEMINT ............................................................................. 16 1.3 LSD .................................................................................. 16 1.4 SKAT................................................................................. 16 1.5 TransScm .......................................................................... 16 1.6 DIKE ................................................................................. 17 1.7 SIMILARITY FLOODING........................................................ 17 1.8 Cupid ................................................................................ 17 2 Các phương pháp đối sánh lược đồ ............................................... 20 2.1 Tiêu chuẩn phân loại ........................................................... 20 2.2 Đối sánh dựa trên schema (schema-based) ............................ 21 2.2.1 Phương pháp tiếp cận dựa trên ngôn ngữ (linguistic).......... 22 2.2.2 Phương pháp tiếp cận dựa trên ràng buộc......................... 23 2.2.3 Phương pháp tiếp cận dựa trên cấu trúc ........................... 23 2.3 Đối sánh dựa trên dữ liệu..................................................... 23 2.4 Đối sánh kết hợp................................................................. 24 2.5 Match Cardinality ................................................................ 24 2.6 Các hệ số mặc định trong bài toán đối sánh ............................ 25 3 Các phương pháp đánh giá hệ thống đối sánh ................................ 26 Chương 3 Thiết kế hệ thống đối sánh lược đồ. .................................... 30 1 Khảo sát................................................................................... 30 2 Giới thiệu ................................................................................. 33 2.1 Giới thiệu bài toán đối sánh lược đồ. ...................................... 33 2.2 Xử lý schema trong tiếng Việt ............................................... 33 3 Thiết kế.................................................................................... 35 iii Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 3.1 Kiến trúc hệ thống .............................................................. 35 3.2 Input ................................................................................ 36 3.2.1 Schema ..............................Error! Bookmark not defined. 3.2.2 WordNet ...................................................................... 39 3.2.3 Output ........................................................................ 40 3.3 Mức ngôn ngữ (linguistic matching) ....................................... 41 3.3.1 Các thuật toán đối sánh cơ bản ....................................... 42 3.3.2 Thuật toán đối sánh kết hợp ........................................... 44 3.4 Mức cấu trúc ...................................................................... 51 3.5 Chọn lựa ánh xạ ................................................................. 55 4 Cài đặt và kết quả ..................................................................... 56 4.1 Cài đặt .............................................................................. 56 4.2 Kết quả thử ngiệm .............................................................. 60 5 Kết luận và hướng phát triển ....................................................... 71 5.1 Kết luận ............................................................................ 71 5.2 Hướng phát triển ................................................................ 72 Tài liệu tham khảo ............................................................................. 75 Sách, bài báo, luận văn.................................................................... 75 Website ......................................................................................... 75 iv Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 Mục lục hình ảnh Hình 1-1: Đối sánh lược đồ 2 Hình 1-2: Xung đột ngôn ngữ 5 Hình 2-1: Schemas 7 Hình 2-2: Kiến trúc chung của bài toán đối sánh lược đồ 8 Hình 2-3: Minh họa hệ thống tích hợp dữ liệu giúp người dùng tìm văn bản 10 Hình 2-4: Data warehouse 11 Hình 2-5: Kiến trúc COMA++ 15 Hình 2-6: Kiến trúc SEMINT Error! Bookmark not defined. Hình 2-7: Các phương pháp đối sánh lược đồ 20 Hình 2-8: Xây dựng các hệ số ưu tiên 26 Hình 2-9: Đánh giá hệ thống đối sánh 27 Hình 2-10: So sánh F-Measure và Overall 28 Hình 3-1: Sự hỗn tạp của các nguồn dữ liệu 31 Hình 3-2:Lược đồ văn bản 33 Hình 3-3: Kiến trúc hệ thống 36 Hình 3-4: Hợp nhất các lược đồ phân tán 38 Hình 3-5: Hợp nhất các kiểu thiết kế schema 38 Hình 3-6: Loại bỏ nút có kiểu đơn giản 38 Hình 3-7: Tái sử dụng các định nghĩa 39 Hình 3-8:Sơ đồ đối sánh mức ngôn ngữ (linguistic matching) 41 Hình 3-9: Sơ đồ thuật toán đối sánh kết hợp 45 Hình 3-10: Phân tích phần tử đầu vào 46 Hình 3-11: Thực hiện bước Direction và Selection 48 Hình 3-12: Tổng hợp kết quả 49 Hình 3-13: SimCube theo phương pháp đối sánh kết hợp 50 Hình 3-14: Kết quả sau khi thực hiện Aggregation 50 Hình 3-15: Kết quả sau khi thực hiện Direction và Selection 50 Hình 3-16:Kết quả sau khi tổng hợp 51 Hình 3-17: Hệ số tương tự của 2 node lá 52 Hình 3-18: Hệ số tương tự của 2 node trong 52 Hình 3-19: Sự phụ thuộc của hệ số tương tự vào ngữ cảnh 55 Hình 3-20:Cấu trúc VNMatch 57 Hình 3-21: MatchLib, phần core của VNMatch 57 Hình 3-22: Lớp HybridMatcher 58 Hình 3-23: VNMatch Framework (đề xuất) 73 v Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 Mục lục các công thức Công thức 1: Cupid, hệ số tương tự của hai tập hợp................................ 19 Công thức 3 ...................................................................................... 19 Công thức 4 ...................................................................................... 19 Công thức 2: Công thức EditDistance biến đổi ........................................ 42 Công thức 3: Lấy Max......................................................................... 47 Công thức 4: Lấy theo trọng số............................................................ 47 Công thức 5: Lấy theo trung bình......................................................... 47 Công thức 6: AverageSim ................................................................... 49 Công thức 7: DiceSim......................................................................... 49 Công thức 8: Wsim cho các node lá ...................................................... 54 Công thức 9: Liên kết mạnh ................................................................ 54 Công thức 10: ssim trong trường hợp là các node trong........................... 54 vi Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 Bảng các từ viết tắt và thuật ngữ Tiếng Anh Ý nghĩa Ghi chú Data integration Tích hợp dữ liệu Data translation Chuyển đổi dữ liệu Data warehouse Nhà kho dữ liệu DTD Document Type Definition Global schema Lược đồ tổng thể Holonym Bao hàm phần tử “Cây” bao hàm phần tử “Thân cây” Hypernym Bao hàm khái niệm thuật ngữ “Thực vật” bao hàm khái niệm “Cây” Hyponym Ngược với Hypernym “Cây” nằm trong khái niệm “thực vật” Local schema Lược đồ địa phương Meronym Ngược với Holonym “Thân cây” là bộ phận của cây Ontology Đặc tả của khái niệm OWL Web Ontology Language Schema Lược đồ dữ liệu Schema integration Tích hợp lược đồ vii Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 Semantic integration Tích hợp ngữ nghĩa Schema mapping Ánh xạ lược đồ, tương tự đối sánh lược đồ Schema matching Đối sánh lược đồ Synonym Từ đồng nghĩa Web Semantic Web ngữ nghĩa XSD XML Schema Definition viii Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 Tóm tắt luận văn Luận văn cao học với đề tài “Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch” nghiên cứu và tìm hiểu về bài toán đối sánh lược đồ (schema matching). Bài toán đối sánh lược đồ được áp dụng trong các ứng dụng tích hợp dữ liệu (data integration), chuyển đổi dữ liệu (data translation), nhà kho dữ liệu (data warehousing), các ứng dụng web ngữ nghĩa (Web Semantic). Bài toán đối sánh lược đồ có thể được định nghĩa như sau: “Cho hai lược đồ S1 và S2 hãy tìm sự tương đồng giữa các phần tử của S1và S2 bằng cách khai thác tất cả các thông tin tồn tại trong hai lược đồ đó, trong dữ liệu và các nguồn thông tin hỗ trợ khác”. Luận văn tập trung nghiên cứu các phương pháp đối sánh lược đồ dựa trên các dự án đã được phát triển của các viện nghiên cứu, trường đại học và công ty trên thế giới, tìm hiểu và đề xuất một số phương pháp xử lý cho lược đồ được thiết kế dùng tiếng Việt. Đồng thời thiết kế và thi công một hệ thống đối sánh lược đồ, được gọi là VNMatch. VNMatch xử lý đầu vào là hai lược đồ được thiết kế dùng ngôn ngữ XML Schema, kết quả đầu ra là tập các ánh xạ có sự tương đồng về mặt ngữ nghĩa giữa các phần tử của hai lược đồ đó. Từ khóa: Schema matching, semantic integration, schema mapping, matcher; đối sánh lược đồ, ánh xạ lược đồ, tích hợp ngữ nghĩa, tích hợp dữ liệu. 1 Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 Chương 1 Mở đầu Mục tiêu chính của luận văn tốt nghiệp này là nghiên cứu về bài toán đối sánh lược đồ (schema matching). Đối sánh lược đồ là quá trình xác định ngữ nghĩa tương ứng giữa các cấu trúc siêu dữ liệu (metadata) như lược đồ của cơ sở dữ liệu, XSD, Ontology. Đối sánh lược đồ đóng vai trò quan trọng trong các việc tương tác giữa các dịch vụ với nhau và trong ứng dụng tích hợp dữ liệu, Data warehouse, E-Business. 2 Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 1 Đối sánh lược đồ Một lược đồ là một cấu trúc siêu dữ liệu để mô tả dữ liệu được lưu giữ, truy cập, diễn dịch bởi người dùng và các ứng dụng như thế nào. Ngoài các khía cạnh liên quan đến quản lý dữ liệu như định dạng dữ liệu, kiểu dữ liệu, lược đồ còn có sự mở rộng liên quan đến ngữ nghĩa của dữ liệu như tập các giá trị cho phép, các yếu tố tập hợp, toàn vẹn và ràng buộc tham chiếu… Hiện tại có nhiều ngôn ngữ biểu diễn lược đồ đã được phát triển cho các lĩnh vực ứng dụng khác nhau, ví dụ như SQL, DTD, XSD, OWL. Mặc dù có nhiều khả năng và ngôn ngữ biểu diễn khác nhau nhưng lược đồ đã xuất hiện có thể nói là khắp nơi trong hầu hết các ứng dụng về quản lý dữ liệu và xử lý dữ liệu. category publishDate org_id ND 22/10/1990 15 TT 22/09/1999 32 topic publishDate org_name ND 22/10/1990 Bộ tài chính TT 22/09/1999 Bộ thương mại id name 15 Bộ tài chính 32 Bộ thương mại Hình 1-1: Đối sánh lược đồ Hình 1-1 minh họa cho việc tích hợp dữ liệu sử dụng kịch bản đơn giản trong đó ta muốn tích hợp nguồn dữ liệu S vào nguồn dữ liệu T. Cả S và T đều chứa thông tin về cơ sở dữ liệu văn bản pháp quy nhưng trong S người ta dùng hai bảng để biểu diễn, còn trong T người ta sử dụng 1 bảng để biểu diễn, công việc của chúng ta là xây dựng quá trình tự động ánh xạ các phần tử tương đương giữa các phần tử của S với các phần tử của T: S-›category ‹-› T-›Topic 3 Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 Quá trình tự động này người ta gọi chung là đối sánh lược đồ (schema matching). Nó là chìa khóa trong các ứng dụng tích hợp dữ liệu và chuyển đổi dữ liệu. 2 Sự hỗn tạp ngữ nghĩa Việc xác định các thành phần tương đương nhau giữa hai lược đồ cần sự phân tích ngữ nghĩa trong các lược đồ đó hay nói cách khác chính là sự suy diễn ngược lại các khái niệm về lược đồ của người tạo ra nó. Qúa trình này nếu có thể thực hiện được thì sẽ gặp rất nhiều khó khăn vì sự xung đột giữa các nguồn thông tin hỗn tạp cần được xem xét, ví dụ như lược đồ, dữ liệu, tài liệu đặc tả, tình trạng dữ liệu… Việc trích lọc ngữ nghĩa chính xác từ các thông tin metadata này một cách tự động thực sự là một việc nặng nhọc và không có một phương pháp chuẩn nào để thực hiện. Lược đồ cung cấp nhiều thông tin mà chúng ta có thể khai thác chúng để thu nhận được ngữ nghĩa của các phần tử chứa trong lược đồ đó. Ví dụ như các thuộc tính name, description, constraints…Tuy nhiên các thông tin này có thể khác nhau giữa các lược đồ, chúng phụ thuộc vào ngôn ngữ biểu diễn, cấu trúc biểu diễn, ... Vì các lược đồ thường được thiết kế bởi những người khác nhau với những nhận thức khác nhau về thế giới thực cho các mục đích khác nhau. Dưới đây chúng ta tìm hiểu và phân loại những khó khăn, thách thức gặp phải khi nghiên cứu về giải pháp cho bài toán đối sánh lược đồ. Cho 2 cơ sở dữ liệu với hai lược đồ tương ứng S , T. Chúng ta phải xử lý để tự động để xác định được sự tương ứng giữa phần tử category trong S với topic trong T, và name trong S với org_name trong T, nghĩa là s trong S và t trong T cùng mô tả chung một khái niệm trong một lĩnh vực nào đó thì chúng được coi là tương đương. Điều này là một thách thức cho chúng ta vì một số yếu tố sau: Lược đồ • Ngữ nghĩa của các phần tử chỉ được suy diễn từ một số ít các thông tin như người tạo, chú thích, các lược đồ và dữ liệu liên quan. Trích lọc ngữ nghĩa 4 Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 từ các thông tin như vây thực sự là bài toán khó vì những thông tin metadata đó thường không được đầy đủ và chính xác, chú thích không đủ, không phù hợp, trong nhiều trường hợp xây dựng các hệ thống tích hợp dữ liệu qua Web những thông tin metadata đó còn không thể truy cập được. • Do các phần tử của lược đồ thường được đối sánh dựa trên các thông tin hỗ trợ trong lược đồ và dữ liệu. Ví dụ như name, type, value, cấu trúc và các ràng buộc, nhưng các thông tin này không thực sự có thể tin cậy được. Ví dụ các một từ có thể mô tả hai khái niệm khác nhau trong thế giới thực hoặc ngược lại, một khái niệm được phân rã mức chi tiết với cấu trúc khác nhau • Các ràng buộc toàn vẹn thực tế thường được xử lý trong các chương trình truy cập dữ liệu chứ nó không được thể hiện trong lược đồ. • Để xác định được phần tử s trong S được match với t trong T thì một là phải kiểm tra trong tất cả các phần tử trong T để không có phần tử nào khác trong T tốt hơn s. Điều này ảnh hưởng lớn đến hiệu năng của qúa trình tích hợp Dữ liệu Đối với dữ liệu chúng ta còn gặp các trở ngại sau • Các giá trị khác nhau được sử dụng cho cùng một thông tin, ví dụ như F và Female để biểu diễn thông tin giới tính chẳng hạn • Các giá trị được lưu giữ không nhất quán về định dạng, ví dụ như sử dụng Kb và Mb để lưu giữ kích thước dữ liệu chẳng hạn • Dữ liệu không nhất quán về thời gian • Dữ liệu có thể chứa lỗi, sai chính tả, thiếu giá trị, dư thừa .. Dưới đây là một số hình ảnh thể hiện sự xung đột giữa các lược đồ 5 Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 Hình 1-2: Xung đột ngôn ngữ 6 Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch Ngô Văn Quân, lớp cao học CNTT 2004 3 Định nghĩa bài toán Bài toán đối sánh lược đồ có thể được định nghĩa như sau: “Cho hai lược đồ S1và S2 hãy tìm sự tương đồng nhất giữa các phần tử của S1và S2 bằng cách khai thác tất cả các thông tin tồn tại như trong lược đồ, trong dữ liệu và các nguồn thông tin hỗ trợ ”. Bài toán cần phải được giải quyết tới chừng nào có thể theo ý nghĩa của sự tự động. Mục tiêu chính là giảm các thao tác thủ công nhiều nhất có thể để tránh việc giải quyết bài toán đối sánh rất hỗn tạp. 3.1 Lược đồ. Trong các thao tác đối sánh, các lược đồ đầu vào chỉ ra các phần tử cần được đối sánh. Vì vậy ta cần xem xét một số loại lược đồ điển hình và các phần tử của nó