臺灣博碩士論文加值系統

供應鏈環境中的企業要能夠相互溝通，重點在於商業交易資料能相互傳遞與解譯。在傳遞資料的方面，XML已成為大部分企業採用的資料交換格式。在定義資料格式方面，每個企業所使用的產業資料交換標準可能不一樣，所以在相互解譯資料時常會有不能解讀或誤判的情況發生，可稱之為資料交換的綱要衝突問題。針對此問題，常見的解決方法有語意對應以及結構對應兩種，若單獨只考慮語意對應或結構對應可能無法解決一對多或多對一的配對情形，因而造成無法正確判定所對應的結果。
本研究提出結合語意對應與結構對應的混合式演算法－改良型SF(Similarity Flooding)演算法來解決商業交易資料交換的一對一綱要衝突問題，期望在供應鏈環境中的商業交易資料能快速且正確的對應。SF演算法原型在結構對應過程分為四個階段，第一階段以OEM結構表達需要配對的兩個綱要，第二階段將兩個綱要的OEM圖形結合成所有可能配對的連接圖形(Pairwise Connecting Graph, PCG)進行結構圖形的重組，第三階段開始進行結構相似度的計算，第四階段則是將結構對應結果放入篩選機制中，找出最可能的配對提供使用者參考並做出最後判斷。改良型 SF演算法主要針對第二階段的過程進行改善，在結合OEM圖形的過程中參考語意對應相關的資訊，排除較為不可能的配對，達到簡化PCG圖形結構的效果。
改良型SF演算法利用多種機制有效的解決因為語意對應所產生的一對多與多對一的綱要衝突問題，得到較佳的演算效率及配對正確性。在演算法運算時間方面，由於簡化了PCG圖形的結構，因此改良型SF演算法所花費的處理時間也比SF原型演算法來的短。在配對正確性方面，利用對應品質指標Recall及Precision來計算個別演算法的績效，透過結合語意對應與結構對應兩種對應方式，再以二次對應輔助的結果，在多數情況下改良型SF演算法比SF演算法原型有較好的對應品質。

關鍵詞：資料交換、綱要對應、語意相似度、結構相似度。

Data exchange between companies in a supply chain environment needs to fulfill the requirements of common data format and data representation to assure the accuracy of communication. XML has recently emerged as a common data format for cross-platform information exchange over the Internet. Since information systems are developed independently, identical data represented with different schemas in each system is a common state; therefore information systems may not understand the true meaning of exchanged data. This kind of communication problem is named as schema conflict. The core technique for solving schema conflict in data exchange is correctly matching imported XML documents into internal relational database schemas.
There are two major methods in schema matching: linguistic matching and structural matching. From previous research results, only one single method can not effectively solve linguistic matching problems in one-to-many and many-to-one cases. Similarity flooding (SF) originally is a purely structure-oriented algorithm based on the propagation graph, pairwise connecting graph (PCG), and fixpoint computation to detect similar schema structure. A modified similarity flooding method using linguistic similarity values to simplify the PCG is proposed to improve the effectiveness of schema matching.
With a simplified data structure in the PCG, this hybrid method can reduce the computation effort in matching schemas. Based on the experimental results, in most cases this method increases matching accuracy with less computing time compared to the original SF method. The major factor could be only linguistically qualified candidates are included in the PCG, and this modification may increase the matching ability of the proposed method.

Keywords: data exchange, schema matching, similarity flooding, XML.

目錄
摘要 I
Abstract II
致謝 III
目錄 IV
圖目錄 VI
表目錄 VIII
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 1
1.3 研究目的 3
第二章 文獻探討 4
2.1 資料庫的異質性 4
2.2 將XML應用於資料交換 5
2.2.1 DTD與Schema 6
2.3 語意衝突與綱要對應 9
2.4 綱要對應方法 13
2.4.1 綱要對應方法分類 13
2.4.2 目前綱要對應方法 14
2.5 WordNet與其技術 15
2.5.1 WordNet 16
2.5.2 語彙鍵結(Lexical Chain) 17
2.5.3 語意密度(Semantic Density) 21
2.6 相似度的量測 23
2.6.1 語意對應與相似度的量測 23
2.6.2 空間向量的相似度測量 24
2.7 半結構化資料(Semi-Structured Data, SSD) 25
2.7.1 OEM圖形 26
2.8 XML 與Semi-Structure Data 27
2.9 SF( Similarity Flooding ) 演算法 29
2.9.1 資料模型的轉換 29
2.9.2 SF演算法中的語意相似度 30
2.9.3 PCG (Pairwise Connectivity Graphic) 圖形的組合 30
2.9.4 利用Fixpoint Computation計算結構相似度 31
2.9.5 相似度指派 32
2.10 對應品質衡量指標Recall與Precision 32
第三章 混和式綱要對應演算法-改良型SF演算法 34
3.1演算法的基本假設 34
3.2 演算法流程及運行介面 34
3.3 資料模型的轉換 36
3.4 改良型SF演算法中的語意相似度 40
3.4.1 完全比對 40
3.4.2 單一字語意對應 40
3.4.3 複合字語意對應 41
3.5 結構對應 42
3.6 結構對應融合語意對應簡化結構 43
3.7 相似度的指派 44
3.8 二次對應 47
3.9 演算法的限制 48
第四章 改良型SF演算法與範例驗證 49
4.1 改良型SF演算法實做介紹 49
4.1.1 改良型演算法架構與運行介面 49
4.1.2 相關軟體與工具 51
4.2 範例實做 52
4.2.1 範例一 52
4.2.2 範例二 55
4.2.3 範例三 58
4.2.4 範例四 62
4.2.5 範例五 66
4.6範例實做討論 70
4.6.1 範例結果分析 70
4.6.2 對應品質與時間 71
第五章 結論與未來建議 73
5.1 結論 73
5.2 未來建議 74
參考文獻 75
附錄 78


