臺灣博碩士論文加值系統

在網際網路的應用上，快取的資料對於查詢處理的效能扮演重要的角色。目前大部分的研究皆針對快取管理的問題加以探討，至於XML資料的快取維護問題並未有相關的研究。本研究提出以堆疊為基礎的快取更新維護策略，將產生的中間查詢結果儲存於堆疊結構之中，而依照各堆疊之間所建立的指標導引，以便將查詢結果取出。當XML來源資料庫更新時，代理伺服器（proxy）便能依照傳回的更新路徑，直接維護快取中的查詢堆疊結構，而無需返回來源資料庫取得其他任何資訊或者重建整個代理伺服器的資料。因此，本研究的貢獻為（1）支援XML單支和分支（twig）查詢處理。（2）加速使用者查詢效率。（3）節省快取的儲存空間。（4）能漸進地維護快取的資料。

In Web applications, cached data plays an important role in improving the performance of query processing. Extensive research has addressed the problem of cache management but only few have studied the problem of incremental cache maintenance for XML data. In this thesis, a new method is proposed to maintain cached XML data using a stack-based query processing scheme, which stores intermediate query results in a sequence of stacks. The stacks along with a pointer structure can preserve the relationships among the elements that are selected by the query. When an update operation occurs on the source XML data, the information about the updated path is sent to the proxy server where the proposed method can adjust the stacks and pointers accordingly so that the update can be accommodated in the cache. It is not necessary to return to the source database to capture more information, or to rebuild the query structures in the proxy. The contributions of this research can be summarized as: (1) Supporting both path and twig XML queries, (2) Improving query performance, (3) Reducing the storage size, and (4) Incrementally maintaining the cache.

摘要 i
Abstract ii
誌謝 iii
第一章 簡介 1
1.1 研究動機、背景與目的 1
1.2 論文架構 4
第二章 相關研究 5
2.1 View的更新維護處理 5
2.2傳統以堆疊為基礎的XML文件查詢方法 9
2.3 XML快取相關研究 12
第三章 以堆疊為基礎的XML查詢處理方法 14
3.1 單一路徑查詢處理 14
3.2 分支路徑查詢處理 21
第四章 XML快取更新維護 24
4.1 XML來源資料更新 24
4.2單一路徑查詢之漸進式快取維護處理 27
4.2.1 單一路徑查詢之漸進式快取維護演算法 27
4.2.2 漸進式快取維護之新增運算模組 32
4.2.3 漸進式快取維護之刪除運算模組 43
4.3分支路徑查詢之漸進式快取維護處理 52
4.3.1 漸進式分支快取維護之新增處理 52
4.3.2 漸進式分支快取維護之刪除處理 62
第五章 實驗評估 71
5.1實驗環境與設定 71
5.2單一路徑查詢處理之查詢時間實驗 73
5.2.1 實驗數據結果 74
5.2.2 實驗數據分析 77
5.3單一路徑查詢處理之快取維護時間實驗 79
5.3.1 實驗數據結果 80
5.3.2 實驗數據分析 83
5.4單一路徑查詢處理之累計查詢時間實驗 85
5.4.1 實驗數據結果 86
5.4.2 實驗數據分析 92
第六章 結論與未來研究 94
6.1結論 94
6.2討論與未來研究 95
參考文獻 97

[1] S. Abiteboul, J. McHugh, M. Rys, V. Vassalos, and J. L. Wiener, “Incremental maintenance for materialized views over semistructured data,” in Proc. of VLDB Conference, 1998.

[2] S. Al-Khalifa, H. V. Jagadish, N. Koudas, J. M. Patel, D. Srivastava, and Y. Wu, “Structural joins: A primitive for efficient XML query pattern matching,” in Proc. of Intl. Conf. on Data Engineering, 2002.

[3] M. Arlitt, L. Cherkasova, J. Dilley, R. Friedrich, and T. Jin, “Evaluating content management techniques for Web proxy caches,” in Proc. of the Workshop on Internet Server Performance, 1999.

[4] F. Bancilhon and N. Spyratos, “Update semantics of relational views,” in ACM Transactions on Database Systems, pages 557–575, Dec 1981.

[5] N. Bruno, N. Koudas, and D. Srivastava, “Holistic twig join: Optimal XML pattern matching,” in Proc. of the 2002 ACM SIGMOD Intl. Conf. on Management of Data, 2002.

[6] N. Bruno, L. Gravano, N. Koudas, and D. Srivastava, “Navigation- vs. index-based XML multi-query processing,” in Proc. of Intl. Conf. on Data Engineering, 2003.

