Luận văn Đối sánh tự động lược đồ XML

Mục lục Danh mục từ viết tắt, thuật ngữ Danh mục bảng biểu Danh mục hình vẽ Mở đầu 1. Giới thiệu chung 2. Nội dung luận văn 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 đồ 1.1.2 Các lĩnh vực ứng dụng đối sánh lược đồ 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 đồ 1.2.2 Các tiếp cận đối sánh lược đồ 1.2.3 Các phương pháp đối sánh lược đồ 1.3 Các hệ thống đối sánh lược đồ XML 1.3.1 Cupid (trung tâm nghiên cứu Microsoft 1.3.2 Similarity Flooding (Đại học Stanford và đại học Leipzig) 1.3.3 LSD (Đại học Washington 1.3.4 Clio (IBM Almaden và đại học Toronto 1.3.5 Một số hệ thống đối sánh lược đồ khác 1.4 Kết chương Chương 2 Các định nghĩa hình thức 2.1 Vấn đề đối sánh lược đồ XML 2.1.1 Đối sánh ngữ nghĩa và đối sánh cú pháp 2.1.2 Thông tin đầu vào của tiến trình đối sánh 2.1.3 Thông tin đầu ra của tiến trình đối sánh 2.1.4 Các định nghĩa hình thức 2.2 Mô hình hóa lược đồ XML 2.2.1 Các nút đồ thị lược đồ 2.2.2 Các cạnh đồ thị lược đồ 2.2.3 Các ràng buộc đồ thị lược đồ 2.2.4 Các định nghĩa hình thức 2.3 Ánh xạ nguồn–đích 2.4 Kết chương Chương 3 Đối sánh tự động lược đồ XML 3.1 Tổng quan về đối sánh tự động lược đồ XML 3.2 Đo độ tương đồng ngôn ngữ 3.2.1 WordNet và quan hệ ngữ nghĩa giữa các từ 3.2.2 Thuật toán của Hirst và St-Onge 3.2.3 Giải pháp của hệ thống Cupid 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ế 3.3.1 Xét tính tương thích kiểu dữ liệu lược đồ XML 3.3.2 Phân tích phân cấp kiểu người thiết kế 3.4 Đo độ tương đồng cấu trúc 3.4.1 Định nghĩa ngữ cảnh nút 3.4.2 Đo độ tương tự đường dẫn 3.4.3 Đo độ tương đồng ngữ cảnh nút 3.5 Đo độ tương đồng nút và tạo ánh xạ giữa các phần tử 3.5.1 Đo độ tương đồng nút 3.5.2 Tạo ánh xạ giữa các nút và cạnh đối sánh 3.6 Đánh giá tiến trình đối sánh lược đồ XML 3.6.1 Các phương pháp đánh giá 3.6.2 Đánh giá giải pháp 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 3.7.1 Tổng quan về tài liệu có cấu trúc 3.7.2 Chuyển đổi tự động tài liệu có cấu trúc 3.7.3 Mô hình cho hệ thống chuyển đổi tự động tài liệu XML 3.8 Kết chương Kết luận và hướng phát triển 1. Đóng góp chính của luận văn 2. Hướng phát triển Danh mục tài liệu tham khảo Phụ lục Phụ lục A: Ngôn ngữ đánh dấu mở rộng - XML Phụ lục B: Lược đồ XML Phụ lục C: Thuật toán của Hirst và St-Onge

pdf114 trang | Chia sẻ: maiphuongtl | Lượt xem: 1697 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Luận văn Đối sánh tự động lược đồ XML, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
húng tôi đã kết hợp nhiều phương pháp khác nhau trong lĩnh vực đối sánh lược đồ nhằm đưa ra một kết quả ánh xạ chính xác đến mức có thể. Các phương pháp này bao gồm đối sánh ngôn ngữ, xét tính tương thích kiểu dữ liệu, phân tích phân cấp kiểu người thiết kế và đối sánh cấu trúc. Ngoài ra chúng tôi cũng đã mô tả tiến trình phát hiện các ánh xạ phức hợp và các phép toán chuyển đổi. Các phép toán này chủ yếu được phát hiện bằng cách sử dụng phân cấp kiểu người thiết kế và đối sánh cấu trúc. Trong luận văn này, để đối sánh cấu trúc chúng tôi dựa trên khái niệm ngữ cảnh nút. Có ba loại ngữ cảnh cho một nút đã cho: ngữ cảnh tổ tiên, ngữ cảnh con và ngữ cảnh lá. Từ kết quả đánh giá chất lượng đối sánh có thể thấy rằng sự kết hợp các ngữ cảnh này đã cải thiện được hiệu quả cho pha đối sánh cấu trúc. Trong thời gian tới chúng tôi sẽ xem xét kỹ hơn vấn đề kết hợp kết quả đối sánh tự động với phản hồi người dùng và kiểm thử giải pháp với CSDL lược đồ lớn hơn. Ngoài ra chúng tôi cũng sẽ thử nghiệm việc thay đổi các tham số được sử dụng để xem xét ảnh hưởng của chúng trên kết quả ánh xạ, từ đó chọn được những tham số tốt nhất. Cũng trong chương này chúng tôi đã áp dụng đối sánh lược đồ vào một lĩnh vực ứng dụng khá điển hình, đó là vấn đề chuyển đổi tài liệu có cấu trúc. Chúng tôi đã mô tả các khái niệm cơ bản nhất về tài liệu có cấu trúc cũng như các nghiên cứu điển hình về vấn đề này. Dựa trên các giải thuật đã được đưa ra gần đây, chúng tôi tổng hợp một mô hình cho hệ thống chuyển đổi tự động tài liệu XML. Chúng tôi hy vọng rằng bằng cách áp dụng giải pháp đối sánh lược đồ đã nêu trên vào mô hình này, vấn đề chuyển đổi tự động tài liệu XML sẽ được giải quyết triệt để hơn. Việc thực thi mô hình này là một trong những hướng phát triển tiếp theo của đề tài. Kết luận và hướng phát triển Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 81 Kết luận và hướng phát triển 1. Đóng góp chính của luận văn Trong luận văn này chúng tôi đã xem xét một cách khá toàn diện vấn đề đối sánh lược đồ, tập trung vào vấn đề đối sánh tự động lược đồ XML. Đối sánh lược đồ là một vấn đề đã thu hút nhiều chú ý và đã có nhiều nghiên cứu khác nhau quan tâm đến vấn đề tự động hóa tiến trình đối sánh lược đồ, đặc biệt là lược đồ XML. Mặc dù các nghiên cứu này đã đề cập đến rất nhiều khía cạnh trong vấn đề đối sánh tự động, vẫn còn nhiều vấn đề cần được giải quyết thấu đáo hơn, thậm chí vẫn còn một số vấn đề chưa được đề cập đến. Trong luận văn này, ngoài việc trình bày các khái niệm cơ bản về vấn đề đối sánh lược đồ, chúng tôi đã cố gắng tổng hợp lại các kết quả nghiên cứu mới nhất về đối sánh lược đồ, đặc biệt là lược đồ XML. Tiếp theo chúng tôi đã đưa ra một giải pháp đối sánh toàn diện và hiệu quả hơn. 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 và hy vọng rằng có thể áp dụng giải pháp đã đưa ra cho mô hình này. Đóng góp đầu tiên của luận văn, được trình bày trong chương 1, là một khảo sát tương đối toàn diện về vấn đề đối sánh lược đồ. Chúng tôi dựa trên các khảo sát của Rahm và Berntein, Zamboulis, Đoàn An Hải, Đỗ Hồng Hải, Shvaiko và Euzenat, Madhavan, Budanisky, v.v.. cũng như một số nghiên cứu gần đây về lĩnh vực này. Dựa trên các khảo sát, chúng tôi đã mô tả một cách khá đầy đủ các kết quả nghiên cứu về vấn đề đối sánh tự động lược đồ XML. Kết luận và hướng phát triển Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 82 Một đóng góp tiếp theo của luận văn, được trình bày trong chương 2, là việc tổng hợp lại các định nghĩa hình thức về vấn đề đối sánh lược đồ cũng như sử dụng một số nghiên cứu trong các lĩnh vực khác nhằm đưa ra các định nghĩa hình thức cho vấn đề đối sánh tự động lược đồ XML một cách đầy đủ hơn. Đặc biệt chúng tôi cũng đã trình bày các định nghĩa hình thức cho đồ thị lược đồ, một mô hình khá hiệu quả để biểu diễn lược đồ XML. Đồ thị lược đồ là một mô hình đã được sử dụng trong rất nhiều hệ thống đối sánh lược đồ. Các định nghĩa hình thức này cho phép xem xét vấn đề đối sánh lược đồ một cách có hệ thống hơn và góp phần quan trọng vào việc đánh giá các giải pháp đối sánh lược đồ đã được đề xuất. Một đóng góp quan trọng của luận văn, được trình bày trong chương 3, là việc đưa ra một giải pháp đối sánh tự động lược đồ XML. Như đã trình bày trong suốt chương 3, giải pháp này dựa trên việc kết hợp một số nghiên cứu riêng lẻ trong đối sánh lược đồ cũng như một số ý tưởng trong các lĩnh vực khác (tích hợp dữ liệu, tìm kiếm và so sánh văn bản, xử lý truy vấn…). Giải pháp này bao gồm các khía cạnh chính sau: - Đo độ tương đồng thuật ngữ của các nút lược đồ dựa trên tên của chúng. Phép đo này sử dụng WordNet làm nguồn từ vựng và sử dụng thuật toán của Hirst và St-Onge để đưa ra các quan hệ ngữ nghĩa thích hợp cho vấn đề đối sánh lược đồ. - Đo độ tương đồng ràng buộc của các nút lược đồ dựa trên các ràng buộc tương ứng của chúng. Ở đây chúng tôi giới hạn trong việc sử dụng kiểu dữ liệu. Để so sánh các kiểu dữ liệu, chúng tôi đã sử dụng phân cấp kiểu lược đồ XML trong đó sự tương thích của hai kiểu phụ thuộc vào vị trí tương ứng của chúng trong phân cấp. - Đo độ tương đồng cấu trúc của các nút lược đồ dựa trên trên sự tương đồng của ngữ cảnh cấu trúc mà chúng xuất hiện. Trong luận văn này chúng Kết luận và hướng phát triển Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 83 tôi đã xem xét các giới hạn của giải pháp hiện hành qua việc nghiên cứu các hệ thống Cupid, SF và XClust, sau đó đưa ra một phương pháp đối sánh cấu trúc mà xét đến đầy đủ các ngữ cảnh của nút trong đồ thị lược đồ. Ở đây chúng tôi đã biểu diễn mỗi ngữ cảnh nút như một đường dẫn và sau đó dựa trên phép đo độ tương tự đường dẫn để so sánh các ngữ cảnh này. Trong luận văn này chúng tôi đã nới lỏng khái niệm đối sánh mạnh thường được sử dụng trong việc giải quyết vấn đề trả lời truy vấn và sử dụng ý tưởng của Carmel về việc so sánh đường dẫn để áp dụng cho vấn đề đối sánh lược đồ. - Đưa ra thuật toán kết hợp tất cả các phép đo tương đồng trên và đưa ra kết quả ánh xạ, các phép toán chuyển đổi và các điều kiện cho việc thực hiện các ánh xạ. Để tạo kết quả ánh xạ này, chúng tôi đã sử dụng ý tưởng về chiến lược phân tích trên-xuống trong lĩnh vực tích hợp dữ liệu. - Khía cạnh cuối cùng là việc đánh giá thực nghiệm cho giải pháp. Chúng tôi đã sử dụng một tập dữ liệu từ ứng dụng thực tế để đánh giá giải pháp đối sánh lược đồ đưa ra. Ngoài ra chúng tôi cũng đã so sánh giải pháp này với các hệ thống Cupid và SF và chỉ ra rằng nó thực hiện tốt hơn các thuật toán này. Đóng góp cuối cùng của luận văn, được trình bày trong phần cuối chương 3, là một khảo sát về vấn đề chuyển đổi tài liệu có cấu trúc và một mô hình cho hệ thống chuyển đổi tự động tài liệu XML mà có khả năng áp dụng được giải pháp đối sánh tự động lược đồ XML nói trên. Trong phần này chúng tôi đã trình bày các khái niệm cơ bản về tài liệu có cấu trúc, vấn đề sử dụng lại cấu trúc cũng như một khái niệm gắn liền với sử dụng lại cấu trúc: chuyển đổi 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, bao gồm các nghiên cứu cơ bản trong lĩnh vực này cũng như vấn đề tạo chương trình XSLT. Dựa trên các nghiên cứu gần đây về lĩnh vực này, chúng tôi đã tổng hợp một mô hình cho phép giải quyết hiệu quả vấn đề chuyển đổi tự động tài liệu XML. Kết luận và hướng phát triển Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 84 2. Hướng phát triển Cho đến đây, ta đã hoàn thành mục tiêu đặt ra ban đầu, đó là tổng kết lại các nghiên cứu đã công bố và đưa ra giải pháp tối ưu hơn cho vấn đề đối sánh lược đồ. Tuy nhiên như đã thấy, vấn đề này vẫn chưa được giải quyết triệt để. Ta vẫn còn có thể mở rộng kết quả này để thu được một giải pháp đối sánh toàn diện hơn. Sau đây là một số hướng phát triển cho đề tài này: * Đối sánh ngôn ngữ và đối sánh dựa trên ràng buộc Về cơ bản, giải pháp của chúng tôi vẫn chỉ quan tâm nhiều đến đối sánh cấu trúc. Vấn đề còn lại là đối sánh ngôn ngữ và đối sánh dựa trên ràng buộc. Trong đối sánh ngôn ngữ, chúng tôi đã sử dụng giải thuật của Hirst và St-Onge nhằm so sánh tên các phần tử cũng như giải pháp của hệ thống Cupid nhằm giải quyết các vấn đề như tên phần tử có tồn tại từ viết tắt, từ rút gọn, các dấu chấm câu, v.v.. Tuy vậy, để khai thác các quan hệ từ đồng nghĩa hoặc tổng quát nghĩa ta còn cần phải sử dụng các từ điển chuyên đề hoặc các từ điển như WordNet. Thêm vào đó, đối sánh thuật ngữ có thể phải sử dụng các từ điển chuyên đề bao gồm tên chung, từ đồng nghĩa, từ viết tắt, v.v.. Có thể dựa vào các nghiên cứu về từ điển chuyên đề để thực hiện công việc này. Ngoài ra cũng có thể sử dụng kết hợp các phương pháp đối sánh xâu thích hợp để bổ sung cho kết quả đối sánh ngôn ngữ. Trong đối sánh dựa trên ràng buộc, chúng tôi đã giới hạn trong việc phân tích sự tương thích kiểu dữ liệu. Tuy vậy, ta có thể thêm vào tập ứng viên đối sánh một số ràng buộc như đơn nhất hay toàn vẹn bằng cách sử dụng các kỹ thuật như được mô tả trong [13]. Hơn nữa, các phân tích về ràng buộc kiểu dữ liệu của chúng tôi cũng bị giới hạn ở một số khía cạnh, chẳng hạn như chúng tôi không xét đối sánh mẫu. Để mở rộng vấn đề này, ta có thể sử dụng các nghiên cứu về biểu thức chính quy và đối sánh mẫu. Kết luận và hướng phát triển Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 85 * Tương tác người dùng hiệu quả Một trong những vấn đề quan trọng nhất của đối sánh lược đồ là tương tác người dùng hiệu quả. Đầu vào người dùng cần phải được đưa vào tại các thời điểm then chốt mà ở đó nó là có ích nhất, không nhất thiết phải là trước và/hay sau đối sánh, điều này làm cho việc hiệu chỉnh sau khi đối sánh dễ dàng hơn vì các phỏng đoán sai lệch mà không có sự xác nhận của người dùng sẽ không được xét đến. Hơn nữa, sự phát triển mạnh mẽ của các hệ thống chia sẻ dữ liệu Web sẽ làm tăng hơn nữa vấn đề tương tác người dùng. Trong thực tế, ngay cả nếu tồn tại một giải pháp đối sánh gần hoàn hảo, người dùng vẫn phải xác nhận tính hợp lệ của một số lượng lớn các kết quả đối sánh được đưa ra. Vấn đề ở đây là làm thế nào để giảm thiểu tương tác người dùng nhưng vẫn tối đa hóa được ảnh hưởng của phản hồi người dùng. * Duy trì ánh xạ Trong các môi trường động như Web, các nguồn dữ liệu có thể thay đổi không chỉ về dữ liệu mà còn cả về lược đồ và ngữ nghĩa. Các thay đổi này phải được phản ánh lại trong ánh xạ. Các ánh xạ gây ra sự không nhất quán do sự thay đổi của lược đồ phải được phát hiện và hiệu chỉnh. Có thể thấy rằng việc duy trì bằng tay các ánh xạ là không khả thi. Điều này đòi hỏi phải phát triển các kỹ thuật thích ứng tự động các ánh xạ khi các lược đồ thay đổi. * Đánh giá hiệu năng Để đánh giá giải pháp đối sánh lược đồ đã đưa ra một cách chính xác hơn, ta cần sử dụng một tập rộng các ứng dụng và dữ liệu. Bên cạnh đó, như [6] đã mô tả, việc định lượng sự giảm bớt can thiệp người dùng trong giải pháp đối sánh là rất quan trọng, do vậy ta cần các phép đo đánh giá được vấn đề này. Cuối cùng, ta cần áp dụng nhiều hơn nữa các nghiên cứu thực nghiệm để chỉ ra ảnh hưởng của các trọng số đã chọn lên tiến trình đối sánh. Danh mục tài liệu tham khảo Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 86 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. Danh mục tài liệu tham khảo Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 87 [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, 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, 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, C. Vanoirbeek. 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: Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 88 Phụ lục Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 89 Phụ lục A: Ngôn ngữ đánh dấu mở rộng - XML 1. Tổng quan về XML XML (Extensible Markup Language - ngôn ngữ định dạng mở rộng) [23], là chuẩn đặc tả dữ liệu được sử dụng rộng rãi nhất hiện nay. Có thể thấy rằng XML có quan hệ rất gần gũi với HTML - ngôn ngữ định dạng dùng rộng rãi trong các trang Web hiện nay: cả hai đều dựa trên chuẩn ngôn ngữ định dạng tổng quát SGML (Standard Generalized Markup Language). Điểm khác biệt lớn nhất là các thẻ HTML đã được định nghĩa trước, còn các thẻ XML là do người sử dụng định nghĩa và tùy theo mục đích sử dụng mà có nhiều loại định dạng khác nhau phát sinh từ cách thức chuẩn của XML. Sau đây ta xét một số đặc trưng của XML: - Dễ dàng trao đổi dữ liệu: XML lưu ở dạng text và có thể dễ dàng cấu hình cũng như thay đổi chúng bằng các trình soạn thảo thông thường. XML đã được chuẩn hóa, mọi người đều có thể hiểu và sử dụng nó. Điều này giải quyết được khó khăn của việc chuyển đổi qua lại giữa rất nhiều định dạng dữ liệu hiện nay. - Tùy biến ngôn ngữ định dạng: có thể tạo ra các ngôn ngữ định dạng tùy biến dựa trên XML. Không chỉ vậy, có thể mở rộng chúng, có thể ghi chú thích trong tài liệu. Đây là một trong những khả năng mạnh nhất của XML. - Dữ liệu có cấu trúc và tích hợp: XML không chỉ cho phép lưu dữ liệu vào file XML dựa trên thẻ mà còn tổ chức dữ liệu theo cấu trúc, theo đó các phần tử thẻ tích hợp với nhau tạo nên một cấu trúc dữ liệu phân cấp hoàn chỉnh. Điều này cho phép ta định nghĩa dữ liệu có cấu trúc một cách hết sức thuận lợi. Nhìn chung XML hoàn toàn thích hợp cho việc liên lạc giữa các môđun, các thành phần trong bất kì chương trình ứng dụng nào dù nhỏ hay lớn. 1.1 Khuôn dạng tài liệu XML Các phần của tài liệu XML được gọi là thực thể, nó có thể chứa dữ liệu văn bản hoặc nhị phân nhưng không được cả hai. Một thực thể có thể tham chiếu đến thực thể khác, có thể dùng để phân tích hoặc làm dữ liệu thông thường (không dùng cho mục đích phân tích). Tài liệu XML được bắt đầu bằng chỉ thị . Nếu toàn bộ tài liệu là một thực thể duy nhất không tham chiếu đến các thực thể khác thì thêm chỉ thị standalone = “yes”. Sau đó là các thẻ chứa dữ liệu theo cấu trúc phân cấp. Phụ lục Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 90 - Định dạng và dữ liệu kí tự: tài liệu XML tạo thành từ thành phần định dạng và thành phần dữ liệu kí tự, còn dữ liệu nhị phân chưa có quy định cách đưa vào mà chỉ được tham chiếu đến bằng cách biểu diễn thực thể. Định dạng bao gồm thẻ bắt đầu, thẻ kết thúc, các phần tử thẻ rỗng, các tham chiếu thực thể, tham chiếu ký tự, lời chú thích, phân đoạn CDATA, khai báo kiểu tài liệu và chỉ thị xử lý. Tất cả các dữ liệu còn lại trong tài liệu không phải là định dạng đều được xem là dữ liệu ký tự. - Phần khởi đầu (prolog): bắt đầu ngay từ những dòng đầu của tài liệu, nhìn chung bao gồm các khai báo, chú thích, chỉ thị xử lý, khoảng trắng và khai báo kiểu tư liệu (DTD). Chuẩn XML không yêu cầu khai báo prolog, tuy vậy ta nên dùng nó, ít nhất cũng nên có dòng khai báo phiên bản sử dụng. - Các khai báo: khai báo XML sử dụng phần tử . Có 3 kiểu khai báo thuộc tính: khai báo phiên bản cho biết phiên bản đặc tả XML, khai báo mã hóa cho biết bộ mã đang sử dụng (mặc định là UTF-8, có thể sử dụng mã Unicode, UCS-2, UCS-4…), khai báo thực thể độc lập là “yes” nếu tài liệu không tham chiếu đến các thực thể khác bên ngoài, nếu không là “no”. - Chú thích: bắt đầu bằng . Chú thích không được đặt trước khai báo, không thể dùng chuỗi -- trong đoạn chú thích. Chú thích có thể dùng để loại bỏ một đoạn mã nào đó (trong nội dung chú thích không được chứa chú thích khác). - Chỉ thị xử lý: bắt đầu bằng , nhằm chỉ dẫn cho bộ phân tích cách xử lý tài liệu XML. Ví dụ: - Thẻ và các phần tử (element): thẻ mở có dạng “”, thẻ đóng có dạng “. Thẻ bắt đầu phải có thẻ kết thúc tương ứng. Tên thẻ có quy định chặt chẽ: bắt đầu bằng kí tự, gạch chân (_), dấu hai chấm (:), kế tiếp có thể là kí tự, kí số, gạch chân, gạch nối, dấu chấm, dấu hai chấm (nên tránh dùng) nhưng không được là khoảng trắng. Thẻ phân biệt chữ hoa và chữ thường. Phần tử có thể chỉ có duy nhất một thẻ, tức là phần tử rỗng không kèm theo dữ liệu. Ví dụ: . Phần tử gốc là phần tử chứa tất cả các phần tử và các cặp thẻ khác trong tài liệu. - Thuộc tính: tương tự thuộc tính các thẻ trong HTML, có dạng name=value. Ví dụ: . Nhìn chung nếu có quá nhiều thuộc tính trong thẻ sẽ làm tài liệu khó đọc. Tên thuộc tính theo đúng quy tắc đặt tên thẻ, còn trị gán cho Phụ lục Võ Sỹ Nam. Luận văn cao học – 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:

Các file đính kèm theo tài liệu này:

  • pdf000000208336R.pdf
Tài liệu liên quan