近年來，資料轉換已成為商業交易中不可或缺的角色。W3C所提出的XML已成為資料轉換的熱門媒體，並廣泛應用在資料庫領域上。許多利用XML當媒介物的資料轉換研究，多集中在關聯式資料庫，少部分則應用於階層式資料庫。一般商業資料之間，常常會有多對多關係建立之必要。然而，階層式資料模型不易表現資料之間的多對多關係。網狀式資料模型則容易滿足此一特性描述。在本研究中，我們在一個已知資料交換模型下提出六個資料轉換的演算法。透過此六個演算法，使用網狀式資料模型資料庫的組織或企業可利用XML文件來交換資料。XML文件可以保有原來資料庫的資料與資料間的關係，XML Schema或DTD則被用來保存資料的總體架構與資料型態，避免在資料交換的過程中發生資料型態遺失而造成不可預期的錯誤。我們並將透過實驗來分析此資料交換模型的效能。

In recent year, data exchange takes an essential role in business transactions. XML, proposed by W3C, becomes a new media for data exchange and is applied widespread on the database fields. Many research for data conversion by XML focus on the relational databases. Some papers propose the data conversion between hierarchical data model. It is necessary to establish data with many-to-many relationship among the ordinary business data. However, data with many-to-many relationships can not be represented the by hierarchical data model. The network data model (NDM) can satisfy this characteristic. In our research, we propose six data conversion algorithms in a data exchange model. By the six algorithms, the enterprises and organizations which use the NDM-based database can exchange their business data by XML documents. The XML documents keep the relationships among data in the database. XML Schema or DTD is used to preserve the overall structure and data types of data, to avoid the unpredicted errors during the process of data conversion. Experiments are performed to analyze the performance of the proposed model.

Table of Contents
LIST OF TABLES VI
LIST OF FIGURES VIII
1. INTRODUTION 1
1.1. Background and Motivation 1
1.2. Objective and Thesis Outline 2
2. PREVIOUS WORK 4
2.1. Papers Survey 4
2.2. XML 7
2.2.1. XML Documents 7
2.2.2. Document Type Definition (DTD) 10
2.2.3. XML Schema 12
2.3. Network Data Model (NDM) in IMS 13
2.3.1. The Database Description Block of NDM-based database 17
3. THE DATA EXCHANGE MODEL 19
3.1. Data Conversion from NDB to XML 21
3.1.1. The NDBToXML Algorithm 21
3.1.2. The DBDToDTD Algorithm 25
3.1.3. The DBDToXSchema Algorithm 29
3.2. Data Conversion from XML to NDB 34
3.2.1. The XMLToNDB Algorithm 34
3.2.2. The DTDToDBD Algorithm 37
3.2.3. The XSchemaToDBD Algorithm 40
4. EXPERIMENTS 45
4.1. Experiments Environment 45
4.2. Experiment parameters 49
4.3. Experiment Result and Analysis 51
5. CONCLUSION 61
6. REFERENCE 62
APPENDIX A: The XML Schema created by the DBDToXschema. 68
APPENDIX B: The DTD file created by the DBDToDTD 72
APPENDIX C: A TSL used to generate the hierarchical structure of an NDB 73



List of Tables
Table 1. Data types in IMS, XML Schema, and DTD. 33
Table 2. The experiment results of NDBToXML with 80% bridge segment instances and 4 segments. 52
Table 3. The experiment results of NDBToXML with 80% bridge segment instances and 8 segments. 52
Table 4. The experiment results of NDBToXML with 80% bridge segment instances and 12 segments. 53
Table 5. The experiment results of NDBToXML with 100 records and 4segments. 54
Table 6. The experiment results of NDBToXML with 100 records and 8 segments. 54
Table 7. The experiment results of NDBToXML with 100 records and 12 segments. 55
Table 8. The experiment results of XMLToNDB with 80% duplicate element instances and 4 elements. 56
Table 9. The experiment results of XMLToNDB with 80% duplicate element instances and 8 elements. 56
Table 10. The experiment results of XMLToNDB with 80% duplicate element instances and 12 elements. 57

Table 11. The experiment results of XMLToNDB with 100 records and 4 elements. 58
Table 12. The experiment results of XMLToNDB with 100 records and 8 elements. 58
Table 13. The experiment results of XMLToNDB with 100 records and 12 elements. 59

