XML文件映射為嵌套表格的方法研究與應用

摘要:XML文件的高可擴展性和通用性目前被廣泛用作中間數據模式，而嵌套表格在描述具有層次結構的復雜對象方面具有簡單、直觀的特點，在最終編程領域適合作為復雜數據結構的呈現方式被使用。論文提出一種將復雜層次結構的XML文件映射為嵌套表格的方法，利用中間數據結構，給出了復雜層次結構的XML文件映射為中間數據結構的算法。實驗表明方法有效地降低了XML文件到嵌套表格映射的復雜性。

關鍵字:XML;嵌套表格;映射;中間數據結構

中圖分類號:TP311文獻標識碼:A 文章編號:1009-3044(2010)01-247-03

Research and Application of Method Mapping XML to Nested Tables

ZHU Jing， SUN Zhong-lin， WEI Yong-shan

(Shandong University of Science and Technology College of Information Science and Engineering， Qingdao 266510，China)

Abstract: XML file is widely used as intermediate data model due to its scalability and universality， while the nested table is suited to be used to present complex data in the final program area because of its simpleness and intuitive in describe the complex object that has a hierarchical structure. Paper proposes a method to map the XML file with complex hierarchy to the nested table by an intermediate data structure and gives a algorithms to map the XML file with complex hierarchy to the intermediate data structure. Experiments prove that this method is effective in reducing the complexity of converting XML file to nested table.

Key words: xml; nested table; mapping; intermediate data structure

最終用戶編程面向的是一些沒有計算機編程背景的普通用戶，近年來流行Yahoo! Pipes、Microsoft Popfly等互聯網情景構造工具是常見的最終用戶編程例子[1]。但是大多這類工具都是提供了基于數據流的可視化編程環境，研究表明，數據流和控制流對于最終用戶來說是難以理解的編程概念[2]，易用性較差。從面向最終編程領域的角度來講，嵌套表格是一種常用的數據表現形式，對最終用戶來說沒有理解上的困難，并且嵌套表格具有強大的數據呈現能力，比較適合作為面向最終用戶的編程界面。因此，在情景應用構造工具中，采用嵌套表格數據呈現方式，會大大降低情景應用構造的復雜性，從而提高工具的易用性[3]。情景應用中涉及到的數據是通過訪問形式多樣的個性化網絡信息資源到的，為降低最終用戶訪問網絡信息資源的復雜性，常常需要將個性化的資源進行統一的資源描述。目前XML已經成為互聯網上數據表示和數據交換的新標準，它具有較強的數據描述能力[3]，可以描述各種各樣不同形式的網絡資源。論文研究的工作是在情景應用構造環境下最終用戶能夠自主將需要訪問的個性化網絡資源通過統一的XML文檔表示的前提下進行的(由本課題小組其它人員完成)。

因此，在情景應用環境中，用嵌套表格來呈現復雜結構的XML文件尤為重要，這與本文的研究目標是一致的。論文提出一種將樹形結構表示的XML文件映射為嵌套表格的方法，提出了一種中間數據結構，并給出了XML文件轉化為中間數據結構的算法。通過大量的實驗證明該方法能夠有效地降低XML文件向嵌套表格映射的復雜性。

1XML映射為嵌套表格的方法

1.1 XML文件到嵌套表格的實例

XML文件是一種具有層次關系的樹狀結構，節點之間存在上下層關系，本質上來說是嵌套與被嵌套的關系，如圖1所示，它表示的是一個XML文件所對應的樹型數據結構示意圖，其中，節點用矩形表示，數據用正方形表示，1表示記錄條數為1條，N表示記錄條數為多條。

將圖1所表示的樹形結構的XML文件轉化成相應嵌套表格的樣式，如表1所示，可以看出嵌套表格數據模型對最終用戶提供了可視化的數據呈現方式，以簡單、直觀的方式展現了XML文件的模式和數據。

整個嵌套表格數據模型由兩部分構成:表頭結構和表格體內容。表頭結構表示的是XML文件模式，表格體內容表示的是XML數據記錄。

在表頭結構中，節點“客戶”、“聯系方式”、“訂單”、“訂單詳細”是一類由多個子節點構成的節點，在嵌套表格模型中是由通過多個列的組合而形成的，將其稱之為組合列。而節點“電話”、“數量”等(XML文件中對應的葉結點)沒有任何子節點構成，在嵌套表格中僅占有一列的位置，將其稱之為原子列。

1.2中間數據結構

