快取記憶體管理機制最主要的優點就是能夠縮短使用者查詢的執行時間，目前已有一些相關的研究被發表出來。然而儘管延伸式標籤語言資料庫變的越來越普遍，可是將快取記憶體管理機制運用到延伸式標籤語言資料庫的研究仍是相當有限，所以本研究提出了運用在延伸式標籤語言資料庫上的一個新的快取記憶體管理機制，我們稱之為SPIP( Sequential- Pattern and Interest-Interval Prediction ) 。
這個SPIP機制可分成兩個主要部分：1.探勘機制：從使用者的查詢記錄檔中透過資料探勘的技術去發掘使用者有興趣的規則。2.預測快取機制：將使用者最常查詢的問題答案和我們所發現的有趣規則其所代表的答案預先載入到快取記憶體中。透過實驗的評估我們可以發現SPIP不論是在命中率或是不同系統狀況下的執行時間均比其他的快取機制如LRU都優良。

The main advantages of cache management policies are the response time to an user’s query can be shorten and a number of relevant studies have been proposed. However, the researches on integrating cache management policies into XML database systems are still very limited despite that XML databases have become more and more popular. This research presents a new cache memory replacement policy named SPIP (Sequential-Pattern and Interest-interval Prediction) for XML databases.
The SPIP policy consists of two main components: 1) The mining method that uses a data mining technique to discover the user’s interesting rules from the user query log, 2) The predictive caching policy which preload into cache memory the results of the query the user is most likely to ask based on the current user query and the discovered interesting rules. Through experimental evaluation, SPIE was shown to perform better than other caching policies like LRU in terms of the cache hit ratio and the query response time under various system conditions.

