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ó. Tùy thuộc vào lĩnh vực của ứng dụng lược đồ có thể tồn tại dưới nhiều định dạng và ngôn ngữ khác nhau như SQL, UML, DTD, OWL. • SQL (Structured Query Language): Định nghĩa lược đồ cho cơ sở dữ liệu quan hệ. • XSD (XML Schema Definition): Định nghĩa cho các tài liệu có cấu trúc XML để trao đổi qua môi trường Web. • OWL (Web Ontology Language): Định nghĩa Ontology cho Sematic Web. 7 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 CREATE TABLE Document( docID INT, signerID INT, content TEXT, PRIMARY KEY (docID ), FOREIN KEY (signerID) REFERENCES Users(userID ) ) ; CREATE TABLE Users( userID INT, firstname VARCHAR(200), lastname VARCHAR(200), birthday DATE, PRIMARY KEY (userID) ); SQL XSD Hình 1-3: Lược đồ 3.2 Đầu vào bài toán (Input) Bài toán đối sánh lược đồ bao gồm các loại thông tin đầu vào để có thể tính toán mức độ tương đồng như sau. • Thông tin lược đồ: Các thông tin như name, data type, description. constraint .. • Dữ liệu: Trong các ứng dụng tích hợp dữ liệu, chuyển đổi dữ liệu thì dữ liệu luôn đi kèm với lược đồ và chúng cũng được khai thác để xác định ngữ nghĩa cho các phần tử lược đồ. • Thông tin hỗ trợ: Tất cả các loại thông tin khác mà chúng ta có thể khai thác cho quá trình đối sánh lược đồ. Các thông tin hỗ trợ như từ điển đồng nghĩa, domain … 3.3 Đầu ra bài toán (Output) Với đầu vào là 2 lược đồ S1, S2 bài toán cần đưa ra kết quả là một tập các phần tử ánh xạ giữa 2 lược đồ đó, ta gọi các phần tử này là co-elenment. Mỗi co- elenment được ánh xạ với một hoặc vài phần tử của S1, S2. Mỗi co-elenment 8 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 trong có thể chứa một biểu thức đối sánh để chỉ ra mối liên hệ giữa các phần tử của S1, S2. Chúng ta hãy xem xét một số khía cạnh của các biểu thức này • Ngữ nghĩa: Các biểu thức ánh xạ có thể là các biểu thức vô hướng, các quan hệ về mặt thuật ngữ, các quan hệ hướng đối tượng, các hàm biểu diễn mối liên quan giũa các phần tử. • Trực tiếp hay gián tiếp: Các phần tử được ánh xạ trực tiếp giữa chúng hoặc gián tiếp thông qua các biểu thức 3.4 Kiến trúc chung Kiến trúc chung của bài toán đối sánh lược đồ được mô tả trong hình dưới: Schemas, Mappings, Auxiliary sources Matching Implementation Internal Schema representation Schema Import/Export Internal Mapping representation Mapping Import/Export Application/Tools Data integration/ Translation Application/Tools Data warehouse Application/Tool Sematic Web Hình 1-4: Kiến trúc chung của bài toán đối sánh lược đồ 9 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 Kiến trúc này tương thích với nhiều lĩnh vực ứng dụng khác nhauh cho nhiều loại lược đồ khác nhau. Đầu vào của hệ thống là các lược đồ và các thông tin hộ trợ việc đối sánh như: Từ điển, Ontology, Các hệ số tương tự giữa các kiểu dữ liệu … Phần xử lý bao gồm các thao tác chuyển đổi biểu diễn của lược đồ thành cấu trúc biểu diễn lược đồ bên trong của hệ thống, có thể là dạng đồ thị. Tiếp theo là các thuật toán đối sánh đối với các lược đồ đã được biểu diễn dưới cấu trúc bên trong của hệ thống. Cuối cùng là kết quả đối sánh và các thao tác xử lý kết quả đó như chuyển đổi định dạng biểu diễn, kết xuất cho các ứng dụng. Các ứng dụng của hệ thống sau khi đã có kết quả đối sánh bao gồm nhiều lĩnh vực ứng dụng khác nhau như Tích hợp dữ liệu. chuyển đổi dữ liệu, Semantic Web … 4 Ứng dụng của bài toán đối sánh lược đồ Để nêu lên vai trò quan trọng của bài toán đối sánh lược đồ, chúng ta sẽ xem xét một vài ứng dụng về cở sở dữ liệu để minh họa. 4.1 Các ứng dụng tích hợp dữ liệu và nhà kho dữ liệu Tích hợp lược đồ là một trong những mục tiêu quan trọng nhất của bài toán đối sánh lược đồ. Vấn đề này đã được nghiên cứu từ đầu những năm 80, nó xuất hiện khi người ta cần xây dựng một hệ thống cơ sở dữ liệu bao gồm một vài hệ thống cơ sở dữ liệu khác nhau và thiết kế lược đồ của cơ sở dữ liệu đó (global schema) từ các lược đồ địa phương (local schema). Trong ngữ cảnh của ứng dụng trí tuệ nhân tạo hoặc Web ngữ nghĩa, tích hợp lược đồ tương đương với bài toán trộn các ontology được phát triển độc lập để xây dựng một cơ sở tri thức tích hợp. 10 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 Source schema Source schema Source schemaMediated schema Documents DB1 Documents DB2 Documents DB3 Tìm các văn bản phát hành năm 1999 Hình 1-5: 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 Hình 2-3 minh họa cho hệ thống tích hợp dữ liệu văn bản để trợ giúp người dùng tìm được văn bản cần thiết. Với truy vấn người dùng tới lược đồ trung gian (Mediated schema), hệ thống sẽ sử dụng tập các ánh xạ ngữ nghĩa giữa lược đồ trung gian và các lược đồ địa phương của nguồn dữ liệu để chuyển đổi thành truy vấn trên các nguồn dữ liệu. Sau khi thực hiện truy vấn trên các nguồn dữ liệu sẽ tổng hợp kết quả và trả lại cho nguời dùng. Các ứng dụng chia sẻ dữ liệu trình bày ở trên đang xuất hiện rất nhiều trong các lĩnh vưc hiện nay như thương mại điện tử, sinh học, và trong Ubicomp. Internet đã mang lại hàng triệu nguồn dữ liệu và cần phải tạo khả năng chia sẻ dữ liệu giữa chúng. 11 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 Documents DB1Documents DB2Documents DB3 Data warehouse Data transformation, data integration Hình 1-6: Data warehouse 4.2 E-Business Với sự phổ biến của Internet hiện nay, các công ty kinh doanh ngày càng phải quản lý các giao dịch online của họ như trao đổi thông tin, đặt hàng, xác nhận và thanh toán. Các giao dịch này là quá trình trao đổi các tài liệu hay thông điệp (message) giữa các công ty. Thường thì mỗi một công ty phát triển một ứng dụng với một định dạng message khác nhau như EDI (Electronic Data Exchange), 12 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 XML hoặc bất kỳ định dạng nào. Để hệ thống trao đổi được các message đó, các ứng dụng cần phải chuyển đổi được các message từ định dạng này sang định dạng khác. Điều này chính là động lực cho bài toán đối sánh lược đồ phát triển để chuyển đổi các message. 4.3 Semantic Web Tốc độ phát triển của Internet nhanh như hiện nay với lượng thông tin khổng lồ khiến chúng ta rất khó khai thác và sử dụng hiệu quả. Bởi vì các thông tin trên Web hiện nay được thiết kế chủ yếu cho con người đọc và sử dụng chứ không phải máy tính, nghĩa là máy tính không thể hiểu được nội dung. Mục đích của Semantic Web là làm giàu các tài liệu Web hiện nay bằng các mô tả ngữ nghĩa nhằm mục đích máy tính có thể hiểu được để có thể tự động hóa tối đa các thao tác mà con người phải xử lý với dữ liệu. Quá trình làm giàu hay được gọi chú thích (annotation) ngữ nghĩa cho các tài liệu Web sử dụng các Ontology. Một Ontology định nghĩa các thuật ngữ được sử dụng để biểu diễn một lĩnh vực tri thức nào đó. Ontology được sử dụng trong cơ sở dữ liệu, trong các ứng dụng và kể cả trong cuộc sống hằng ngày để chia sẻ thông tin về một lĩnh vực cụ thể nào đó. Ontology bao gồm các định nghĩa mà máy có thể hiểu được của các khái niệm cơ bản và quan hệ giữa chúng trong một lĩnh vực cụ thể Tuy nhiên các tài nguyên trên Web (Ví dụ Website, web service ...) khác nhau không chắc sử dụng cùng một Ontology, vì vậy việc truy vấn và khai thác các tài nguyên Web này cần thực hiện qua một ontology trung gian, Ontology trung gian là ánh xạ của các ontology địa phương. Như vậy đối sánh ngữ nghĩa của các khái niệm trong các ontology cần được xử lý để có thể thực hiện truy vấn trên ontology trung gian. 13 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 5 Các vấn đề mở Mặc dù còn có nhiều các nghiên cứu hiệu quả trong bài toán đối sánh lược đồ nhưng phần lớn các thao tác đối sánh vẫn được thực hiện thủ công bởi các chuyên gia trong lĩnh vực làm việc của họ. Điều này xảy ra bởi vì các giải pháp tự động hoặc bán tự động vẫn chưa thỏa mãn yêu cầu người dùng. Trong phần này tôi trình bày một số vấn đề còn đang được nghiên cứu trong lĩnh vực đối sánh lược đồ. Tuy nhiên tôi chỉ tổng hợp được một số các vấn đề qua các bài báo cũng như các dự án nghiên cứu về lĩnh vực này. Những thông tìn tổng hợp này có thể đủ hoặc không đủ về tất cả những nghiên cứu trước đây và hiện tại. 5.1 Khả năng biểu diễn của ngôn ngữ Các ngôn ngữ biểu diễn lược đồ hiện đại như XML schema, SQL (1999,2003) hỗ trợ rất nhiều khả năng mô hình hóa như các kiểu dữ liệu được định nghĩa bởi người dùng, tổng hợp, suy diễn, tái sử dụng đối tượng, phân tán và namespace… Các tính năng nâng cao này chính là dấu hiệu cho sự phức tạp của bài toán đối sánh lược đồ. Hầu hết các kiểu thiết kế lược đồ có thể được sử dụng như một sự lựa chọn để biểu diễn các khái niệm trong thế giới thực, nên dẫn tới sự khác nhau về ngữ nghĩa, cấu trúc trong lược đồ. Vì vậy đối sánh lược đồ với các lược đồ được biểu diễn bằng ngôn ngữ nâng cao đã trở thành một thách thức vì nó phụ thuộc và khả năng hợp nhất của các kiểu thiết kế khác nhau. 5.2 Làm việc với các lược đồ có kích thước lớn Các lược đồ trong thế giới thực ngày càng lớn về kích thước và độ phức tạp để đương đầu với các yêu cầu về biểu diễn và quản lý dữ liệu. Hơn nữa các lược đồ thường sử dụng các chung thành phần (shared element) để tránh các đặc tả khác nhau và giữ cho lược đồ ở mức đơn giản nhất có thể phục vụ cho việc bảo trì và vận hành được tốt hơn. Cuối cùng, các thao tác đối sánh cần kiểm tra trên một 14 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 không gian tìm kiếm lớn để xác định các phần tử tương đương, vì vậy cần phải tìm ra các phương pháp hiệu quả tốt nhất có thể. 5.3 Sự kết hợp của các phương pháp đối sánh Để thu được các kết quả đối sánh với độ chính xác cao thì việc sử dụng một thuật toán đơn lẻ sẽ không thành công. Như vậy cần sự kết hợp của nhiều thuật toán, phương pháp với nhau, vì vậy hầu hết các kết quả trước đây đều sử dụng khái niệm đối sánh kết hợp (hybrid và composition) của nhiều thuật toán. Hybrid sử dụng các thuật toán để xây dựng thành một thuật toán đơn còn Composition sử dụng kết quả của một vài thuật toán khác nhau để tổng hợp. 15 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 2 Các phương pháp tiếp cận Trong phần này tôi trình bày về các dự án nghiên cứu về lĩnh vực như data warehouse, data integration,… Trong đó hầu hết các dự án đều sử dụng đối sánh lược đồ như một module trung tâm để xử lý dữ liệu. 1 Các dự án liên quan 1.1 COMA++ COMA (Combination of Matching algorithms) [7] là công cụ đối sánh lược đồ kết hợp (Composite). COMA cung cấp thư viện các thuật toán đối sánh, cung cấp framework để kết hợp các phương pháp đối sánh và một nền tảng cơ sở để đánh giá hiệu quả của các phương pháp khác nhau. COMA++ được xây dựng trên ngôn ngữ Java, MySQL. COMA++ đã được sử dụng trong hệ thống tích hợp dữ liệu về thông tin trong ngành sinh học. Hình 2-1: Kiến trúc COMA++ 16 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.2 SEMINT SEMINT là hệ thống đối sánh lược đồ dựa trên dữ liệu (instance-based). Nó bao gồm 15 tiêu chuẩn dựa trên ràng buộc và 5 tiêu chuẩn dựa trên nội dung (content-based) được hình thành từ các bản ghi dữ liệu và được chuẩn hóa trong khoảng [0,1], mỗi thuộc tính là một điểm trong một không gian 20 chiều. Đối sánh lược đồ bằng cách tạo các ánh xạ giữa các phần tử độc lập sử dụng mạng neuron. SemInt không hỗ trợ đối sánh dựa trên ngôn ngữ. 1.3 LSD LSD (Learning source description) sử dụng phương pháp composite để kết hợp các thuật toán đối sánh khác nhau. Nó dựa trên domain cụ thể của lược đồ tổng thể để so sánh với các lược đồ mới được đối sánh. Học máy (machine learning) được sử dụng cho các các thuật toán độc lập và kết hợp các kết quả. Đối với đối sánh cho thuộc tính name, LSD sử dụng phương pháp đối sánh dựa trên instance. 1.4 SKAT SKAT (Semantic knowledge articulation tool) thực hiện đối sánh dựa trên lược đồ (schema-based) sử dụng các luật. Các luật là các biểu thức trong logic vị từ để thể hiện các quan hệ tương đương, không tương đương và các hàm được định nghĩa để sinh ra các luật đối sánh mới. 1.5 TransScm TransScm sử dụng phương pháp schema-based để thực hiện việc chuyển đổi dữ liệu. Lược đồ đầu vào (DTD hoặc OODB) được biểu diễn dưới dạng đồ thị. Các luật được xây dựng bởi người quản trị được áp dụng vào các node của đồ thị. Quá trình đối sánh được thực hiện theo mô hình top-down và đối sánh từng node một với nhau với quy luật là các node cha sẽ cần kết quả đối sánh của các node con. • Tự động chuyển đổi dữ liệu giữa các lược đồ instance 17 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 • Các lược đồ đầu vào được biểu diễn như các đồ thị gán nhãn 1.6 DIKE Hệ thống DIKE tích hợp nhiều lược đồ quan hệ bằng cách khai thác yếu tố tương tự giữa hai phần tử của lược đồ phụ thuộc vào sự tương tự của các phần tử hàng xóm. Đây là hệ thống đối sánh dựa trên cấu trúc (Structure-based), đối sánh từng cặp của các phần tử đầu vào. Số cạnh của của đường dẫn ngắn nhất giữa các phần tử được sử dụng như khoảng cách để xác định các phần tử liên quan. • Thuật toán tự động xác định quan hệ ngữ nghĩa (synonymy,hypernymy,homonymy) giữa các phần tử của các lược đồ ER. 1.7 SIMILARITY FLOODING SIMILARITYFLOODING[10] chuyển đổi các lược đồ (Rational, RDF, XML) vào trong một đồ thị gán nhãn và tính toán theo kiểu fix-point để xác định tương ứng địa phương 1:1 và m:n giữa các node của đồ thị. Thuật toán sử dụng phương pháp đối sánh hybrid với một bộ đối sánh đơn giản cho các thuộc tính name. Không giống các phương pháp đối sánh dựa trên lược đồ khác, SIMILARITYFLOODING không khai thác các quan hệ thuật ngữ trong các từ điển ngoài như (synonym, wordnet …) mà chỉ dựa trên thuộc tính name. Thuật toán chính được sử dụng trong SIMILARITYFLOODING là đối sánh dựa trên cấu trúc. 1.8 Cupid Cupid [3] là hệ thống đối sánh kết hợp (hybrid) bao gồm kỹ thuật đối sánh trên mức ngôn ngữ và cấu trúc. Thuật toán đối sánh lược đồ ánh xạ giữa các phần tử của lược đồ dựa trên tên, kiểu dữ liệu, các ràng buộc, cấu trúc của lược đồ và sự trợ giúp của từ điển đồng nghĩa. Cupid nhắm vào việc tính toán hệ số tương tự giữa các các phần tử của 2 lược đồ và đưa ra sự ánh xạ từ các hệ số này. 18 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ự động đối sánh dựa trên ngôn ngữ • Đối sánh dựa trên cả phần tử và cấu trúc • Hướng tới sự tương tự của các phần tủ nguyên tố (Ví dụ như các lá), vì vậy ngữ nghĩa của lược đồ sẽ được thu nhận nhiều hơn • Khai thác các khóa (key), các ràng buộn và các view Đối sánh mức ngôn ngữ sẽ so sánh các phần tử của lược đồ một các độc lập dựa trên tên, kiểu dữ liệu, lĩnh vực.. Chúng ta sẽ sử dụng một từ điển gần nghĩa (thesaurus) để trợ giúp việc so sánh các name bằng cách xác định các từ rút gọn, các từ viết tắt, và các từ đồng nghĩa. Đối sánh ngôn ngữ trong Cupid được chia thành 3 bước sau: 1. Chuẩn hoá (Normalization): Trong bước này chúng ta chuẩn hoá phần tử, phân tích phần tử bằng cách tokenization (phân tích các phần tử dựa trên dấu chấm câu, chữ hoa, chữ thường ...). Trong bước này ta sử dụng từ điển đồng nghĩa 2. Phân loại theo các phần tử (Categorization): Các phần tử của lược đồ được phân loại thành các nhóm khác nhau, sự phân loại này được dựa trên kiểu của dữ liệu (datatype), tên của thuộc tính (name). Một phần tử có thể thuộc nhiều loại. 3. So sánh (Comparison): Trong bước này sẽ tính toán một hệ số gọi là hệ số tương tự về ngôn ngữ giữa các phần tử (linguistic similarity-ls). Kết quả của pha này là một bảng các hệ số lsim của các phần tử giữa hai lược đồ. Hệ số lsim nằm trong khoảng [0,1]. Nếu lsim = 1 thì hai phần tử hoàn toàn tương đương nhau. Để so sánh độ tương tự của hai chuỗi đầu vào dựa trên phân tích token, Cupid sử dụng công thức sau. 19 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 Công thức 1: Cupid, hệ số tương tự của hai tập hợp 21 )2,1(*)11(22 max)2,1(*)22(11 max )2,1( TT ttsimTtTtttsimTtTt TTns + ∈∑ ∈+∈∑ ∈= Chú thích: Các thuộc tính được phân tích thành các từ (word) hay token, ta có một tập các token để biểu diễn các phần tử của lược đồ 1.Chọn một token từ phần tử thứ nhất 2.Tìm kiếm token giống nhất với token đã cho. 3.Thực hiện 1) và 2) đối với mọi token của phần tử thứ nhất và tính tổng độ giống nhau. 4. Thực hiện 1) 2) 3) cho phần tử thứ 2 5.Chuẩn hóa 2 tổng với tổng số token của phần tử thứ nhất và thứ hai Đánh giá theo category Cho w1 … w2 là hệ số ưu tiên theo category với 1=∑ iw Công thức 2: Cupid, đánh giá theo Category ∑ ∈ = TokenTypei iTiTnsiwAAns )2,1(.)2,1( Cuối cùng ta có công thức tính hệ số tương tự giữa hai thuộc tính Công thức 3: Cupid, công thức tính lsim ),(max).,(),( 21,2121 21 TTnsAAnsAAlsim CTT ∈ = Đây là công thức cho ra kết quả cuối cùng của đối sánh dựa trên ngôn ngữ. 20 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 2 Các phương pháp đối sánh lược đồ Đã có rất nhiều các nghiên cứu trong nhiều lĩnh vực khác nhau như chuyển đổi và tích hợp lược đồ (schema translation, schema integration), biểu diễn tri thức, học máy và các hệ thống thu thập thông tin nhắm tới mục đích tự động quá trình đối sánh lược đồ nhiều nhất có thể. Mục đích của phần này giới thiệu các phương pháp tiếp cận trong các lĩnh vực đó, các đặc điểm chung và ứng dụng của nó. Trong phần tiếp theo, tôi trình bày các tiêu chí phân loại cho bài toán đối sánh lược đồ được tham khảo trong [6]. 2.1 Tiêu chuẩn phân loại Bài toán đối sánh lược đồ đã được nghiên cứu trong một thời gian dài, và đã có nhiều ứng dụng cụ thể áp dụng bài toán này. Hình 3 minh họa các phương pháp đối sánh lược đồ đã được nghiên cứu và phát triển trong các ứng dụng cụ thể. Hình 2-2: Các phương pháp đối sánh lược đồ 21 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 ta phân biệt các phương pháp đối sánh dựa trên phương pháp tiếp cận mà chúng sử dụng • Schema-based ›‹ Instance-based: Schema-based chỉ sử dụng các thông tin chứa trong lược đồ như metadata, name, type, description... Còn Instance-based sử dụng dữ liệu để trích lọc ngữ nghĩa (contents) • Element-based ›‹ Structural-based: Element-based là quá trình đối sánh có thể thực hiện trên từng phần tử trong lược đồ một cách độc lập, ví dụ như các thuộc tính (attributes). Structural-based thực hiện đối sánh có sự kết hợp các phần tử lại với nhau. • Linguistic ›‹ Constraint: Đối sánh có thể sử dụng cách tiếp cận ngôn ngữ như so sánh các thuộc tính name, description .. hoặc sử dụng cách tiếp cận ràng buộc như xem xét cả ràng buộc định nghĩa trên các phần tử như kiểu dữ liệu, unique, key… • Hybrid ›‹ Composite: Để có một kết quả đối sánh tốt hơn người ta thường kết hợp một vài cách tiếp cận với nhau. Các cách tiếp cận này có thể được thực hiện trong một bộ đối sánh hybrid hoặc kết hợp các kết quả đối sánh của các cách tiếp cận độc lập (composite) 2.2 Đối sánh dựa trên lược đồ (schema-based) Phương pháp đối sánh dựa trên lược đồ chỉ xem xét các thông tin về lược đồ, tùy thuộc vào việc sử dụng ngôn ngữ định nghĩa lược đồ các ta có các thuộc tính khác nhau của phần tử lược đồ như name, description, data type, constraints, .. và các quan hệ giữa chúng. Tiếp theo tôi trình bày về bộ đối sánh dựa trên ngôn ngữ và ràng buộc, phương pháp tiếp cập chung đối với mức element để so sánh các thuộc tính của các phần tử lược đồ để xác định độ tương đồng giữa chúng. 22 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 2.2.1 Phương pháp tiếp cận dựa trên ngôn ngữ (linguistic) Phương pháp này chủ yếu xem xét các thuộc tính dạng chuỗi ký tự của các phần tử lược đồ như name, description.Thuộc tính name có thể được so sánh qua 2 dạng là cú pháp (syntactic) và ngữ nghĩa (semantic). Đối sánh thuật ngữ name dựa trên cú pháp là tính toán độ tương đồng chỉ dựa trên các chuỗi biểu diễn name. Có nhiều thuật toán đã được phát triển ứng dụng cho các lĩnh vực khác như sửa lỗi chính tả (spelling correction), thu thập thông tin … Trong đó đặc biệt 3 thuật toán sau: EditDistance, N-Gram, SoundEx đã được áp dụng vào bài toán đối sánh lược đồ. • EditDistance (Levenstein):Sử dụng kỹ thuật quy hoạch động, độ tương đồng của 2 chuỗi được tính từ số lần thực hiện các thao tác: xóa, thêm, thay thế của một ký tự cần thiết để chuyển một chuỗi này thành chuỗi kia. • N-Gram: Chuỗi được so sánh theo tập n-gram của nó. Ví dụ chuỗi doc và document là tương tự theo tập tri-gram, {doc} và {doc,ocu,cum,ume,men,ent} chia sẻ phần tử doc. • SoundEx: Phương pháp này tính độ tương đồng âm giữa các name tương ứng với mã SoundEx. Phương pháp này hiệu quả cho các từ được viết khác nhau có khả năng giống nhau,ví dụ document, documentation. Đối sánh dựa trên ngữ nghĩa sử dụng các quan hệ về mặt thuật ngữ để ước lượng độ tương đồng giữa các name như synonymy, hypernymy, hyponymy. ví dụ từ Car và automobile là đồng nghĩa nên tương tự nhau. Cách tiếp cận này cần trợ giúp của các thông tin hỗ trợ như từ điển, thesaurus, ontology hoặc các bảng định nghĩa từ đồng nghĩa cho các ngôn ngữ khác nhau. Ngoài ra trên thực tế các lược đồ còn có nhiều sự hỗn tạp mà chúng thường gặp như: • Từ được ghép bởi nhiều từ khác: Ví dụ Org_Sender. • Từ được viết gọn lại: Ví dụ Org có nghĩa là Organization. • Từ có nhiều nghĩa. 23 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 2.2.2 Phương pháp tiếp cận dựa trên ràng buộc Các lược đồ thường chứa các thông tin ràng buộc như size, data type, key, range, unique… cho mỗi phần tử. Nếu các thông tin này xuất hiện trong cả hai lược đồ thì nó sẽ được khai thác để ước lượng độ tương đồng. Ví dụ có thể tính toán độ tương đồng giữa hai phần tử dựa trên data type, key… Đối với các thông tin này, cách tiếp cận chung là tạo một bảng trong đó chứa hệ số tương tự của các ràng buộc. Ví dụ như kiểu String và kiểu varchar là hoàn toàn tương tự nhau. 2.2.3 Phương pháp tiếp cận dựa trên cấu trúc Phương pháp tiếp cận này khai thác các quan hệ giữa các phần tử và đối sánh kết hợp các phần tử xuất hiện trong cùng một cấu trúc. Phụ thuộc vào các ngôn ngữ mô tả lược đồ khác nhau mà có các kiểu quan hệ giữa các phần tử khác nhau. Ví dụ như các quan hệ is-a/part-of, hoặc các ràng buộc tham chiếu. Thông thường lược đồ được biểu diễn dưới dạng đồ thị (có hướng hoặc vô hướng). Để xác định độ tương đồng giữa các phần tử người ta thường sử dụng khái niệm phần tử hàng xóm (element neighborhood) để hạn chế phạm vi khi so sánh các phần tử. 2.3 Đối sánh dựa trên dữ liệu Phương pháp này duyệt qua các bản ghi dữ liệu để xác định sự tương ứng và được chọn khi các thông tin trong lược đồ bị giới hạn hoặc trong trường hợp dữ liệu được biểu diễn dưới dạng bán cấu trúc. Trong trường hợp đặc biệt không có lược đồ người ta phải xây dựng nó từ các dữ liệu đã có, trường hợp này người ta phải sử dụng các kỹ thuật được gọi là trích lọc lược đồ. Ngay cả khi có lược đồ thì thông tin về dữ liệu cũng có thể được xem xét để tăng khả năng khai thác ngữ nghĩa trong lược đồ Đối với phương pháp này, kích thước dữ liệu đầu vào bài toán lớn hơn nhiều so với lược đồ nên thời gian thực hiện đối sánh cũng là một trong những vấn đề cần quan tâm. 24 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 2.4 Đối sánh kết hợp Đối sánh chỉ sử dụng một phương pháp tiếp cận sẽ không thích hợp để cho ra một kết quả tốt với sự đa dạng của lược đồ. Vì vậy hầu hết các hệ thống đối sánh lược đồ hiện tại đều kết hợp sử dụng nhiều phương pháp đối sánh. Đối sánh kết hợp có thể được thực hiện theo hai cách khác nhau là hybrid hoặc composite. Hybrid tích hợp nhiều cách tiếp cận vào trong engine trong khi composite kết hợp kết quả của nhiều cách tiếp cận độc lập lại với nhau. Trong hầu hết các hệ thống có sử dụng đối sánh lược đồ đều sử dụng đối sánh kết hợp (Cupid) 2.5 Match Cardinality Kết quả đối sánh giữa hai lược đồ S1 và S2 là tập các co-element giữa các phần tử của nó, một phần tử S1 (S2) có thể tồn tại trong nhiều co-element. Hơn nưa, một hay nhiều phần tử S1 có thể tương đương với một hoặc nhiều phần tử của S2. Vì vậy chúng ta có các quan hệ về số lượng 1:1. 1:n, n:1, m:n . Cardinality s (S1) t (S2) 1:1 Price Cost Price=Cost n:1 FirstName, LastName Name Concat(FirstName, LastName) = Name 1:n Name FirstName, LastName Split(Name) = {FirstName, LastName} m:n P.PersName, P.DeptNoD.DeptNo, D.DeptName A.Person, A.Department SELECT P.PersName, D.DeptNameFROM P, D WHERE P.DeptNo=D.DeptNo = {A.Person, A.Department} Bảng 1: Đối sánh dựa trên số lượng phần tử 25 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 2.6 Các hệ số mặc định trong bài toán đối sánh Trong các phương pháp đối sánh đã trình bày ở trên trong các dự án cụ thể đều có sử dụng các hệ số mặc định để chỉ ra sự tương tự giữa các phần tử theo các tiêu chí đặc biệt. Ví dụ bảng hệ số tương tự giữa các phần tử khi so sánh các kiểu dữ liệu của chúng với nhau, với tiêu chí này người ta không xây dựng bất cứ thuật toán nào mà thường sử dụng các hệ số được định nghĩa sẵn. Ngoài ra còn các hệ số mặc định để chỉ ra độ ưu tiên của một thuật toán so với thuật toán khác, ví dụ độ ưu tiên của mức ngôn ngữ so với độ ưu tiên của mức cấu trúc. Type(s) Type(t) Datatype_match(s,t) string string 1.0 string date 0.2 decimal float 0.8 float float 1.0 float integer 0.9 … … … Có một số phương pháp để xây dựng bảng hệ số như trên nhưng phương pháp thường được các chuyên gia sử dụng là dựa vào thực nghiệm. Quá trình xây dựng các hệ số được thực hiện theo các bước sau: 1. Thực hiện đối sánh bằng tri thức chuyên gia, được kết quả là một tập hợp các ánh xạ giữa các phần tử của hai lược đồ Sexp kết quả thực tế mà bài toán cần hướng tới). 2. Thực hiện đối sánh tự động với hai lược đồ và cũng thu được tập hợp các ánh xạ giữa các phần tử của hai lược đồ Sauto. 3. Sẽ có sự khác nhau giữa tập hợp ánh xạ do chuyên gia và tập ánh xạ do máy thực hiện. Các hệ số Wdefault sẽ được điều chỉnh sao cho tập Sauto giống với tập Sexp nhất có thể. 26 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 2-3: Xây dựng các hệ số ưu tiên Các hệ số thu được có thể được áp dụng cho nhiều bài toán khác nhau, thuật toán khác nhau. 3 Các phương pháp đánh giá hệ thống đối sánh Để đánh giá kết quả của các hệ thống đối sánh lược đồ chúng ta có thể sử dụng các phương pháp sau đây 1. So sánh kết quả đối với kết quả đối sánh của các chuyên gia. Đây là một phương pháp khá hiệu quả và nó thường được sử dụng để xây dựng các hệ số ưu tiên trong các thuật toán đối sánh. Các hệ số được điều chỉnh sao cho kết quả tự động bằng máy với kết quả của chuyên gia giống nhau nhất. Thực hiện với nhiều lược đồ sẽ thu được các hệ số thực nghiệm tối ưu nhất. 2. So sánh kết quả đối sánh với kết quả của các hệ thống khác. 3. Đánh giá tự động: Ký hiệu B là tập các ánh xạ đúng (ánh xạ đúng là ánh xạ do chuyên gia thực hiện), C: Tập các ánh xạ sai, A tập ánh xạ đúng 27 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 nhưng không được thuật toán tìm thấy và D là tập ánh xạ sai được thuật toán loại bỏ Hình 2-4: Đánh giá hệ thống đối sánh Ta có hai công thức sau để ước lượng hiệu quả của thuật toán đối sánh • Cho biết sự tin cậy của thuật toán đối sánh Precision= CB B + , • Cho biết phần trăm của các ánh xạ hợp lệ (có giá trị) Recall= AB B + Khi tập A và tập C không tồn tại thì Precision và Recall có giá trị 1. Tuy nhiên một giá trị Recall hoặc Precision thì không thể ấn định được chất lượng của thuật toán đối sánh. Như vậy cần phải xem xét các phương pháp kết hợp hai giá trị trên đối lại với nhau. Có một số phương pháp kết hợp đã được xây dựng sau 1. FMeasure(α ) được mô tả trong [9]: FMeasure(α )= recallprecision recallprecision CBA B **)1( * **)1( αααα +−=++− Trong đó 0<α <1 cho phép các giá trị thể hiện sự quan trọng khác nhau đối với Precision và Recall. FMeasure(α ) hội tụ về Precision khi α =1 và hội tụ về Recall khi α =0 28 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 2. FMeasure : Khi Precision và Recall được xem có độ quan trọng bằng nhau ta có công thức sau FMeasure= recallprecision recallprecision CBBA B +=+++ **2 *2 3. Overall: Đây là công thức được nêu trong [10] và công thức này được nhắm vào chính các ứng dụng đối sánh lược đồ Overall= )12(*1 precision recall BA CB BA CA −=+ −=+ +− Để so sánh hai phương pháp FMeasure và Overall ta có hình sau. Nhìn vào đồ thị ta thấy FMeasure tối ưu hơn so với Overall. Với cùng giá trị của Precision và Recall thì FMeasure cao hơn so với Overall. Overall nhạy cảm với biến Precision hơn. Khi Precision=0,5 thì Overall=0; Hình 2-5: So sánh F-Measure và Overall 29 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 30 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 3 Thiết kế hệ thống đối sánh lược đồ. 1 Khảo sát Hiện nay các công ty, tổ chức đều có các cơ sở dữ liệu chưa các thông tin quản lý, tác nghiệp điều hành. Đối với các công ty, hoặc các tổ chức có qui mô lớn, dữ liệu phân tán trên cả mặt logic và vật lý. Các tổ chức này thường dùng các hệ quản trị cơ sở dữ liệu và hệ thống phần mềm khác nhau để quản lý cơ sở dữ liệu, điều này dẫn đến việc tích hợp dữ liệu các cơ sở dữ liệu này thành một thể thống nhất gặp rất nhiều khó khăn vì sự hỗn tạp của dữ liệu. Các hệ thống cơ sở dữ liệu thường được dùng bao gồm: Lotus notes, MS SQL Server, Oracle, MySQL. Trong hình dưới đây minh họa sự hỗn tạp của các nguồn dữ liệu văn bản, đây là một mô hình đang được áp dụng trong các tổ chức ở Việt Nam hiện nay. 31 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 Organization 3Organization 2Organization 1 Domino SQL server Oracle Schema1 Schema2 Schema3 E-docman App E-docman App E-docman App Mediator Local schemaLocal schema Global schema Query Result Hình 3-1: Sự hỗn tạp của các nguồn dữ liệu Hiện tại nhu cầu về bài toán tích hợp dữ liệu (Data integration) hoặc chuyển đổi dữ liệu (Data translation) một cách tự động hoặc bán tự động là thực sự cần thiết. Trên thực tế các công ty hay tổ chức hiện nay khi xây dựng các ứng dụng có sử dụng dữ liệu đã có sẵn thì thường phải xây dựng một công cụ với các thao tác thủ công (manual) để tiến hành chuyển đổi hoặc tích hợp dữ liệu cũ vào ứng dụng mới. Những thao tác thủ công sẽ không lợi ích về mặt kinh tế cũng như 32 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 xử lý sẽ xuật hiện các lỗi thao tác bằng tay. Như vậy người ta cần phải xây dựng các mô hình tự động hoặc bán tự động cho bài toán này để giảm thiểu tối đa các thao tác thủ công. 33 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 2 Giới thiệu Trong hình dưới đây là hai lược đồ về cơ sở dữ liệu văn bản. chúng ta có thể nhận ngay ra các xung đột trong hai lược đồ này. Vấn đề đặt ra bây giờ là xử lý các xung đột đó một cách tự động nhiều nhất các thao tác có thể. Hình 3-2:Lược đồ văn bản 2.1 Giới thiệu bài toán đối sánh lược đồ. Đối sánh (Match) là thao tác xử lý 2 lược đồ đầu vào và cho đầu ra một ánh xạ các phần tử phù hợp giữa hai lược đồ. Đối sánh lược đồ là bước khó trong nhiều ứng dụng: Trong Thương mại điện tử, trợ giúp ánh xạ các message giữa các định dạng XML khác nhau, trong Datawarehouse, giúp ánh xạ dữ liệu nguồn vào trong các lược đồ của Warehouse… 2.2 Xử lý lược đồ trong tiếng Việt Trên thực tế trong các ứng dụng về cơ sở dữ liệu ở Việt Nam hiện nay, có rất nhiều các lược đồ được thiết kế sử dụng tiếng Việt, các thuộc tính định danh (identify name) thường sử dụng tiếng Việt không dấu để biểu diễn, còn các các mô tả thuộc tính có thể là tiếng Việt có dấu hoặc không có dấu. Ngoài ra các lược đồ này còn kết hợp cả tiếng Anh, như vậy việc xử lý các lược đồ này còn gặp rất 34 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 nhiều khó khăn do có quá nhiều các xung đột về ngữ nghĩa, từ vựng, sự hạn chế của các giải thuật xử lý ngôn ngữ cho tiếng Việt … Dựa trên những thuật toán xử lý cho các thứ tiếng khác ta cũng hoàn toàn có thể xây dựng được thuật toán xử lý cho tiếng Việt, nếu ta có được các bộ từ điển như tiếng Anh. Tôi đề xuất một vài phương pháp tiếp cận cho tiếng Việt trong bài toán đối sánh lược đồ có thể sử dụng trong đối sánh ngôn ngữ 1. Nếu ta xây dựng được một từ điển phân loại (taxonomy) giống như Wordnet3 cho tiếng Việt, chúng ta hoàn toàn có thể thực hiện các thuật toán đối sánh như trong tiếng Anh. Có thể xem một trong những thuật toán này tại đây4 2. Ngoài ra ta cũng có thể xây dựng một thuật toán kết nối đến từ điển Việt – Anh để xử lý. Quá trình sẽ được thực hiện như sau: Kết nối đến từ điển và tìm các từ tiếng Anh tương ứng và sau đó sử dụng các thuật toán cho tiếng Anh. Sử dụng các phương pháp trên tất nhiên chúng ta phải có một bộ phân tích cú pháp cho tiếng Việt, nghiên cứu sinh Lê Hồng Phương 5 đang phát triển dự án vnLTAG6 cho tiếng Việt mục đích để xây dựng một văn phạm LTAG cho tiếng Việt. Trước đó tác giả này đã xây dựng công cụ vnTokenizer để xử lý ngôn ngữ tiếng Viêt có chức năng tact từ tiếng Việt tự động và phân loại chúng. 3 4 5 Doctorant, Equipe Langue et Dialogue, LORIA,INRIA Lorraine, 615 rue du Jardin Botanique, lehong@loria.fr 6 35 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 Thiết kế Trong phần này tôi trình bày về kiến trúc của hệ thống đối sánh lược đồ và các bước thực hiện. Ý tưởng của hệ thống này là sử dụng đối sánh kết hợp (compostion), sử dụng tổng hợp 3.1 Kiến trúc hệ thống Kiến trúc của hệ thống đối sánh lược đồ của DocMatcher được mô tả trong hình sau. Hệ thống bao gồm các module sau với sự hỗ trợ của giao diện đồ hoạ trên nền Window: • Xử lý thông tin đầu vào (input) • Đối sánh với các thuật toán • Tổng hợp kết quả • Kết xuất thông tin ra 36 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 3-3: Kiến trúc hệ thống 3.2 Input Đầu vào của hệ thống bao gồm các lược đồ cần đối sánh và các nguồn thông tin hỗ trợ việc đối sánh. 3.2.1 Lược đồ XSD là một trong những ngôn ngữ biểu diến lược đồ mạnh nhất và được ứng dụng rộng rãi trong nhiều lĩnh vực. Vì vậy XSD được lấy làm ví dụ để minh hoạ cho đầu vào của hệ thống đối sánh. Các tài liệu XML schema (XSD) được phân tích và xử lý để chuyển đổi sang dạng đồ thị có hướng. Các ngôn ngữ biểu diễn lược đồ khác như XML DTD hay SQL (ví dụ SQL-92) cũng có thể áp dụng phương pháp mô hình hoá với XSD. XSD có nhiều cách thiết kế mà chúng ta cần xem xét để phân tích các vấn đề xung đột. 37 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. XSD Schema có thể được thiết kế theo kiểu phân tán hoặc nguyên khối, thường thì các lược đồ được thiết kế theo cách truyền thống là tất cả các thành phần được gộp vào chung một tài liệu. Tuy nhiên đối với các lược đồ có kích thước lớn, đặc biệt là trong các ứng dụng Web Lược đồ được tách thành nhiều tài liệu và các namespace khác nhau. Ví dụ các tài liệu XSD có thể sử dụng các cú pháp include, redefine, import để tích hợp các tài liệu với nhau. 2. Kiểu thiết kế Composition và Deviration: Một vài ngôn ngữ như XSD và ngôn ngữ SQL mở rộng cho hướng đối tượng hỗ trợ việc định nghĩa kiểu rất linh hoạt (user-defined types) cho các phần tử và thuộc tính. Các kiểu mới có thể xây dựng dựa theo phương pháp composition hoặc derivation. Theo phương pháp composition thì kiểu mới có thể xây dựng dựa trên các phần tử và thuộc tính đã tồn tại. Theo phương pháp derivation thì các kiểu mới được xây dựng bằng cách thừa kế các một kiểu cơ sở và các thuộc tính của nó. 3. Phương pháp khai báo inline và khai báo chia sẻ: Khai báo inline là các phần tử được khai báo kiểu ngay trong phạm vi khai báo của phần tử đó, còn khai báo theo kiểu chia sẻ là định nghĩa ra các kiểu chung rồi các phần tử có chung một kiểu sử dụng các kiểu chung đó. Phân tích lược đồ đầu vào là một trong những bước quan trọng của bài toán đối sánh.Các bước chuyển đổi từ lược đồ đầu vào thành đồ thị có hướng bao gồm các bước sau: 1. Hợp nhất các thiết kế: Để dễ dàng điều khiển, các lược đồ được phân tích và hợp nhất thành một lược đồ. 38 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 3-4: Hợp nhất các lược đồ phân tán 2. Hợp nhất các các kiểu thiết kế: Composition là phương pháp chung để xây dựng kiểu, kiểu thừa kế (derivation) được chuyển thành kiểu composition Hình 3-5: Hợp nhất các kiểu thiết kế lược đồ 3. Chuẩn hoá lược đồ bằng cách loại bỏ các nút biểu diễn kiểu (type). Hình 3-6: Loại bỏ nút có kiểu đơn giản 4. Gộp các khai báo bằng cách chia sẻ các thành phần 39 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 3-7: Tái sử dụng các định nghĩa Kết quả thu được là đồ thị liên thông có hướng biểu diễn lược đồ, với cách biểu diễn này các lược đồ đầu vào được biểu diễn dưới dạng đơn giản nhất có thể. 3.2.2 WordNet WordNet7 là cơ sở dữ liệu về từ vựng tiếng Anh. WordNet được thiết kế để thực hiện kết nối cho các loại từ POS (Parts-of-Speech) gồm Danh từ, Động từ, Tính từ và Trạng từ. Một khối nhỏ nhất trong WordNet được gọi là một synset để biểu diễn ý nghĩa cho một từ cụ thể. Nó bao gồm một từ và giải nghĩa của từ đó cộng với các từ đồng nghĩa. Ý nghĩa cụ thể của một từ theo POS được gọi là 1 sense. Mỗi sense của một từ nằm trong các synset khác nhau. Mỗi synset có chú thích để định nghĩa khái niệm mà nó biểu diễn. Ví dụ từ night, nighttime, dark cấu tạo một synset có chú thích như sau: “the time after sunset and before sunrise while it is dark outside”. Synset kết nối đến các synset khác qua các quan hệ ngữ nghĩa rõ. Một vài quan hệ như (hypernym, hynonym cho danh từ, hypernym và troponym cho động từ) và cấu tạo thành cây is-a-kind-of (holonymy) và is-a-part-of (meronymy cho danh từ). Ví dụ tree is-a-kind-of plant, tree là hyponym của plant và plant là hypernym của tree, tương tụ trunk is-a-part-of tree và tree là meronymy của trunk. 7 40 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 Trong [8]8 có đề cập vấn đề sử dụng WordNet để xây dựng thuật toán tính toán độ tương tự của hai câu. Hiện tại trong phiên bản này, do hạn chế về thời gian nên WordNet chưa được tích hợp vào trong hệ thống để tính toán độ tương tự. Thay vào đó là một bảng các cặp từ đồng nghĩa với độ chính xác 1.0. WordNet sẽ được tích hợp vào hệ thống trong thời gian sắp tới. 3.2.3 Output Đầu ra của bài toán đối sánh là tập các ánh xạ chỉ ra sự tương đương giữa các phần tử của hai lược đồ. Ký hiệu ↔ để chỉ ra một ánh xạ giữa hai lược đồ, ví dụ S1↔ S2 để chỉ ra một ánh xạ của hai lược đồ, hoặc s1↔ s2 để chỉ ra một ánh xạ của hai phần tử. Với một tập các ánh xạ như vậy, chúng ta cần các thao tác để hỗ trợ việc sử dụng chúng trong các ứng dụng khác nhau. Các hàm thao tác kết quả ánh xạ Transpose(m: S1↔S2) {s2↔s1 | s1↔s2 ∈ m} Domain(m: S1↔S2) {s1 ∈ S1 | Σs2 ∈S2 ∧ s1↔s2 ∈ m} InvertDomain(m: S1↔S2) S1 \ Domain(m: S1↔S2) RestrictDomain(m: S1↔S2, S) {s1↔s2 | s1↔s2 ∈m ∧ s1∈S} MappingMerge(m1: S1↔S2, m2: S1↔S2) {s1↔s2 | s1↔s2 ∈m1 ∨ s1↔s2 ∈m2} Diff(m1: S1↔S2, m2: S1↔S2) {s1↔s2 | s1↔s2 ∈ m1 ∧ s1↔s2 ∉m2} Intersect(m1: S1↔S2, m2: S1↔S2) {s1↔s2 | s1↔s2 ∈m1 ∧ s1↔s2 ∈m2} Bảng 2: Chú thích: • Transpose: Hoán đổi vị trí của phần tử nguồn và phần tử đích trong tất các các ánh xạ đầu ra. Thao tác này không thể áp dụng cho các ánh xạ chưa biểu thức, nó chỉ được dành riêng cho các giá trị tương tự. 8 41 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 • Domain và InvertDomain: Domain trả về tập các phần tử nguồn trong các cặp ánh xạ. Ngược lại InvertDomain trả về tập các phần tử nguồn không nằm trong tập các cạnh ánh xạ. • RestrictDomain có tham số đầu vào là tập ánh xạ và tập các phần tử, kết quả trả về tập các ánh xạ với các phần tử nguồn nằm trong tập các phần tử đã cho • MappingMerge: Tham số đầu vào là hai tập các ánh xạ và đầu ra là tập các ánh xạ nằm trong cả hai tập ánh xạ đầu vào. • Intersect: Tương tự MappingMerge. • Diff: Tham số đầu vào là 2 tập ánh xạ và đầu ra là tập các ánh xạ chỉ nằm mộ trong hai tập hợp đầu vào. 3.3 Mức ngôn ngữ (linguistic matching) Pha đầu tiên của ứng dụng đối sánh lược đồ là dựa trên thuộc tính name và description của các phần tử lược đồ cộng với sự hỗ trợ của từ điển đồng nghĩa, từ điển viết tắt. Các bản ghi dữ liệu không được sử dụng để đối sánh ở bước này. Kiến trúc của bước đầu tiên được minh hoạ trong hình sau: Hình 3-8:Sơ đồ đối sánh mức ngôn ngữ (linguistic matching) 42 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.3.1 Các thuật toán đối sánh cơ bản Các thuật toán cơ bản được áp dụng cho các phần tử đầu vào, đối với mỗi thuật toán này ta xây dựng được một mảng các hệ số tương tự giữa các phần tử đầu vào. Tiếp theo là ta xây dựng thuật toán kết hợp các kết quả đối sánh được tính toán từ các thuật toán này. Hệ thống áp dụng các thuật toán sau 1. EditDistance(ed): Giá trị tương tự tính toán theo hệ số ed được biến đổi để đảm bảo giá trị các hệ số tương tự nằm trong khoảng [0,1]. Thuật toán Levenshtein (hay được gọi là EditDistance) dùng để tính độ tương tự giữa hai chuỗi s và t, khoảng Levenshtein là số lần cần thiết thực hiện các thao tác xóa, thêm, thay đổi để chuyển từ một chuỗi s thành chuỗi t • s là “document” , t là “document” thì LD(s,t)=0. • s là “document” , t là “documents” thì LD(s,t)=1. Giá trị của khoảng Levenshtein (LD) càng lớn thì sự khác nhau giữa hai chuỗi càng lớn. Ta xây dựng công thức tính độ tương tự của hai chuỗi dựa trên hệ số ed và chuẩn hóa giá trị của nó trong khoảng [0,1], ta có công thức sau đây: Công thức 4: Công thức EditDistance biến đổi ))(),(max( ),(1),( tlenslen tsldtssim −= Trong đó: ld(s,t) là khoảng Levenshtein, max (len(s),len (t)) là chuỗi có độ dài lớn nhất trong hai chuỗi s,t. Như vậy công thức 1 tương đương với nếu sim(s,t) càng lớn thì sự giống nhau càng lớn 43 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 Ví dụ: s T sim(s,t) Document Doc 0.37 Documents Document 0.89 Document Document 1 … … … 2. N-Gram:Chuỗi được so sánh theo tập n-gram của nó. Ví dụ chuỗi doc và document là tương tự theo tập tri-gram, {doc} và {doc,ocu,cum,ume,men,ent} chia sẻ phần tử doc. Ví dụ: s t sim(s,t) … … 3. Synonym: Tổ chức một từ điển các từ đồng nghĩa hoặc có thể kết nối đến WordNet để tra cứu các từ đồng nghĩa Synonym Customer Client Customer Buyer Tree Plant provider supplier … … 44 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 4. Abbreviation: Tổ chức một từ điển các từ viết tắt Cust Customer id identifier phone telephone doc document …. … 3.3.2 Thuật toán đối sánh kết hợp Mục đích của thuật toán này là kết hợp các kết quả tính toán của các thuật toán cơ bản để xác định được các phần tử tương ứng giữa các phần tử của hai lược đồ. Sơ đồ thuật toán được mô tả sau đây 45 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 3-9: Sơ đồ thuật toán đối sánh kết hợp Chú thích thuật toán ExtractAttribute: Thực hiện việc phân tích các chuỗi đầu vào theo các quy tắc về synonym, từ viết tắt, từ viết gọn, phân tích token… matchers: Các thuật toán đối sánh cơ bản agg: Phương pháp tổng hợp kết quả từ simCube dir:Chiều so sánh của thuật toán, dựa trên số lượng phần tử của s1 và s2 sel: Phương pháp chọn lựa các giá trị đối sánh combineMethod: Phương pháp tính toán kết hợp các kết quả 46 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 Phân tích các phần tử(Element) Trong bước này ta phân tích phần tử thành các token bằng cách sử dụng các phương pháp chuẩn hoá phần tử, danh mục các ký tự đặc biệt (stop word), danh mục từ viết tắt (Abbreviation)…và một số tiêu chuẩn khác. Kết quả của bước này thu được hai tập hợp tương ứng chứa các token của hai phần tử. Hình 3-10: Phân tích phần tử đầu vào Tổng hợp các kết quả đối sánh (Aggregation) Thực hiện các thuật toán đối sánh khác nhau sẽ thu được một ma trận 3 chiều (m,s1,s2) với m là thuật toán, s1,s2 tương ứng là các phần tử của hai lược đồ. Các ô trong ma trận là giá trị các hệ số tương tự theo từng thuật toán. Từ ma trận này tính ra được ma trận hai chiều hệ số tương tự của 2 phần tử (s1,s2) theo các phương pháp sau đây. s1 s2 Matcher s1 s2 Sim_cube(m,s1,s2) Sim_array(s1,s2) 47 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. Max: Lấy hệ số tương tự lớn nhất của một thuật toán, sử dụng phương pháp này sẽ cho kết quả tối ưu đặc biệt trong trường hợp giá trị tương tự được chỉ định hoặc lấy trong các bảng hệ số. Công thức 5: Lấy Max ),,(max),( 2121 ssmssMSim Mm∈= 2. Trọng số: Các thuật toán đối sánh được gán các trọng số ưu tiên khác nhau wi, dựa trên các trọng số này sẽ tính được hệ số tương tự s1 và s2. Công thức 6: Lấy theo trọng số ∑∑ == ∈ 1)s,s,(w )s,WSim(s Mm 21m21 iwmsim 3. Trung bình: Trả về hệ số tương tự trung bình của các thuật toán đối với (s1,s2) Công thức 7: Lấy theo trung bình ∑ ∈ = Mm msimA )s,s,( M 1Sim 21 Xác định chiều đối sánh (Direction) Xác định chiều đối sánh phụ thuộc và số lượng phần tử của s1 và s2, ký hiệu là |s1|,|s2|. Có thể xảy ra 3 trường hợp sau 1. |s1|>|s2|: Đối sánh một lược đồ có số lượng phần tử lớn hơn với lược đồ có số lượng phần tử nhỏ hơn, các phần tử s1 được so sánh với mỗi phần tử s2 2. |s1|<|s2|:Đối sánh một lược đồ có số lượng phần tử nhỏ hơn với lược đồ có số lượng phần tử lớn hơn, các phần tử s2 được so sánh với mỗi phần tử s1 3. Cả hai chiều Chọn lựa giá trị ứng cử (Select candidate) 1. Chon lựa theo ngưỡng: Xem xét các phần tử và giá trị tương tự không vượt qua ngưỡng. (ví dụ 0.5) 48 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 2. MaxN: Chọn lựa theo số lượng phần tử có giá trị tương tự lớn nhất: Ví dụ có 1 phần tử của S1 với hệ số có giá trị lớn nhất là 0,9, chọn giá trị này làm giá trj ứng cử. Với n > 1 thì chúng ta có vài giá trị để tính toán 3. MaxDelta: Phần tử s1 vơi giá trị tương tự lớn nhất được chọn làm giá trị ứng cử cộng với các phần tử Hình 3-11: Thực hiện bước Direction và Selection Tổng hợp kết quả Bước tiếp theo là kết hợp các giá trị tương tự cho tập các token của một phần tử. Để thực hiện việc này có thể sử dụng hai phương pháp Average và Dice sau đây để tính. Hai phương pháp này đều sử dụng các giá trị ứng cử được lựa chọn mc. Giả sử tất cả các giá trị ứng cử cho S1 và S2 đều được xác định, ta có 2 công thức sau: 1. Average: Giá trị tương tự trung bình được xác định bằng cách chia tổng các giá trị tương tự của tất cả các giá trị ứng cử của 2 tập S1, S2 cho tổng các phần tử của S1, S2. 49 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 Công thức 8: AverageSim 21 )1,2(22 ))1,2(,2( )2,1(11 ))2,1(,1( )2,1( SS SsmcSs Ssmcssim SsmcSs Ssmcssim SSASim + ∑ ∅≠∧∈ +∑ ∅≠∧∈= 2. Dice: Phương pháp này dựa trên hệ số Dice[] và trả về tỷ lệ của số phần tử có thể được đối sánh trên tổng số phần tử của S1, S2. Công thức 9: DiceSim { } { } 21 )1,2(222)2,1(111)2,1( SS SsmcSssSsmcSss SSDSim + ∅≠∧∈+∅≠∧∈= Đối với phương pháp Dice, ta nhận thấy các giá trị tương tự độc lập không ảnh hưởng đến giá trị tương tự của toàn bộ tập hợp. Do vậy Dice sẽ tối ưu hơn và cho giá trị tương tự lớn hơn so với phương pháp Average. Trong trường hợp tất cả các giá trị ứng cử đều bằng 1.0 thì cả hai sẽ cho cùng một kết quả. Hình 3-12: Tổng hợp kết quả Ví dụ: Giả sử có hai phần tử cần đối sánh Document_Signer và Dokument_User_Sign, sau khi phân tích thành các token ta có hai tập hợp sau {Document,Signer} và {Dokument,User,Sign}, sau khi áp dụng các thuật toán 50 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 đối sánh cơ bản ta có ma trận 3 chiều các giá trị tương tự nhau. Áp dụng thuật toán Max ta thu được mảng hai chiều các giá trị tương tự Document Dokument NGram(3) 0.699999988 Document Dokument EditDistance 0.875 Document user NGram(3) 0 Document user EditDistance 0.25 Document sign NGram(3) 0 Document sign EditDistance 0.125 signer Dokument NGram(3) 0 signer Dokument EditDistance 0.125 signer user NGram(3) 0.285714298 signer user EditDistance 0.333333333 signer sign NGram(3) 0.571428597 signer sign EditDistance 0.666666667 CubeSim Hình 3-13: SimCube theo phương pháp đối sánh kết hợp Document Dokument EditDistance 0.875 Document user EditDistance 0.25 Document sign EditDistance 0.125 signer Dokument EditDistance 0.125 signer user EditDistance 0.333333333 signer sign EditDistance 0.666666667 SimMatrix Hình 3-14: Kết quả sau khi thực hiện Aggregation Document Dokument EditDistance 0.875 signer sign EditDistance 0.666666667 Dokument Document EditDistance 0.875 user signer EditDistance 0.333333333 sign signer EditDistance 0.666666667 Document_signer->Dokument_user_sign Dokument_user_sign->Document_signer Hình 3-15: Kết quả sau khi thực hiện Direction và Selection 51 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 3-16:Kết quả sau khi tổng hợp 3.4 Mức cấu trúc Trong phần trước tôi đã trình bày thiết kế thuật toán đối sánh ở mức ngôn ngữ đối với các phần tử của lược đồ. Kết quả đầu ra là một ma trận các hệ số đối sánh tương ứng giữa các phần tử. Trong phần này tôi trình bày thuật toán đối sánh mức cấu trúc (structure-base). Thuật toán đối sánh mức cấu trúc dựa trên cấu trúc cây của lược đồ. Một số khái niệm về cây trong thuật toán • Node anh em: là các node có cùng cha • Node lá: Là các node không có con • Node trong: Không phải node lá Đối sánh mức cấu trúc sẽ xem xét ngữ cảnh (context) của một node hiện tại dựa trên các thông tin như các node lá, node cha, node con cháu… Để tính độ tương tự cho hai node ta xây dựng các qui tắc sau. 1. Trường hợp các node lá: Hệ số tương tự được tính dựa trên các yếu tố sau: hệ số tương tự mức ngôn ngữ, hệ số tương tự kiểu dữ liệu (data type), hệ số tương tự của node cha và các anh chị em của nó. Ví dụ trong hình dưới đây ta ta tính độ tương tự của hai node s3 và t4 dựa trên giá trị tương tự của mức ngôn ngữ, kiểu dữ liệu (data type), các node anh em (s4,t5), các node cha (s2,t2) 52 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 s1 s5s2 s4s3 t1 t3t2 t5t4 Sim(s3,t4)= Sim_context(lang,type,vicinity) Hình 3-17: Hệ số tương tự của 2 node lá 2. Trường hợp các node giữa: Hệ số tương tự được tính dựa trên các yếu tố sau: hệ số tương tự mức ngôn ngữ, hệ số tương tự kiểu dữ liệu (data type), hệ số tương tự của cây con có gốc tại hai node đó tương tự nhau. s1 s5s2 s4s3 t1 t3t2 t5t4 Sim(s1,t1)= Sim_context(lang,type,subtree) Hình 3-18: Hệ số tương tự của 2 node trong 53 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 Thuật toán đối sánh lược đồ dựa trên cấu trúc được mô tả dưới đây TreeMatch(Source S, Target T) For s ∈ S, t ∈ T (s,t: leaves) Set ssim(s,t) = datatype_match(s,t) S’=post_order(S), T’=post_order(T) For each s in S’ For each t in T’ ssim(s,t)=struct_sim(s,t) wsim(s,t)=wstruct.ssim(s,t)+(1-wstruct)lsim(s,t) if(wsim(s,t)>thhigh) increase_struct_sim(leaves(s),leaves(t),cinc) if(wsim(s,t)<thlow) decrease_struct_sim(leaves(s),leaves(t),cinc) Giải thích thuật toán: 1. Đầu tiên ta khởi tạo hệ số đối sánh theo cấu trúc ssim theo kiểu dữ liệu của phần tử được so sánh. Thủ tục datatype_match(s,t) được tham chiếu vào một bảng định nghĩa sẵn các hệ số đối sánh theo kiểu dữ liệu. Hệ số dsim(s,t) này nằm trong khoảng [0,1], nhằm mục đích tăng giảm các hệ số sau này, dsim được chuẩn hóa về khoảng [0,0.5] (dsim=dsim/2). Bảng đối sánh được định nghĩa tương tự bảng sau. Type(s) Type(t) datatype_match(s,t) string string 1.0 string date 0.2 decimal float 0.8 float float 1.0 float integer 0.9 … … … 2. Các phần tử của hai cây được duyệt theo thứ tự sau. 54 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. Trường hợp các phần tử là lá (leaf): Bước tiếp theo tính giá trị đối sánh cho hai phần tử s và t, giá trị ssim(s,t) chính là giá trị được tính trong vòng lặp trước với luật đối sánh trên kiểu dữ liệu của phần tử (datatype_match(s,t)). Trong đó wstruct là hệ số chỉ ra độ ưu tiên của đối sánh cấu trúc so với đối sánh mức ngôn ngữ. wstruct thường được chọn bằng 0.5 Công thức 10: Wsim cho các node lá wsim(s,t)=wstruct.ssim(s,t)+(1-wstruct)lsim(s,t) Ví dụ: Trong ví dụ tính lsim của phần tử document_signer và document_user_sign cho giá trị 0.68. Hệ sô sim(s,t) với tiêu chí là kiểu dữ liệu có giá trị 0.5(giá trị max) Ta có wsim (s,t)=0.5(0.5)+0.5.0.68=0.59 4. Trường hợp các phần tử không phải là lá (leaf):Khi một trong các phần tử không phải là lá (leaf), ssim được tính dựa trên số lượng của lá trong cây con có gốc tại các phần tử đang được so sánh.Một node lá trong một lược đồ nếu có một liên kết mạnh (strong link) tới một node lá trong một lược đồ khác nếu trọng số tương tự vượt qua ngưỡng chấp nhận được (thaccept). Trong công thức dưới đây trả về tập hợp các node lá trong cây con có gốc là s và có ít nhất một liên kết mạnh với node lá của cây có gốc là t. Công thức 11: Liên kết mạnh { }acceptthyxwsimtleavesysleavesxxtssl >∈∃∧∈= ),(),()(),( Công thức tính hệ số tương tự cuối cùng là: Công thức 12: ssim trong trường hợp là các node trong )()( ),(),( ),( tleavessleaves stsltssl tsssim += Υ Trong đó leaves(s): là số node lá của cây có gốc tại s 5. Nếu hai phần tử được so sánh là có mức giống nhau cao, ví dụ hệ số tương tự vượt quá ngưỡng thhigh thì tăng ssim của từng cặp của lá trong hai cây con có gốc tương ứng bởi hai phần tử một giá trị cinc (Tăng ssim nhưng không vượt quá 1.0). Ngược lại nếu hệ số tương tự nhỏ hơn thlow thì ta 55 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 giảm ssim của các node lá đi một giá trị cdec. Ví dụ trong hình 8, Org_Send được ánh xạ với Sender có hệ số giống nhau cao nên các node con của hai node đó được tăng thêm độ giống nhau hơn so với cặp name, address khác, tương tự như vậy nếu hệ số ssim nhỏ hơn ngưỡng thlow ta sẽ giảm hệ số ssim của các node lá Document Signer Org_Send Firstname Lastname Org_name Org_address Org_Receive Org_name Org_address Docs Signer Sender Name OrgName OrgAddress DeliverTo name address Organization ssim++ ssim-- Hình 3-19: Sự phụ thuộc của hệ số tương tự vào ngữ cảnh Trong thuật toán đối sánh dựa trên cấu trúc ở trên ta đã xem xét các yếu tố liên quan đến ngữ cảnh của từng phần tử trong lược đồ. Hai phần tử là tương tự nếu các lá của chúng là tương tự. Hệ số tương tự của các node lá được tăng hay giảm lại phụ thuộc vào node tổ tiên của chúng. Duyệt cây theo thứ tự sau bảo đảm rằng trước khi hai phần tử s1,s2 được so sánh thì các node lá của chúng đã được so sánh. 3.5 Chọn lựa ánh xạ Sau khi thực hiện hai thuật toán đối sánh mức ngôn ngữ và đối sánh mức cấu trúc ta có một tập các ánh xạ giữa các phần tử của hai lược đồ đầu vào. Đầu tiên ta xét trường hợp là các node lá, nếu với mỗi phần tử t trong lược đồ nguồn 56 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 và s trong lược đồ đích nếu ssim lớn hơn một giá trị thaccept (giá trị ngưỡng chấp nhận được) thì chọn ánh xạ này. Đối với trường hợp không là node lá, ta sẽ duyệt theo thứ tự sau hai lược đồ một lần nữa để tính toán lại hệ số tương tự của các node không phải là lá vì quá trình cập nhật hệ số tương tự của các node lá sẽ ảnh hưởng đến hệ số tương tự của các node không phải là lá. 4 Cài đặt và kết quả 4.1 Cài đặt Hệ thống Demo được xây dựng bằng công cụ Visual Studio .Net 2003, cung cấp giao diện đồ hoạ với các chuẩn sau • Ngôn ngữ cài đặt C# • XML và XML Schema • Các thư viện opensource o WordNet.Net: Từ điển từ vựng tiếng Anh o QuickGraph9: Thư viện hỗ việc xây dựng đồ thị trên ngôn ngữ C# • Môi trường cài đặt: Window 2000 , Window XP, Window 2003 với Net Framework Cấu trúc chương trình 9 57 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 3-20:Cấu trúc VNMatch • 3rdParty: Các thư viện hỗ trợ lập trình • Linguistic: Các thuật toán xử lý ngôn ngữ: EditDistance, NGram … • MatchLib: Phần core của VNMatch, bao gồm đối sánh ngôn ngữ và đối sánh cấu trúc • Schemas: Phần phân tích xử lý lược đồ đầu vào. • Sources: Chứa các lược đồ mẫu • Utils:Một số hàm hỗ trợ • ui:Phần giao diện chương trình Hình 3-21: MatchLib, phần core của VNMatch Lớp HybridMatcher chứa các hàm thực hiện việc đối sánh mức ngôn ngữ giữa các phần tử của hai lược đồ. 58 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 3-22: Lớp HybridMatcher Thông tin hỗ trợ Thông tin hỗ trợ của VNMatch bao gồm các danh mục sau • Bảng Synonym (thesauri.xml): chứa danh mục các từ đồng nghĩa • Bảng Abbreviation (abbreviation.xml): Chứa các từ được viết gọn 59 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 DataType (datatype.xml): Chứa các ánh xạ giữa các kiểu dữ liệu 60 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 4.2 Kết quả thử ngiệm Thử nghiệm trên 2 lược đồ đầu vào, hai lược đồ này biểu diễn mô hình các đối tượng trong một phiếu thanh toán đơn hàng. Schema1 <xsd:schema xmlns:xsd="" elementFormDefault="qualified"> 61 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 62 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 63 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 64 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 Schema2 <xsd:schema xmlns:xsd="" elementFormDefault="qualified"> 65 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 66 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 67 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 Kết quả 68 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 - PurchaseOrder.InvoiceTo.Address.country PurchaseOrder.InvoiceTo.Address.country: 0.9958 - PurchaseOrder.InvoiceTo.Address.postalCode PurchaseOrder.InvoiceTo.Address.postalCode: 0.9958 - PurchaseOrder.InvoiceTo.Address.street1 PurchaseOrder.InvoiceTo.Address.street: 0.9958 - PurchaseOrder.InvoiceTo.Address.city PurchaseOrder.InvoiceTo.Address.city: 0.9958 - PurchaseOrder.InvoiceTo.Address.stateProvince PurchaseOrder.InvoiceTo.Address.state: 0.97213334 - PurchaseOrder.InvoiceTo.Address PurchaseOrder.InvoiceTo.Address: 0.85524625 - PurchaseOrder.InvoiceTo.Contact.contactName PurchaseOrder.ContactPerson.firstName: 0.61975986 - PurchaseOrder.InvoiceTo.Contact.contactName PurchaseOrder.ContactPerson.lastName: 0.621613 - PurchaseOrder.InvoiceTo.Contact.companyName PurchaseOrder.InvoiceTo.Organization.name: 0.61861247 - PurchaseOrder.InvoiceTo.Contact.e-mail PurchaseOrder.ContactPerson.email: 0.5943921 - PurchaseOrder.InvoiceTo.Contact.telephone PurchaseOrder.ContactPerson.tel: 0.7819118 - PurchaseOrder.InvoiceTo.Contact PurchaseOrder.ContactPerson: 0.64217 - PurchaseOrder.InvoiceTo PurchaseOrder.InvoiceTo: 0.77725554 - PurchaseOrder.Items.Item.partDescription PurchaseOrder.Line.productName: 0.6937629 - PurchaseOrder.Items.Item.unitOfMeasure PurchaseOrder.Line.unitOfMeasureRef: 0.8225684 - PurchaseOrder.Items.Item.quantity PurchaseOrder.Line.quantity: 0.85372746 69 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 - PurchaseOrder.Items.Item.unitPrice PurchaseOrder.Line.unitPrice: 0.8566578 - PurchaseOrder.Items.Item.itemNumber PurchaseOrder.Line.lineNo: 0.8529762 - PurchaseOrder.Items.Item.partNumber PurchaseOrder.Line.productRef: 0.86023074 - PurchaseOrder.Items.Item PurchaseOrder.Line: 0.66273284 - PurchaseOrder.Header.yourAccountCode PurchaseOrder.currencyCode: 0.5750351 - PurchaseOrder.Header.orderNum PurchaseOrder.customerOrderRef: 0.73732954 - PurchaseOrder.Header.Contact.contactName PurchaseOrder.ContactPerson.firstName: 0.62261695 - PurchaseOrder.Header.Contact.contactName PurchaseOrder.ContactPerson.lastName: 0.62415266 - PurchaseOrder.Header.Contact.e-mail PurchaseOrder.ContactPerson.email: 0.59765023 - PurchaseOrder.Header.Contact.telephone PurchaseOrder.ContactPerson.tel: 0.78516996 - PurchaseOrder.Header.Contact PurchaseOrder.ContactPerson: 0.64673144 - PurchaseOrder.Header.orderDate PurchaseOrder.orderDate: 0.79244316 - PurchaseOrder.DeliverTo.Address.country PurchaseOrder.DeliverTo.Address.country: 0.9958 - PurchaseOrder.DeliverTo.Address.postalCode PurchaseOrder.DeliverTo.Address.postalCode: 0.9958 - PurchaseOrder.DeliverTo.Address.street1 PurchaseOrder.DeliverTo.Address.street: 0.9958 - PurchaseOrder.DeliverTo.Address.city PurchaseOrder.DeliverTo.Address.city: 0.9958 70 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 - PurchaseOrder.DeliverTo.Address.stateProvince PurchaseOrder.DeliverTo.Address.state: 0.97213334 - PurchaseOrder.DeliverTo.Address PurchaseOrder.DeliverTo.Address: 0.85524625 - PurchaseOrder.DeliverTo.Contact.contactName PurchaseOrder.ContactPerson.firstName: 0.619998 - PurchaseOrder.DeliverTo.Contact.contactName PurchaseOrder.ContactPerson.lastName: 0.6215336 - PurchaseOrder.DeliverTo.Contact.companyName PurchaseOrder.DeliverTo.Organization.name: 0.61861247 - PurchaseOrder.DeliverTo.Contact.e-mail PurchaseOrder.ContactPerson.email: 0.59503114 - PurchaseOrder.DeliverTo.Contact.telephone PurchaseOrder.ContactPerson.tel: 0.78255093 - PurchaseOrder.DeliverTo.Contact PurchaseOrder.ContactPerson: 0.64306474 - PurchaseOrder.DeliverTo PurchaseOrder.DeliverTo: 0.77725554 - PurchaseOrder PurchaseOrder: 0.8594128 71 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 5 Kết luận và hướng phát triển Phần này sẽ tóm tắt lại các vấn đề đã được nghiên cứu và giải quyết trong luận án, và tiếp theo sẽ là các xu hướng sẽ được nghiên cứu trong tương lai. 5.1 Kết luận Đối sánh lược đồ là một module quan trọng để giải quyết vấn đề tương tác giữa các ứng dụng và tích hợp dữ liệu trong nhiều lĩnh vực. Để giảm thiểu các thao tác thủ công nhiều nhất có thể, các phương pháp tiếp cận bán tự động (semi-automatic) cần hỗ trợ một cách hiệu quả người dùng trong bài toán đối sánh lược đồ. Luận văn này nghiên cứu về thực trạng của bài toán đối sánh lược đồ, thiết kế và thi công một ứng dụng đối sánh. Luận văn bao gồm các phần chính sau: Tổng quan về bài toán đối sánh lược đồ và các phương pháp tiếp cận Đầu tiên phân loại các dạng bài toán đối sánh để có một cái nhìn tổng quan về các phương pháp đã được đề cập. Dựa vào sự phân loại các bài toán, các phương pháp được sử dụng, đối sánh lược đồ được chia thành các phương pháp cơ bản sau: schema-based, instance-based, element-based, structure-based, language-based, constraint-based. Tiếp theo mô tả các kỹ thuật được sử dụng trong từng phương pháp đối sánh. Ngoài ra luận văn còn đề cập đến các phương pháp đánh giá hiệu quả của các thuật toán. Và cuối cùng là một số đề xuất phương pháp giải quyết cho các lược đồ được xây dựng bằng tiếng Việt. Thiết kế hệ thống đối sánh lược đồ VNMatch VNMatch được xây dựng trên cách tiếp cận của COMA++ và Cupid [3]. VNMatch xử lý dữ liệu đầu vào là các lược đồ được thiết kế bằng ngôn ngữ XMLSchema1. Phần đối sánh dựa trên ngôn ngữ (language-based) của VNMatch dựa trên mô hình của COMA++, tuy nhiên VNMatch được thiết kế một cách mềm 1 72 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 dẻo để dễ dàng bổ xung thêm các matcher (thuật toán đối sánh ) để nâng cao độ chính xác. Phần đối sánh mức cấu trúc (Structure-based) được thiết kế dựa trên mô hình của Cupid [3], đối sánh cấu trúc được thực hiện trên ngữ cảnh của node được so sánh, trong VNMatch ngữ cảnh được xét cho một node là các node lá của nó. 5.2 Hướng phát triển Mặc dù đã cố gắng hoàn thành luận văn về đối sánh lược đồ nhưng cũng còn rất nhiều vấn đề cầnphải làm để nâng cao được chất lượng của kết quả đối sánh. Mục tiêu của tôi trong thời gian sắp tới là tiếp tục hoàn thiện VNMatch theo hai tiêu chí sau đây. Hoàn thiện VNMatch • Xử lý được các lược đồ dữ liệu đầu vào như chuẩn SQL, OWL, XDR … • Làm mịn các thuật toán đối sánh dựa trên ngôn ngữ và cấu trúc, đặc biệt là kết hợp thêm các phương pháp đối sánh có cấu trúc để nâng cao chất lượng kết quả. • Xây dựng một thuật toán đối sánh đơn giản dựa trên ngôn ngữ cho tiếng Việt. • Tìm một bài toán tích hợp dữ liệu hoặc chuyển đổi dữ liệu cụ thể để áp dụng VNMatch. Xây dựng VNMatch Framework Xây dựng VNMatch thành một framework để thực hiện các bài toán đối sánh lược đồ. Việc phát triển một framework cho bài toán đối sánh này cũng được đánh giá rất quan trọng. Dựa trên framework, các nhà nghiên cứu sau này có thể tận dụng được các thuật toán có sẵn cũng như dễ dàng cài đặt một hệ thống đối sánh mà không phải mất nhiều thời gian. VNMatch Framework có các tính năng sau: • Về mặt kỹ thuật VNMatch Framework sẽ cung cấp khả năng tùy biến (customization) đối với các thuật toán đối sánh (matcher). Tùy biến quá trình tổng hợp kết quả của các thuật toán. 73 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 • Người sử dụng thực thi một thuật toán mới (matcher) có thể dễ dàng thêm vào hệ thống và kiểm tra được chất lượng của thuật toán. • Hỗ trợ những người nghiên cứu sau này có một công cụ để kiểm tra các kết quả nghiên cứu một cách nhanh nhất • Có thể tái sử dụng các kết quả nghiên cứu trước. Người dùng sẽ dành thời gian nghiên cứu phát triển các thuật toán đối sánh mà phải quan tâm nhiều đến phần cài đặt và tổng hợp. Hình 3-23: VNMatch Framework (đề xuất) VNMatch Framework bao gồm các thành phần chính sau 74 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. Biểu diễn lược đồ: Module này xử lý các loại lược đồ đầu vào cơ bản như SQL, XML Schema. Cung cấp một mô hình biểu diễn dưới dạng đồ thị cho tất cả các loại lược đồ. 2. Các Matcher: Các Matcher sẽ được thêm mới, thay đổi, hoặc loại bỏ trong hệ thống. 3. Matcher Combination Controller: Đây là phần nhân của hệ thống, sử dụng các đặc tả được định nghĩa trong Matcher Configuration và Combination configuration để xử lý. 4. Biểu diễn ánh xạ đầu ra VNMatch framework rất cần được sự hỗ trợ của các thầy, các cô và các bạn sinh viên để có thể trở thành một công cụ đắc lực phục vụ trước hết cho cộng đồng những người nghiên cứu về lĩnh vực này. 75 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ài liệu tham khảo Sách, bài báo, luận văn [1]. AnHai Doan,Alon Y. Halevy Sem. Sematic Integration in the database community: A Brief surve, 2005 [2]. Natalya F.Noy: Semantic Integration: A survey of ontology-based approaches, 2005 [3]. Jayant Madhavan, Philip A.Bernstein, Erhard Rahm. Generic schema matching with Cupid, 2001 [4]. Karthik Jagannathan: An approach to schema mapping generation for data warehousing, 2003 [5]. Adia Boukottaya, Christine Vanoirbeek 2005. Schema Matching for Transforming Structured Documents,2005 [6]. Rahm, E., P.A. Bernstein: A Survey of Approaches to Automatic Schema Matchin,2001 [7]. Do Hong Hai Ph.D. Thesis:Schema matching anf mapping-based Data integration, 2005 [8]. Troy Simpson, Thanh Dao: WordNet-based semantic similarity measurement [9]. Information Retrieval 2nd edition, C. J. Van Rijsbergen. [10]. Melnik, S., H. Garcia-Molina, E. Rahm: Similarity Flooding: A Versatile Graph Matching Algorithm and its Application to Schema Matching, 2002 Website [11]. World Wide Web Consortium [12]. OntologyMatching [13]. The MOMIS Project 76 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 [14]. [15]. COMA++ project [16]. Similarity Flooding project [17]. Data, Information, and Process Integration with Semantic Web Services --- Hết---