臺灣博碩士論文加值系統

隨著電子商務（Electronic Commerce）的蓬勃發展，為了統一不同領域所使用的電子文件格式，W3C（World Wide Web Consortium）組織便開發了延伸式標籤語言（eXtensible Markup Language；XML）作為企業互相傳遞資訊的標準語言。未來隨著企業廣泛的應用勢必會產生大量的XML文件，儘管由於電腦硬體技術的進步，大幅的增加了資料儲存體的容量，但是資訊量的爆增，仍使得資料儲存體的容量難以負荷，因此如何發展一個有效的壓縮方法來降低資料的儲存空間便成了一項重要的議題。
目前用來儲存XML文件的方式大致可分為關聯式資料庫（Relational Database）及原生型XML資料庫（Native XML Database）。關聯式資料庫的儲存方式是將一份XML文件拆解成數個部份，然後透過一些規則對映的方式儲存在數個關聯表裡，但由於XML文件是一種具有階層架構的文件，此舉不僅會破壞XML原有的結構，也會降低系統的執行效率；而原生型XML資料庫的儲存方式是可以直接將XML文件存入資料庫中，而不需透過複雜的對映，故在效率上比利用關聯式資料庫的方式更佳。
另外，傳統的無失真資料壓縮方法如霍夫曼編碼法（Huffman Coding）、算數編碼法（Arithmetic Encoding）及字典壓縮法（Dictionary Coding）等，都僅能對資料作單純的壓縮而無法從資料庫中發現知識（Knowledge DBcovery in Databases）。
本篇論文基於上述理由提出一個資料壓縮的方法，利用資料探勘中的關聯技術找出原生型XML資料庫中的高頻標籤集（frequent tag data sets）及高頻字元資料集（frequent character data sets），接著分別利用這些高頻標籤集及高頻字元資料集建立壓縮規則進行原生型XML資料庫壓縮。本研究的壓縮技術之貢獻將使得在壓縮資料的同時也能找出隱含在文件中的資訊。另外，XML文件數量會隨著時間成長而產生異動，導致之前所探勘出的高頻標籤集及高頻字元資料集有所變動，因此本研究在最會亦會結合動態探勘演算法的概念，將所產生的高頻標籤集、高頻字元資料集及壓縮規則作一動態維護，不必因為資料的異動而重新對整個原生型XML資料庫作探勘及壓縮。由實驗結果顯示本論文所提壓縮方法對XML文件的壓縮率平均在75%，且動態壓縮方法的壓縮時間比靜態壓縮方法的壓縮時間節省約40秒，因此本論文所提之壓縮方法是非常有效的。

Since XML becomes a standard, applications based on it have grown rapidly. However the existing database systems, namely relational databases, provide inadequate facilities to manage the nested and ordered structures in XML documents. Therefore, there exist two important issues about the storage capacity for huge XML documents and the complexity mapping between the relational databases and XML repository. Though database compression can relief the storage capacity problem, the traditional compression method, like Huffman Coding, Arithmetic Encoding, Dictionary Coding, etc., cannot explore useful information.

For solving above the problems, we propose a compression method to compress the native XML database via data mining techniques. We apply the association mining technique to explore the frequent character data sets and frequent tag sets and then we use those frequent sets to establish the compression rules to compress the XML documents. In addition, XML documents may pile up over time. Therefore, we apply the dynamically mining techniques to maintain the compression rules. The approach contributes to the native XML database both in extracting hidden information and in lossless compression, respectively. The experimental results show that our compression method has powerful compression effectiveness.

