An XML Schema Similarity Evaluation Method Based on Structural and Semantic Relationships

With the rapid development of Internet applications, XML has become a standard for data interchange over the Internet. As a result, many documents are stored in XML format. Some of these XML documents are specified by XML schemas. However, XML schemas representing same or similar objects may be designed differently by different developers. If we need to integrate those documents representing similar objects, the first thing should be done is schema matching. The performance of schema matching highly depends on the efficacy of evaluating XML schema similarity. In this thesis, we proposed an effective algorithm called HSim (Holistic Similarity) to compute XML schema similarity by considering element and structural similarities together. For the evaluation of element similarity, we consider two approaches. First, we develop an evaluation method based on WordNet lexical database for semantic similarities of element names. Second, we develop another method for evaluating data type similarities. For the evaluation of structural similarity, we consider the sub-tree similarity with backward paths taken into consideration. From the experimental results, the F-measure of the proposed HSim algorithm is about 7% to 87% higher than all context method of COMA 3.0 in the purchase order dataset. Besides, HSim outperformed other methods in COMA 3.0.在現今網際網路快速發展下，許多數位化文件資料多以 XML 文件方式儲存或交換，其中，有些文件是以 XML 綱要(XML Schema)定義這些 XML 文件的格式。然而，XML 綱要的設計，卻常因人而異，以致有些相同性質的文件卻具有不同的 XML 綱要，若要整合這些相似性質的文件勢必需進行 XML 綱要的整合工作。整合相似性質之 XML 綱要，常見的方法為 Schema matching，其結果的好壞取決於如何有效地評估兩個 XML 綱要之相似度。以前的研究在評估相似度方面，主要是考慮元素相似度(Element similarity)或者結構相似度(Structure similarity)。有部分研究同時考慮結構與元素關係，但因仍缺少部分因素考量，致使比對精準度不佳。本論文提出一個整體相似度(Holistic Similarity, HSim)演算法，結合元素與結構相似度評估方法，能更精確計算 XML 綱要相似度。在元素相似度方面，本論文考量以下兩點，一為基於WordNet 詞彙庫，發展元素在名稱上之語義相似度評估方法，其二為資料型別(Data type similarity)相似度 在結構相似度方面 將輸入之 XML 綱要轉化成 XML。樹，並且考量子樹結構之相似度。經由實驗結果證實，本論文方法 HSim 在資料集 Purchase Order 相似度評估上優於 COMA 3.0 All context 方法7%~87%(F-measure)，另外與 COMA3.0 其他方法作比較，本論文方法 HSim 相似度評估亦較佳。誌謝.......................... i 摘要....................ii Abstract ............................... iii 目錄........................... iv 表目錄............................. v 圖目錄.............................. vi 第一章緒論.............................................. 1 1.1 研究背景與動機.............................. 1 1.2 研究目的.................................. 3 1.3 主要貢獻................................. 4 1.4 論文架構................................ 5 第二章相關研究.................................... 6 2.1 基於語義相似度之演算法.................... 6 2.2 基於結構相似度之演算法.................... 12 2.3 基於建置 mediated schema 之演算法 .................................................... 17 第三章系統架構與演算法.......................... 19 3.1 系統架構................................. 19 3.2 評估語義相似度............................. 21 3.3 評估結構相似度............................. 29 3.4 評估節點相似度........................... 42 第四章系統實作與實驗結果...................... 45 4.1 開發工具與實驗環境................... 45 4.2 測試資料集............................... 46 4.3 分析與討論................................ 48 第五章結論與未來研究方向....................... 53 5.1 結論........................................ 53 5.2 未來研究方向............................... 55 參考文獻................................ 5