表格是由許多單元格(cell)組成的，而每個單元格都是由行和列組成的地址標識的，因此實現XML文件向支持嵌套的表格映射，實際就是將XML文件的模式信息和數據信息都轉化成為表格中相應的由行列坐標地址標識的表頭單元格信息和表格體單元格信息。通過表1可以看出，在嵌套表格中是通過上下、左右相鄰單元格的跨行跨列合并來嵌套地表示XML模式和數據的層次關系。因此，得出每個用行列坐標標識的的單元格合并信息是問題解決的關鍵。

在該方法中，設計一種中間數據結構來存儲映射所需要的單元格合并信息(行列坐標標識)和單元格內容顯示信息，此中間數據結構有效地降低了XML向嵌套表格轉換的復雜性，同時論文在第三節具體給出了復雜層次結構的XML文件映射為中間數據結構的算法。表頭中間結構和數據中間結構分別通過算法1和算法2生成，兩者的中間數據結構內部含義相同，下面只通過表頭中間數據結構來具體說明單元格合并信息和內容顯示信息。

表2和表3表示表頭對應的中間數據結構，表2 MergeArray表示表頭單元格合并信息，表3 MergeContentArray表示合并后要顯示的表頭內容信息。表2中相鄰同種顏色的單元格內部坐標相同，表示要合并的單元格，合并信息是通過跨行、跨列合并單元格實現的，合并后單元格中顯示的內容為左上角單元格的內容。例如表2第一行合并后顯示表3中(0，0)單元格中的內容即“客戶信息”。通過使用此中間數據結構比較容易繪制出表1所表示的嵌套表格樣式。

2 映射算法

2.1 XML文件模式映射到嵌套表格的中間數據結構算法

算法思想:遍歷XML文件，使用隊列從根節點開始逐層處理元素。一次入隊一層元素并以*作為層分隔符號。然后從隊列中逐個取元素處理，此元素葉節點數量即為此元素應占的單元格數，處理完將此元素的子元素全部入隊并入隊*，如果此元素為葉節點，則壓入空格占位(即需要合并行)。遞歸處理直至隊列為空或隊列中所有元素均為空格退出。表4具體描述了算法的過程。

2.2 XML文件數據映射到嵌套表格的中間數據結構算法

算法思想:解析xml文件，獲取某個結點下的所有葉結點，其中包括了重復的葉結點，進行去重處理后得到唯一的葉結點。查找每個葉結點的公有父節點(即一條數據塊記錄的根節點)，然后逐個處理公共父節點。獲取每個父節點下的葉結點數據后，即形成一個記錄的數據塊，每條數據記錄內容采用對齊比較的方式，每個葉節點均對應不同數量的數據，每個葉節點均和數據數量最多的葉節點比較，缺少的個數即為需要合并的行數。表5具體描述了算法的過程。

3 總結

XML文件到嵌套表格的映射在面向最終用戶領域編程方面經常會涉及到，但是對于復雜的XML文件實現向嵌套表格的直接映射比較復雜，為此，論文提出一種中間數據結構降低XML文件向嵌套表格映射的復雜性，通過中間數據結構來存儲XML文件向嵌套表格的映射信息，通過中間數據結構生成算法得到關鍵的單元格合并信息和單元格顯示信息，通過大量的實例驗證了論文提出的映射方法的有效性。

參考文獻:

[1] 楊少華.用戶主導的互聯網情景應用構造研究[D].北京:中科院計算所，2009.

[2] J. Wong and J. Hong， What do we mashup when we make mashups?[R] In: Proc. of the 4th International Workshop on End-User Software Engineering (WEUSE'08)， Leipzig， Germany，2008，35-39.

[3] 王桂玲.用戶主導的互聯網虛擬應用構造與方法研究[D].北京:中科院計算所，2009 .

[3] 吳楊楊，陳鍛生.一個基于XML的Web信息源集成方案究[J].計算機工程與應用，2001，10:34-37.

[4] 王喆，潘懋，郭艷軍.基于XML元數據和Schema的信息提取研究[J].計算機工程與應用，2008，44(33):135-137.

[5] Guiling Wang， Shaohua Yang， Yanbo Han. Mashroom: End-User Mashup Programming Using Nested Tables[J].In Proc. of the 18th International World Wide Web Conference (WWW)， Madrid， Spain， 2009， pp. 861-870.

[6] B.A.Nardi，J.R. Miller.The Spreadsheet Interface: A Basis for End User Programming[R]，HP Labs Technical Reports，.2007.

[7] H.L. Lau and W. Ng， Querying XML Data Based on Nested Relational Sequence Model[R]，In: Proc. of the Poster Track of International Conference on World Wide Web (WWW Poster'02)， Honolulu， Hawaii， USA， 2002.