圖目錄
圖2- 1、XML Schema與DTD資料型別差異 (Birbeck & Duckeet [2]) 7
圖2- 2、以區段為基礎的對應策略 (Erhard & Hong-Hai [11]) 8
圖2- 3、System gross architecture (Erhard & Hong-Hai [11]) 8
圖2- 4、Schema與Data衝突分類定義 (Kim & Seo [7]) 10
圖2- 5、ㄧ對一對應關係 11
圖2- 6、一對多對應關係 12
圖2- 7、多對一對應關係 12
圖2- 8、多對多對應關係 13
圖2- 9、綱要對應方法分類圖 14
圖2- 10、car在WordNet中定義的五種語意 16
圖2- 11、名詞“car”的語意關係[1] 17
圖2- 12、考慮Mr.及person所產生的不同語彙鏈結組合 19
圖2- 13、Mr., person及machine所產生的不同語彙鏈結組合 20
圖2- 14、語彙鏈結的第一種可能建構結果 21
圖2- 15、語彙鏈結的第二種可能建構結果 21
圖2- 16、半結構化資料表示法[15] 26
圖2- 17、OEM圖形範例[3] 27
圖2- 18、顯示XML及SSD的差異[15]。 28
圖2- 19、關連式資料庫資料表綱要[18] 29
圖2- 20、OEM圖形[18] 30
圖2- 21、SF範例[18] 30
圖2- 22、SF範例[18] 31
圖2- 23、stable marriage 32
圖2- 24、Precision與Recall示意圖 33
圖3-1、演算法運行流程 35
圖3- 2、XML綱要–Microsoft規範 36
圖3- 3、XML Schema樹形圖 36
圖3- 4、來源Schema OEM/Lore圖形 37
圖3- 5、目標Schema OEM/Lore圖形 37
圖3- 6、來源Schema XML/DOM圖形 38
圖3- 7、目標Schema XML/DOM圖形 39
圖3- 8、語意對應流程 40
圖3- 9、語意對應結果 42
圖3- 10、SF對應結果 43
圖3- 11、XML Schema –W3C規範 45
圖4- 1、實踐改良型SF演算法架構 49
圖4- 2、輸入欲比對來源與目標綱要名稱 50
圖4- 3、來源綱要轉換成OEM 50
圖4- 4、目標綱要轉換成OEM 50
圖4- 5、演算法建議配對結果 51
圖4- 6、範例一來源綱要 52
圖4- 7、範例一目標綱要 52
圖4- 8、範例一XML 綱要的樹形圖 53
圖4- 9、範例一演算法建議配對結果 53
圖4- 10、範例二來源綱要 55
圖4- 11、範例二目標綱要 56
圖4- 12、範例二XML 綱要的樹形圖 56
圖4- 13、範例二演算法建議配對結果 57
圖4- 14、範例三來源綱要 58
圖4- 15、範例三目標綱要 59
圖4- 16、範例三XML綱要的樹形圖 59
圖4- 17、範例三演算法建議配對結果 60
圖4- 18、範例四來源綱要 62
圖4- 19、範例四目標綱要 63
圖4- 20、範例四XML綱要的樹形圖 63
圖4- 21、範例四演算法建議配對結果 64
圖4- 22、範例五來源綱要 66
圖4- 23、範例五目標綱要 67
圖4- 24、範例五XML綱要的樹形圖 67
圖4- 25、範例五演算法建議配對結果 68