List of Figures
Figure 1. An HDM-based database. 5
Figure 2. An XML document. 6
Figure 3. An XML document. 8
Figure 4. A DOM notation. 9
Figure 5. An XML document is represented by a DOM tree. 10
Figure 6. A DTD. 11
Figure 7. An XML Schema. 13
Figure 8. An example of NDM-based database. 14
Figure 9. An NDM-based database. 16
Figure 10. A DBD File. 18
Figure 11. The data exchange model. 20
Figure 12. An NDB in the source unit. 20
Figure 13. An NDB in the destination unit. 21
Figure 14. A segment structure of an NDM-based database. 22
Figure 15. An NDB structures in the experiment. 46
Figure 16. A DBD of the NDB (8 segments). 48
Figure 17. The curves of NDBToXML with 80% bridge segment instances 53
Figure 18. The curves of NDBToXML with 100 records. 55
Figure 19. The curves of XMLToNDB with 80% duplicate element instances. 57
Figure 20. The curves of XMLToNDB with 100 records. 59

[1]L. Aversano, G. Canfora, A. De Lucia, and P. Gallucci, “Integrating document and workflow management tools using XML and web technologies: a case study,” Proceedings of Sixth European Conference on Software Maintenance and Reengineering, pp. 24-33, 2002.
[2]S. Amer-Yahia and D. Srivastava, “A mapping schema and interface for XML stores,” Proceedings of the fourth international workshop on Web information and data management, pp 23-30, 2002
[3]D. Barbosa, A. Mendelzon, J. Keenleyside, and K. Lyons, “ToXgene: An extensible template-based data generator for XML,” Proceedings of the ACM SIGMOD International Conference on Management of Data. Madison, 2002.
[4]E. Bertino and B. Catania, “Integrating XML and Databases,” IEEE Internet Computing, Vol. 5, Issue: 4, 2001.
[5]E. Bertino and E. Ferrari, “XML and Data Integration,” IEEE Internet Computing, Vol. 5, Issue: 6, pp. 75-76, 2001.
[6]P. Bohannon, J. Freire, P. Roy, and J. Simeon, “From XML Schema to relations: a cost-based approach to XML storage,” Proceedings of the 18th International Conference on Data Engineering, 2002.
[7]A. B. Chaudhri, A. Rashid, and R. Zieari, XML Data Management: Native XML and XML-enabled Database Systems, Addison Wesley, 2003
[8]J. K. Chen and M. J. Liu, “A model for data exchange between XML document and hierarchical databases,” proceedings of the 2002 International Computer Symposium, Dec. 18-21, Hualien, Taiwan, ROC, Vol. 5, Session 8, E8-1, 2002
[9]J. K. Chen and M. J. Liu, “An application of XML on hierarchical database for data exchange,” proceedings of the 2003 National Computer Symposium, Dec. 18-19, Taichung, Taiwan, ROC, Session B3, OT-058, 2003
[10]F. M. Cleveland, “Information exchange modeling (IEM) and extensible markup language (XML) technologies,” IEEE Power Engineering Society Winter Meeting, Vol. 1, pp. 592-595, 2002.
[11]S. R. Collins, S. Navathe , L. Mark “XML Schema Mappings for Heterogeneous Database Access,” Information and Software Technology, Vol. 44, Issue: 4, pp. 251-257, 2002
[12]J. Fong, F. Pang, and C. Bloor, “Converting relational database into XML document,”Proceedings of 12th International workshop on Database and Expert Systems Applications, 2001.
[13]E. R. Harold, XML Bible, John Wiley & Sons, 2001.
[14]B. Hofreiter, C. Huemerm, and W. Klas, “ebXML: status, research issues, and obstacles,” Proceedings of the 12th International Workshop, Research Issues in Data Engineering: Engineering E-Commerce/E-Business Systems, pp. 7-16, 2002.
[15]J. Hou; Y. Zhang, and Y. Kambayashi, “Object-oriented representation for XML data Cooperative,” Proceedings of the Third International Symposium, Database Systems for Advanced Applications, pp. 40-49, 2002.
[16]G. Kappel, S. Rausch-Schott, S. Reich, and W. Retschitzegger, “Hypermedia document and workflow management based on active object-oriented databases,” Proceedings of the Thirtieth Hwaii International Conference, System Sciences, Vol. 4, pp. 377-386, 1997.
[17]J. S. Kim, W. Y. Lee, and K. H. Lee, “The cost model for XML documents in relational database systems,” ACS/IEEE International Conference, Computer Systems and Applications, pp. 185-187, 2001.
[18]T. Kudrass, “Management of XML Documents without Schema in Relational Database Systems,” Information and Software Technology, Vol. 44, Issue: 4, pp. 269-275, 2002.
[19]M. J. Liu, “A Data Exchange Model between Hierarchical Databases and XML Documents,” master''s thesis, Dept. of Information Management, Choayang University of Technology, Taiwan, 2004.
[20]Eric Jui-Lin Lu, Shihyu Chou, and Ru-Hui Tsai, “An Empirical Study of
XML/EDI”, The Journal of Systems and Software, vol. 58, no. 3, Sep. 2001,pp. 269-277.
[21]Eric Jui-Lin Lu, Bo-Chan Wu, and Po-Yun Chuang, “A benchmark and case study for XML data management in business information systems,” CYUT-IM-TR-2003-005, Apr. 11, 2003.
[22]T. William Olle, The Codasyl Approach to Data Base Management, John Wiley & Sons, 1978.
[23] A. Renner, “XML data and object databases: the perfect couple?,” Proceedings of the 17th International Conference on Data Engineering, pp. 143-148, 2001.
[24]A. Salminen and F. W. Tompa, “Requirements for XML document Database Systems,” Proceeding of the ACM Symposium, Document Engineering, 2001.
[25]J. Singh, “XML for power market data exchange,” IEEE Power Engineering Society Winter Meeting, Vol. 2, pp. 755-756, 2001.
[26]M. B. Spring, “Reference Model for Data Interchange standards,” Computer, Vol. 29, Issue: 8, pp. 87-88, 1996.
[27]R. Summers, J. J. L. Chelsom, D. R. Nurse, and J. D. S. Kay, “Document management: an Intranet approach,” IEEE the 18th Annual International Conference, Engineering in Medicine and Biology Society, Bridging Disciplines for Biomedicine, Vol. 3, pp.1236-1237, 1997.
[28]M. Sundaram and S. S. Y. Shim, “Infrastructure for B2B Exchanges with RosettaNet,” The third International Workshop on Advanced Issues of E-Commerce and Web-Based Information Systems, pp. 110-119, 2001.
[29]R. W. Taylor and R. L. Frank, “CODASYL Data-Base Management System,” ACM Computing Surveys, Vol. 8, Issue: 1, pp. 67-103, 1976.
[30]S. Wegener and D. Davis, “XML TPS data exchange,” IEEE AUTOTESTCON proceedings of Systems Readiness Technology Conference, pp. 605-615, 2001.
[31]G. Wiederhold, Database Design, 2nd Ed., McGraw-Hill, 1995.
[32]R. Bourret, XML and databases, http://www.rpbourret.com/xml/XMLAndDatabases.htm.
[33]Robin Cover, SGML/XML: Using Elements and Attributes, http://xml.coverpages.org/elementsAndAttrs.html.
[34]IBM, IMS Primer, http://www.redbooks.ibm.com.
[35]IBM, IMS/ESA V5 Admin Guide: DB, http://www-306.ibm.com/software/data/ims/v5pdf/DFSA10C6.PDF.
[36]IBM, IMS V9 Fact Sheet, GC18-7697, 2004, http://www-306.ibm.com/software/data/ims/v9/v9fact.pdf.
[37]IBM, IMS Version 9 Implementation Guide: A Technical Overview, http://www.redbooks.ibm.com/redbooks/pdfs/sg246398.pdf.
[38]IBM, XML Generator, http://www.alphaworks.ibm.com/tech/xmlgenerator.
[39]W3C, Document Object Model (DOM), http://www.w3.org/DOM/.
[40]W3C, Extensible Markup Language (XML) 1.0 W3C Recommendation, 10 February 1998, http://www.w3.org/TR/1998/REC-xml-19980210.
[41]W3C, Extensible Markup Language (XML) 1.1 W3C Recommendation, 4 February 2004, http://www.w3.org/TR/2004/REC-xml11-20040204/.
[42]W3C, XML Schema Part 0: Primer W3C Recommendation, 2 May 2001, http://www.w3.org/TR/2001/REC-xmlschema-0-20010502.
[43]W3C, XML Schema Part 1: Structures W3C Recommendation, 2 May 2001, http://www.w3.org/TR/2001/REC-xmlschema-1-20010502.
[44]W3C, XML Schema Part 2: Datatypes W3C Recommendation, 2 May 2001, http://www.w3.org/TR/2001/REC-xmlschema-2-20010502.
[45]XMark-An XML Benchmark Project, http://monetdb.cwi.nl/xml/index.html.