Luận văn cao học – ngành công nghệ thông tin

  • Số trang: 130 |
  • Loại file: PDF |
  • Lượt xem: 22 |
  • Lượt tải: 0
tranphuong5053

Đã đăng 6896 tài liệu

Mô tả:

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 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 Đối sánh tự động lược đồ XML 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ả./. Luận văn cao học – ngành công nghệ thông tin ii Đối sánh tự động lược đồ XML Hà Nội, tháng 11 năm 2006 Võ Sỹ Nam Mục lục Danh mục từ viết tắt, thuật ngữ ................................................................................ iv Danh mục bảng biểu ................................................................................................... iv 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 đồ ......................................................................................... 7 1.1 Tổng quan về đối sánh lược đồ...................................................................................8 1.1.1 Các khái niệm cơ bản về đối sánh lược đồ ..........................................................8 1.1.2 Các lĩnh vực ứng dụng đối sánh lược đồ .............................................................9 1.2 Các tiếp cận đối sánh lược đồ ...................................................................................15 1.2.1 Phân loại các tiếp cận đối sánh lược đồ .............................................................15 1.2.2 Các tiếp cận đối sánh lược đồ ............................................................................16 1.2.3 Các phương pháp đối sánh lược đồ ...................................................................19 1.3 Các hệ thống đối sánh lược đồ XML ........................................................................21 1.3.1 Cupid (trung tâm nghiên cứu Microsoft) ...........................................................22 1.3.2 Similarity Flooding (đại học Stanford và đại học Leipzig) ..............................24 1.3.3 LSD (đại học Washington) ................................................................................26 1.3.4 Clio (IBM Almaden và đại học Toronto) ..........................................................27 1.3.5 Một số hệ thống đối sánh lược đồ khác .............................................................28 1.4 Kết chương ...............................................................................................................29 Chương 2 Các định nghĩa hình thức ........................................................................ 31 2.1 Vấn đề đối sánh lược đồ XML .................................................................................32 2.1.1 Đối sánh ngữ nghĩa và đối sánh cú pháp ...........................................................32 2.1.2 Thông tin đầu vào của tiến trình đối sánh..........................................................34 2.1.3 Thông tin đầu ra của tiến trình đối sánh ............................................................36 2.1.4 Các định nghĩa hình thức ...................................................................................37 Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin iii Đối sánh tự động lược đồ XML 2.2 Mô hình hóa lược đồ XML .......................................................................................38 2.2.1 Các nút đồ thị lược đồ........................................................................................39 2.2.2 Các cạnh đồ thị lược đồ .....................................................................................39 2.2.3 Các ràng buộc đồ thị lược đồ .............................................................................40 2.2.4 Các định nghĩa hình thức ...................................................................................42 2.3 Ánh xạ nguồn–đích ...................................................................................................45 2.4 Kết chương ...............................................................................................................48 Chương 3 Đối sánh tự động lược đồ XML .............................................................. 50 3.1 Tổng quan về đối sánh tự động lược đồ XML..........................................................51 3.2 Đo độ tương đồng ngôn ngữ .....................................................................................52 3.2.1 WordNet và quan hệ ngữ nghĩa giữa các từ ......................................................53 3.2.2 Thuật toán của Hirst và St-Onge .......................................................................53 3.2.3 Giải pháp của hệ thống Cupid ...........................................................................56 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ế ............................................................................................................................57 3.3.1 Xét tính tương thích kiểu dữ liệu lược đồ XML ................................................57 3.3.2 Phân tích phân cấp kiểu người thiết kế ..............................................................59 3.4 Đo độ tương đồng cấu trúc .......................................................................................60 3.4.1 Định nghĩa ngữ cảnh nút....................................................................................60 3.4.2 Đo độ tương tự đường dẫn .................................................................................61 3.4.3 Đo độ tương đồng ngữ cảnh nút ........................................................................67 3.5 Đo độ tương đồng nút và tạo ánh xạ giữa các phần tử .............................................70 3.5.1 Đo độ tương đồng nút ........................................................................................70 3.5.2 Tạo ánh xạ giữa các nút và cạnh đối sánh .........................................................72 3.6 Đánh giá tiến trình đối sánh lược đồ XML ...............................................................73 3.6.1 Các phương pháp đánh giá ................................................................................73 3.6.2 Đánh giá giải pháp .............................................................................................75 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 ................77 3.7.1 Tổng quan về tài liệu có cấu trúc .......................................................................78 3.7.2 Chuyển đổi tự động tài liệu có cấu trúc .............................................................83 3.7.3 Mô hình cho hệ thống chuyển đổi tự động tài liệu XML ..................................85 3.8 Kết chương ...............................................................................................................87 Kết luận và hướng phát triển .................................................................................... 89 1. Đóng góp chính của luận văn .....................................................................................89 Luận văn cao học – ngành công nghệ thông tin iv Đối sánh tự động lược đồ XML 2. Hướng phát triển ........................................................................................................92 Danh mục tài liệu tham khảo ..................................................................................... 95 Phụ lục ........................................................................................................................ 97 Phụ lục A: Ngôn ngữ đánh dấu mở rộng - XML ...........................................................98 Phụ lục B: Lược đồ XML ............................................................................................108 Phụ lục C: Thuật toán của Hirst và St-Onge ................................................................111 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 Danh mục bảng biểu Bảng 3. 1 Đặc điểm các lược đồ thử nghiệm...................................................... 70 Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin v Đối sánh tự động lược đồ XML 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 Luận văn cao học – ngành công nghệ thông tin 1 Mở đầu 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) Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 2 Mở đầu 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ợ. 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 Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 3 Mở đầu 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. 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ệ Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 4 Mở đầu 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. 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à StOnge để 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 Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 5 Mở đầu đổ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 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. Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 6 Mở đầu 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. Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 7 Chương 1: Đối sánh lược đồ 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. Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 8 Chương 1: Đối sánh lược đồ 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 Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
- Xem thêm -