表目錄
表2- 1、綱要對應方法分類 14
表2- 2、相似度量測比較表 24
表2- 3、文件與關鍵字矩陣型態表 25
表3- 1、圖形建構法則的差異 39
表3- 2、不同資料模型間的數據比較 40
表3- 3、結構相似度計算結果 46
表3- 4、規劃求解結果 46
表4- 1、範例一理想配對 53
表4- 2、範例一理想配對與演算法對應結果 54
表4- 3、範例一演算法相關數據 54
表4- 4、範例二理想配對 56
表4- 5、範例二理想配對與演算法對應結果 57
表4- 6、範例二演算法相關數據 57
表4- 7、範例三理想配對結果 60
表4- 8、範例三理想配對與演算法對應結果 60
表4- 9、範例三演算法相關數據 61
表4- 10、範例四理想配對結果 64
表4- 11、範例四理想配對與演算法對應結果 64
表4- 12、範例四演算法相關數據 65
表4- 13、範例五理想配對結果 68
表4- 14、範例五理想配對與演算法對應結果 68
表4- 15、範例五演算法相關數據 69

參考文獻
[1].A. Suarez, M. Noeda and M. Palomar, “A Method of Restricted Knowledge Acquisition from WordNet,” Proceeding of the 3rd International Conference on Knowledge-Based Intelligent Information Engineering System, IEEE, pp.38-41,1999.
[2].Birbeck, Mark., & Duckeet, J. (2001). PROFESSIONAL XML 2nd Edition.UK. Wrox.
[3].Ekaterina Pavlova, Igor Nekrestyanov, Boris Novikov,”Constraints for Semistructured Data”.
[4].G.A. Miller, “WordNet: An On-line Lexical Database,” International Journal of Lexicography, vol. 3, no. 4, pp.235-312, 1990.
[5].Hong-Hai Do, Erhard Rahm, ”COMA - A system for flexible combination of schema matching approaches” , Proceedings of the 28th VLDB Conference, Hong Kong, China, 2002
[6].Jayant Madhavan, Philip A. Bernstein & Erhard Rahm. (2001). Generic Schema Matching with Cupid.
[7].Kim, Won. & Seo, Jungyun. (1991). Classifying Schematic and Data Heterogeneity in Multidatabase. IEEE COMPUTER, 12-18.
[8].Lear, A.C. (1999). XML seen as integral to application integration. IT Pro, 12-16.
[9].Lee, Chiang., Chen, Cgia-Juan., & Lu, Hongjun. (1995). An aspect of query optimization in multidatabase systems. ACM SIGMOD RECORD, 24(3), 28-33.
[10].Rahm, Erhard., & Bernstein, Philip. (2001). A survey of approaches to automatic schema matching. The VLDB Journal, 10, 334-350
[11].Rahm, Erhard., & Do, Hong-Hai. Matching Large XML Schemas. SIGMOD Record, 33(4), 26-31.
[12].R. Barzilay and M. Elhadad, “Using Lexical Chains for Text Summarization,”ACL/EACL Workshop on Intelligent Scalable Text Summarization, 1997.
[13].R. Mihalcea and D.I. Moldovan, “Word Sense Disambiguation Based on Semantic Density,” Use of WordNet in National Language Processing Systems:Proceedings of the Conference, 1999.
[14].RosettaNet Taiwan URL: http://www.rosettanettaiwan.org.tw/
[15].Serge Abiteboul, Peter Buneman & Dan Suciu, Data On the Web From Relation to Semistructured Data and XML, Morgan Kaufmann Publishers, San Francisco (2000).
[16].Serge Abiteboul.”Querying semistructured data” Proc. Of the Int. Conf. On Database Theory(ICDT), Delphi,Greece, 1997
[17].Sheth, Amit., & Larson, J. (1990). Federated database systems for managing distributed, heterogeneous, and autonomous databases. ACM Computing Surveys, 22( 3), 183-236.
[18].S. Melnik, H. Gracia-Molina, E. Rahm, “Similarity Flooding: A Versatile Graph Matching Algorithm,” ICDE (2002).
[19].Tseng, Frank S.C., Chiang, Jeng-Jye., & Yang, Wei-Pang. (1998). Integration of relations with conflicting schema structures in heterogeneous database systems. Data & Knowledge Engineering, 27, 231-248.
[20].Yen, David C., Huang, Shi-Ming., & Ku, Cheng-Yuan. (2002). The impact and implementation of XML on business-to-business commerce. Computer Standards & Interfaces, 24, 347-362.
[21].曾守正，資料庫系統之理論與實務，華泰文化 (2004)。
[22].陳莉君、柯皓仁、楊維邦，「線上個人化參考文獻管理系統」，(2003)
[23].何明營、項衛中，「運用XML 相關技術強化供應鏈中異質性資料交換的效能」，(2004)。
[24].劉冠宏、項衛中，「運用校正距離計算結構相似度增進資料交換中綱要對應正確性」，(2005)。
[25].羅淑娟、柯秀奎，「文字探勘—應用Raz & Yaung 方法論於文件自動分群」，(2004)。
[26].羅莉鈁、簡永仁，「原生型XML 資料庫系統之研究及應用--以學校法規查詢系統為例」，(2004)。