Đối sánh tự động lược đồ XML

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 ®èi s¸nh tù ®éng l−îc ®å XML NGÀNH: CÔNG NGHỆ THÔNG TIN MS: ………………………. VÕ SỸ NAM NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. HUỲNH QUYẾT THẮNG HÀ NỘI - 2006 Mục lục Danh mục từ viết tắt, thuật ngữ.............................. Error! Bookmark not defined. Danh mục bảng biểu ................................................ Error! Bookmark not defined. Danh mục hình vẽ..................................................... Error! Bookmark not defined. Mở đầu ...................................................................... Error! Bookmark not defined. 1. Giới thiệu chung......................................................... Error! Bookmark not defined. 2. Nội dung luận văn ...................................................... Error! Bookmark not defined. Chương 1 Đối sánh lược đồ ..................................... Error! Bookmark not defined. 1.1 Tổng quan về đối sánh lược đồ ............................... Error! Bookmark not defined. 1.1.1 Các khái niệm cơ bản về đối sánh lược đồ ......... Error! Bookmark not defined. 1.1.2 Các lĩnh vực ứng dụng đối sánh lược đồ ............ Error! Bookmark not defined. 1.2 Các tiếp cận đối sánh lược đồ ................................. Error! Bookmark not defined. 1.2.1 Phân loại các tiếp cận đối sánh lược đồ............. Error! Bookmark not defined. 1.2.2 Các tiếp cận đối sánh lược đồ ............................ Error! Bookmark not defined. 1.2.3 Các phương pháp đối sánh lược đồ.................... Error! Bookmark not defined. 1.3 Các hệ thống đối sánh lược đồ XML...................... Error! Bookmark not defined. 1.3.1 Cupid (trung tâm nghiên cứu Microsoft) ............ Error! Bookmark not defined. 1.3.2 Similarity Flooding (Đại học Stanford và đại học Leipzig) ... Error! Bookmark not defined. 1.3.3 LSD (Đại học Washington)................................. Error! Bookmark not defined. 1.3.4 Clio (IBM Almaden và đại học Toronto) ............ Error! Bookmark not defined. 1.3.5 Một số hệ thống đối sánh lược đồ khác .............. Error! Bookmark not defined. 1.4 Kết chương ............................................................... Error! Bookmark not defined. Chương 2 Các định nghĩa hình thức ...................... Error! Bookmark not defined. 2.1 Vấn đề đối sánh lược đồ XML ................................ Error! Bookmark not defined. 2.1.1 Đối sánh ngữ nghĩa và đối sánh cú pháp ........... Error! Bookmark not defined. 2.1.2 Thông tin đầu vào của tiến trình đối sánh .......... Error! Bookmark not defined. 2.1.3 Thông tin đầu ra của tiến trình đối sánh ............ Error! Bookmark not defined. 2.1.4 Các định nghĩa hình thức.................................... Error! Bookmark not defined. 2.2 Mô hình hóa lược đồ XML...................................... Error! Bookmark not defined. 2.2.1 Các nút đồ thị lược đồ ........................................ Error! Bookmark not defined. 2.2.2 Các cạnh đồ thị lược đồ...................................... Error! Bookmark not defined. 2.2.3 Các ràng buộc đồ thị lược đồ ............................. Error! Bookmark not defined. 2.2.4 Các định nghĩa hình thức.................................... Error! Bookmark not defined. 2.3 Ánh xạ nguồn–đích .................................................. Error! Bookmark not defined. 2.4 Kết chương ............................................................... Error! Bookmark not defined. Chương 3 Đối sánh tự động lược đồ XML ............ Error! Bookmark not defined. 3.1 Tổng quan về đối sánh tự động lược đồ XML....... Error! Bookmark not defined. 3.2 Đo độ tương đồng ngôn ngữ.................................... Error! Bookmark not defined. 3.2.1 WordNet và quan hệ ngữ nghĩa giữa các từ ....... Error! Bookmark not defined. 3.2.2 Thuật toán của Hirst và St-Onge ........................ Error! Bookmark not defined. 3.2.3 Giải pháp của hệ thống Cupid ............................ Error! Bookmark not defined. 3.3 Xét tính tương thích kiểu dữ liệu lược đồ XML và phân tích phân cấp kiểu người thiết kế.................................................................. Error! Bookmark not defined. 3.3.1 Xét tính tương thích kiểu dữ liệu lược đồ XML .. Error! Bookmark not defined. 3.3.2 Phân tích phân cấp kiểu người thiết kế .............. Error! Bookmark not defined. 3.4 Đo độ tương đồng cấu trúc...................................... Error! Bookmark not defined. 3.4.1 Định nghĩa ngữ cảnh nút .................................... Error! Bookmark not defined. 3.4.2 Đo độ tương tự đường dẫn.................................. Error! Bookmark not defined. 3.4.3 Đo độ tương đồng ngữ cảnh nút ......................... Error! Bookmark not defined. 3.5 Đo độ tương đồng nút và tạo ánh xạ giữa các phần tử........Error! Bookmark not defined. 3.5.1 Đo độ tương đồng nút ......................................... Error! Bookmark not defined. 3.5.2 Tạo ánh xạ giữa các nút và cạnh đối sánh ......... Error! Bookmark not defined. 3.6 Đánh giá tiến trình đối sánh lược đồ XML............ Error! Bookmark not defined. 3.6.1 Các phương pháp đánh giá................................. Error! Bookmark not defined. 3.6.2 Đánh giá giải pháp ............................................. Error! Bookmark not defined. 3.7 Áp dụng đối sánh lược đồ trong bài toán chuyển đổi tài liệu có cấu trúc ...Error! Bookmark not defined. 3.7.1 Tổng quan về tài liệu có cấu trúc ....................... Error! Bookmark not defined. 3.7.2 Chuyển đổi tự động tài liệu có cấu trúc.............. Error! Bookmark not defined. 3.7.3 Mô hình cho hệ thống chuyển đổi tự động tài liệu XML ...Error! Bookmark not defined. 3.8 Kết chương ............................................................... Error! Bookmark not defined. Kết luận và hướng phát triển.................................. Error! Bookmark not defined. 1. Đóng góp chính của luận văn.................................... Error! Bookmark not defined. 2. Hướng phát triển........................................................ Error! Bookmark not defined. Danh mục tài liệu tham khảo .................................. Error! Bookmark not defined. Phụ lục....................................................................... Error! Bookmark not defined. Phụ lục A: Ngôn ngữ đánh dấu mở rộng - XML ........ Error! Bookmark not defined. Phụ lục B: Lược đồ XML .............................................. Error! Bookmark not defined. Phụ lục C: Thuật toán của Hirst và St-Onge .............. Error! Bookmark not defined. 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 ®èi s¸nh tù ®éng l−îc ®å XML NGÀNH: CÔNG NGHỆ THÔNG TIN MS: ………………………. VÕ SỸ NAM NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. HUỲNH QUYẾT THẮNG HÀ NỘI - 2006 Đối sánh tự động lược đồ XML Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin i Lời cảm ơn Luận văn này đánh dấu kết thúc hai năm cao học tại trường đại học Bách Khoa Hà Nội. Trong quãng thời gian tuy chưa dài nhưng cũng không phải là ngắn đó, tôi đã trưởng thành rất nhiều về kiến thức cũng như khả năng nghiên cứu. Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo – TS. Huỳnh Quyết Thắng, người đã hướng dẫn, giúp đỡ tôi hết sức tận tình trong quá trình thực hiện luận văn tốt nghiệp. Thầy là người đã cung cấp ý tưởng, tài liệu ban đầu về đề tài, các hướng dẫn quan trọng trong suốt quá trình thực hiện luận văn, dành thời gian đọc và sửa chữa báo cáo cũng như có những góp ý rất quan trọng cho tôi trong suốt quá trình hoàn thiện luận văn này. Tôi xin cám ơn thư viện trường EPFL, Thụy Sỹ đã cung cấp cho tôi một số tài liệu tham khảo bổ ích, xin cảm ơn các nhóm sinh viên K48 khoa Công nghệ thông tin, trường đại học Bách Khoa Hà Nội đã tận tình làm việc cùng tôi và góp nhiều công sức trong quá trình cài đặt thử nghiệm chương trình. Tôi xin gửi lời cám ơn sâu sắc tới các thầy giáo, cô giáo của trường đại học Bách Khoa Hà Nội, khoa Công nghệ thông tin đã tận tình giảng dạy, trang bị kiến thức cho chúng tôi, xin gửi lời cám ơn bộ môn Kỹ thuật hệ thống, khoa Công nghệ thông tin, trường đại học Xây dựng Hà Nội đã hết sức tạo điều kiện về thời gian cho tôi hoàn thành luận văn này. Tôi cũng xin gửi lời cám ơn tới các bạn của tôi, những người đã chia sẻ với tôi nhiệt huyết và niềm say mê học tập & nghiên cứu khoa học, chia sẻ với tôi kiến thức và phương pháp tìm hiểu vấn đề, cung cấp cho tôi các tài liệu thiết thực cũng như những ý tưởng bổ sung cho luận văn, góp phần giúp tôi thực hiện luận văn này trong sự cố gắng và nỗ lực cao nhất. Cuối cùng nhưng cũng là điều quan trọng nhất, cho tôi gửi lời cảm ơn sâu sắc tới bố, mẹ, em trai và những người thân của tôi, những người đã giúp đỡ tôi rất nhiều cả về vật chất lẫn tinh thần trong suốt quá trình học tập và công tác, động viên tôi trong những lúc khó khăn cũng như chia sẻ niềm vui với tôi những lúc thành công. Một lần nữa tôi xin chân thành cám ơn tất cả./. Hà Nội, tháng 11 năm 2006 Võ Sỹ Nam Đối sánh tự động lược đồ XML Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin ii Mục lục Danh mục từ viết tắt, thuật ngữ........................................................................... iv Danh mục bảng biểu .............................................................................................. v Danh mục hình vẽ................................................................................................... v Mở đầu .................................................................................................................... 1 1. Giới thiệu chung...........................................................................................................1 2. Nội dung luận văn ........................................................................................................3 Chương 1 Đối sánh lược đồ ................................................................................... 6 1.1 Tổng quan về đối sánh lược đồ .................................................................................7 1.1.1 Các khái niệm cơ bản về đối sánh lược đồ ...........................................................7 1.1.2 Các lĩnh vực ứng dụng đối sánh lược đồ ..............................................................8 1.2 Các tiếp cận đối sánh lược đồ .................................................................................14 1.2.1 Phân loại các tiếp cận đối sánh lược đồ.............................................................14 1.2.2 Các tiếp cận đối sánh lược đồ ............................................................................15 1.2.3 Các phương pháp đối sánh lược đồ....................................................................17 1.3 Các hệ thống đối sánh lược đồ XML......................................................................20 1.3.1 Cupid (trung tâm nghiên cứu Microsoft) ............................................................21 1.3.2 Similarity Flooding (đại học Stanford và đại học Leipzig) ...............................23 1.3.3 LSD (đại học Washington)..................................................................................24 1.3.4 Clio (IBM Almaden và đại học Toronto) ............................................................25 1.3.5 Một số hệ thống đối sánh lược đồ khác ..............................................................26 1.4 Kết chương ...............................................................................................................28 Chương 2 Các định nghĩa hình thức .................................................................. 29 2.1 Vấn đề đối sánh lược đồ XML ................................................................................30 2.1.1 Đối sánh ngữ nghĩa và đối sánh cú pháp ...........................................................30 2.1.2 Thông tin đầu vào của tiến trình đối sánh ..........................................................32 2.1.3 Thông tin đầu ra của tiến trình đối sánh ............................................................34 2.1.4 Các định nghĩa hình thức....................................................................................35 2.2 Mô hình hóa lược đồ XML......................................................................................36 2.2.1 Các nút đồ thị lược đồ ........................................................................................37 2.2.2 Các cạnh đồ thị lược đồ......................................................................................37 2.2.3 Các ràng buộc đồ thị lược đồ .............................................................................38 2.2.4 Các định nghĩa hình thức....................................................................................40 2.3 Ánh xạ nguồn–đích ..................................................................................................43 2.4 Kết chương ...............................................................................................................46 Đối sánh tự động lược đồ XML Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin iii Chương 3 Đối sánh tự động lược đồ XML ........................................................ 47 3.1 Tổng quan về đối sánh tự động lược đồ XML.......................................................48 3.2 Đo độ tương đồng ngôn ngữ....................................................................................49 3.2.1 WordNet và quan hệ ngữ nghĩa giữa các từ .......................................................49 3.2.2 Thuật toán của Hirst và St-Onge ........................................................................50 3.2.3 Giải pháp của hệ thống Cupid ............................................................................52 3.3 Xét tính tương thích kiểu dữ liệu lược đồ XML và phân tích phân cấp kiểu người thiết kế..................................................................................................................53 3.3.1 Xét tính tương thích kiểu dữ liệu lược đồ XML ..................................................53 3.3.2 Phân tích phân cấp kiểu người thiết kế ..............................................................55 3.4 Đo độ tương đồng cấu trúc......................................................................................56 3.4.1 Định nghĩa ngữ cảnh nút ....................................................................................56 3.4.2 Đo độ tương tự đường dẫn..................................................................................58 3.4.3 Đo độ tương đồng ngữ cảnh nút .........................................................................63 3.5 Đo độ tương đồng nút và tạo ánh xạ giữa các phần tử.........................................66 3.5.1 Đo độ tương đồng nút .........................................................................................66 3.5.2 Tạo ánh xạ giữa các nút và cạnh đối sánh .........................................................67 3.6 Đánh giá tiến trình đối sánh lược đồ XML............................................................68 3.6.1 Các phương pháp đánh giá.................................................................................68 3.6.2 Đánh giá giải pháp .............................................................................................70 3.7 Áp dụng đối sánh lược đồ trong bài toán chuyển đổi tài liệu có cấu trúc ..........72 3.7.1 Tổng quan về tài liệu có cấu trúc .......................................................................73 3.7.2 Chuyển đổi tự động tài liệu có cấu trúc..............................................................76 3.7.3 Mô hình cho hệ thống chuyển đổi tự động tài liệu XML ....................................78 3.8 Kết chương ...............................................................................................................80 Kết luận và hướng phát triển.............................................................................. 81 1. Đóng góp chính của luận văn....................................................................................81 2. Hướng phát triển........................................................................................................84 Danh mục tài liệu tham khảo .............................................................................. 86 Phụ lục................................................................................................................... 88 Phụ lục A: Ngôn ngữ đánh dấu mở rộng - XML ........................................................89 Phụ lục B: Lược đồ XML ..............................................................................................97 Phụ lục C: Thuật toán của Hirst và St-Onge ............................................................100 Đối sánh tự động lược đồ XML Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin iv Danh mục từ viết tắt, thuật ngữ Từ viết tắt/ thuật ngữ Giải nghĩa Ghi chú CSDL Cơ sở dữ liệu TTNT Trí tuệ nhân tạo XML eXtended Markup Language DTD Document Type Definition XSD XML Schema Definition SGML Standard Generalized Markup Language LCS Longest Common Subsequence Đối sánh tự động lược đồ XML Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin v Danh mục bảng biểu Bảng 3. 1 Đặc điểm các lược đồ thử nghiệm...................................................... 70 Bảng 3. 2 Kết quả đo chất lượng đối sánh ......................................................... 71 Danh mục hình vẽ Hình 2. 1 Ví dụ về đồ thị lược đồ ........................................................................ 36 Hình 3. 1 Tiến trình tính toán độ tương đồng phần tử ..................................... 49 Hình 3. 2 Ngữ cảnh của một phần tử lược đồ.................................................... 57 Hình 3. 3 So sánh các đối sánh thực với các đối sánh suy diễn được .............. 70 Hình 3. 4 Biểu đồ so sánh kết quả thực thi ........................................................ 72 Hình 3. 5 Mô hình cho hệ thống chuyển đổi tự động tài liệu XML................. 79 Mở đầu Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 1 Mở đầu 1. Giới thiệu chung Một vấn đề rất quan trọng trong các hệ thống xử lý thông tin là trao đổi và sử dụng lại dữ liệu giữa các hệ thống có dữ liệu không đồng nhất. Tính không đồng nhất của dữ liệu là do các tổ chức hoặc ứng dụng thường tạo ra dữ liệu cho chính mình dựa trên các yêu cầu riêng biệt. Các yêu cầu này hầu hết thường được đặc tả trong các mô hình dữ liệu trừu tượng, còn gọi là các lược đồ (chẳng hạn như lược đồ quan hệ, lược đồ hướng đối tượng và gần đây là lược đồ XML). Trong những năm gần đây, sự phát triển mạnh mẽ của các nguồn dữ liệu Web với rất nhiều mô hình thông tin và cú pháp mã hóa khác nhau đã dẫn đến nhu cầu ngày càng cấp thiết của việc phát triển các phương pháp và công cụ hỗ trợ cho việc trao đổi và sử dụng lại dữ liệu, do vậy đã có rất nhiều nghiên cứu quan tâm đến vấn đề này. Như ta biết, đối sánh lược đồ là vấn đề trung tâm trong hầu hết các nghiên cứu đó. Bài toán đối sánh lược đồ có thể được định nghĩa một cách phi hình thức như sau: [6], [11] “Cho hai lược đồ S1 và S2 trên mô hình dữ liệu bất kỳ, có thể có thêm thông tin phụ trợ và một ánh xạ khởi đầu, hãy tìm ánh xạ giữa các phần tử lược đồ thỏa mãn yêu cầu người dùng”. Nói cách khác, đây là vấn đề tìm kiếm sự tương đồng giữa các phần tử của S1 và S2 (hay là việc xác định các thành phần tương đương nhau giữa hai lược đồ nguồn và đích đã cho) bằng cách khai thác các thông tin tồn tại trong lược đồ, dữ liệu và các nguồn thông tin phụ trợ. Mở đầu Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 2 Thực tế cho thấy, các thách thức gặp phải khi tìm kiếm giải pháp cho bài toán đối sánh lược đồ là rất lớn. Thứ nhất, quá trình này cần đến sự phân tích ngữ nghĩa trong các lược đồ đó, hay nói cách khác ta cần suy diễn được nhận thức về lược đồ của người tạo ra nó. Tuy vậy, các lược đồ thường được thiết kế bởi những con 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. Thứ hai, việc khai thác thông tin cho bài toán đối sánh lược đồ gặp rất nhiều khó khăn vì ta phải khai thác một lượng lớn thông tin hỗn tạp và không chắc chắn, ví dụ như tài liệu đặc tả lược đồ, các nguồn dữ liệu của lược đồ… Từ các phân tích trên, có thể thấy rằng việc đối sánh lược đồ bằng tay thường khá tốn kém và dễ gây lỗi. Điều đó cho thấy việc phát triển các kỹ thuật nhằm tự động hóa một cách tối đa tiến trình đối sánh lược đồ là rất quan trọng. Hiện nay, XML (eXtended Markup Language - ngôn ngữ đánh dấu mở rộng) [24] đã trở thành chuẩn ngôn ngữ hiệu quả và thích hợp cho việc biểu diễn dữ liệu trên Web. Nhu cầu sử dụng XML như là chuẩn biểu diễn và trao đổi dữ liệu ngày càng tăng của cộng đồng Web đã tạo nên một lượng dữ liệu XML ngày càng lớn. Gắn liền với sự gia tăng đó, một lượng lớn các lược đồ XML [25], [26], [27] đã được phát triển với rất nhiều đặc tả khác nhau, dẫn đến một lượng lớn dữ liệu XML không đồng nhất. Thêm vào đó, hiện tại lại có khá nhiều ngôn ngữ lược đồ khác nhau được đưa ra, dẫn đến sự không đồng nhất về mặt cú pháp ở các ngôn ngữ lược đồ. Với sự phát triển nhanh chóng và sự tăng trưởng mạnh mẽ về mặt quy mô của các ứng dụng Web, đặc biệt là sự phổ dụng của Internet và công nghệ XML, đã có rất nhiều nghiên cứu quan tâm đến vấn đề trao đổi và sử dụng lại dữ liệu XML. Vấn đề đối sánh lược đồ XML do vậy ngày càng trở nên quan trọng. Nhằm góp phần tìm hiểu và giải quyết vấn đề đó một cách hiệu quả hơn, luận văn này sẽ tổng hợp lại cũng như đưa ra các đóng góp thêm cho bài toán đối sánh lược đồ XML. Mở đầu Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 3 2. Nội dung luận văn Luận văn này nghiên cứu vấn đề đối sánh tự động lược đồ XML. Luận văn bao gồm ba chương. Chương 1 mô tả tổng quan về vấn đề đối sánh lược đồ. Chương 2 đưa ra các định nghĩa hình thức cho vấn đề đối sánh lược đồ XML. Chương 3 mô tả giải pháp đối sánh tự động lược đồ XML. Cũng trong chương 3, chúng tôi sẽ xem xét vấn đề chuyển đổi tự động tài liệu XML. Cuối cùng, phần kết luận nêu lên những đóng góp chính và các hướng phát triển. Sau đây là những nội dung chính của luận văn: Chương 1: Đối sánh lược đồ. Chương này bao gồm ba nội dung chính: - Trình bày các khái niệm, định nghĩa cơ bản về vấn đề đối sánh lược đồ và các lĩnh vực ứng dụng chính của đối sánh lược đồ như tích hợp lược đồ, tích hợp dữ liệu, kho dữ liệu, chuyển đổi (hay dịch, trao đổi) dữ liệu, quản lý dữ liệu ngang hàng, thương mại điện tử, đối sánh và tích hợp ontology, Web ngữ nghĩa, xử lý truy vấn ngữ nghĩa, v.v.. - Trình bày các tiếp cận đối sánh lược đồ điển hình. Phần này chúng tôi sẽ xem xét các tiếp cận điển hình như tiếp cận dựa trên học máy, dựa trên luật, dựa trên siêu dữ liệu cũng như một số tiếp cận khác. Tiếp theo chúng tôi sẽ xem xét các phương pháp đối sánh điển hình như đối sánh ngôn ngữ, đối sánh dựa trên ràng buộc, đối sánh cấu trúc và một số phương pháp khác. Chúng tôi cũng sẽ phân tích những điểm mạnh cũng như những hạn chế của các giải pháp này, từ đó lựa chọn giải pháp cho tiếp cận của chúng tôi. - Mô tả một số hệ thống đối sánh lược đồ cũng như phân tích các đặc điểm cơ bản nhất của các hệ thống đó. Thông qua các hệ thống này, đặc biệt là hai hệ thống Cupid [11] và Similarity Flooding [12], chúng tôi sẽ phân tích các giới hạn của các thuật toán đối sánh lược đồ hiện tại, từ đó lựa chọn các thuật toán đối sánh sẽ sử dụng trong tiếp cận của chúng tôi. Mở đầu Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 4 Chương 2: Các định nghĩa hình thức. Chương này bao gồm ba nội dung chính: - Trình bày các định nghĩa hình thức cho vấn đề đối sánh lược đồ, tập trung vào lược đồ XML. Các giải pháp hiện hành nhìn chung không quan tâm nhiều đến việc đưa ra các định nghĩa hình thức đầy đủ cho vấn đề. Trong chương này, chúng tôi cũng sẽ mô tả các giả thiết cơ bản cho vấn đề đối sánh lược đồ XML. - Trình bày giải pháp mô hình hóa lược đồ XML dựa trên đồ thị gán nhãn có hướng với các ràng buộc. Các nút của đồ thị biểu diễn các phần tử và các thuộc tính của lược đồ XML trong khi các cạnh của đồ thị biểu diễn các quan hệ khác nhau giữa các phần tử. - Mô tả đại số ánh xạ nguồn–đích áp dụng cho vấn đề chuyển đổi dữ liệu. Đại số ánh xạ nguồn–đích là một mở rộng của đại số quan hệ chuẩn. Trong luận văn này chúng tôi sẽ xem xét tập các phép toán bao gồm hợp, chọn, nhập, tách, nối, áp dụng và đổi tên. Chương 3: Đối sánh tự động lược đồ XML. Chương này mô tả giải pháp đối sánh tự động lược đồ XML, đánh giá giải pháp và mô tả một ứng dụng điển hình cho đối sánh lược đồ, vấn đề chuyển đổi tự động tài liệu XML. Chương này bao gồm các nội dung chính sau: - Mô tả tiến trình tính toán độ tương đồng phần tử theo ba pha: + Đo độ tương đồng ngôn ngữ: sử dụng thuật toán của Hirst và St- Onge để tính toán khoảng cách ngữ nghĩa dựa trên WordNet [7]. Thuật toán này được thay đổi để đưa ra hệ số tương đồng cũng như các quan hệ ngữ nghĩa (tương đương, rộng hơn, hẹp hơn, v.v..). + Xét tính tương thích kiểu dữ liệu: dựa trên việc phân tích các kiểu dữ liệu lược đồ XML để suy ra hệ số tương thích kiểu dữ liệu. Với nút nguyên tố (tức nút lá) chúng tôi sử dụng phân cấp kiểu lược đồ XML [27], còn với nút Mở đầu Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 5 trung gian chúng tôi sử dụng các tính năng như thừa kế kiểu, nhóm thay thế và kiểu trừu tượng để tìm kiếm các ánh xạ phức hợp. + Đo độ tương đồng cấu trúc: khác với các thuật toán đối sánh cấu trúc hiện hành, chúng tôi nhấn mạnh vào khái niệm ngữ cảnh của phần tử. Ngữ cảnh của một phần tử là sự kết hợp ngữ cảnh tổ tiên, ngữ cảnh con và ngữ cảnh lá của nó. Để so sánh các ngữ cảnh này, chúng tôi so sánh các đường dẫn dựa trên các ý tưởng về trả lời truy vấn đường dẫn. - Đưa ra các ánh xạ trực tiếp cũng như phức hợp giữa các phần tử lược đồ (với các phép toán chuyển đổi và điều kiện chuyển đổi tương ứng) từ độ tương đồng phần tử đã tính toán. - Đánh giá giải pháp đối sánh lược đồ XML đã đưa ra sử dụng các phép đo chất lượng được đã được định nghĩa trong [5]. Cũng trong chương này, chúng tôi sẽ xem xét một trong những ứng dụng điển hình của đối sánh lược đồ, vấn đề chuyển đổi tài liệu có cấu trúc. Đầu tiên chúng tôi mô tả tổng quan về tài liệu có cấu trúc, tiếp theo chúng tôi trình bày vấn đề chuyển đổi tự động tài liệu có cấu trúc và cuối cùng chúng tôi đưa ra một mô hình cho hệ thống chuyển đổi tự động tài liệu XML. Trong tương lai chúng tôi có ý định áp dụng giải pháp đối sánh lược đồ nêu trên vào mô hình này. Kết luận và các hướng phát triển. Trong phần này, chúng tôi sẽ nêu lên các đóng góp chính của luận văn và đưa ra một số định hướng phát triển trong tương lai cho đề tài. Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 6 Chương 1 Đối sánh lược đồ Trong chương này chúng tôi tổng hợp lại các kết quả nghiên cứu điển hình về vấn đề đối sánh lược đồ. Trước hết chúng tôi trình bày các khái niệm cơ bản cũng như các lĩnh vực ứng dụng điển hình của đối sánh lược đồ. Như ta sẽ thấy, các lĩnh vực này là rất phong phú, cho thấy tầm quan trọng của bài toán đối sánh lược đồ. Tiếp theo chúng tôi mô tả các tiếp cận đối sánh cơ bản và các phương pháp đối sánh thông dụng hiện nay. Dựa trên các khảo sát về đối sánh lược đồ cũng như một số nghiên cứu gần đây, chúng tôi tiến hành phân tích và so sánh các tiếp cận này. Như ta sẽ thấy, các giải pháp đối sánh thường kết hợp nhiều phương pháp khác nhau để tăng tính hiệu quả cho tiến trình đối sánh. Trong chương này chúng tôi cũng mô tả một số hệ thống đối sánh lược đồ điển hình đã được thực hiện, đánh giá và so sánh các thuật toán được sử dụng trong các hệ thống này. Từ các đánh giá đó chúng tôi nêu ra các hạn chế cơ bản của các thuật toán này, đặc biệt là trong vấn đề chuyển đổi dữ liệu. Cuối cùng, trên cơ sở các phân tích trên, chúng tôi sẽ chứng tỏ rằng các thuật toán đối sánh lược đồ hiện tại cần được phát triển và hoàn thiện thêm nhằm giải quyết vấn đề tự động hóa tiến trình đối sánh lược đồ một cách có hiệu quả nhất. Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 7 1.1 Tổng quan về đối sánh lược đồ 1.1.1 Các khái niệm cơ bản về đối sánh lược đồ Đối sánh lược đồ là quá trình thao tác trên các lược đồ với đầu vào là hai lược đồ không đồng nhất và có thể có thêm thông tin phụ, trả về một tập các ánh xạ cho biết sự liên quan ngữ nghĩa giữa các phần tử lược đồ [17]. Trong thực tế, đối sánh lược đồ thường được thực hiện bằng tay với sự hỗ trợ của các công cụ đồ họa. Quá trình này thường tốn thời gian và dễ gây lỗi, bởi vậy đã có nhiều nghiên cứu được tiến hành nhằm tự động hóa tiến trình đối sánh lược đồ. Tuy nhiên đây là một vấn đề khó và phức tạp do một số lý do cơ bản sau: [21] - Các phần tử lược đồ được đối sánh trên cơ sở ngữ nghĩa của chúng. Ngữ nghĩa có thể được thể hiện từ một số nguồn thông tin như người thiết kế, tài liệu, lược đồ và thể hiện dữ liệu. Thực tế cho thấy người thiết kế rất khó để nhớ được tất cả chi tiết lược đồ và tài liệu hiện có thì thường không chính xác, không được cập nhật và không thể truy cập. Do đó tiến trình đối sánh lược đồ thường dựa hoàn toàn trên các dấu hiệu trong lược đồ và thể hiện dữ liệu. - Các lược đồ đã phát triển cho các ứng dụng khác nhau thì thường không đồng nhất, tức là mặc dù dữ liệu chúng mô tả là tương đồng về ngữ nghĩa nhưng cấu trúc và cú pháp sử dụng lại có thể khác nhau đáng kể. - Để giải quyết các xung đột ngữ nghĩa và lược đồ, đối sánh lược đồ thường dựa trên tên phần tử, kiểu dữ liệu phần tử, các định nghĩa cấu trúc, các ràng buộc toàn vẹn và các giá trị dữ liệu. Tuy vậy, các dấu hiệu này thường không chắc chắn và không đầy đủ. Ví dụ các nhãn giống nhau có thể được sử dụng cho các phần tử lược đồ có ý nghĩa hoàn toàn khác nhau. Ngược lại, hai phần tử với các nhãn khác nhau có thể._. tham chiếu tới cùng một thực thể thực tế. Kiểu dữ liệu cũng thường không chính xác (ví dụ sử dụng kiểu "string" Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 8 thay vì "date") và các ràng buộc thường là không đầy đủ. Trong điều kiện này, vấn đề chính sẽ không chỉ là việc phải xác định được các quan hệ đang tồn tại giữa các phần tử lược đồ mà còn phải chắc chắn rằng tiến trình đối sánh sẽ không đưa ra các ánh xạ không chính xác. - Ánh xạ đơn giản nhất là ánh xạ một-một, nối kết một phần tử lược đồ nguồn trực tiếp tới một phần tử lược đồ đích. Tuy vậy trong thực tế, một phần tử trong lược đồ này có thể tương ứng với nhiều phần tử trong lược đồ khác bằng cách áp dụng một hoặc một vài phép toán (ví dụ phần tử đích “Name” tương ứng với ghép nối của hai phần tử nguồn “firstName” và “lastName”) và thậm chí nhiều phần tử trong lược đồ này cũng có thể tương ứng với nhiều phần tử trong một lược đồ khác. Loại ánh xạ này được gọi là phức hợp hay gián tiếp và thường không thể suy ra được ngay từ lược đồ và các thể hiện mà thường đòi hỏi sự can thiệp của người dùng. Việc khám phá ánh xạ phức hợp là một vấn đề khó và phức tạp bởi vì quá trình đối sánh không chỉ cần tìm kiếm các ánh xạ này mà còn phải nhận biết các phép toán cần đến chẳng hạn như ghép nối hai phần tử, hợp nhất hoặc phân chia các giá trị dữ liệu, v.v.. - Hiển nhiên quá trình đối sánh lược đồ không thể thực hiện tự động được hoàn toàn, do vậy nó đòi hỏi phải có sự can thiệp của người dùng. Từ đó có thể thấy một điều quan trọng là quá trình đối sánh không chỉ cần tự động đến mức có thể mà còn phải nhận biết được khi nào đầu vào người dùng là cần thiết và đầu vào đó phải được khai thác một cách hiệu quả nhất. 1.1.2 Các lĩnh vực ứng dụng đối sánh lược đồ Đối sánh lược đồ là bước then chốt trong những ứng dụng mà dữ liệu chúng xử lý được cấu trúc hóa dưới các mô hình đã chỉ ra (chẳng hạn như lược đồ quan hệ, lược đồ hướng đối tượng, DTD, lược đồ XML, v.v..) hoặc những ứng dụng mà các lược đồ chúng khai thác là không đồng nhất. Đối Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 9 sánh lược đồ cho phép thao tác trên các lược đồ, dịch dữ liệu và trả lời truy vấn qua các lược đồ không đồng nhất. Nhiều ứng dụng khác nhau dựa trên đối sánh lược đồ đã xuất hiện và đã được nghiên cứu rộng rãi trong các lĩnh vực cơ sở dữ liệu (CSDL) và trí tuệ nhân tạo (TTNT) [17], chẳng hạn như tích hợp lược đồ, tích hợp dữ liệu, kho dữ liệu, chuyển đổi (hay dịch, trao đổi) dữ liệu, quản lý dữ liệu ngang hàng, thương mại điện tử, đối sánh và tích hợp ontology, Web ngữ nghĩa, xử lý truy vấn ngữ nghĩa, v.v.. Sau đây chúng tôi sẽ xem xét tổng quan các vấn đề chính trong các lĩnh vực này. 1.1.2.1 Tích hợp lược đồ Hầu hết các nghiên cứu về đối sánh lược đồ ban đầu là nhằm giải quyết vấn đề tích hợp lược đồ, là vấn đề hợp nhất các lược đồ tự trị và không đồng nhất thành một lược đồ tổng thể, gọi là lược đồ trung gian. Vấn đề tích hợp lược đồ là một mối quan tâm chính trong hai thập kỷ qua trong lĩnh vực CSDL [17]. Do các lược đồ là tự trị và được phát triển độc lập, chúng thường biểu diễn không đồng nhất các ngôn ngữ và cấu trúc khác nhau. Quá trình tích hợp đòi hỏi nhận dạng được các phụ thuộc liên lược đồ. Đây là một quá trình đối sánh lược đồ. Một khi chúng đã được nhận dạng, các phần tử đối sánh được hợp nhất dưới một lược đồ trung gian cố kết. 1.1.2.2 Tích hợp dữ liệu Các hệ thống tích hợp dữ liệu có mục đích cung cấp cho người dùng một giao diện truy vấn đồng bộ cho rất nhiều nguồn dữ liệu. Hai thành phần chính tạo thành kiến trúc của một hệ thống tích hợp dữ liệu: trình bao bọc và trình môi giới. Trình bao bọc bọc một nguồn thông tin và mô hình hóa nguồn thông tin đó sử dụng một lược đồ nguồn. Trình môi giới duy trì một lược đồ tổng thể và các ánh xạ giữa lược đồ tổng thể và các lược đồ nguồn. Mỗi khi người dùng đưa ra một truy vấn trên lược đồ tổng thể, trình môi giới sử dụng các ánh xạ này để công thức hóa lại một truy vấn tổng thể thành một tập các truy Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 10 vấn con mà có thể thi hành trong các lược đồ nguồn và như vậy trình môi giới có thể tập hợp các trả lời được trả lại từ các nguồn và kết hợp chúng thành trả lời cho truy vấn [21]. Như vậy một vấn đề then chốt trong việc xây dựng hệ thống tích hợp dữ liệu là việc cung cấp chính xác các ánh xạ giữa các lược đồ tổng thể và nguồn. Hiện nay, có hai giải pháp chính cho việc cung cấp các ánh xạ này: khung nhìn tổng thể và khung nhìn cục bộ. Trong tiếp cận đầu, lược đồ trung gian được định nghĩa dưới dạng các lược đồ của các nguồn. Còn trong tiếp cận sau, các mô tả của nguồn được cho theo hướng ngược lại. Thuận lợi chính của tiếp cận đầu là việc công thức hóa lại truy vấn là đơn giản. Tuy vậy, việc thêm các nguồn vào lược đồ trung gian lại không phải là việc tầm thường. Ngược lại, trong tiếp cận sau, việc công thức hóa lại truy vấn khó hơn nhưng việc thêm vào các nguồn mới thì khá đơn giản. Từ đó một số nghiên cứu đã đề xuất giải pháp kết hợp hai tiếp cận trên để tích hợp các nguồn dữ liệu không đồng nhất [20]. 1.1.2.3 Kho dữ liệu Một biến thể của vấn đề tích hợp dữ liệu là tập hợp các nguồn dữ liệu tích hợp vào một kho tập trung, gọi là kho dữ liệu. Quá trình này đòi hỏi phải chuyển đổi dữ liệu từ định dạng nguồn thành định dạng kho dữ liệu, do đó có thể sử dụng đối sánh lược đồ để thực hiện các chuyển đổi này. Với một nguồn dữ liệu đã cho, một phương pháp thích hợp để tạo các chuyển đổi là tìm kiếm các phần tử của nguồn mà có mặt trong kho dữ liệu. Thuận lợi chính của kho dữ liệu là hiệu quả cao trong trả lời truy vấn (bởi vì các truy vấn được áp dụng trực tiếp tới dữ liệu trong kho). Tuy vậy, nó đòi hỏi kho phải được cập nhật khi dữ liệu thay đổi, điều này không thích hợp khi điều quản một số lượng lớn nguồn hoặc khi nguồn thường xuyên thay đổi. Hiện nay một khung làm việc Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 11 hỗ trợ cho các khung nhìn tích hợp mà kết hợp các tiếp cận kho dữ liệu và kho ảo đã được đề xuất [17]. 1.1.2.4 Chuyển đổi dữ liệu Trong vài năm gần đây, sự phát triển nhanh chóng của thông tin trực tuyến trong các nguồn không đồng nhất phân biệt lưu trữ dưới các định dạng khác nhau đã dẫn đến một ứng dụng khác đòi hỏi việc đối sánh lược đồ: trao đổi dữ liệu. Trao đổi dữ liệu mà thường được gọi là dịch hay chuyển đổi dữ liệu là vấn đề dịch nội dung của nguồn dữ liệu thành thể hiện của một lược đồ đích mà phản ánh dữ liệu nguồn chính xác đến mức có thể. Tuy vấn đề trao đổi dữ liệu có một số điểm tương đồng với vấn đề tích hợp dữ liệu, vẫn có một số khác biệt quan trọng giữa hai vấn đề này. Trong kịch bản chuyển đổi dữ liệu, lược đồ đích nhìn chung được tạo ra độc lập và có các ràng buộc của bản thân nó. Còn trong tích hợp dữ liệu lược đồ tổng thể là một lược đồ ảo và có tính hòa hợp, không có các ràng buộc định nghĩa trước. Một khác biệt quan trọng nữa là trong trao đổi dữ liệu ta phải tạo ra một thể hiện đích mà phản ánh tốt nhất thể hiện nguồn đã cho. Trong tích hợp dữ liệu không có sự trao đổi nào về dữ liệu được yêu cầu. Việc tự động hóa quá trình dịch dữ liệu đòi hỏi sử dụng đối sánh lược đồ để phát hiện sự tương đồng giữa lược đồ nguồn và đích, đây là một bước then chốt để đưa ra một chương trình dịch thích hợp [17]. 1.1.2.5 Thương mại điện tử 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ý nhiều giao dịch trực tuyến 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 giữa các công ty. Tuy vậy các công ty thường phát triển ứng dụng với các định dạng thông điệp khác nhau như EDI (Electronic Data Exchange), Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 12 XML (Extended Markup Language) hoặc một số định dạng khác. Để trao đổi các thông điệp đó, các ứng dụng cần phải chuyển đổi được các thông điệp từ định dạng này sang định dạng khác. Như đã nói ở trên, đây chính là vấn đề chuyển đổi dữ liệu [17]. 1.1.2.6 Quản lý dữ liệu ngang hàng Một ứng dụng quan trọng của đối sánh lược đồ là quản lý dữ liệu ngang hàng, là một mở rộng tự nhiên của tích hợp dữ liệu. Ngược lại với môi trường tích hợp dữ liệu, một quản lý dữ liệu ngang hàng không dựa trên khái niệm lược đồ trung gian mà cho phép một số tùy ý các điểm truy vấn và lấy dữ liệu trực tiếp từ mỗi điểm khác. Việc xử lý thông tin và lấy nội dung giữa vô số các điểm tự trị đòi hỏi các kỹ thuật đối sánh thích hợp để xác định các ánh xạ giữa các khái niệm của các điểm khác nhau mà có liên quan về ngữ nghĩa [17]. 1.1.2.7 Đối sánh và tích hợp ontology Ontology được định nghĩa như là việc khái niệm hóa một lĩnh vực dưới dạng các khái niệm và quan hệ. Hiện nay ontology được thừa nhận là một công cụ cơ bản cho phép chia sẻ tri thức giữa các ứng dụng phân tán và không đồng nhất. Nhiều nghiên cứu xoay quanh ontology đã được thực hiện, từ thiết kế đến phát triển và sử dụng lại. Đối sánh ontology là một trong những bước cơ bản của hầu hết các ứng dụng dựa trên ontology, trong đó có vấn đề tích hợp ontology. [6]. 1.1.2.8 Web ngữ nghĩa Một trong những vấn đề đang được quan tâm nhiều hiện nay là Web ngữ nghĩa, tức là vấn đề sử dụng một số ontology lĩnh vực nhằm mô tả ý nghĩa của dữ liệu trên Web. Sự phát triển nhanh chóng của Internet với lượng thông tin khổng lồ khiến ta rất khó khai thác và sử dụng hiệu quả các nguồn thông tin Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 13 đó, 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 sử dụng chứ không phải máy tính. Mục đích của Web ngữ nghĩa 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 làm cho máy tính có thể hiểu được. Phương pháp làm giàu các tài liệu Web hiện nay là sử dụng ontology. Tuy vậy các Website khác nhau lại thường sử dụng ontology khác nhau, bởi vậy để làm cho Web có khả năng liên tác được, ta cần các kỹ thuật đối sánh thích hợp giữa các ontology tự trị để xác định các ánh xạ ngữ nghĩa giữa các khái niệm ontology khác nhau mà có liên quan về ngữ nghĩa [6]. 1.1.2.9 Xử lý truy vấn ngữ nghĩa Tích hợp dữ liệu, kho dữ liệu, và chuyển đổi dữ liệu nhìn chung là các vấn đề tương tự nhau bởi vì chúng đều phải phân tích các lược đồ để đưa ra các ánh xạ (và có thể một lược đồ tích hợp) – ta gọi đây là việc phân tích tại thời điểm thiết kế. Một vấn đề khác hơn đôi chút là xử lý truy vấn ngữ nghĩa - một vấn đề tại thời điểm thực thi ở đó người dùng sẽ chỉ rõ đầu ra của một truy vấn và hệ thống sẽ tính toán xem làm thế nào để đưa ra đầu ra đó. Đặc tả của người dùng được phát biểu dưới dạng các khái niệm quen thuộc với họ mà có thể không giống như tên các phần tử được chỉ ra trong lược đồ CSDL. Bởi vậy, trong pha đầu tiên của việc xử lý truy vấn, hệ thống phải ánh xạ các khái niệm người dùng yêu cầu trong đầu ra truy vấn tới các phần tử lược đồ. Đây cũng là một ứng dụng tự nhiên của phép toán đối sánh. Sau khi ánh xạ đầu ra truy vấn tới các phần tử lược đồ, hệ thống phải nhận được một phát biểu cho biết ngữ nghĩa của ánh xạ. Đã có nhiều kỹ thuật được phát triển trong nhiều thập kỷ qua nhằm thu nhận các phát biểu này. Một trong những hướng nghiên cứu hiện nay là tổng quát hóa các kỹ thuật này để chỉ ra ngữ nghĩa của một ánh xạ đưa ra bởi phép toán đối sánh tìm được [17]. Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 14 1.2 Các tiếp cận đối sánh lược đồ 1.2.1 Phân loại các tiếp cận đối sánh lược đồ Đối sánh lược đồ là một vấn đề mới mẻ và thường được nghiên cứu riêng lẻ trên nhiều lĩnh vực khác nhau, do vậy đã có nhiều khảo sát được đưa ra nhằm phân loại các tiếp cận này. Đáng chú ý hơn cả là khảo sát của Rahm & Bernstein [17], trong đó các tác giả 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 như sau: * Tiếp cận dựa trên lược đồ >< Tiếp cận dựa trên thể hiện: Tiếp cận dựa trên lược đồ chỉ sử dụng các thông tin chứa trong lược đồ như tên, kiểu... Còn tiếp cận dựa trên dữ liệu chỉ sử dụng nội dung dữ liệu. * Tiếp cận dựa trên phần tử >< Tiếp cận dựa trên cấu trúc: quá trình đối sánh có thể thực hiện cho từng phần tử (như các thuộc tính) hoặc kết hợp các phần tử với nhau trong 1 cấu trúc. * Tiếp cận dựa trên ngôn ngữ >< Tiếp cận dựa trên ràng buộc: đối sánh có thể sử dụng cách tiếp cận dựa trên ngôn ngữ như so sánh tên các phần tử, các thông tin mô tả phần tử hoặc sử dụng cách tiếp cận dựa trên ràng buộc như ràng buộc như kiểu dữ liệu, ràng buộc đơn nhất, khóa, v.v.. * Tiếp cận lai >< Tiếp cận kết hợp: Để có một kết quả đối sánh tốt hơn ta thường kết hợp các tiếp cận độc lập 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 lai hoặc kết hợp các kết quả đối sánh của các tiếp cận độc lập khác nhau. * Số yếu tố đối sánh: kết quả đối sánh có thể là một hay nhiều phần tử của lược đồ nguồn đối sánh với một hay nhiều phần tử của lược đồ đích. Có bốn trường hợp cơ bản, bao gồm đối sánh 1:1, 1:n, n:1 và n:m. Ngoài ra một phần tử của lược đồ này cũng có thể liên quan đến nhiều phần tử của lược đồ kia, khi đó có thể cần đến các phép toán hợp nhất hoặc phân tách. Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 15 * Thông tin trợ giúp: các tiếp cận đối sánh thường sử dụng nhiều nguồn thông tin trợ giúp khác nhau như từ điển, lược đồ tổng thể, các kết quả đối sánh sẵn có từ trước hay đầu vào người dùng. 1.2.2 Các tiếp cận đối sánh lược đồ Các tiếp cận đối sánh lược đồ đã được phát triển chủ yếu trong các nghiên cứu về CSDL và TTNT. Trong mục này chúng tôi sẽ tổng kết lại, mô tả và so sánh các tính năng đặc trưng của các tiếp cận này. 1.2.2.1 Tiếp cận dựa trên học máy Học máy là khả năng khai thác các kết quả nhận được trước đó của một máy để cải thiện hiệu năng của nó, đặc biệt là để tự động hóa các quá trình đắt tiền và tốn thời gian. Nhiều nghiên cứu gần đây trong các lĩnh vực CSDL và TTNT đã tận dụng các kỹ thuật học máy để thực hiện đối sánh lược đồ [21], [6]. Các công cụ đối sánh lược đồ dựa trên học máy thông thường bao gồm một số các môđun, gọi là người học bao gồm một môđun riêng và siêu người học để kết hợp chúng. Mỗi người học khai thác một loại thông tin khác nhau có trong các định nghĩa cấu trúc và/hoặc trong các nguồn dữ liệu. Một khi người học đã được đào tạo, công cụ đối sánh có thể tìm kiếm các ánh xạ cho một nguồn dữ liệu mới bằng cách áp dụng các người học và sau đó kết hợp các kết quả của chúng bằng cách sử dụng một siêu người học. Ví dụ hệ thống LSD [6] áp dụng một chiến lược siêu học để tạo nên một số đối sánh cơ sở mà có xem xét đến các thể hiện dữ liệu hoặc thông tin lược đồ. Ngoài ra còn một số hệ thống khác như được nêu trong mục 1.3. 1.2.2.2 Tiếp cận dựa trên luật Phần lớn các công cụ đối sánh lược đồ hiện tại đều sử dụng luật để đối sánh các lược đồ không đồng nhất. Đã có nhiều nghiên cứu về vấn đề này cả trong lĩnh vực CSDL và TTNT [6], [17], [21]. Các tiếp cận dựa trên luật khai Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 16 thác nhiều loại thông tin lược đồ như tên phần tử, kiểu dữ liệu, các ràng buộc phần tử và phân cấp cấu trúc. Hệ thống Cupid [11] và Similarity Flooding [12] sử dụng các luật tính toán độ tương đồng giữa hai lược đồ như là tổng có trọng số của các độ tương đồng tên phần tử, kiểu dữ liệu và vị trí cấu trúc. 1.2.2.3 Tiếp cận dựa trên siêu dữ liệu Một tiếp cận khác cho vấn đề đối sánh lược đồ là tiếp cận dựa trên siêu dữ liệu. Các tiếp cận dựa trên siêu dữ liệu khai thác thêm thông tin ngữ nghĩa được cung cấp chung bởi các chuyên gia lĩnh vực, ví dụ như siêu dữ liệu RDF hoặc các ontology lĩnh vực. Nhìn chung tiếp cận này cố gắng ánh xạ tự động tất cả các trường của mỗi nguồn dữ liệu (hoặc lược đồ) để định nghĩa trước ontology lĩnh vực và sau đó thực hiện đối sánh lược đồ ở mức ontology. Như vậy tiếp cận này thực chất là giải pháp chuyển vấn đề ánh xạ các nguồn dữ liệu và các lược đồ thành việc ánh xạ các ontology. 1.2.2.4 Một số tiếp cận khác Ngoài việc sử dụng kỹ thuật học máy, một số tiếp cận còn sử dụng mạng nơ-ron để đối sánh lược đồ [21]. Tiếp cận sử dụng mạng nơ-ron khai thác các ưu điểm của mạng nơ-ron trong việc phát hiện sự tương đồng giữa các nguồn dữ liệu. Lợi ích chính của mạng nơ-ron là thuật toán sử dụng trong pha đào tạo không cần huấn luyện. Một số tiếp cận khác cũng đã được đề xuất cho vấn đề đối sánh lược đồ, chẳng hạn tiếp cận hướng đối tượng [21]. Tiếp cận hướng đối tượng dựa trên biểu diễn các lược đồ theo mô hình hướng đối tượng, sau đó dịch các đặc tả lược đồ thành các biểu diễn hướng đối tượng này. Tiếp cận này thường được sử dụng trong các hệ thống tích hợp dữ liệu. 1.2.2.5 So sánh các tiếp cận Các tiếp cận trên cơ sở luật nhìn chung có giá thành không lớn và hiệu năng cao do chúng không đòi hỏi phải có pha đào tạo và thường chỉ hoạt động Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 17 trên các lược đồ mà bỏ qua các thể hiện dữ liệu. Tiếp cận trên cơ sở luật thích hợp trong việc thu thập dễ dàng tri thức người dùng về lĩnh vực. Tuy vậy các tiếp cận trên cơ sở luật không thể khai thác thông tin về các thể hiện một cách hiệu quả và gặp phải một số vấn đề với các phần tử lược đồ mà không tìm thấy các luật hiệu quả; khi đó ta cần cung cấp các dấu hiệu cần thiết. Các tiếp cận trên cơ sở học yêu cầu nhiều dữ liệu đào tạo và các ví dụ đào tạo đúng. Hơn nữa các tiếp cận trên cơ sở học không thể làm việc chính xác nếu không cung cấp một đối sánh ban đầu (mà thông thường được người dùng cung cấp) và một tập tiêu biểu các nguồn dữ liệu, điều này giới hạn đáng kể việc ứng dụng của các phương pháp này. Do các tiếp cận trên cơ sở học dựa cơ bản trên các nguồn dữ liệu và trên các ánh xạ giữa các nút lá của hai cây, chúng không khai thác được các cấu trúc phân cấp thực sự, là vấn đề căn bản của dữ liệu có cấu trúc. Cuối cùng, nhiều tiếp cận trên cơ sở học chỉ sử dụng một người học đơn, và do đó mức chính xác và khả năng ứng dụng bị hạn chế [6], [21]. 1.2.3 Các phương pháp đối sánh lược đồ Dù sử dụng các tiếp cận trên cơ sở luật hay trên cơ sở học, tất cả các công cụ đối sánh đều khai thác tên phần tử, kiểu dữ liệu, các ràng buộc và định nghĩa cấu trúc. Trên cơ sở xem xét các dự án đã thực hiện và các khảo sát về vấn đề đối sánh lược đồ [17] ta có thể phân chia các phương pháp đối sánh lược đồ thành ba loại: đối sánh ngôn ngữ, đối sánh trên cơ sở ràng buộc và đối sánh cấu trúc. Các công cụ đối sánh lược đồ thường kết hợp các phương pháp này để thực hiện quá trình đối sánh. 1.2.3.1 Đối sánh ngôn ngữ Đối sánh ngôn ngữ về cơ bản dựa trên tên các thành phần lược đồ để tìm kiếm đối sánh giữa các lược đồ. Để làm việc, đối sánh ngôn ngữ thường yêu Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 18 cầu sử dụng tên mô tả. Sự tương đồng của tên được đo theo nhiều cách khác nhau như đo sự bằng nhau của tên, sự bằng nhau của biểu diễn tên hợp quy tắc sau khi phân luồng và các xử lý khác, sự tương đồng của tên dựa trên các dãy con chung, khoảng cách soạn thảo…, hay còn gọi là so sánh cú pháp. Đối sánh tên dựa trên cú pháp chỉ tính toán độ tương đồng dựa trên các xâu biểu diễn tên. Nhiều thuật toán so sánh xâu đã được phát triển trong các lĩnh vực khác nhau như sửa lỗi chính tả, thu thập văn bản, v.v.. Đối với vấn đề đối sánh lược đồ, đã có nhiều thuật toán dạng này được áp dụng, chẳng hạn như EditDistance, N-Gram, SoundEx, v.v.. EditDistance là phương pháp tính độ tương đồng của hai xâu từ số lần thực hiện các thao tác xóa, thêm, thay thế ký tự cần thiết để chuyển một xâu này thành xâu kia. N-Gram là phương pháp so sánh xâu theo tập n-gram của nó, ví dụ xâu doc và document tương tự nhau theo tập tri-gram vì tập {doc} và tập {doc,ocu,cum,ume,men,ent} chia sẻ phần tử “doc”. Còn SoundEx là phương pháp tính độ tương đồng âm thanh giữa các tên tương ứng với mã SoundEx. Phương pháp này tỏ ra khá hiệu quả cho các từ được viết khác nhau nhưng có khả năng giống nhau, ví dụ document và documentation. Sự tương đồng của tên cũng có thể được tính toán dựa trên các quan hệ đồng nghĩa, trái nghĩa, tổng quát, bộ phận… giữa các từ, hay còn gọi là so sánh ngữ nghĩa. Các quan hệ này thu được bằng cách sử dụng từ điển nói chung và các từ điển chuyên ngành nói riêng. Việc sử dụng phương pháp đối sánh ngôn ngữ có thể đưa đến những đối sánh không chính xác về mặt ngữ nghĩa. Ví dụ hai phần tử cùng tên có thể biểu diễn các khái niệm hoàn toàn khác nhau hoặc ngược lại, hai phần tử có tên không giống nhau song lại có thể biểu diễn ngữ nghĩa tương đồng. Hơn nữa đối sánh ngôn ngữ còn phải đối phó với các trường hợp đặc biệt như sử dụng chữ viết tắt, chữ rút gọn (là từ gồm những chữ cái đầu của các từ), tên có giới từ hay mạo từ, v.v.. Tuy còn tồn tại các vấn đề trên, đối sánh ngôn ngữ Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 19 lại khá dễ thực hiện và có thể cho một ánh xạ ban đầu, sau đó ta có thể xác nhận hoặc hủy bỏ bằng các phương pháp đối sánh khác. 1.2.3.2 Đối sánh dựa trên ràng buộc Các ràng buộc lược đồ (nếu chúng là các tập thích đáng) có thể cho một dấu hiệu đáng quan tâm về cách đối sánh các phần tử lược đồ và do đó giảm nhẹ số lượng các ứng viên đối sánh (thu được từ phương pháp đối sánh ngôn ngữ). Các ràng buộc lược đồ bao gồm kiểu dữ liệu, phạm vi giá trị, các ràng buộc đơn nhất và toàn vẹn, v.v.. Như ta biết, các khuyến nghị lược đồ thường cung cấp một tập các kiểu dữ liệu nguyên gốc, do vậy việc phân tích các kiểu dữ liệu này có thể cung cấp cho ta các ứng viên đối sánh. Một ví dụ về hệ thống sử dụng tính tương thích kiểu dữ liệu là Cupid [11]. Việc so sánh phạm vi giá trị số và/hoặc mẫu ký tự cũng có thể có ích trong việc suy ra các ứng viên đối sánh này, ví dụ chúng có thể cho phép nhận biết số điện thoại, mã bưu điện và địa chỉ. Vấn đề nảy sinh trong việc sử dụng kiểu dữ liệu là khi chúng không đủ rõ ràng (ví dụ một trường đã được khai báo như một số nguyên lại được khai báo như một xâu). 1.2.3.3 Đối sánh cấu trúc Thông tin cấu trúc (đặc biệt là các cấu trúc phân cấp) là rất có ích trong việc xem xét tính tương đồng về ngữ nghĩa của các phần tử lược đồ. Độ tương đồng cấu trúc là một phép đo độ tương đồng của ngữ cảnh mà trong đó các phần tử xuất hiện. Trong khi rất nhiều tài liệu, công trình nghiên cứu đề cập đến đối sánh ngôn ngữ và đối sánh dựa trên ràng buộc và hầu hết đều áp dụng được cho DTD và lược đồ XML, cho đến nay rất ít nghiên cứu quan tâm đến cấu trúc của XML trong các phương pháp đối sánh lược đồ của chúng. Lí do cơ bản là hầu hết các hệ thống đối sánh lược đồ được phát triển trong lĩnh vực CSDL và do đó về cơ bản chỉ đối phó với các lược đồ quan hệ. Ngược lại với dữ liệu XML, CSDL quan hệ có rất ít dữ liệu cấu trúc. Hầu hết công việc Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 20 trong đối sánh cấu trúc lược đồ quan hệ được thực hiện theo các khóa ngoại để tìm kiếm quan hệ giữa các dữ liệu. Một số dự án gần đây bắt đầu quan tâm đến cách khai thác cấu trúc XML trong quá trình đối sánh. Hệ thống Xyleme [4] tính toán độ tương đồng cấu trúc giữa hai phiên bản của cùng một tài liệu XML trên cơ sở các quan hệ tổ tiên và con cháu giữa các nút. Xyleme là một công cụ phát hiện các thay đổi phiên bản giữa các tài liệu XML, điều này nghĩa là các tài liệu nguồn và đích có độ tương đồng cao, là một giả thiết không có giá trị lắm trong đối sánh lược đồ. 1.3 Các hệ thống đối sánh lược đồ XML Gần đây đã có nhiều tiếp cận khác nhau về vấn đề đối sánh lược đồ được đưa ra trong các lĩnh vực ứng dụng khác nhau, chẳng hạn như chuyển đổi tự động tài liệu có cấu trúc. Các tác giả trong [9] đề xuất một tiếp cận trực tiếp cú pháp cho việc tự động hóa các chuyển đổi cấu trúc giữa hai văn phạm trên cơ sở các bộ chuyển đổi phi trạng thái hữu hạn. Ý tưởng ở đây là tạo một chuyển đổi bán tự động nếu người dùng định nghĩa một đối sánh giữa các phần tử chứa văn bản tài liệu (tức là các lá). Tiếp cận này gặp phải một số hạn chế: đầu tiên nó chỉ làm việc nếu hai văn phạm có phần chung, làm hạn chế phạm vi của các chuyển đổi trong các chuyển đổi cục bộ. Hơn nữa, tiếp cận này không có khả năng giải quyết tất cả sự không đồng nhất có thể xảy ra giữa các tài liệu có cấu trúc, chẳng hạn một kiểu phần tử cấu trúc trong tài liệu nguồn sẽ được chuyển đổi thành cùng kiểu phần tử trong tài liệu đích. Ví dụ, một danh sách các nút thay thế trong tài liệu nguồn chỉ có thể được chuyển đổi thành một danh sách bao gồm cùng số lượng các phần tử lặp lại. Bên cạnh các nghiên cứu trong lĩnh vực tài liệu, các nghiên cứu trong lĩnh vực CSDL và TTNT đã xem xét một cách rộng hơn vấn đề đối sánh lược Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 21 đồ trong nhiều lĩnh vực ứng dụng khác nhau. Với sự phát triển của XML, nhiều thuật toán đối sánh đã xem xét cấu trúc phân cấp của XML. Sau đây chúng tôi sẽ xem xét một số giải thuật và hệ thống đối sánh lược đồ điển hình. 1.3.1 Cupid (trung tâm nghiên cứu Microsoft) Cupid là một bộ đối sánh lai kết hợp một vài phương pháp đối sánh [11]. Đây là một bộ đối sánh được phát triển với mục đích áp dụng cho các mô hình dữ liệu tổng quát và đã được áp dụng cho các nguồn dữ liệu XML và quan hệ. Tiến trình đối sánh có ba pha: * Pha đầu tiên là đối sánh ngôn ngữ. Trước hết tên phần tử được phân tích thành các token dựa trên các dấu phân tách và được mở rộng để nhận dạng các chữ viết tắt (abbreviation) hoặc chữ rút gọn (acronym) sử dụng một từ điển đồng nghĩa cho cả ngôn ngữ chung và các tham khảo riêng lĩnh vực. Sau đó Cupid sẽ phân cụm các phần tử lược đồ thành các danh mục dựa trên kiểu dữ liệu và nội dung ngôn ngữ để giảm bớt số lượng phép so sánh một- một giữa các phần tử lược đồ (chỉ các phần tử thuộc về các danh mục giống nhau trong hai lược đồ mới được xem xét). Tiếp theo Cupid tính toán một hệ số tương đồng ngôn ngữ giữa các cặp tương thích về kiểu dữ liệu và nội dung ngôn ngữ dựa trên việc đối sánh xâu con và một từ điển đồng nghĩa có các quan hệ đồng nghĩa (synonymy) và bao nghĩa (hypernymy). Kết quả của pha này là một bảng các hệ số tương đồng ngôn ngữ trong phạm vi [0, 1] giữa các phần tử trong hai lược đồ. * Pha thứ hai chuyển đổi các lược đồ nguyên thủy thành cây và sau đó thực hiện đối sánh cấu trúc từ dưới lên. Giả thiết cơ bản trong pha đối sánh cấu trúc của Cupid là nhiều nội dung thông tin được biểu diễn trong các lá và các lá đó có ít sự thay đổi giữa các lược đồ và tiếp đó là cấu trúc trong. Các phần tử trong hai cây đang được so sánh được duyệt theo thứ tự trước. Độ tương đồng giữa các nút là dựa trên độ tương đồng ngôn ngữ và độ tương Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 22 đồng của các tập lá của chúng. Nếu độ tương đồng vượt qua một ngưỡng thì độ tương đồng tập lá của chúng được tăng lên, với lý lẽ là các lá với các tổ tiên tương đồng cao sẽ xuất hiện trong các ngữ cảnh tương đồng. Việc tính toán độ tương đồng cấu trúc có một sự đệ quy lẫn nhau: hai phần tử là tương đồng nếu các tập lá tương ứng của chúng là tương đồng, và sự tương đồng của các lá lại bị tác động bởi độ tương đồng của các nút trung gian. Pha này kết thúc bằng việc tính toán trung bình có trọng số của độ tương đồng ngôn ngữ và cấu trúc. * Pha thứ ba sẽ đưa ra ánh xạ cuối cùng giữa các phần tử lược đồ dựa trên các hệ số thu được trong pha hai. Pha này phụ thuộc nhiều vào ứng dụng nên không được nhấn mạnh trong thuật toán. Cấu trúc lược đồ trong Cupid được sử dụng như là một ràng buộc đối sánh, tức là cấu trúc của hai nút càng tương đồng thì hai nút càng tương đồng. Do điều này, Cupid phải đối mặt với những vấn đề như các khái niệm tương đương xuất hiện trong các cấu trúc khác nhau hoàn toàn hay các khái niệm độc lập hoàn toàn lại thuộc vào các cấu trúc đồng dạng. Dù gặp phải các vấn đề này, Cupid vẫn là thuật toán đối sánh đáng chú ý cho dữ liệu XML do đã vượt ra ngoài biểu diễn cây cổ điển để điều quản các lược đồ XML (hay bất kỳ đồ thị có gốc nào đó) với việc xem xét các kiểu chia sẻ và các ràng buộc tham chiếu. Ý tưởng ở đây là dựa trên việc chuyển đổi đồ thị có gốc thành cây và điều này là vì hai lý do: sử dụng lại thuật toán đối sánh cấu trúc cho cây và đối phó với các ánh xạ phụ thuộc ngữ cảnh. Trong trường hợp các kiểu chia sẻ, với mỗi phần tử Cupid thêm một nút cây lược đồ mà các nút kế tiếp nó là các nút tương ứng với các phần tử có thể tiếp cận đến qua một số bất kỳ các quan hệ IsTypeOf theo sau bởi một quan hệ chứa đơn. Cây cũng được tăng cường thêm các nút nhằm mô hình hóa các ràng buộc tham chiếu, là các ràng buộc mà được thể hiện như là các khung nhìn kết nối tiềm tàng. Với mỗi khóa Chương 1: Đối sánh lược đồ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 23 ngoại, một nút mới mà biểu diễn kết nối các phần tử participate (các bảng trong các lược đồ quan hệ) được đưa ra. Tuy có các mở rộng này, Cupid vẫn không khai thác các tính năng khác của lược đồ XML như nhóm thay thế, kiểu trừu tượng, v.v.. điều mà có thể cho ta các dấu hiệu có ý nghĩa trong việc giải quyết vấn đề đối sánh lược đồ XML. 1.3.2 Similarity Flooding (đại học Stanf._.chuyên ngành công nghệ thông tin 91 thuộc tính là text, do vậy nếu ta gán cho nó một số thì phải đặt trong dấu nháy kép. Nếu chuỗi chứa các ký tự định dạng, ta dùng thực thể thay thế (“'”~”‘”, “"”~”“”). Để mô tả về ngôn ngữ của dữ liệu, ta dùng thuộc tính xml:lang, ví dụ: Hello Hi Một số vấn đề khác cũng quan trọng không kém nhưng do khuôn khổ phần phụ lục này ta sẽ không nêu ra ở đây như khuôn dạng cấu trúc tài liệu XML, phân đoạn CDATA, không gian tên của XML, Infoset v.v.. có thể tham khảo trong [23]. 1.2 Định nghĩa kiểu tư liệu (DTD) và tính hợp lệ của tài liệu XML Định nghĩa kiểu tư liệu - DTD (Document Type Definition) là quy định cách thức lưu giữ dữ liệu của tài liệu XML. Khai báo thường đặt ở phần khởi đầu tài liệu. Có thể định nghĩa lồng nhau các phần tử DTD. Có thể định nghĩa DTD với nội dung hỗn hợp, ví dụ: , hoặc định nghĩa cho các phần tử rỗng, ví dụ: . Ta cũng nên chú thích cho các phần tử định nghĩa DTD (giống như chú thích XML). - Định nghĩa DTD ngoại: sử dụng từ khóa SYSTEM trong chỉ thị khai báo . - Tham chiếu DTD dùng chung: sử dụng từ khóa PUBLIC thay cho SYSTEM. Thực tế ta có thể dùng chung hai loại tham chiếu nội và ngoại trong cùng tài liệu XML vào cùng thời điểm. Một số vấn đề quan trọng khác như không gian tên và các định nghĩa DTD... có thể tham khảo trong [23]. 1.3 Thực thể và thuộc tính DTD của tài liệu XML - Có hai loại thực thể: thực thể tổng quát - dạng & … ; và thực thể tham số - dạng % … ;. Thực thể có thể là nội hoặc ngoại, có thể ở dạng phân tích hoặc không phân tích. - Thuộc tính: sử dụng chỉ thị khai báo để định nghĩa danh sách các thuộc tính sẽ kết hợp với phần tử thẻ DTD nào đó. - Tạo các thực thể tổng quát nội: có thể tạo các định nghĩa tham chiếu cho thực thể lồng nhau, nhưng không được theo kiểu tham chiếu vòng. - Tạo các thực thể tổng quát ngoại: tương tự DTD, có thể sử dụng SYSTEM hoặc PUBLIC cho khai báo thực thể ngoại. Có thể sử dụng định nghĩa FPI. Có thể sử dụng tham chiếu thực thể ngoại để nhúng dữ liệu từ tài liệu khác vào tài liệu gốc. Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 92 - Tham chiếu thực thể tổng quát được định nghĩa trước: ngoài năm loại đã được định nghĩa trước, ta có thể đưa vào các ký tự đặc biệt khác sử dụng mã kí tự. - Tạo các thực thể tham số nội: các tham chiếu thực thể tổng quát không được dùng cho các định nghĩa DTD, do đó ta sử dụng tham chiếu thực thể tham số dạng % … ;. Tuy vậy không thể đưa tham chiếu thực thể tham số nội vào các khai báo DTD khác mà chỉ có thể sử dụng chúng trong phần khai báo DTD chính. - Tạo các thực thể tham số ngoại: các thực thể tham số ngoại có thể dùng ở bất cứ đâu trong khai báo DTD, do đó tránh được các khai báo lặp lại. - Sử dụng INCLUDE và IGNORE: để thêm vào hay bỏ qua các đoạn định nghĩa DTD. Có thể sử dụng chúng kết hợp với các tham số thực thể để tham số hóa các khai báo DTD, khi đó có thể bỏ qua hoặc thêm vào một tập các khai báo DTD chỉ bằng cách thay đổi giá trị của thực thể tham số. Kỹ thuật này giúp tập trung hóa các thực thể cần dùng để tùy biến. Nó đã được sử dụng trong các định nghĩa XHTML 1.1 DTD. Một số vấn đề quan trọng khác như các tính chất của thuộc tính, nhúng dữ liệu phi XML vào tài liệu, nhúng nhiều thực thể phi định dạng vào tài liệu v.v.. có thể tham khảo trong [23]. 2. Xử lý tài liệu XML Để phân tích tài liệu XML ta có thể dùng rất nhiều thư viện lập trình từ các ngôn ngữ khác nhau: XML for Java (XML4J), Microsoft XML Parser, Java Standard Extension for XML, Python XML Parser… Hiện nay, thay cho bộ mã ký tự một byte ASCII truyền thống người ta đang chuyển dần sang bộ mã kí tự hợp nhất hai bytes Unicode. Thậm chí một đặc tả mới về tập kí tự 4 bytes đang hình thành đó là UCS (Universal Character System). 2.1 Xử lý bằng Java Script theo mô hình DOM DOM - mô hình đối tượng tài liệu (Document Object Model) được W3C định nghĩa dưới dạng cây phân cấp bao gồm các nút chứa phần tử, dữ liệu văn bản, thuộc tính… và các nút con. Có tất cả 12 loại nút trong mô hình DOM (xem các tài liệu tham khảo liệt kê cuối bài). W3C cũng định nghĩa nhiều cấp độ cho mô hình DOM, thông dụng nhất hiện nay là cấp độ 1. Cấp độ này tập trung vào sự kết hợp giữa tài liệu HTML và XML. - Có hai cách để nạp tài liệu XML vào trình duyệt bằng JavaScript: hoặc sử dụng lớp đối tượng Microsoft.XMLDOM hoặc dùng phần tử nạp dữ liệu . Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 93 Để lấy về các nút trong tài liệu, trước hết ta lấy về nút gốc bằng phương thức documentElement, sau đó đi qua các nút con bằng các phương thức fistChild, nextChild, previousChild, lastChild, các nút cùng cấp bằng firstSibling, nextSibling, previousSibling, lastSibling, sau đó có thể hiển thị thông tin ra trình duyệt. Đối với cách thứ hai, ta sử dụng thẻ nạp trực tiếp dữ liệu XML vào trang HTML để xử lý bằng JavaScript. Ngoài ra ta có thể dùng trực tiếp tên của các phần tử để lấy ra danh sách các nút bằng phương thức getElementByTagName(“NODE_NAME”). Bên cạnh đó, ta có thể lấy về danh sách các thuộc tính của nút bằng phương thức attributes, sau đó gọi phương thức getNameItem để lấy về tham chiếu đến một nút cụ thể theo tên, cuối cùng ta dùng phương thức value lấy về giá trị thực tế của thuộc tính. - Phân tích toàn bộ tài liệu XML: sử dụng thủ tục đệ quy. Phương thức childNodes dùng để lấy về danh sách các nút con nếu có, sau đó đệ quy duyệt tiếp xuống các phần tử con. Mô hình DOM gồm 12 kiểu nút, ta có thể sử dụng giá trị nodeType để xác định kiểu dữ liệu và thuộc tính nodeValue để trích rút nội dung dữ liệu của nút. Ta cũng có thể dùng sự kiện onreadstatechange kiểm tra trạng thái nạp và hủy dữ liệu XML của trình duyệt. Sự kiện ondataavailable cho biết quá trình nạp dữ liệu dã hoàn tất và dữ liệu đang trong trạng thái sẵn sàng để xử lý. Ta có thể kiểm tra tính hợp lệ của tài liệu XML bằng JavaScript với mô hình tài liệu DOM. Dựa vào đối tượng parseError của dữ liệu nguồn để biết được các thông tin về lỗi. Có thể xem chi tiết hơn trong [23]. - Ngoài khả năng xử lý tài liệu, JavaScript còn có thể thay đổi nội dung cấu trúc tài liệu (dùng các phương thức createElement(), insertBefore(), createTexxtNode(), appendChild()…) 2.2 Xử lý bằng Java theo mô hình DOM Dùng Java có thể xử lý tài liệu XML mà không phụ thuộc vào trình duyệt. Thư viện xử lý phân tích tài liệu XML mà ta sử dụng ở đây là XML4J. Ta sẽ mô tả một vài phương thức xử lý trong gói thư viện này. Giả sử ta đã có một tập tin XML “order.xml” với các thẻ định dạng theo mô hình cây phân cấp (đã xem xét ở các phần trước). Để xử lý được bằng Java, trước hết ta đưa vào thư viện xử lý DOM: Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 94 import org.w3c.dom.*; import org.apache.xerces.parsers.DOMParser; Sau đó quy trình xử lý tương tự như khi sử dụng JavaScript. Để đếm số phần tử trong tài liệu XML, ta dùng phương thức getLength(). Để đọc và hiển thị toàn bộ nội dung tài liệu, ta dùng kĩ thuật đệ quy. Một chương trình như vậy sẽ có các phương thức chính sau: - Xử lý nút trong tài liệu (nút phần tử, nút thuộc tính…): cài đặt phương thức display() để kiểm tra và xử lý một nút dữ liệu của cây tài liệu DOM. Đối với mỗi kiểu nút, ta so khớp kiểu của nút nhận được với hằng được định nghĩa sẵn (có 12 loại nút trong mô hình DOM). Với mỗi nút phần tử, để xử lý thuộc tính, ta dùng phương thức getAttributes(), trả về một mảng danh sách các thuộc tính có trong phần tử. Ta có thể dùng vòng lặp for để duyệt qua từng phần tử thuộc tính. Mỗi phần tử có thể bao gồm danh sách các phần tử con, ta gọi phương thức getChildNodes() để lấy ra danh sách các phần tử con nếu có của phần tử hiện hành. Tiếp đến vòng lặp for được gọi để đi đến từng nút con gọi đệ quy lại phương thức display(). Cách thức xử lý nút phân đoạn CDATA, nút dữ liệu văn bản, nút chỉ thị xử lý, thẻ đóng… hoàn toàn tương tự. Bằng cách xử lý này, ta có thể xây dựng được chương trình tìm kiếm thông tin trong tài liệu XML. Thay vì kết xuất ra màn hình văn bản, ta có thể kết xuất ra màn hình đồ họa, cũng vậy ta có thể ứng dụng XML cho hiển thị đồ họa. - Duyệt đến từng nút cụ thể trong tài liệu: tương tự trong JavaScript, ta có thể sử dụng các phương thức trong Java như getFirstChild(), getNextSibling()… để duyệt đến từng nút trong tài liệu. - Thay đổi nội dung tài liệu: ngoài việc đọc và phân tích nội dung tài liệu, ta có thể thêm hoặc thay đổi cấu trúc dữ liệu đầu vào để tạo ra một cấu trúc tài liệu XML mới. Tương tự JavaScript, trong Java ta dùng các phương thức createElement(), createTexxtNode(), appendChild()… 2.3 Xử lý bằng Java theo mô hình SAX - SAX (Simple API for XML) là mô hình xử lý dữ liệu XML theo hướng sự kiện. Dữ liệu mà ta mong muốn sẽ tự động gửi đến khi một sự kiện phát sinh thay vì phải lấy dữ liệu ra bằng cách lần đến từng nút. Trong mô hình DOM, để chọn kiểu nút cần xử lý, ta dùng các mệnh đề case và so sánh với các hằng đã định nghĩa. Còn trong mô hình SAX, trình phân tích sẽ chịu trách nhiệm đọc và diễn dịch toàn bộ nội dung tài liệu. Khi phát hiện một Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 95 kiểu nút nào đó, sự kiện tương ứng sẽ phát sinh và hàm xử lý sự kiện dành cho nút sẽ được gọi đến. Thư viện XML4J hỗ trợ cả hai mô hình DOM và SAX. Trong chương trình Java sử dụng các khối thư viện: org.xml.sax.*, org.xml.sax.helpers.DefaultHandler, org.apache.xerces.parsers.SAXParser. Sau đó quy trình xử lý bao gồm: khởi tạo bộ phân tích SAX, nạp dữ liệu vào bộ phân tích (tương tự mô hình DOM). Sử dụng các phương thức startElement(), endDocument(), ta có thể xử lý các thẻ trong tập tin, chẳng hạn so sánh xem thẻ đọc được có phải có tên là “NAME” không. startElement() bao gồm một số tham số như địa chỉ nguồn, tên thẻ mở không có tiếp đầu ngữ của không gian tên, tên thẻ đầy đủ, danh sách thuộc tính có trong phần tử thẻ. Một số các phương thức khác như startDocument(), startCDATA(), characters(), processingInstruction() là các phương thức xử lý sự kiện tương ứng với các kiểu nút DOCUMENT_NODE, ELEMENT_NODE, CDATA_SECTION_NODE, TEXT_NODE và PROCESSING_INSTRUCTION_NODE. Cách thức sử dụng các phương thức này cũng tương tự như các phương thức trên. - Để tìm kiếm và lọc ra một phần tử trong tài liệu XML, ta cài đặt điều kiện lọc trong phương thức startElement() thông qua cờ printFlag, tức là chỉ có những phần tử thỏa mãn điều kiện lọc thì cờ printFlag mới được bật (true). - Trong mô hình SAX, khác với DOM, tài liệu không được xem là cấu trúc cây, ta chỉ đến được một nút khi có sự kiện nào đó phát sinh, do đó không thể dùng các phương thức dạng như firstChild()… mà phải tự đánh dấu và tìm ra phần tử dựa vào sự kiện. Khác với DOM, trong mô hình SAX ta không thể đi đến một mục dữ liệu nào đó trực tiếp, do đó để thay đổi cấu trúc dữ liệu XML, chẳng hạn chèn một nút mới, phải dựa vào sự kiện startElement(). 3. XML và các vấn đề khác 3.1 Ràng buộc dữ liệu XML trong IE theo mô hình DSO - Ràng buộc dữ liệu cho phép kết nối dữ liệu trong tài liệu XML vào mô hình ADO của Microsoft. Bằng cách này, có thể xử lý dữ liệu trong tài liệu đơn giản và dễ dàng tương tự như đang làm việc trên hệ CSDL thực sự. Kỹ thuật này cũng cho phép chuyển dữ liệu từ các hệ CSDL vào tài liệu và ngược lại. Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 96 - DSO cung cấp khá đầy đủ các phương thức, thuộc tính và sự kiện để xử lý dữ liệu trong tập recordset. Do khuôn khổ phần phụ lục này, ta sẽ không trình bày vấn đề này ở đây. Chi tiết hơn có thể xem trong [23]. 3.2 Một số khái niệm XML mới: XPath, XLink, XBase, XPointer - XPath là một dạng đường dẫn trong tài liệu XML, tương tự như đường dẫn của hệ thống tập tin. XPath có nhiều ứng dụng quan trọng trong xử lý tài liệu chuyển dịch XSL, đặc tả XPointer… - XLink là một dạng mở rộng của HTML Link, nó có nhiều tùy biến và linh hoạt hơn liên kết HTML như liên kết giản đơn, liên kết mở rộng, định vị, cung liên kết, tài nguyên liên kết, tiêu đề liên kết, tùy biến… - XBase là khái niệm định địa chỉ cơ sở cho tài liệu XML, có thể hiểu nó như là cách định nghĩa địa chỉ gốc giúp thu gọn địa chỉ liên kết. - XPointer là con trỏ chỉ mục giúp chỉ ra chính xác vị trí nút tài liệu, nó xây dựng dựa trên khái niệm XPath. XPointer định nghĩa một vị trí dữ liệu dựa trên điểm trỏ (point). 3.3 Hiển thị tài liệu XML: CSS và XSL - CSS và XSL đều có tác dụng tạo định dạng hiển thị cho trang XML. CSS là một tập mẫu định dạng kiểu cho XML. XSL là một tài liệu tuân theo đúng quy tắc và cú pháp xây dựng tài liệu XML. XSL có các quy định chặt chẽ về kiểu nút theo cấu trúc cây, nhìn chung có cách xử lý tương tự như mô hình DOM hay SAX. Có thể lập trình và biến đổi dữ liệu XML nhờ các thẻ điều khiển mà XSL cung cấp (xem chi tiết trong [23]). 3.4 Ứng dụng XML: XHTML, CDF, RDF, VML, WML, SOAP, AppML... Các ứng dụng XML hiện nay đã phát triển rất phong phú: XHTML - HTML mở rộng, CML - ngôn ngữ định dạng hóa học, MathML - ngôn ngữ định dạng toán học, CDF - khuôn dạng định nghĩa kênh, RDF – khung định nghĩa tài nguyên, SMIL - ngôn ngữ tích hợp đa phương tiện đồng bộ, EBRL - ngôn ngữ định dạng báo cáo, XUL - ngôn ngữ cấu hình giao diện người dùng, VML - ngôn ngữ định dạng vector, WML - ngôn ngữ định dạng mạng không dây, SOAP - giao thức truy cập đối tượng giản lược, v.v.. Đặc biệt AppML được Microsoft hứa hẹn là một trong những mô hình ứng dụng trong tương lai. Có thể tìm hiểu thêm trong [23]. Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 97 Phụ lục B: Lược đồ XML Lược đồ XML được W3C (World Wide Web Consortium) bắt đầu quan tâm từ năm 1998 và phiên bản đầu tiên được công bố chính thức vào 5/2001 [24], [25], [26], với mục đích tạo ra một ngôn ngữ lược đồ có ý nghĩa hơn DTD. Cấu trúc của một tài liệu XML được định nghĩa trong một lược đồ XML dưới dạng các quan hệ phân cấp đã định nghĩa trước giữa các phần tử XML và/hoặc các thuộc tính với các ràng buộc đặc trưng có liên quan (ví dụ như thứ tự và số yếu tố). Trong mục này, ta sẽ đưa ra các tính năng chính cần quan tâm của ngôn ngữ lược đồ XML khi định nghĩa vấn đề đối sánh lược đồ XML. 1. Các kiểu dữ liệu lược đồ XML Một kiểu dữ liệu lược đồ XML (sử dụng thuật ngữ của [26]) là một bộ-3, bao gồm: - Một tập các giá trị phân biệt, gọi là không gian giá trị (miền), - Một tập các biểu diễn từ vựng, gọi là không gian từ vựng, - Một tập các giới hạn kiểu mô tả các thuộc tính của không gian giá trị, các giá trị riêng lẻ hoặc các mục từ vựng. Kiểu trong lược đồ XML có thể là đơn giản hoặc phức hợp. Kiểu đơn giản cho phép nội dung dữ liệu là ký tự nhưng không phải là phần tử con hoặc thuộc tính. Kiểu phức hợp thì cho phép có phần tử con hoặc thuộc tính. Khuyến nghị lược đồ XML định nghĩa 44 kiểu đơn giản nội tại mô tả các kiểu dữ liệu được sử dụng chung. Chúng bao gồm kiểu xâu (string), kiểu số (numerical) (ví dụ float, decimal, integer), kiểu ngày tháng (date) và thời gian (time) (ví dụ date, duration, time). Lược đồ XML cũng cho phép người dùng dẫn xuất ra các kiểu riêng từ các kiểu nội tại bằng cách áp dụng một số giới hạn kiểu, ví dụ như hạn chế phạm vi hợp lệ của các giá trị số bằng cách thiết lập các giá trị lớn nhất/nhỏ nhất và giới hạn chiều dài của giá trị xâu. Lược đồ XML đề nghị hai cách khác để định nghĩa các kiểu đơn giản dẫn xuất: dẫn xuất theo danh sách và dẫn xuất theo hợp. Không gian giá trị của một kiểu dữ liệu danh sách là một tập các dãy chiều dài hữu hạn của các giá trị nguyên tố. Kiểu dữ liệu nguyên tố trong định nghĩa của một kiểu dữ liệu danh sách được xem là itemType của kiểu dữ liệu danh sách đó. 2. Khai báo thuộc tính và phần tử Định nghĩa thuộc tính và định nghĩa phần tử cho phép cả toàn cục hoặc cục bộ. Nếu là toàn cục, chúng được định nghĩa như là con trực tiếp của phần tử , và sau đó có thể được tham chiếu từ các phần tử tùy ý. Nếu là cục bộ, chúng được Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 98 định nghĩa trong một phần tử . Định nghĩa thuộc tính được cho bởi các phần tử chỉ ra tên, kiểu (luôn là kiểu đơn giản), số yếu tố nhỏ nhất (tùy chọn hoặc yêu cầu) và lớn nhất và có thể là một giá trị mặc định hoặc một giá trị cố định. Khai báo phần tử kết hợp tên với định nghĩa kiểu (đơn giản hoặc phức hợp), giá trị mặc định (tùy chọn) và tập các định nghĩa ràng buộc đồng nhất (có thể rỗng). Sự kết hợp có thể là toàn cục hoặc giới hạn phạm vi trong một định nghĩa kiểu phức hợp. 3. Các kiểu phức hợp Ngược lại với kiểu đơn giản, kiểu phức hợp cho phép có các phần tử con hoặc các định nghĩa thuộc tính. Các kiểu dữ liệu này sau đó được sử dụng cho việc định nghĩa kiểu phần tử. Đây là một trong những khác biệt chính của lược đồ với DTD: các phần tử (tức là các thẻ được sử dụng trong tài liệu) có thể khác với các kiểu dữ liệu (định nghĩa như là các kiểu phức hợp). Kiểu dữ liệu phức hợp cũng có thể được dẫn xuất từ các kiểu dữ liệu đã tồn tại bằng cách hạn chế một kiểu dữ liệu phức hợp khác (trong thành phần của nó hoặc trong cấu trúc của nó) hoặc mở rộng một kiểu dữ liệu đơn giản hoặc phức hợp. Định nghĩa kiểu phức hợp bao gồm các thuộc tính sau: - Tên. - Kiểu cơ sở và phương pháp dẫn xuất (nếu là kiểu dẫn xuất). - Khai báo thuộc tính chứa phần tử con như đã mô tả ở trước. - Kiểu nội dung (elementOnly, empty, mixed hoặc kiểu đơn giản). - Mô hình nội dung (trong trường hợp elementOnly): chứa phần tử con (như đã mô tả ở dưới) khai báo cấu trúc của nội dung phần tử. Nội dung phần tử có thể được lồng thêm vào các phần tử , , và cho phép chỉ ra các thuộc tính tương đồng như DTD. 4. Khả năng thay thế phần tử và kiểu Lược đồ XML cung cấp cơ chế nhóm thay thế cho phép các phần tử (kiểu) được thay thế bởi các phần tử (kiểu) khác. Cụ thể hơn, các phần tử có thể được gán cho một nhóm phần tử đặc biệt mà được xem là có khả năng thay thế cho một phần tử có tên đặc biệt gọi là phần tử đầu. Các phần tử trong một nhóm thay thế phải có cùng kiểu như phần tử đầu, hoặc có thể có kiểu dẫn xuất từ kiểu của phần tử đầu. Tương tự như sự thay thế phần tử, lược đồ XML đưa ra khả năng thay thế kiểu, tức là khả năng thay thế nội dung phần tử bằng nội dung khác. Nguyên lý của thay thế kiểu là một kiểu cơ sở có thể được thay thế bởi bất kỳ một kiểu dẫn xuất nào. Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 99 5. Kiểu trừu tượng và phần tử trừu tượng Lược đồ XML đưa ra khái niệm kiểu trừu tượng và phần tử trừu tượng. Như thường thấy trong mô hình hóa hướng đối tượng, kiểu trừu tượng có thể không có thể hiện trực tiếp nhưng có thể có kiểu con cụ thể. Nếu một phần tử được khai báo là kiểu trừu tượng thì trong một tài liệu thể hiện XML mô hình nội dung của phần tử đó có thể không phải là của kiểu trừu tượng nhưng là của một trong các kiểu dẫn xuất của kiểu trừu tượng đó. Khái niệm trừu tượng cũng áp dụng cho phần tử. Nếu một phần tử được khai báo trừu tượng thì trong một tài liệu thể hiện XML phần tử đó có thể không xuất hiện nhưng các phần tử thuộc nhóm thay thế cho phần tử trừu tượng lại có thể xuất hiện tại vị trí của nó. 6. Ràng buộc toàn vẹn Lược đồ XML hỗ trợ ràng buộc toàn vẹn và ràng buộc toàn vẹn tham chiếu đã biết trong mô hình quan hệ: duy nhất, khóa và khóa tham chiếu. Duy nhất/khóa chỉ ra một danh sách thuộc tính phải nhận dạng duy nhất mỗi mục giữa một tập các nút được đánh địa chỉ bằng một bộ chọn (là một biểu diễn XPath được hạn chế). Cơ chế này mạnh hơn khái niệm ID/IDREF trong DTD. Lược đồ XML có nhiều ràng buộc tham chiếu và đồng nhất như: - Nội dung phần tử có thể được định nghĩa là duy nhất. - Các thuộc tính không chỉ mục (non-ID) có thể được khai báo hoặc là duy nhất hoặc là khóa. - Sự kết hợp nội dung phần tử và các thuộc tính có thể được khai báo là duy nhất hoặc khóa, tức là không chỉ duy nhất mà luôn hiện diện và không rỗng. - Lược đồ XML phân biệt giữa duy nhất và khóa. - So sánh giữa các trường khóa tham chiếu và các trường khóa hoặc duy nhất là so sánh bằng nhau về giá trị mà không phải bằng nhau về xâu. Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 100 Phụ lục C: Thuật toán của Hirst và St-Onge 1. Quan hệ từ Kỹ thuật đối sánh thuật ngữ đã đề xuất trong chương 3 sử dụng ba loại quan hệ: quan hệ rất mạnh (extra-strong) giữa một từ và sự nhắc lại nguyên thể của nó, quan hệ mạnh (strong): gồm một trong ba kịch bản đã giải thích trong mục 3.2.2 của chương 3 và quan hệ trung bình (medium), xảy ra khi có một đường dẫn được phép kết nối các synset liên kết với mỗi từ. Các định nghĩa của đường dẫn được phép sử dụng một phân loại các quan hệ synset WordNet thành các liên kết lên, xuống và ngang. Bảng C.1 sau đưa ra các ví dụ về các quan hệ synset WordNet và các hướng tương ứng của chúng. Còn hình C.1 sau các ví dụ về đường dẫn được phép cũng như không được phép. Dựa trên định nghĩa các đường dẫn được phép và lấy chiều dài lớn nhất của đường dẫn được phép bằng 4, ta phân biệt bảy trường hợp như minh họa trong hình C.2. Quan hệ Hướng Also see Horizontal Attribute Horizontal Cause Down Entailment Down Holonymy Down Hypernymy Up Hyponymy Down Meronymy Up Pertinence Horizontal Similarity Horizontal Bảng C.1 Phân loại các quan hệ trong WordNet thành các hướng Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 101 Hình C.1 Đường dẫn được phép và không được phép trong thuật toán của Hirst và St-Onge Hình C.2: Phân loại các quan hệ ngữ nghĩa trong WordNet 0 1 1 1 1 5 5 5 5 5 5 4 4 4 3 3 3 3 7 7 7 2 6 6 6 2 6 6 2 2 6 Các nút trong đồ thị này mô tả các synset của các từ (word). Các quan hệ ngữ nghĩa giữa các từ được chai thành bốn loại: Tương đương (Equivalent): tồn tại một hay nhiều liên kết ngang giữa các synset của các từ (trường hợp 3). Rộng hơn (Broader than): tồn tại một hay nhiều liên kết lên giữa hai synset (trường hợp 1) hoặc các liên kết lên theo sau là các liên kết ngang (trường hợp 5). Liên quan tới (Related-to): tồn tại một liên kết lên theo sau là một liên kết xuống và có thể là các liên kết ngang (hai từ có một từ bao (hypernym) chung) (trường hợp 4). Hẹp hơn (Narrower than): tồn tại một (hoặc nhiều) liên kết xuống giữa hai synset (trường hợp 2) hoặc một liên kết xuống theo sau bởi các liên kết ngang (trường hợp 6 và 7). Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 102 2. Thuật toán đối sánh thuật ngữ // Quan hệ rất mạnh if (word1=word2) return 24; else // Quan hệ mạnh S1=synsetsOf(word1); S2=synsetsOf(word2); foreach s1 in S1 H1=horizontalSynsets(word1); U1=UpwardSynsets(word1); D1=DownwardSynsets(word1); foreach s2 in S2 H2=horizontalSynsets(word2); U2=UpwardSynsets(word2); D2=DownwardSynsets(word2); if s1=s2 then return 16; if (s1 is In(H2) or s2 is In(H1)) return 16; if (s1 is In(U2) or s1 is In(D2)) return 16; if (s2 is In(U1) or s2 is In(D1)) return 16; endif // Quan hệ trung bình listOfWeight=medStrong(0,0,0,s1,S2); return (max(listOfWeight)); MedStrong (state, distance, chdir, from, To) if ((from is In(To) and (distance > 1)) // tìm thấy đường dẫn listOfWeigth.add(8-distance-chdir); return true; endif if (distance >= 5) // đường dẫn quá dài return false; endif if (state = 0) H=horizontalSynsets(from); U=UpwardSynsets(from); D=DownwardSynsets(from); retU=retD=retH=false; foreach u in U retU=retU or medStrong(1,distance+1,0,h, To); // thử đi lên (state =1) foreach d in D retD=retD or medStrong(2,distance+1,0,d, To); // thử đi xuống (state =2) foreach h in H retH=retH or medStrong(3,distance+1,0,d, To); // thử đi ngang (state =3) return (retU or retD or retH); endif if (state = 1) // thay đổi hướng đầu tiên là lên, sau đó có thể chuyển sang lên hoặc ngang H=horizontalSynsets(from); U=UpwardSynsets(from); D=DownwardSynsets(from); retU=retD=retH=false; foreach u in U retU=retU or medStrong(1,distance+1,0,h, To); // thử đi lên (state =1) foreach d in D retD=retD or medStrong(4,distance+1,1,d, To); // thử đi xuống (state =4) foreach h in H retH=retH or medStrong(5,distance+1,1,d, To); // thử đi ngang (state =5) return (retU or retD or retH); endif Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 103 if (state = 2) // đi xuống H=horizontalSynsets(from); D=DownwardSynsets(from); retD=retH=false; foreach d in D retD=retD or medStrong(2,distance+1,0,d, To); // thử đi xuống (state =2) foreach h in H retH=retH or medStrong(6,distance+1,0,d, To); // thử đi ngang (state =6) return (retD or retH); endif if (state = 3) // đi ngang H=horizontalSynsets(from); D=DownwardSynsets(from); retD=retH=false; foreach d in D retD=retD or medStrong(7,distance+1,0,d, To); // thử đi xuống (state =7) foreach h in H retH=retH or medStrong(3,distance+1,0,d, To); // thử đi ngang (state =3) return (retD or retH); endif if (state = 4) // đi lên hoặc xuống D=horizontalSynsets(from); retD=false; foreach d in D retD=retD or medStrong(4,distance+1,0,d, To); // thử đi ngang (state =4) return (retD); endif if (state = 5) // đi lên hoặc ngang H=horizontalSynsets(from); D=DownwardSynsets(from); retD=retH=false; foreach d in D retD=retD or medStrong(4,distance+1,2,d, To); // thử đi xuống (state =4) foreach h in H retH=retH or medStrong(5,distance+1,1,d, To); // thử đi ngang (state =5) return (retD or retH); endif if (state = 6) // đi xuống và ngang H=horizontalSynsets(from); retH=false; foreach h in H retH=retH or medStrong(6,distance+1,1,d, To); // thử đi ngang (state =6) return (retH); endif if (state = 7) // đi ngang và xuống D=horizontalSynsets(from); retD=false; foreach d in D retD=retD or medStrong(7,distance+1,1,d, To); // thử đi ngang (state =7) return (retD); endif Danh mục tài liệu tham khảo [1] S. Amer-Yahia, S. Cho, D. Srivastava. Tree Pattern Relaxation, EDBT, 2002. [2] A. Budanitsky, G. Hirst. Semantic distance in WordNet: An experimental, application oriented evaluation of five measures, 2003. [3] D. Carmel, N. Efraty, G.M. Landau, Y.S. Maarek, Y. Mass. An Extension of the vector space model for querying XML documents via XML fragments. Second Edition of the XML and IR Workshop, In SIGIR Forum, Volume 36 Number 2, Fall 2002. [4] G. Cobena, S. Abiteboul, A. Marian. Detecting changes in XML Documents. In ICDE, 2002. [5] H.H. Do, S. Melnik, E. Rahm. Comparison of schema matching evaluations. In Proceedings of the second International Workshop on Web Databases, 2002. [6] A.H. Doan. Learning to map between structured representations of data. PhD thesis, University of Washington, 2002. [7] Lexical chains as representations of context for the detection and correction of malapropisms. In: Christiane Fellbaum (editor), WordNet: An electronic lexical database, Cambridge, MA: The MIT Press, 1998. [8] ISO, Information Processing- Text and Office systems- Standard Generalization Markup Language (SGML), (ISO 8879:1986), International Organisation for Standardisation, Geneva, 1986. [9] P. Leinonen. Automating XML Document Structure Transformations. In Proceedings of the ACM Symposium on Document Engineering, France, 2003. [10] G. Linden. Structured document transformations. Report A-1997-2. CS Department of University of Helsinki, Finland, 1997. [11] J. Madhavan, P.A. Bernstein, E. Rahm. Generic schema matching with Cupid. In Proceedings of the International Conference on Very Large Databases (VLDB), 2001. [12] S. Melnik, H. Garcia-Molina, E. Rahm. Similarity Flooding: A versatile Graph Matching Algorithm and its Application to Schema Matching. In Proceedings of the 18th International Conference on Data Engineering, 2002. [13] R. Miller. The Clio Project: managing heterogeneity. ACM SIGMOD Record 30(1): 78-83, 2001. [14] A. G. Miller (1995). WordNet: A lexical Database for English. ACM 38 (11), pages 39-41, 1995. [15] Mong Li Lee, Liang Huai Yang, Wynne Hsu, Xia Yang. XClust: Clustering XML Schemas for Effective Integration, in 11th ACM International Conference on Information and Knowledge Management, McLean, Virginia, November 2002. [16] E. Pietriga, J-Y. Vion-Dury, V. Quint. Vxt: a visual approach to XML transformations. In Proceedings of the ACM Symposium on Document Engineering, 2001. [17] E. Rahm and P.A. Bernstein. A survey of approaches to automatic schema matching. In VLDB Journal, pages 10: 334-350, 2001. [18] N. Routledge, L. Bird, A. Goodchild. UML and XML Schema, ADC, 2002. [19] D. Shasha, J. Wang, K. Zhang, and F. Shih. Fast algorithms for the unit cost editing distance between trees. In Journal of Algorithms, pages 581-621, 1990. [20] L. Xu. Source Discovery and Schema Mapping for Data Integration, PhD thesis, 2003. [21] L. Zamboulis. XML Schema Matching & XML Data Migration & Integration: A Step Towards The Semantic Web Vision. Technical Report, 2003. [22] A. Boukottaya. Schema Matching for Transforming Structured Documents. In DocEng'05, 2-4, 2005. [23] A. Vernet. XML transformation languages. Có thể xem tại: [24] XML Schema, W3C Recommendation, 2004. Có thể xem tại: [25] XML Schema Part 0: Primer, W3C Recommendation, 2004. Có thể xem tại: [26] XML Schema Part 1: Structures, W3C Recommendation, 2004. Có thể xem tại: [27] XML Schema Part 2: Datatypes, W3C Recommendation 2004. Có thể xem tại: [28] XSL Transformations (XSLT), W3C Recommendation, 2004. Có thể xem tại: ._.