[7] D. Calvanese, G. D. Giacomo, M. Lenzerini, and M. Y. Vardi, “View-based query processing for regular path queries with inverse,” in Proc. of ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000.

[8] Y. H. Chen and M. C. Ho, “Aggregate query processing of streaming XML data,” in Proc. ICS Conference, 2004.


[9] B. Chidlovskii and U. M. Borghoff, “Semantic caching of Web queries,” VLDB Journal, 9(1), 2-17, 2000.

[10] S. S. Cosmadakis and C. H. Papadimitriou, “Updates of relational views,” Journal of the Association for Computing Machinery, pages 742–760, Oct 1984.

[11] S. Dar, M. J. Franklin, B. T. Jónsson, D. Srivastava, and M. Tan, “Semantic data caching and replacement,” in Proc. of VLDB Conference, 1996.

[12] K. Dimitrova, M. El-Sayed, and E. A. Rundensteiner, “Order-sensitive view maintenance of materialized XQuery views,” in Proc. ER Conference, 2003.

[13] M. C. Ho, Efficient evaluation of XPath queries on streaming XML data, Master Thesis. Department of Computer Science and Information Engineering, National Chiayi University, 2005.

[14] S. Irani, “Page replacement with multi-size pages and applications to Web caching,” in Proc. of the ACM Symposium on the Theory of Computing, 1997.

[15] S. Jin and Z. Bestavros, “Popularity-aware greedy dual-size Web proxy caching,” in Proc. of the Intl. Conference on Distributed Computing Systems, 2000.

[16] H. Kang, S. Han, and Y. Kim, “Scheme of storing XML query cache,” in Proc. of ADC Conference on Information Technology, Vol. 39, 2005.

[17] Y. Kanza, W. Nutt, and Y. Sagiv, “Queries with incomplete answers over semistructured data,” in Proc. of ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems, 1999.

[18] F. Lam, W. M. Shui, D. K. Fisher, and R. K. Wong, “Skipping strategies for efficient structural joins,” in Proc. of the ACM 13th Conference on Information and Knowledge Management (CIKM), 2004.


[19] H. Liefke and S. B. Davidson, “View maintenance for hierarchical semistructured data,” in Proc. DaWaK Conference, 2000.

[20] J. Lu, T. Chen, and T. W. Ling, “Efficient processing of XML twig patterns with parent child edges: A look-ahead approach,” in Proc. of the ACM 13th Conference on Information and Knowledge Management (CIKM), 2004.

[21] T. Malik, R. Burns, and A. Chaudhary, “Bypass caching: Making scienticfic databases good network citizens,” in Proc. of Intl. Conf. on Data Engineering, 2005.

[22] P. J. Marron and G. Lausen, “Efficient cache answerability for XPath queries,” in Proc. DIWeb International Workshop, 2002.

[23] Y. Papakonstantinou and V. Vassalos, “Query rewriting for semistructureddata,” in Proc. of ACM SIGMOD International Conference, 1999.

[24] L. Quan, L. Chen, and E. A. Rundensteiner, “Argos: Efficient refresh in an XQL-based Web caching system,” in Proc. WebDB Conference, 2000.

[25] A. Sawires, J. Tatemura, O. Po, D. Agrawal, and K. S. Candan, “Incremental maintenance of path-expression views,” in Proc. ACM SIGMOD International Conference on Management of Data, 2005.

[26] L. Wang, E. A. Rundensteiner, and M. Mani, “Updating XML views,” in Proc. Of VLDB Conference, 2005.

[27] L. Wang, E. A. Rundensteiner, and M. Mani, “U-Filter: A lightweight XML view update checker,” in Proc. of VLDB Conference, 2005.

[28] L. H. Yang, M. L. Lee, and W. Hsu, “Efficient mining of XML query patterns for caching,” in Proc. of VLDB Conference, 2003.

[29] C. Zhang, J. Naughton, D. DeWitt, Q. Luo, and G. Lohman, “On supporting containment queries in relational database management systems,” in Proc. of the 2001 ACM SIGMOD Intl. Conf. on Management of Data, 2001.

[30] Y. Zhuge and H. Garcia-Molina, “Graph structured views and their incremental maintenance,” in Proc. of Intl. Conf. on Data Engineering, 1998.

[31] J. Clark and S. DeRose, XML Path Language (XPath) version 1.0 W3C recommendation, (1999). Available: http://www.w3.org/TR/xpath.html

[32] W3C Recommendation, “XML Path Language (XPath) Version 2.0,” 2005. Available: http://www.w3.org/TR/2005/WD-xpath20-20050404