XML纲要自动映对技术之研究

XML 綱要自動映對技術之研究 /趙景明 蕭貞貞 95 XML 綱要自動映對技術之研究綱要自動映對技術之研究 趙景明 東吳大學資訊科學系 .tw 蕭貞貞 東吳大學資訊科學系 .tw 摘要摘要 綱要映對是指將個綱要的元素做語意和結構上的對應，是綱要整合的重要工作， 綱要映對在資庫相關域應用非常廣泛，如：資整合、電子商務、語意查詢處 等。以前大部份的綱要映對研究偏重在關式的資模式上，較少對 XML 文件做處。 近順應全球資訊網的發展，愈愈多研究偏重在 XML 文件以及 XML 綱要 DTD 的 轉換和映對上，但以 XML Schema 做映對的研究仍屬少。而且大部份的綱要映對研究 是半自動產生映對，需要部份人工輔助。因此，本研究探討 XML 綱要映對的相關方 法及問題，並以綱要映對為基礎，提出一個 XML Schema 的自動綱要映對架構，藉由 XML Schema 豐富的內容及混合的比對方法，確的比對出綱要之間的映對關係。 關鍵字：關鍵字：XML 綱要、綱要映對、綱要整合。 訊管展望 第 9 卷 第 1 期 民國 96 6 月 96 Automatic Mapping of XML Schema Ching-Ming Chao Dept. of Computer XML Schema tutorial, 2003)，首先擷取檔案型態為 xsd 且檔名 相似的資，如：books.xsd 和 publication.xsd，以避免需要的資擷取太多，下載 後，檢查所擷取的資，刪除內容完全相同及為英文的檔案，並修正有語法錯誤及 碼的資，另外，元素名稱為分大小寫也沒有區隔的組合字，如：bookname，目 前的映對規則無法斷字，所以會將其修正為 bookName 或 book_name 等可拆解的字，以 映對。蒐集的資包含三個域：訂單資、書籍資、員工資，共有 143 份，資 特性如表 6 所示。其中書籍資與目的綱要差最低，因可描述書籍的項目較有限 也固定，有些資甚至只有結構和限制條件的差；員工資差程最高，因與人相 關的資範圍廣泛，描述方式也較為複雜，甚至同樣取得二份名為 person.xsd 檔，資 內容可能只有 firstname 和 lastname 二個元素相似。 圖 10 目的綱要：publication_sample.xsd 表 6. 實驗資 XML Schema 的特性 資型 綱要 節點 階層 與目的綱要元素差 訂單資 28 5286 39 中 書籍資 68 6189 39 低 員工資 47 9296 515 高 三、實驗結果與分析三、實驗結果與分析 本實驗分為二部份，將所有資剖析存入資庫後，首先將各域資逐一與其目 的綱要做映對，藉以測試對同域綱要的敏感，並將實驗門檻值分別設定為 0.6、0.7， 以檢驗門檻值差的變化，產生結果如表 7、表 8 所示。再將所有資做交叉驗證，每 份資與三份目的綱要做一次映對，藉以驗證同域的綱要是否可以區分出，並 設定實驗門檻值為 0.6，產生結果如表 9 所示。實驗結果明如下： XML 綱要自動映對技術之研究 /趙景明 蕭貞貞 113 表 7. 門檻值為 0.6 的映對結果 資型 比對基礎 綱要 映對 失敗 映對 訂單資 Order_sample.xsd 28 18 10 64% 書籍資 Publication_sample.xsd 68 51 17 75% 員工資 Person_sample.xsd 47 25 22 53% 表 8. 門檻值為 0.7 的映對結果 資型 比對基礎 綱要 映對 失敗 映對 訂單資 Order_sample.xsd 28 8 20 29% 書籍資 Publication_sample.xsd 68 39 29 57% 員工資 Person_sample.xsd 47 14 33 30% 表 9. 門檻值為 0.6 的交叉驗證結果 比對基礎 訂單資 書籍資 員工資 總 Order_sample.xsd 18 0 4 22 Publication_sample.xsd 1 51 0 52 Person_sample.xsd 3 2 25 30 (1) 同結構相同元素名稱大致可區分出，如：Customer.Product.Name 和 Publicaion.Author 在元素比對時相似為 1，但經過結構比對後，相似為 0.576。 (2) 元素語意透過 WordNet 的協助大致可正確辨別。用大小寫及底線區隔組合字的元 素，也大致可正確判斷，但組合字判斷，由於是拆開分別比對，即使人工辨別為同義 詞，也一定能得到 0.9 以上的係，計算出的元素相似會比人工辨別稍微低一些。 (3) 元素的名稱是影響元素相似的最重要因素，難以辨別的元素名稱會影響語意分 析。有些元素只取前幾個字母，如：pub_date，或只取發音字母，如：btn (button)， 做成組合字，還有些元素在元素名稱前加上專案名稱縮寫等特殊意義的縮寫字，這些 情況會造成無法正確判斷元素的語意。另外還有一種情況，元素名稱之間沒有語 意關係，卻有相同概，也會造成判斷時的誤差，如：BookName 和 Title。由此可 知，可以處越多的元素名稱變化，就可以提高元素層級的映對。 (4) 元素的限制條件、資格式等，只要綱要內有定義，大致可正常判斷。但是許多綱 要得會定義的很詳細，充分的定義則會產出較多的映對。 (5) 綱要結構的映對，管是巢結構或考結構大致能正確辨別，也能清楚找出階 層關係，做子樹的比對。但由於結構映對建在元素的語意映對上，判別結構關係的 同時也會受語意相似的影響。 (6) 同域的綱要，有少幾個通用元素，如：name、title、address 等，又位於 較有影響的結構位置，則會提高映對係，使得相同的綱要映對成功。 (7) 訂單資和書籍資，由於部份綱要包含較多的人員資，如：訂單資內的客 戶資訊、書籍資內的作者或出版商資訊，在判斷時容造成混淆。而員工資無法 全部映對除綱要混雜其它資訊，如：resume 以外，員工資包含的元素種太 多，命名方式較多元，元素差太大，也是主要的原因。 (一) 節點與映對結果 研究綱要的節點介於 5296 個之間，由於每個節點在元素層級映對階段，必 訊管展望 第 9 卷 第 1 期 民國 96 6 月 114 須互相比較相似，節點越多，產生的相似矩陣越大，需要的儲存空間較大，演算時 間也會較久，尤其在找出字詞的相關詞性時，但並影響元素相似的評估。在結構層 級映對上，在同階層內，節點的多寡，在判斷兄弟節點相似時會有些微影響， 如：A 節點有 5 個兄弟節點，而 B 節點有 10 個兄弟節點，則最多只會有 5 個節點是相 似的，遇到這種情況，在兄弟節點的相似計算時會做加權處，影響較小。如果考慮 到同階層的因素，則影響會比同階層稍微多一些，因為每個內部節點的相似，必須 考慮其子節點的相似，所以當二個內部節點的子節點差較大時，雖然也會依條 件做加權處，但是層層計算後仍舊會影響其相似。如圖 11 所示。 (二) 綱要層級與映對結果 研究資的綱要層級介於 315 個之間，雖然每個節點在元素映對階段，必須互 相比較相似，節點相同但層級同的綱要，產生的相似矩陣是一樣的，所以需 要的儲存空間也相同，演算時會多做幾次層級的遞迴，但並影響元素相似的評估。 在結構層級映對上，綱要層級越多，會低綱要映對的正確，因為有太多節點是內 部節點，所以計算結構相似時，除元素本身，也必須考慮其子節點的相似。另外， 計算元素本身相似時已經因為同的兄弟節點組合而稍微低其本身的結構相似 ，所以當每個內部節點在依子節點相似和本身相似的權重比計算後，可能會將 原本的相似低的較多。而且層層計算，所花費的演算時間也會較多。如圖 12 所示。 100 100% 節點 映 對 綱要層級 15 映 對 100% 圖 11 節點與映對分析圖 圖 12 綱要層級與映對分析圖 (三) 實驗結果評估 圖 13 Recall/Precision 評估 最後，本研究使用資訊檢域常用的正確(Recall)和確(Precision)(Reid, 2001)評估第二部份交叉驗證的結果，如圖 13 所示，將評估結果分為四，A是系統 映對到且為相似的綱要，B是系統映對到但相似的綱要，C是系統没有映對到但卻相 似的綱要，D是系統没有映對到也相似的綱要，A+B是映對結果，A+C是人工辨別為 XML 綱要自動映對技術之研究 /趙景明 蕭貞貞 115 相似的綱要，B+D是人工辨別為相似的綱要。正確=(映對到的相似綱要/全部 相似的綱要)，即為(A/(A+C)；確=(映對到相似的綱要/全部映對到的綱要 )，即為(A/(A+B)。映對有效性的計算結果如表 10 所示，明如下： 表 10. 實驗結果評估 資型 (A+C) (A+B) (A) (B) (C) 正確(A/(A+C) 確(A/(A+B) 訂單資 28 22 18 4 10 64% 82% 書籍資 68 52 51 1 17 75% 98% 員工資 47 30 25 5 22 53% 83% (1) 訂單資共有 28 份，產生出的映對有 22 份，其中符合人工比對的正確結果有 18 份，有 4 份屬於此型資，有 10 份屬於此型的資沒有判斷出，故正確 為 18/28=0.64，確為 18/22=0.82。 (2) 書籍資共有 68 份，產生出的映對有 52 份，其中符合人工比對的正確結果有 51 份，有 1 份屬於此型資，有 17 份屬於此型的資沒有判斷出，故正確 為 51/68=0.75，確為 51/52=0.98。 (3) 員工資共有 47 份，產生出的映對有 30 份，其中符合人工比對的正確結果有 25 份，有 5 份屬於此型資，有 22 份屬於此型的資沒有判斷出，故正確 為 25/47=0.53，確為 25/30=0.83。 伍、結 伍、結 本研究以 XML Schema 為研究對象，應用綱要模式，並結合一般文獻上的映對方 法，但也針對元素名稱的詞性變化及結構關係做較多的考，如：同時以父子和兄弟 節點評估元素的結構關係，並可動態調整權重等。另外，本研究也採用後序追蹤的計 算方式，可以由下往上辨別綱要的差，產生較確的映對結果。另外，因應網頁資 的成長，要處的綱要映對也隨著愈多、愈複雜，用人工或半自動的方式，耗費時間和 人，本研究使用自動化的綱要映對技術以增加處速。未，希望能夠再結合相關 的斷字技術，將元素剖析的完善，以提升效及自動化的程。 訊管展望 第 9 卷 第 1 期 民國 96 6 月 116 考文獻 考文獻 周坤約、洪博文、歐翼德譯，專業XML程式設計, 2002，第 2 版，台，碁峯資訊。 郭木興、蔡德男，”以 XML 為基之資倉儲資轉換閘建置研究”，資管學報，2004， 第十一卷，第四期，頁 105-129。 Batini, C., Lenzerini, M., and Navathe, SB. “A comparative analysis of methodologies for database schema integration,” ACM Computing Surveys (18:4), 1986. Bergamaschi, S., Castano, S. and Vincini, M. “Semantic Integration of Semistructured and Structured Data Sources,” ACM SIGMOD Record (28:1), 1999, pp.54-59. Boukottaya, A., Vanoirbeek, C., Paganelli, F. and Khaled, O.A. “Automating XML documents transformations: a conceptual modelling based approach,” Proceedings of the first Asian-Pacific conference on Conceptual modelling, Lausanne, Switzerland, 2004. Cheng, K., Kambayashi, Y., Lee, S.T., and Mohania, M. “Functions of a Web Warehouse,” Proceedings of 2000 Kyoto International Conference on Digital Libraries: Research and Practice, Kyoto University, Kyoto, Japan, 2000, pp.372-379. Chua, H., Chiang, H.L. and Lim, E.P. “Instance-based attribute identification in database integration,” The VLDB Journal (12:3), 2003, pp.228-243. Dhamankar, R., Lee, Y., Doan, A., Halevy, A. and Domingos, P. “iMAP: Discovering Complex Semantic Matches between Database Schemas,” Proceedings of the 2004 ACM SIGMOD international conference on Management of data, 2004. Doan, A., Domingos, P. and Halevy, A. “Reconciling schemas of disparate data sources: a machine-learning approach,” ACM SIGMOD Record (30:2), 2001. Embley, D. W., Xu, L. and Ding, Y. “Automatic Direct and Indirect Schema Mapping: Experiences and Lessons Learned,” ACM SIGMOD Record (33:4), 2004, pp.14-19. Lee, D. and Chu, W.W. ” Comparative Analysis of Six XML Schema Languages,” ACM SIGMOD Record (29:3), 2000, pp.76-87. Lee, M. L., Yang, L. H., Hsu, W. and Yang, X. “XClust:clustering XML schemas for effective integration,” Proceedings of the eleventh international conference on Information and knowledge management, Virginia, USA, 2002. Madhavan, J., Bernstein, P.A., Domingos, P. and Halevy, A. “Representing and Reasoning about Mappings between Domain Models,” Eighteenth national conference on Artificial intelligence, Alberta, Canada, 2002. Madhavan, J., Bernstein, P.A. and Rahm, E. “Generic Schema Matching with Cupid,” Proceedings of the 27th International Conference of Very Large Data Bases, 2001. Mitra, P., Wiederhold, G. and Kersten, M. “A Graph-Oriented Model for Articulation of Ontology Interdependencies,” Proceedings of the 7th International Conference on Extending, 2000. Oxford Particle Physics Grid Research, https:/grid.physics.ox.ac.uk/library/xml/xml-schemas/examples/, 2005. Parent, C. and Spaccapietra, S. “Issues and Approaches of Database Integration,” Communications of the ACM (41:5), 1998, pp.166-178. Rahm, E., Bernstein, P. A., “A survey of approaches to automatic schema matching”, The VLDB Journal (10:4), 2001, pp.334-350. Reid, J. “Evaluation of IR Systems”, http:/www.dcs.qmul.ac.uk/jane/courses/IRIC/Evaluation.ppt, 2001. Reynaud, C., Sirot, J.P. and Vodislav, D. “Semantic Integration of XML Heterogeneous Data Sources,” Proceedings of the 2001 International Symposium on Database Engineering & Applications, 2001. XML 綱要自動映對技術之研究 /趙景明 蕭貞貞 117 Sihem A.Y. and Divesh S. “A Mapping Schema and Interface for XML Stores,” Proceedings of the 4th international workshop on Web information and data management, Virginia, USA, 2002. Su, H., Kuno, H. and Rundensteiner, E.A. “Automating the Transformation of XML Documents,” Proceedings of the 3rd international workshop on Web information and data management, Georgia, USA, 2001. World Wide Web Consortium (W3C), Extensible Markup Language (XML), /TR/xmlschema-0/, 2004. World Wi