XML網頁資料倉儲系統中歷史資料之儲存與查詢

A Way of Storing and Querying Historical Data in an XML Web Warehouse

10.29767/ECS.200509.0002

趙景明(Ching-Ming Chao)；黃仁俊(Jen-Chun Huang)；高顥璋(Hao-Chang Kao)

歷史資料 ； XML ； 網頁資料倉儲 ； Edit Script ； 二進制定址二元樹 ； Historical Data ； XML ； Web Warehouse ； Edit Script ； Binary-Addressing Binary Tree

Electronic Commerce Studies

3卷3期（2005 / 09 / 30）

241 - 264

繁體中文

本研究首先描述XML網頁資料倉儲(XML Web Warehouse)的架構，並提出儲存及查詢其中歷史資料的方法。我們利用物件導向技術，將XML網頁資料的每一個元素視為一個物件(Object)加以處理，並將XML網頁資料視為一個樹狀結構；我們接著獨立出時間資料，利用版本與時間對應的方式，將每一份XML網頁資料的版本狀態延伸至每一個元素。在歷史資料部分，我們採用Edit Script的方式儲存各個元素版本的內容，僅將元素各版本間變動的演進部分予以紀錄，以節省更多的儲存空間。一般在Edit Script的研究上，可分為時序漸進式，如RCS、SCCS等；以及索引編排式，如DNN等。其共同的缺點在於，取得某個版本的資料需要花費龐大的計算量。故此，本研究主要沿續此一大方向，首先提出狹義及廣義的網頁資料倉儲的概念及架構，接著提出以二進制定址二元樹的編碼方式編寫Edit Script，以增加Edit Script的效率。本研究繼而針對網頁資料倉儲一般的歷史資料查詢，提出所需的運算子，並據以編寫對應的演算法。

In this article, we proposed a way of storing and querying historical data in an XML Web Warehouse. First, we treat every element and all its versions in an XML document as objects in a tree structure, while the temporal aspect of every object was compiled as a whole. Edit Script was used to store the change between versions. Following the course of other researchers, we constructed the ”Binary-Addressing Binary Tree” to store the Edit Script. Then we proposed the Operators and algorithms to implement historical querying in the Warehouse.

1. Chien, Shu-Yao,Vassilis J. Tsotras,Carlo Zaniolo(2001).Copy-Based versus Edit-Based Version Management Schemes for Structured Documents.International Workshop on Research Issues on Data Engineering.
2. Chien, Shu-Yao,Vassilis J. Tsotras,Carlo Zaniolo,Donghui Zhang(2001).Storing and Querying Multiversion XML Documents Using Durable Node Numbers.The 2nd International Conference on Web Information Systems Engineering
3. Czumaj, Artur,Ian Finch,Leszek Gasieniec,Alan Gibbons,Paul Leng(1999).Algorithms and Data Structures, 6th International Workshop.Vancouver, British Columbia, Canada:
4. Jin, Shudong,Azer Bestavros(2000).Temporal Locality in Web Request Streams: Sources, Characteristics, and Caching Implications.Proceedings of International Conference on Measurements and Modeling of Computer Systems,Santa Clara, CA:
5. The Internet Archive-The Wayback Machine-Surf the Web as it was
6. Lucie Xyleme(2001).A Dynamic Warehouse for XML Data of the Web.IEEE Data Engineering Bulletin,24(2),40-47.
7. Marinan, Amelie,Serge Abiteboul,Laurent. Mignet(2001).Change-Centric Management of Versions in an XML Warehouse.Proceedings of the 27th International Conference on Very Large Databases
8. Ng, Wee-Keong,Ee-Peng Lim,Chee-Thong Huang(1998).Santa Barbara.California, USA:
9. Nørv°ag, Kjetil(2002).Algorithms for Temporal Query Operators in XML Databases.Proceedings of Workshop on XML-Based Data Management (XMLDM) (in conjunction with EDBT'2002), Prague, Czech Republic,March,169-183.
10. Oliboni, Barbara,Elisa Quintarelli,Letizia Tanca(2001).Temporal Aspects of Semistructured data, Proceeding of Eigth International Symposium on Temporal Representation and Reasoning.Civdale del Friuli, Italy,June,119-127.
11. Oliver, Ian(1993).Programming Classics.Australia:Prentice Hall.
12. Rochkind, Marc J.(1975).The Source Code Control System.IEEE Transactions on Software Engineering,Dec,364-370.
13. Shu, Hong,Jun Chen(1998).An Algebraic Model of Complex Temporal Objects International Association for Primate Refuges and Sanctuaries.GIS-Between Visions and Applications,32(4)
14. Tichy, Walter F.(1985).RCS-A System for Version Control.Software-Practice & Experience,15(7),637-654.
15. Wang, Fusheng,Carlo Zaniolo(2003).Temporal Queries in XML Document Archives and Web Warehouses.Proceedings of the 10th International Symposium on TEMPORAL REPRESENTATION AND REASONING and 4th International Conference on TEMPORAL LOGIC, Cairns,Queensland, Australia:
16. Zhang, Shuohao,Curtis E.(2002).Proceedings of the International Workshop on Database and Network Information Systems, Aizu.Japan:
17. 趙景明、高顥璋(2004)。以物件導向樹狀結構儲存XML網頁資料倉儲之歷史版本資料。第五屆電子化企業經營管理理論暨實務研討會論文集，台灣·彰化: