臺灣博碩士論文加值系統

隨著網路的日漸普及，網路的使用人口日益加增，當人們在選擇發表資訊的媒介時，越來越多的人考慮以網頁的型式發表。然而，網路管理者於儲存網頁資料時，限於記憶體空間以及時效性等因素，必需隨時執行資料更新。為了能完整保存資料的歷史沿革，並且兼顧記憶空間的有效利用，網頁資料倉儲(Web warehousing)的概念便應運而生。網頁資料倉儲的功能，主要在儲存網頁資料的演進，進而針對所存的資料加以分析。而其中，如何有效地儲存並查詢歷史性資料則為一項重要的議題。
近年來相關的研究主要圍繞在如何以Edit Script儲存各個版本資料間的差異，其中可略分為時序漸進式，以及索引編排式。時序漸進式，如RCS、SCCS等，其主要的概念是以Edit Script逐次編寫各相鄰歷史版本之間的差異；而索引編排式的作法則將版本資訊加以分類，使得舊版本在存取時更有效率，如DNN等。然而這些方法共同的缺點在於取得某個版本的資料皆需要花費龐大的計算量。
故此，本研究主要沿續此一大方向，首先提出以二進制定址二元樹的編碼方式編寫Edit Script，以增加Edit Script的效率。二進制定址二元樹的主要精神在於，每一個節點皆有一固定之Binary ID，且此ID即為其固定的邏輯位址，因此能大為增加取得特定版本資料的效率。本研究繼而針對網頁資料倉儲一般的歷史資料查詢，歸納出五類常見的查詢種類，並根據這五類查詢提出實作時所需的運算子，並據以編寫對應的演算法。最後，本研究架構出一個實驗系統以實作本文所提出的運算子及演算法，以實際查詢所需資料。

With the increasingly widespread use and users of Internet, more and more people tend to publish their information as Web pages. However, while storing these information, Web masters have to replace information with newer one. In order to keep full track of historical data and to manage storage space efficiently at the same time, the idea of Web Warehousing was proposed. The main function of a Web Warehouse is to store the complete evolution of web pages, then to analyze the data stored in it. Among the related research fields, effective historical-data storage is an important issue.
Researchers have focused on storing changes between versions with Edit Script. Among them are research topics such as RCS, SCCS, DNN, etc. They either store the changes between consecutive versions in Edit Script, or divide version information into groups. The drawback in common is that retrieving a specific version of data requires a lot of computation.
Hence, following this trend, we first proposed an Edit Script encoding model using Binary-Code-Addressing Binary Tree to make the computation more effective. The main idea of Binary-Code-Addressing Binary Tree is that every node in the tree has a fixed Binary ID, and this ID is then the logical address of this node. We concluded five main categories of common queries on historical data in Web warehouses. Then we proposed operators and syntax for these queries, and the required algorithm. Finally, we constructed an experiment system to implement the operators and algorithm, to really use these operators and syntax on queries.

誌謝 i
摘要 ii
Abstract iii
目錄 iv
圖目錄 viii
1 緒論 1
1.1 研究動機與背景 1
1.2　研究目的 2
1.3　研究流程 2
1.4　論文架構 3
2　基本觀念介紹 5
2.1　資料倉儲系統 5
2.1.1　資料倉儲系統的源起 5
2.1.2　資料倉儲系統的定義 5
2.1.3　資料倉儲的組成元件 6
2.2 XML相關技術簡介 7
2.2.1　XML簡介 7
2.2.2　XML與HTML的比較 9
2.2.3　XML的優越性 9
2.2.4　XML SCHEMA簡介 11
2.2.5　XSLT 簡介 12
2.3　XQUERY 簡介 12
2.4　WEB SERVICES 15
2.4.1　WEB SERVICES 簡介 15
2.4.2　WEB SERVICES 的相關標準 16
2.4.2.1　SOAP 17
2.4.2.2　WSDL 17
2.4.2.3　UDDI 18
3　文獻探討 20
3.1 歷史資料庫 20
3.2 網頁資料倉儲系統 20
3.2.1 完整備份式 20
3.2.2 HTML-CENTRIC 21
3.2.3 XML-CENTRIC 22
3.3 EDIT SCRIPT處理 24
3.3.1 時序漸進式 25
3.3.2 索引編排式 25
4 研究方法 27
4.1 資料模式 27
4.2 二進制定址二元樹 30
4.2.1二進制定址二元樹的定義 30
4.2.2二進制定址二元樹的各項運算 32
4.2.2.1二進制定址二元樹的搜尋 32
4.2.2.2二進制定址二元樹的新增 33
4.2.2.3二進制定址二元樹搜尋前任者及繼任者 34
4.2.3二進制定址二元樹的運用 35
4.2.4二進制定址二元樹於實際運用上的調整 37
4.3 查詢流程 37
4.3.1 歷史資料查詢 38
4.3.2 歷史資料查詢語法 39
4.3.3 歷史資料庫運算子 43
4.3.4 歷史資料查詢演算法 46
5 實驗及討論 51
5.1 實驗架構 51
5.2 實驗系統簡介 53
5.3 系統效能分析 57
6. 結論及未來方向 58
6.1 結論 58
6.2 未來研究方向 58
7 參考文獻 60
附錄一 parser.asp 65
附錄二 cmd_parser.asp 68