[1] S. Abiteboul. Querying semistructured data. In Proceedings of the International Conference on Database Theory, January 1997.
[2] S. Abiteboul, R.Goldman, J.McHugh, V. Vassalos, and Y.Zhuge. Views for semistructured data. In Proceedings of the Workshop on Management of Semistructured Data. May,1997.
[3] Alan Jay Smith, “Cache Memories”. ACM Computing Surveys (CSUR) Volume 14 , Issue3(September 1982) , pp. 473 - 530 . IEEE/ACM Transactions on Networking, Vol. 8, No. 2, 2000, pp.158-170.
[4] S. Abiteboul, D. Quass, J. McHung, J.Widom and J. Wiener. The Lorel Query Language for Semistructured Data. Joutnal of Digital Libraries. November 1996.
[5] R. Agrawal, R. Srikant. “Fast Algorithm for Mining Association Rules.” Proc. Of the 20th Very Large Data Bases (VLDB-94), pp.487-499, Santiago, Chile, 1994.
[6] R. Agrawal and R. Srikant, “Mining Sequential Patterns.” In Proc. of the 11th Int’l Conference on Data Engineering, Taipei, Taiwan, March 1995
[7] F. Bancilhon, C.Delobel, and P.Kanellakis, editors. Building an Object-Oriented Database Sysyem : The Story of O2. 1992
[8] D. W. Cheung, J. Han, V. T. Ng, and C. Y. Wong. “Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique.” In Proc. of the International Conference on Data Engineering, pages 106-114, 1996.
[9] P. Cao and S. Irani, “GreedyDual-size: A cost-aware WWW proxy caching algorithm.” Proc. of USENIX Symposium on Internet Technology and Systems, 1997, pp.165-173.
[10] X. Du, Z. Liu and N. Ishii “Discovering of User-Interests from Range Queries.” Proc. of the 9th Int’l Conference on Database and Expert Systems Applications (DEXA), Vienna, Austria, August, 1998.
[11] K.-S. Fu, Y. T. Chen, and G. P. Cardillo, “A dynamic programming approach to sequential pattern recoginition” IEEE Trans. Part. Anal. Mach. Intell., vol. PAMI-8, no. 3, pp. 313-326, 1986.
[12] R.G.G. Cattell. The Object Database Standard: ODMG-93. Morgan Kaufmuann,1994
[13] M. N. Garofalakis, R. Rastogi, and k. Shim, “SPIRIT: Sequential Pattern Mining with Regular Expression Constraints”, Proc. of 25th International Conference on Very Large Databases, pp. 223~234, September, 1999.
[14] R. Goldman and J. Widom. DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. Proceedings of the Twenty-Third International Conference on Very Large Data Bases, pages 436-445, Athens,Greece,
August 1997.
[15] Jiawei Han, Jian Pei, Behzad Mortazavi-Asl, et. al, “FreeSpan: frequent pattern-projected sequential pattern mining.” Proc. of the 6th ACM SIGKDD nt’l Conference on Knowlwdge discovery and data mining (KDD), Boston, Massachusetts, United States,2000.
[16] Han, J., Pei, J., Mortazavi-Asl, B., Chen, Q., Dayal, U. and Hsu, M.-C. “Frequent pattern projected sequential pattern mining”, In proc. 2000 Int. Conf. Knowledge Discovery and Data mining (KDD) 355-359, Boston, MA, August 2000.
[17] M.Kifer, W.Kim, and Y.Sagiv. Querying object-oriented databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data, June 1992.
[18] D. Lee, et al., ”On the Existence of a Spectrum of Policies the Subsumes LRU,LFU Policies.” Proc. of ACM SIGMETERICS Conference,1999.
[19] Yi Li, Kevin Lü, “Performance Issues of a Web Databae”. In Proceedings of the 11th International Conference on Database and Expert Systems Applications, London, UK, September 4-8, 2000, pp. 825-834.
[20] Jason McHugh, Serge Abiteboul, Roy Goldman, Dallan Quass, Jennifer Widom. Lore: A Database Management System for semistructured Data. SIGMOD Record, 26(3): 54-66, September 1997.
[21] J. Melton and A.R. Simon. Understanding the New SQL: A Complete Guide. 1993
[22] Y. Papakonstantinou, II. Garcia-Molina, and J. Widom, “Object exchange across heterogeneous information sources.” Prof. of the 11th Int’l Conference on Data Engineering, pp.251-260, Taipei, Taiwan, March 1995.
[23] John T. Robinson, Murthy V. Devarakonda, “Data cache management using frequency-based replacement”, In Proceedings of the ACM conference on Measurement and modeling of computer systems, Univ. of Colorado, Boulder,
Colorado, United States, 1990, pp134 – 142.
[24] L. Rizzo and L. Vicisano, “Replacement Policies for a Proxy Cache.”
[25] R. Srikant and R.Agrawal. “Mining Sequential Patterns: Generalizations and Performance Improvements”. Research Report RJ9994, IBM Almade Research Center, San Jose, California, December 1995.
[26] R. Srikant and R. Agrawal, “Mining Sequential Patterns: Generalizations And Performance Improvements.” Proc. of the 5th Int'l Conference on Extending
Database Technology (EDBT), Avignon, France, March 1996.
[27] Dongwook Shin, Hyuncheol Jang and Honglan Jin. BUS: an effective indexing and retrieval scheme in structured documents. Proceedings of the third ACM Conference on Digital libraries. June 23 - 26, 1998
[28] Anthony K. H. Tung, Y. C. Tay and Hongjun Lu, “BROOM: Buffer Replacement using Online Optimization by Mining”, In Proceedings of the 7th International Conference on Information and Knowledge Management,
Bethesda, Maryland, USA, November 3-7, 1998, pp.185-192.
[29] Li-Cheng Wu, Jorng-Tzong Horng, Baw-Jhiune Liu, Chin-Yea Wang, Gwo-Dong Chen. Indexing Semistructured Data Using PATRICIA Tree. DEXA 2000: 859-868
[30] Mohammed J. Zaki, ” Efficient Enumeration of Frequent Sequences.” Proc. Of the 7th Int’l Conference on Information and Knowledge Management (CIKM),Bethesda, Maryland, USA, November, 1998.
[31] Mohammed J. Zaki, “Sequence mining in categorical domains: incorporating constraints.” Proc. of the 9th Int’l Conference on Information and Knowledge Management (CIKM), McLean, Virginia, United States, 2000
[32] W3C, “Extensible Markup Language ( XML ) 1.0 Recommendation”, http://www.w3c.org/TR/1998/REC-XML-19980210.html, February 1998.
[33] W3C, “HTML 4.01 Specification”, http://www.w3c.org/TR/html401, December 1999.
[34] 許毅嘉, “關聯法則應用於代理伺服器上之快取置換機制”, 碩士論文, 國立中興大學資訊科學研究所, 中華民國, 2001.
[35] 陳桂惠, “WWW代理伺服器的部份快取置換策略”, 碩士論文, 元智大學資訊工程研究所, 中華民國, 2000.
[36] 林昇慶, “XML文件資料庫系統”, 碩士論文, 國立台灣大學資訊工程研究所, 中華民國, 2001.
[37] 方乃騏, “Generalizing Sequential Pattern Discovery: Signed and Quantitative Sequential Patterns”, 碩士論文, 中山大學, 中華民國,1999.
[38] 方世榮, “統計學導論二版”,華泰書局,1995.
[39] 何淑媛, “XML與軟體代理人於電子資料交換之應用研究”, 碩士論文, 逢甲大學資訊工程研究所, 中華民國, 2002.