摘　要 I
Abstract III
誌　謝 V
表　目　錄 XI
圖　目　錄 XIII
第一章　緒論 1
1.1　研究背景 1
1.2　研究動機及目的 2
1.3 論文架構 4
第二章　文獻探討 5
2.1 XML（eXtensible Markup Language） 5
2.1.1 DTD及XML Schema 6
2.1.2 原生型XML資料庫 8
2.2 資料探勘 9
2.2.1 關聯規則 10
2.2.2 Apriori演算法 11
2.3 動態資料探勘 12
2.3.1 FUP演算法 12
2.3.2 FUP2演算法 14
2.4 資料壓縮與資料庫壓縮 16
2.4.1 資料壓縮 17
2.4.2 資料庫壓縮 18
第三章　研究方法 21
3.1 剖析DTD並對相對應的XML文件進行編碼 24
3.2 探勘高頻字元資料集 31
3.3 探勘高頻標籤集 37
3.4 建立壓縮規則與計算壓縮空間 39
3.4.1 利用高頻字元資料集建立壓縮規則 39
3.4.2 利用高頻標籤集建立壓縮規則 40
3.4.3 壓縮經驗法則（Heuristic Compression Method） 41
3.5 動態維護高頻字元資料集 43
3.5.1 新增加XML文件時之所有字元資料集維護 43
3.5.2 刪除XML文件時之所有字元資料集 45
3.6 動態維護高頻標籤集 47
3.6.1 新增加XML文件時之所有標籤集維護 47
3.6.2 刪除XML文件時之所有標籤集維護 49
3.7 動態維護字元資料集壓縮規則Metarule C 50
3.8 動態維護標籤集壓縮規則Metarule T 51
第四章　範例說明 53
4.1 剖析DTD並對相對應的XML文件進行編碼 53
4.2 探勘高頻字元資料集 57
4.2.1 探勘長度為1之高頻字元資料集 57
4.2.2 探勘長度大於1之高頻字元資料集 58
4.3 探勘高頻標籤集 59
4.4 建立壓縮規則與計算壓縮空間 61
4.5 動態維護高頻字元資料集及高頻標籤集 63
4.6 動態維護壓縮規則 70
第五章　實驗設計與實驗結果 73
5.1 實驗平台 76
5.2 實驗分析 76
5.2.1 靜態壓縮 78
5.2.1.1不同最小支持度之壓縮率 78
5.2.1.2 不同文件個數之壓縮率 79
5.2.1.3 與壓縮軟體RAR及ZIP壓縮率比較 81
5.2.1.4 不同文件個數之壓縮效率 82
5.2.1.5 針對字元資料之壓縮經驗法則比較 83
5.2.2 動態壓縮 85
5.2.2.1 與靜態壓縮方法之壓縮效率比較……………………85
5.2.2.2 與靜態壓縮方法之壓縮率比較 86
第六章　結論 87
參考文獻 88

[1]R. Agrawal and R. Srikant(1994), “Fast Algorithms for Mining Association Rules,” Proc. 20th Int’l Conf. on Very Large Data Bases (VLDB’94), pp.487-499.
[2]R. Agrawal, T. Imielinski, and A. Swami(1993), “Mining Association Rules between Sets of Items in Large Databases,” Proc. of the ACM SIGMOD Conf. on Management of Data, Washington, D.C., pp. 207-216.
[3]S. Banerjee, V. Krishnamurthy, M. Krishnaprasad, and R. Murthy(2000), “Oracle8 i - The XML Enabled Data Management System,” Proceedings of the Interntional Conference on Data Engineerng (ICDE), California, pp.561-568.
[4]S. Babu, M. Garofalakis, and R. Rastogi (2001), “SPARTAN: A Model-Based Semantic Compression System for Massive Data Tables,” Proc. 2001 ACM-SIGMOD Int’l Conf. on Management of Data (SIGMOD’01), pp.283-294.
[5]E. Bertino and B. Catania (2001), “Integrating XML and Database,” IEEE Internet Computing, Vol. 5, No. 4, pp. 84-88.
[6]R. Bourret, C. Bornhovd, and A. Buchmann (2000), “A Generic Load/Extract Utility for Data Transfer between XML Documents and Relational Databases,” Proceedings of the Second International Workshop on Advaced Issues of E-commerce and Web-based Information Systems, pp.134-143.
[7]A. Cannane and H. E. Williams (2000), “A Compression Scheme for Large Databases,” Australasian Database Conf., vol. 22, no. 2, pp. 6-11.
[8]S.W., Changchien and T.C., Lu （2001）“A New Efficient Association Rules Mining Method Using Class Inheritance Tree (CIT),” Submitted for Publication and Presentation in 12th Conference ICIM.
[9]S. Chan, T. Dillon, and A. Siu(2002), “Applying a Mediator Architecture Employing XML to Retailing Inventory Control,” The Journal of Systems and Software, Vol.60, pp. 239-248.
[10]David W. Cheung, Jiawei Han, Vincen T. Ng and C.Y.Wong (1996), “Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique”, Proc. Int’l Conf. on Data Engineering, New Orleans, Louisiana, pp.106-114.
[11]D. W. Cheung, S.D. Lee and B. Kao(1997), “A General Incremental Technique for Maintaining Discovered Association Rules”, Proceedings of the Fifth International Conference on Database Systems for Advanced Applications (DASFAA), pp.185-194.
[12]W.P. Cockshott, D. McGregor, N. Kotsis, and J. Wilson (1998), “Data Compression in Database Systems,” Proc. Int’l Database Engineering and Applications Symposium, pp. 111-120.
[13]D. Florescu and D. Kossmann (1999), “Storing and Querying XML Data Using an RDBMS,” IEEE Data Engineering Bulletin, Vol. 22, No. 3, pp. 27-34.
[14]D. Florescu and D. Kossman (1999), “A Performance Evaluation of Alternative Mapping Schemes for Storing XML Data in Relational Database,” Rapport de Recherche No. 3680 Inria, Rocquencourt.
[15]J. Fong, H. K. Wong, and Z. Cheng (2003), “Converting Relational Database into XML Documents with DOM,” Information and Software Technology, Vol. 45, pp. 335-355.
[16]C. L. Goh, K. M. Aisaka, Tsukamoto, K. Harumoto, and S. Nishio (1998), “Database Compression with Data Mining Methods,” Proc. 5th Int’l Conf. on Foundations of Data OrganiPation (FODO''98), pp.97-106.
[17]J. Han and M. Kamber, (2001), Data Mining: Concepts and Techniques, Morgan Kaufmann.
[18]D. Huffman (1951), “A Method for the Construction of Minimum Redundancy Codes,” Proc. of the Institute of Radio Engineers, Vol. 40, pp.1098-1101.
[19]J. W. Lee, K. Lee, and W. Kim (2001), “Preparations for Semantics-Based XML Mining,” Proceedings of the IEEE International Conference on Data Mining , pp. 345-352.
[20]C.H. Lee, S.W. Changchien, and W.T. Wang (2003), “Association Rules Mining for Native XML Database,” Department of Information Management, Chaoyang University of Technology, CYUT-IM-TR-2003-011.
[21]A. Moffat and J. Zobel, “Text Compression for Dynamic Document Databaes,” IEEE Trans. on Knowledge and Data Engineering, vol. 9, no. 2, pp. 302-313, 1997.
[22]Vincent To-Yee Ng, J. Man-Lee Wong, P. Bao (2001), Incremental mining of association patterns on compressed data, IFSA World Congress and 20th NAFIPS International Conference, Vol.1, pp. 441-446.
[23]M. Rys (2001), “Bringing the Internet to Your Database: Using SQL Server 2000 and XML to Build Loosely-Coupled Systems,” Proceedings of the International Conference on Data Engineering, pp. 465-472.
[24]J. Shanmugasundaram, E. Shekita, R. Barr, M. Carey, B. Lindsay, H. Pirahesh, and B. Reinwald (2000), “Efficiently Publishing Relational Data as XML Documents,” Proceedings of the 26th International Conference on Very Large Databases, pp. 65-76.
[25]J. Shanmugasundaram, E. Shekita, J. Kiernan, R. Krishnamurthy, E. Viglas, J. Naughton, and I. Tatarinov (2001), “A General Technique for Querying XML Documents using a Relational Database System,” ACM SIGMOD Special Section on Advanced XML Data Processing, Vol. 30, No.3.
[26]J. Shanmugasundaram, K. Tufte, G. He, C. Zhang, D. De-Witt and J. Naughton (1999), “Relatinal Databases for Quetying XML Documents: Limitataions and Opportunities,” Proceedings of the 25th Internationl Confetence on Vety Large Databases (VLDB’99), Edinburgh, UK, pp.302-314.
[27]M. Strobel (2002), “An XML Schema Representation for the Communication Design of Electronic Negotiations,” Computer Networks, Vol. 39, pp. 661-680.
[28]D. Suciu (2001), “On Database Theory and XML,” ACM SIGMOD Special Section on Advanced XML Data Processing, Vol. 30, Issue 3, pp. 39-45.
[29]T. A. Welch (1984), “A Technique for High-Performance Data Compression,” IEEE Computer, Vol. 17, pp.8-19.
[30]I. H. Witten, R. M. Neal, and J.G. Cleary (1987), “Arithmetic Coding for Data Compression,” Communications of ACM, Vol. 30, No. 6, pp.520-540.
[31]J. Ziv and A. Lempel (1977), “A Universal Algorithm for Sequential Data Compression,” IEEE Trans. on Information Theory, Vol. IT-23, pp.337-343.
[32]J. Ziv and A. Lempel (1978), “Compression of Individual Sequences via Variable-Rate Coding,” IEEE Trans. on Information Theory, Vol. IT-24, pp.530-536.
[33]李金鳳、張簡尚偉、王威澤（2001），「以廣義化關聯資料探勘方法設計物件導向資料庫壓縮技術之研究」， 2001全國計算機會議—資料庫與軟體工程，台北。
[34]Apache (2005), “Apache Xindice,” http://xml.apache.org/xindice/
[35]Bourret, R., “XML and Databases,” http://www.rpbourret.com/xml/XMLAndDatabases.htm
[36]I. Dayen (2005), “Storing XML in Relational Database,” http://www.xml.com/pub/a/2001/06/20/databases.html.
[37]IBM Almaden Research Center (2005), Quest synthetic data generation, http://www.almaden.ibm.com/software/quest/Resources/datasets/syndata.html.
[38]Ipedo(2005), “Ipedo XML Database,” http://www.ipedo.com/html/products_xml_dat.html
[39]Software AG (2005), “Tamino XML Server,” http://www.softwareag.com/tamino/default.htm
[40]WINZIP, http://www.winzip.com, 2005
[41]WINRAR, http://www.rarsoft.com, 2005
[42]World Wide Web Consortum (2005), “Extensible Markup Language (XML) Version 1.1,” http://www.w3.org/TR/2004/REC-xml11-20040204/
[43]X-Hive (2005), “X-Hive/DB,” http://www.x-hive.com/products/db/index.html