[1]　吳昭宗等，「資料倉儲應用XML於資料擷取、傳送、轉換及載入之探討」，電信研　究雙月刊，第32卷第4期，p.p.511-520，2002年
[2]　資通電腦，「資料倉儲系統簡介(上)」，資訊與電腦，第194期，p.p.124-129，1996年
[3]　資通電腦，「資料倉儲系統簡介(下)」，資訊與電腦，第195期，p.p.117-119，1996年
[4]　黃士銘，「建置一網際網路資料倉儲系統」，資訊管理學報，第九卷第一期，p.p.135-152
[5] Amagasa, T., Yoshikawa, M., and Uemura,S. “A Data Model for Temporal XML Document,” in Proceedings of the 13th International Conference of on Database and Expert Systems Applications , 2002
[6] Bertino, E., Ferrai, E. and G. Guerrini, “ A Formal Temporal Object-Oriented Data Model,” in Proceedings of the 5th International Conference on Extending Database Technology, 1996
[7] Chawathe, S., Rajaraman, A., Garcia-Molina, H. and Widom, J. “Change Detection in Hierarchically Structured Information,” ACM SIGMOD, 1996
[8] Chien, S., Tsotras, V. J. and Zaniolo, C.” Copy-Based versus Edit-Based Version Management Schemes for Structured Documents,” in Proceedings of the 11th International Workshop on Research Issues on Data Engineering ,2001
[9] Chien, S., Tsotras,V. J. and Zaniolo, C.” XML Document Versioning,” SIGMOD Record 30(3), pp.46-53, 2001
[10] Chien, S., Tsotras,V. J. and Zaniolo, C. ” Efficient Management of Multiversion Documents by Object Referencing, ” in Proceedings of the 27th International Conference on Very Large Databases , Rome, Italy, September, 2001
[11] Chien, S., Tsotras, V. J., Zaniolo, C. and Zhang, D. "Storing and Querying Multiversion XML Documents Using Durable Node Numbers," in Proceedings of The 2nd International Conference on Web Information Systems Engineering , Kyoto, Japan, 2001 pp.232-
[12] Clifford, J., Croker, A., Grandi, F., and Tuzhilin, A. “ On Temporal Grouping,” in Proceedings Of the International Workshop on Temporal Databases, 1995
[13] Cobena, G., Abiteboul, S., and Marian, A. "Detecting Changes in XML Documents," in Proceedings of the 18th International Conference on Data Engineering, San Jose, CA, February 2002, pp 41-52
[14] Czumaj, A., Finch, I., Gasieniec, L., Gibbons, A., Leng, P. H., Rytter,W. and Zito, M.” Efficient Web Searching Using Temporal Factors,” in Proceedings of Algorithms and Data Structures, 6th International Workshop, Vancouver, British Columbia, Canada, August, 1999, pp. 294-305
[15] Dyreson, C. E. “Observing Transaction-Time Semantics with TTXPath,” in Proceedings of the 2nd International Conference on Web Information Systems Engineering. , Kyoto, Japan, 2001, pp. 193-202
[16] Dyreson, C. E. "Towards a Temporal World-wide Web: A Transaction Time Web Server," in Proceedings of the 12th Australian Database Conference, Queensland, Australia , January 2001 pp.169-175
[17] Grandi, F., Mandreoli, F., Tiberio,P., and Bergonzini, M. "A Temporal Data Model and System Architecture for the Management of Normative Texts," in Proceedings Of the 11th Italian Symposium on Advanced Database Systems, Cetraro, Italy, June 2003, pp. 169-178
[18] Grandi, F., and Mandreoli, F. "The Valid Web: An XML/XSL Infrastructure for Temporal Management of Web Document," in Proceedings of the International Conference on Advances in Information Systems , Izmir, Turkey, October 2000. LNCS 1909
[19] Jin, S. and Bestavros, A. “Temporal Locality in Web Request Streams: Sources, Characteristics, and Caching Implications,” in Proceedings of International Conference on Measurements and Modeling of Computer Systems , Santa Clara, CA, June 2000, pp. 110-111
[20] Kahle, B. and Alexa et al., “The Internet Archive – The Wayback Machine – Surf the Web as it was,” http://www.archive.org/index.html
[21] Marinan, A., Abiteboul, S. and Mignet, L. “Change-Centric Management of Versions in an XML Warehouse,” in Proceedings of the 27th International Conference on Very Large Databases, Roma, Italy, 2001, pp. 581-590
[22] Ng, W.K., Lim, E.P., Huang, C.T., Bhowmick, S.S. and Qin, F.Q. “Web Warehousing: An Algebra for Web Information,” in Proceedings of the IEEE Forum on Research and Technology Advances in Digital Libraries, Santa Barbara, California, USA. April 1998, pp. 228-237.
[23] Nørv°ag, K.. "Temporal Query Operators in XML Databases," in Proceedings of the 17th ACM Symposium on Applied Computing , Madrid, Spain, March, 2002, pp.402-406
[24] Nørvåg, K. "Temporal XML Data Warehouses: Challenges and Solutions," in Proceedings of Workshop on Knowledge Foraging for Dynamic Networking of Communities and Economies, Shiraz, Iran, October 2002.
[25] Nørv°ag, K. "Algorithms for Temporal Query Operators in XML Databases," in Proceedings of Workshop on XML-Based Data Management (XMLDM) (in conjunction with EDBT’2002), Prague, Czech Republic, March 2002 .pp.169-183
[26] Oliboni, B., Quintarelli, E. and Tanca, L. "Temporal Aspects of Semistructured data," in Proceeding of Eigth International Symposium on Temporal Representation and Reasoning, TIME-01 2001, Civdale del Friuli, Italy , June,2001.pp.119-127
[27] Rochkind, M.J. “The Source Code Control System,” IEEE Transactions on Software Engineering, SE-1,4,Dec. 1975, pp.364-370
[28] Shu, H. and Chen, J. "An Algebraic Model of Complex Temporal Objects" International Association for Primate Refuges and Sanctuaries, Vol. 32, Part 4 "GIS-Between Visions and Applications", Stuttgart, 1998
[29] Snodgrass, R. “Temporal Object-Oriented Databases: a Critical Comparison,” Modern Databases Systems: The Object Model, Interoperability and Beyond. Addions-Wesley/ ACM Press, 1995
[30] Tichy, W.F. “RCS – A System for Version Control,” Software–Practice&Experience 15, 7, July 1985, pp.637-654
[31] Wang, F. and Zaniolo, C.. "Preserving and Querying Histories of XML-Published Relational Databases." in Proceedings of the 2nd Intl' Workshop on Evolution and Change in Data Management (ECDM 2002), Tampere, Finland, October 2002. , pp. 26-38
[32] Wang, F. and Zaniolo, C. "Representing and Querying the Evolution of Databases and their Schemas in XML." in Workshop on Web Engineering, Fifteenth International Conference on Software Engineering and Knowledge Engineering,Hotel Sofitel, San Francisco Bay , July, 2003.
[33] Wang, F. and Zaniolo, C. "Temporal Queries in XML Document Archives and Web Warehouses." in Proceedings of the 10th International Symposium on TEMPORAL REPRESENTATION AND REASONING and 4th International Conference on TEMPORAL LOGIC, Cairns, Queensland, Australia, July, 2003
[34] Wang, Y., DeWitt, D.J. and Cai, J. “X-Diff: A Fast Change Detection Algorithm for XML Document,” in Proceedings of the 19th International conference on Data Engineering 2003
[35] Xyleme, Lucie “A Dynamic Warehouse for XML Data of the Web,” IEEE Data Engineering Bulletin, Vol..24, No.2, 2001, pp. 40-47
[36] Zhang, S., Dyreson, C. "Adding Valid Time to XPath," Lecture notes in Computer Science 2544, Proceedings of the International Workshop on Database and Network Information Systems (DNIS), Aizu, Japan, December 2002. pp.29-42