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

một tên ràng buộc (chẳng hạn như ràng buộc duy nhất, số yếu tố), Ccategory là một danh mục ràng buộc (ràng buộc trên nút, Chương 2: Các định nghĩa hình thức Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 41 ràng buộc trên cạnh, ràng buộc trên tập cạnh), Capply-to định nghĩa các thành phần áp dụng ràng buộc (ví dụ tên nút trong trường hợp ràng buộc trên nút) và Cvalue là giá trị của ràng buộc (nếu nó tồn tại, nếu không thì lấy giá trị mặc định ∅). Ta không cần kiểm tra tính hợp khuôn dạng của đồ thị lược đồ (ví dụ nếu nhãn cạnh là thuộc tính thì kiểm tra rằng nút nguồn là một nút phức hợp và nút đích là một nút nguyên tố). Điều này là do ta xây dựng đồ thị lược đồ trên cơ sở các lược đồ XML hợp lệ đã có. Dựa trên các khái niệm nút và cạnh, ta đưa ra thêm các khái niệm đường dẫn, đường dẫn nguyên thủy như sau: Định nghĩa 2.7 (Đường dẫn) Một đường dẫn từ một nút n1 tới nút nk là một dãy n1, n2, … , nk, trong đó n1, n2, … , nk ∈NG, và với bất kỳ hai nút liên tiếp ni and ni+1 (1 ≤ i ≤ k-1), tồn tại một cạnh ei (l, ni , ni+1) ∈ EG – {Ea}. Một đường dẫn chỉ bao gồm các cạnh chứa và cạnh thuộc-tính-của. Ta gọi n1 và nk lần lượt là nút bắt đầu và nút kết thúc của đường dẫn. Đường dẫn được xem là đi qua nút ni (1 ≤ i ≤ k). Độ dài của đường dẫn là tổng số nút mà đường dẫn đi qua, tức là, k với đường dẫn P = (n1, n2, … , nk), biểu thị như length(P)= k. Định nghĩa 2.8 (Đường dẫn nguyên thủy) Một đường dẫn từ nút n1 tới nút nk, là một đường dẫn nguyên thủy khi và chỉ khi nút bắt đầu n1 không có cạnh vào (nghĩa là nút bắt đầu là gốc của đồ thị lược đồ). Khái niệm đồ thị lược đồ được mô tả ở trên không bao gồm các tính năng như thừa kế kiểu và kiểu trừu tượng. Các vấn đề này sẽ được xem xét trong chương 3. Chú ý rằng đồ thị lược đồ được xây dựng bằng cách mở rộng các kiểu chia sẻ trong lược đồ XML. Dựa trên việc hình thức hóa đồ thị lược đồ, ta đưa ra thêm một số định nghĩa về việc chuyển đổi khởi dựng nguồn thành khởi dựng đích (khái niệm khởi dựng ở đây nhằm nói đến nút và cạnh trong đồ thị lược đồ). Một phần tử ánh xạ liên kết một khởi dựng từ S tới một khởi Chương 2: Các định nghĩa hình thức Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 42 dựng tương đồng ngữ nghĩa từ T (lần lượt là các đồ thị lược đồ nguồn và đích). Mặc dù một nguồn có thể không có một khởi dựng tương ứng trực tiếp tới một khởi dựng đích, các khởi dựng đích có thể được dẫn xuất từ các khởi dựng nguồn bằng cách áp dụng một tập các phép toán đã định nghĩa trước. Cơ chế này có những điểm tương đồng với việc tạo khung nhìn ảo trong tích hợp dữ liệu, ở đó một khung nhìn ảo trên nguồn phải đối sánh với một lược đồ trung gian (ví dụ ghép nối của các phần tử nguồn FirstName và LastName thành một phần tử ảo Name mà đối sánh với phần tử đích Name). Khung nhìn ảo cũng áp dụng được cho cạnh (ví dụ hai cạnh Author→FirstName và Author→LastName được hợp nhất với nhau thành một cạnh ảo Author→Name đối sánh với cạnh Author→Name trong lược đồ đích). Dựa trên các định nghĩa trong [20] cho vấn đề tạo khung nhìn ảo, ta có thể đưa ra các định nghĩa hình thức ánh xạ giữa các lược đồ nguồn và đích như sau: Định nghĩa 2.9 (Bảng ký tự lược đồ) Cho một lược đồ K (tuân theo hình thức đồ thị lược đồ), ta gọi bảng ký tự lược đồ của K hay ΣK là hợp của các nút và các cạnh trong đồ thị lược đồ của K: ΣK = NK ∪EK. Định nghĩa 2.10 (Khung nhìn ảo) Cho một lược đồ nguồn S và bảng ký tự ΣS của nó, một khung nhìn ảo υS trên S là một dẫn xuất từ bảng ký tự ΣS áp dụng một tập các phép toán đã định nghĩa trước O ={o1,…on.}. Định nghĩa 2.11 (Phần tử ánh xạ, ánh xạ trực tiếp, ánh xạ phức hợp) Cho VS là tập các khung nhìn ảo có thể được xây dựng trên ΣS. Một phần tử ánh xạ là một hàm mst: ΣS∪VS → ΣT, nối kết một phần tử s trong ΣS∪VS tới một phần tử t trong ΣT. Một phần tử ánh xạ là một ánh xạ trực tiếp nếu nó nối kết một phần tử trong ΣS (⊆VS) tới một phần tử trong ΣT và là một ánh xạ phức hợp nếu nó nối kết một phần tử ảo υS ∈VS tới một phần tử đích trong ΣT qua một biểu thức ánh xạ đã định nghĩa trên O. Chương 2: Các định nghĩa hình thức Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 43 2.3 Ánh xạ nguồn–đích Một trong những ứng dụng cơ bản của đối sánh lược đồ là vấn đề chuyển đổi giữa các nguồn dữ liệu có cấu trúc tuân theo các lược đồ tương đồng. Vấn đề này đòi hỏi ta phải thiết lập các ánh xạ thích hợp giữa các phần tử tương đồng trong hai lược đồ nguồn và đích đã cho, hay còn gọi là ánh xạ nguồn– đích. Các nghiên cứu trong lĩnh vực CSDL đã đưa ra mô hình đại số quan hệ khá hoàn chỉnh, do vậy ta có thể mở rộng mô hình này cho vấn đề ánh xạ nguồn–đích trong đối sánh lược đồ. Nhiều nghiên cứu khác nhau (chủ yếu trong lĩnh vực tích hợp dữ liệu) đã mô tả các phép toán tạo khung nhìn ảo trên các lược đồ. Để giải quyết vấn đề này, họ chỉ ra một tập các phép toán sử dụng như là các chuyển đổi truy vấn để tích hợp thông tin nguồn vào khung nhìn đích. Một mở rộng của nghiên cứu này đã được đề xuất trong [20] nhằm công thức hóa lại các truy vấn trong hệ thống tích hợp dữ liệu. Tuy vậy, các nghiên cứu này chỉ quan tâm đến các lược đồ quan hệ và chúng không hoàn toàn áp dụng được cho lược đồ XML. Các nghiên cứu về đối sánh cây, chẳng hạn như [19] lại chú ý đến vấn đề phát hiện thay đổi cho cây gán nhãn. Họ đưa ra ba phép toán trong đối sánh cây: delete, insert, relabel. Kịch bản thao tác "rẻ nhất" cho việc chuyển đổi cây nguồn thành một cây đích là kết hợp các phép toán này. Tuy vậy, trong các tiếp cận này, nhãn của nút không quan trọng. Phép toán gán lại nhãn được xem là “rẻ” hơn phép xóa theo sau là một phép toán chèn. Trong thực tế, nhãn là tên tổng quát của thẻ XML mang thông tin ngữ nghĩa nên việc gán lại nhãn một nút thành một nút khác không liên quan về ngữ nghĩa có thể cho ra một kết quả không mong muốn trong đối sánh lược đồ XML. Dựa vào các nghiên cứu trên và xuất phát từ các phép toán cơ bản đã được mô tả trong đại số quan hệ chuẩn, ta có thể đưa ra các phép toán ánh xạ nguồn–đích áp dụng cho đối sánh lược đồ XML. Sau đây chúng tôi sẽ xem Chương 2: Các định nghĩa hình thức Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 44 xét những vấn đề cần phải giải quyết trong đối sánh lược đồ XML, từ đó mô tả các phép toán này. Các vấn đề mô tả ở đây về cơ bản dựa trên nghiên cứu về đại số ánh xạ nguồn–đích đã được đưa ra trong [22]. ● Người thiết kế lược đồ có thể mô tả các khái niệm tương tự về mặt ngữ nghĩa bằng cách sử dụng các tên khác nhau. Để giải quyết vấn đề này, ta cần một phép toán đổi tên như sau: Rename: t = rename(s), tạo ra một khởi dựng giống như s nhưng với một tên khác là t. Ví dụ: writer=rename (author) chỉ ra rằng một thể hiện nguồn author được đổi tên thành thể hiện đích writer. ● Với mỗi nút đích, có thể có một tập con thích hợp các giá trị mong đợi hoặc một tập mẹ thích hợp các giá trị mong đợi trong nguồn. Ví dụ ta hãy xét một lược đồ 1 trong đó một Author có con là các nút Paper và Book mô tả publication của nó. Ngược lại, Author trong một lược đồ 2 đã cho có một nút con là Publication. Trong lược đồ 1, các nút Paper và Book là các tập con của nội dung Publication trong lược đồ 2, và các quan hệ Author→Paper và Author→Book đều là chi tiết hóa của quan hệ Author→Publication trong lược đồ 2. Do đó, nếu lược đồ 2 là đích, ta có thể cần đến phép hợp các nội dung của Paper và Book và các quan hệ Author→Paper và Author→Book. Nếu lược đồ 1 là đích, ta cần tìm kiếm một cách để lựa chọn nội dung của các paper và các book và các quan hệ giữa author và các paper và author và book từ các quan hệ giữa author và publication. Để giải quyết vấn đề này, ta cần hai phép toán hợp và chọn như sau: Hợp: Union: t = union (s1, s2), tạo ra một khởi dựng t mà nội dung của nó là hợp của các giá trị s1 và các giá trị s2, Chọn: Selection: t = selectP (s) (trong đó P là một vị từ) tạo ra một khởi dựng t mà nội dung của nó là một phần của nội dung của s mà thỏa mãn vị từ P. Chương 2: Các định nghĩa hình thức Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 45 ● Người thiết kế lược đồ có thể không chọn cách biểu diễn các giá trị ở cùng mức nguyên tố. Ví dụ, một tên tác giả được biểu diễn trong lược đồ đã cho sử dụng phần tử Name. Trong khi trong một lược đồ khác, nó được tách thành First-Name và Last-Name. Nếu lược đồ 1 là đích, ta cần nối các giá trị của First-Name và Last-Name lại với nhau, còn nếu lược đồ 2 là đích, ta cần tách các giá trị của các phần tử Name thành các giá trị First-Name và Last- Name. Để giải quyết vấn đề này, ta cần hai phép toán nhập và tách như sau: Nhập: Merge: t = merge (S1…Si), tạo ra một khởi dựng t mà giá trị của nó thu được bằng cách nối các giá trị s1...si với nhau, Tách: Split: (t1…ti) = splitcriteria (s), trong đó t1...ti thu được bằng cách phân chia một khởi dựng s dựa vào tiêu chuẩn tách biệt. Một ví dụ của tiêu chuẩn tách biệt này là khoảng trắng (“white space”) trong trường hợp các xâu. ● Một khởi dựng đích có thể thu được bằng cách áp dụng một phép kết nối tự nhiên (như trong các lược đồ quan hệ) các khởi dựng nguồn. Để giải quyết vấn đề này, ta cần một phép toán nối như sau: Nối: Join: t= joinP(S1,S2), tạo ra khởi dựng đích t là kết nối tự nhiên của S1 và S2 dưới vị từ P. ● Ta thường cần một số hàm đặc biệt để chuyển đổi nội dung của các giá trị nguồn thành các giá trị đích, chẳng hạn như chuyển đổi đơn vị, chuyển đổi định dạng ngày tháng hay các hàm toán học như min, avg, div, v.v.. Đối với trường hợp này, ta cần một phép toán áp dụng như sau: Áp dụng: Apply: t = applyf (s1…si) trong đó f là một hàm của các biến s1…si và trả về t, mà giá trị của nó tương ứng với f (s1…si). ● Với mỗi trường hợp mà ta có một đối sánh một-một mà không có bất kỳ sự thay đổi nào, ta cần một phép toán nối như sau: Connect: t = connect(s), tạo ra khởi dựng t có cùng nội dung và nhãn như s. Chương 2: Các định nghĩa hình thức Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin 46 2.4 Kết chương Việc đưa ra các định nghĩa hình thức cho vấn đề đối sánh lược đồ là một bước quan trọng trong tiến trình đối sánh. Điều này giúp người dùng đánh giá và so sánh được khả năng ứng dụng của các giải pháp đối sánh. Dựa trên việc phân tích thông tin vào và ra cho một hệ thống đối sánh lược đồ XML, chúng tôi đã mô tả các giả thiết cơ bản cho tiến trình đối sánh. Tiếp theo, chúng tôi đã mô tả các định nghĩa cho mô hình dữ liệu biểu diễn lược đồ XML, là đồ thị gán nhãn có hướng và có gốc, hay còn gọi là đồ thị lược đồ. Ngoài việc tính toán độ tương đồng giữa các phần tử lược đồ, các giải pháp đối sánh thường quan tâm đến việc phát hiện ánh xạ giữa các nút và cạnh đối sánh cũng như các phép toán chuyển đổi nhằm mục đích truy lục dữ liệu từ lược đồ nguồn. Do đó trong chương này chúng tôi cũng đã mô tả các phép toán ánh xạ nguồn–đích như đổi tên, nối và áp dụng nhằm tạo các ánh xạ trực tiếp cũng như hợp, chọn, nhập và tách để tạo các ánh xạ phức hợp. Tuy vậy, công việc cơ bản trong bất cứ giải pháp đối sánh lược đồ nào vẫn là việc tính toán độ tương đồng giữa các phần tử lược đồ, do vậy ta cần phải chỉ ra các tiêu chuẩn đối sánh cũng như việc thực hiện chúng. Bên cạnh đó, do tiến trình đối sánh lược đồ là không thể tự động được hoàn toàn, nghĩa là cần phải có sự xác nhận của người dùng, các giải pháp đối sánh lược đồ cần phải kết hợp được phản hồi người dùng trong kết quả đối sánh. Các vấn đề này sẽ được trình bày trong chương tiếp theo. Chương 3: Đố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 47 Chương 3 Đối sánh tự động lược đồ XML Trong chương này đầu tiên chúng tôi mô tả các thuật toán đối sánh lược đồ khác nhau và cách kết hợp chúng để thu được độ tương đồng giữa các thực thể lược đồ. Vấn đề đặt ra ở đây là làm thế nào để sử dụng một cách tối đa thông tin cấu trúc nhằm thu được các ánh xạ giữa các lược đồ XML nguồn và đích. Để thực hiện điều này, chúng tôi dựa vào các kết quả nghiên cứu trong nhiều lĩnh vực như tích hợp dữ liệu, chuyển đổi dữ liệu, trả lời truy vấn, v.v.. nhằm đưa ra phép đo độ tương đồng giữa các phần tử lược đồ một cách chính xác và hiệu quả nhất có thể. Tiếp theo chúng tôi chỉ ra cách tạo ra các ánh xạ trực tiếp lẫn gián tiếp dựa trên các phép đo độ tương đồng này. Cuối cùng, chúng tôi đánh giá giải pháp đã đưa ra dựa trên một tập dữ liệu thực tế được cung cấp trong [5]. Quá trình đánh giá bao gồm hai phần: thứ nhất là đánh giá giải pháp theo các phép đo chất lượng đối sánh và thứ hai là so sánh giải pháp với hai hệ thống điển hình hiện này là Cupid và SF. Cuối cùng, để đưa ra một áp dụng cho giải pháp đã mô tả, trong phần cuối chương này chúng tôi sẽ xem xét vấn đề chuyển đổi tài liệu có cấu trúc, một trong những lĩnh vực ứng dụng điển hình của đối sánh lược đồ XML. Ngoài việc tổng hợp lại các nghiên cứu liên quan về vấn đề này, chúng tôi cũng đề xuất một mô hình cho hệ thống chuyển đổi tự động tài liệu XML. Chương 3: Đố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 48 3.1 Tổng quan về đối sánh tự động lược đồ XML Để đối sánh lược đồ, về cơ bản ta cần tính toán độ tương đồng giữa các phần tử lược đồ. Để tính toán độ tương đồng phần tử, các tiếp cận đối sánh lược đồ hiện nay thường kết hợp nhiều phương pháp đối sánh khác nhau. Một trong những tiếp cận đáng chú ý là giải pháp được đưa ra trong [22], trong đó các tác giả đã áp dụng đối sánh lược đồ cho vấn đề chuyển đổi tài liệu có cấu trúc. Dựa trên các nghiên cứu này, chúng tôi đưa ra một tiến trình tính toán độ tương đồng phần tử như mô tả trong hình 3.1. Chúng tôi sử dụng các tiêu chuẩn đối sánh cơ bản sau: đối sánh thuật ngữ, xét tính tương thích kiểu dữ liệu và đối sánh cấu trúc. Sau đây là các bước cơ bản trong tiến trình này: - Đo độ tương đồng ngôn ngữ: pha này tính toán độ tương đồng giữa các nút lược đồ nguồn và đích dựa trên độ tương đồng nhãn có sử dụng WordNet. Pha này có đầu vào là các nhãn trong hai đồ thị lược đồ và đưa ra một ma trận độ tương đồng ngôn ngữ (trong phạm vi [0, 1]) giữa các nút nguồn và đích. - Xét tính tương thích kiểu dữ liệu: pha này tính toán độ tương đồng giữa các nút nguồn và đích dựa trên các ràng buộc của chúng. Ở đây chúng tôi chỉ xét các nút nguyên tố được xem là tương đồng trong pha đối sánh thuật ngữ. Trong pha này chúng tôi sử dụng phân cấp kiểu nội tại của lược đồ XML [27] và các ràng buộc miền trên các nút nguyên tố nguồn và đích để cập nhật cho phép đo độ tương đồng thuật ngữ. - Đo độ tương đồng cấu trúc: pha này tính toán độ tương đồng của các nút lược đồ nguồn và đích sử dụng các đặc điểm cấu trúc của chúng dựa trên khái niệm ngữ cảnh nút. Chúng tôi thực hiện đối sánh cấu trúc theo hai bước. Bước đầu tiên là gán cho mỗi nút trong lược đồ nguồn và đích một ngữ cảnh. Tiếp theo chúng tôi so sánh các ngữ cảnh này để đưa ra một hệ số tương đồng nút phản ánh sự tương đồng cấu trúc giữa hai nút lược đồ. Bước thứ hai chúng tôi sử dụng độ tương đồng nút đã có để đưa ra tập các phần tử ánh xạ phức Chương 3: Đố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 49 hợp và trực tiếp. Trong bước này, chúng tôi cũng xác nhận tính hợp lệ của các ánh xạ phức hợp đã tạo ra trong pha phân tích phân cấp kiểu người thiết kế. Hình 3. 1 Tiến trình tính toán độ tương đồng phần tử 3.2 Đo độ tương đồng ngôn ngữ Mục đích của pha này là tính toán độ tương đồng giữa các nút lược đồ dựa trên độ tương đồng nhãn của chúng. Để thực hiện đối sánh ngôn ngữ, chúng tôi xem xét ý nghĩa của tên phần tử và thiết lập các quan hệ ngữ nghĩa giữa chúng dựa trên WordNet, một CSDL từ vựng điện tử cho các từ tiếng Anh [14]. 3.2.1 WordNet và quan hệ ngữ nghĩa giữa các từ WordNet phân biệt các quan hệ ngữ nghĩa khái niệm mà liên kết các khái niệm và các quan hệ từ vựng liên kết các từ riêng lẻ. Về cơ bản chúng tôi chỉ xét các quan hệ ngữ nghĩa khái niệm. Trong WordNet thông tin từ vựng được tổ chức dưới dạng ý nghĩa từ hơn là hình thái từ. Ý nghĩa từ được xem xét qua Ma trận độ tương đồng ngôn ngữ Đo độ tương đồng ngôn ngữ Xét tính tương thích kiểu dữ liệu Đo độ tương đồng ngữ cảnh nút Đồ thị lược đồ Ngữ cảnh tổ tiên Ma trận độ tương đồng ngôn ngữ đã hiệu chỉnh Đo độ tương đồng nút Ma trận độ tương đồng phần tử Ngữ cảnh con Ngữ cảnh lá Chương 3: Đố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 50 khái niệm synset (synonym set - tập các từ đồng nghĩa). Trong WordNet một hình thái từ có thể được kết hợp với nhiều synset, mỗi synset tương ứng với một nghĩa khác nhau của từ. WordNet được tổ chức theo các quan hệ ngữ nghĩa. Bởi vì một quan hệ ngữ nghĩa là một quan hệ giữa các ý nghĩa, và bởi vì ý nghĩa có thể được biểu diễn bằng các synset, một cách tự nhiên có thể coi các quan hệ ngữ nghĩa như là các con trỏ giữa các synset. WordNet sử dụng nhiều quan hệ ngữ nghĩa khác nhau như đồng nghĩa/trái nghĩa hay tổng quát/đặc biệt. Các liên kết WordNet có thể có ba hướng: lên, xuống và ngang. Hướng lên tương ứng với sự tổng quát hóa của ngữ cảnh (kết nối nhiều khái niệm riêng biệt thành một một khái niệm tổng quát hơn). Liên kết xuống tương ứng với sự chi tiết hóa của ngữ cảnh. Liên kết ngang là các chi tiết hóa rất cụ thể và ít xảy ra hơn các liên kết lên và xuống. Bảng C.1 trong phụ lục C cho ta ví dụ về các liên kết này. 3.2.2 Thuật toán của Hirst và St-Onge Hầu hết các thuật toán đối sánh lược đồ đều sử dụng WordNet để đối sánh ngôn ngữ, nhưng thường ít cho ta thấy cách họ khai thác WordNet như thế nào. Budanisky và Hirst đã đưa ra một khảo sát về các thuật toán này, bao gồm các thuật toán của Hirst và St-Onge, thuật toán của Leacock và Chodorow, thuật toán của Jiang và Conrath, thuật toán của Resnik và thuật toán của Lin [2]. Dựa trên kết quả thực nghiệm, có thể thấy thuật toán của Jiang và Conrath đưa ra độ tương đồng ngôn ngữ với độ chính xác cao nhất. Rất tiếc các tác giả lại không cho biết cách làm của họ. Trong luận văn này về cơ bản chúng tôi dựa trên nghiên cứu về thuật toán của Hirst và St-Onge [7]. Khi tìm kiếm quan hệ giữa hai từ, mỗi synset của từ đầu tiên phải được xem xét cùng với mỗi synset của từ thứ hai, sau đó tìm kiếm một kết nối có thể giữa một số synset của từ thứ nhất và một số synset của từ thứ hai. Chương 3: Đố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 51 Hirst và St-Onge đưa ra ba mức quan hệ: rất mạnh, mạnh) và trung bình. Quan hệ rất mạnh tương ứng với sự lặp lại từ (ví dụ author và authors, foot và feet). Các quan hệ rất mạnh có trọng số cao. Hai từ có quan hệ mạnh nếu tồn tại một liên kết ngang giữa các synset của chúng. Trong luận văn này, chúng tôi giới hạn quan hệ mạnh trong các tiêu chí sau: - Có một synset chung cho hai từ. - Có một liên kết ngang giữa các synset của mỗi từ. - Một trong các từ là một từ ghép và từ kia là một phần của từ ghép, và có thể có bất kỳ loại liên kết nào giữa các synset liên kết mỗi từ. Quan hệ mạnh có trọng số thấp hơn quan hệ rất mạnh. Không giống như các quan hệ rất mạnh và mạnh, quan hệ trung bình có các trọng số khác nhau phụ thuộc vào đường dẫn hiện có giữa các cặp synset. Ý tưởng của Hirst và St-Onge trong việc đo độ quan hệ ngữ nghĩa đó là hai khái niệm là gần gũi về ngữ nghĩa nếu các synset của chúng được kết nối bởi một đường dẫn không quá dài và không thay đổi hướng quá thường xuyên. Họ cũng định nghĩa một tập các đường dẫn được phép như sau: một đường dẫn được xem là được phép nếu các liên kết tạo ra đường dẫn tuân theo ba điều kiện sau: - Không có một hướng khác trước một liên kết lên (một khi ngữ cảnh được đặc biệt hóa sử dụng một liên kết xuống hoặc ngang, không được mở rộng ngữ cảnh sử dụng một liên kết lên). - Không có nhiều hơn một thay đổi về hướng được phép (các thay đổi hướng tạo thành các thay đổi ngữ nghĩa trong ngữ cảnh và do đó phải bị giới hạn). Luật này có một ngoại lệ theo nghĩa một hướng ngang có thể được sử dụng để tạo sự chuyển tiếp từ một hướng lên thành một hướng xuống. - Độ dài đường dẫn được giới hạn trong một ngưỡng nào đó (nhìn chung được lấy bằng bốn hoặc năm). Chương 3: Đố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 52 Hình C.1 trong phụ lục C minh họa các ví dụ về đường dẫn được phép. Để tính toán trọng số của quan hệ trung bình, đầu tiên chúng tôi nhận dạng đường dẫn ngắn nhất giữa một cặp các synset. Nếu đường dẫn là không được phép, thì trọng số gán cho quan hệ là NULL (tức là không có quan hệ). Trong trường hợp khác, trọng số của đường dẫn và do đó độ tương đồng ngôn ngữ được cho bởi công thức sau: c – độ dài đường dẫn – k × số lần thay đổi hướng Trong đó c và k là các hằng số với c = 8 và k = 1. Việc lựa chọn c và k là từ thực nghiệm dựa trên các ví dụ đã cung cấp trong [2] trong đó các tác giả so sánh một vài thuật toán đo khoảng cách ngữ nghĩa. Bằng cách chuẩn hóa phép đo này, ta nhận được một hệ số ngôn ngữ lsim, có phạm vi giữa [0, 1], trong đó 0 có nghĩa là không có quan hệ ngữ nghĩa tồn tại giữa hai từ và 1 có nghĩa là giữa các từ rất tương đồng. Mô tả chi tiết về thuật toán của Hirst và St-Onge có thể xem trong phụ lục C. Hình C.2 trong phụ lục C minh họa các loại quan hệ ngữ nghĩa sử dụng trong thuật toán này. Có thể sử dụng thuật toán tương tự cho tên kiểu. Để đơn giản hóa vấn đề, trong luận văn này chúng tôi giả thiết rằng các nút có cùng tên như kiểu của chúng. 3.2.3 Giải pháp của hệ thống Cupid Trong phần trên, chúng tôi đã sử dụng WordNet làm nguồn từ vựng nhằm so sánh tên các phần tử theo thuật toán của Hirst và St-Onge. Tuy nhiên, trong thực tế các phần tử lược đồ thường có tên khác nhau do sử dụng từ viết tắt, từ rút gọn, dấu chấm câu… Do đó, môđun xử lý độ tương đồng ngôn ngữ cần phải giải quyết được vấn đề này. Trong [11] các tác giả đã đề xuất một bước chuẩn hóa để giải quyết vấn đề này. Đầu tiên họ thực hiện bước phân tích tên thành các token sử dụng dấu Chương 3: Đố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 53 chấm câu, chữ hoa..., tiếp theo là họ chỉ ra từ viết tắt, từ rút gọn và cuối cùng là loại bỏ giới từ, mạo từ, v.v... Trong mỗi bước này, họ sử dụng một từ điển chuyên đề bao gồm cả ngôn ngữ chung lẫn các tham chiếu riêng cho lĩnh vực. Về cơ bản, giải pháp của chúng tôi sử dụng ý tưởng này. Sau bước chuẩn hóa, hệ thống Cupid còn thực hiện tiếp các bước như phân chia các từ thành danh mục (nhằm giảm bớt các ứng viên đối sánh, tăng tốc độ cho pha đối sánh) và thực hiện đối sánh ngôn ngữ bằng cách sử dụng các phương pháp đối sánh xâu. Thay vì vậy, trong giải pháp của chúng tôi, tiến trình đối sánh được thực hiện nhờ sử dụng thuật toán của Hirst và St-Onge đã mô tả ở trên. Tuy vậy, cho dù dùng phương pháp nào đi nữa, đối sánh ngôn ngữ vẫn có thể cho kết quả tương đồng cao ngay cả khi các nút không có sự tương ứng ngữ nghĩa với nhau, do đó cần phải có phương pháp hiệu chỉnh sai lệch này. Sau đây ta sẽ nêu các phương pháp đối sánh này. 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 Để hiệu chỉnh bước đầu kết quả thu được từ pha đối sánh ngôn ngữ, các tiếp cận hiện nay thường xem xét thêm các ràng buộc lược đồ. Một trong những giải pháp thông dụng nhất là xét tính tương thích kiểu dữ liệu. Các khuyến nghị lược đồ XML cung cấp khá nhiều kiểu dữ liệu nội tại và biểu thức chính quy khác nhau [27], vì vậy có thể sử dụng các thông tin này để xây dựng một bảng hệ số tương thích giữa các kiểu dữ liệu, kí hiệu là dsim. Các kiểu dữ liệu lược đồ XML được phân thành nhiều danh mục (gọi là các kiểu dữ liệu nguyên thủy) chẳng hạn như Duration, Boolean, String, Decimal, v.v.. Mỗi danh mục có một vài kiểu dữ liệu dẫn xuất (chẳng hạn integer là kiểu dữ liệu dẫn xuất từ Decimal, và long là kiểu dữ liệu dẫn xuất từ integer). Hai Chương 3: Đố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 54 kiểu dữ liệu được xem là tương đồng nhau nếu chúng thuộc cùng danh mục kiểu dữ liệu, và sự tương thích kiểu dữ liệu của chúng phụ thuộc vào vị trí tương ứng của chúng trong phân cấp kiểu dữ liệu lược đồ XML. Dựa trên phân cấp kiểu dữ liệu lược đồ XML ta sẽ xây dựng một bảng tương thích kiểu dữ liệu cho biết hệ số tương tự giữa hai kiểu dữ liệu đã cho (như một bảng đã được xây dựng trong [11]). Ví dụ hệ số dsim giữa các kiểu int và short bằng 0,8 (do kiểu short được dẫn xuất từ kiểu int). Độ tương thích kiểu dữ liệu thường được định nghĩa cho các nút nguyên tố để đo độ tương đồng giữa các r