(3.239.33.139) 您好!臺灣時間:2021/03/08 17:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:洪一景
研究生(外文):Yi-Ching Hung
論文名稱:XML資料庫系統之並行控制機制設計
論文名稱(外文):Concurrency Control Design in XML Database Management Systems
指導教授:陳世穎陳世穎引用關係
學位類別:碩士
校院名稱:臺中技術學院
系所名稱:資訊科技與應用研究所
學門:電算機學門
學類:電算機應用學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:中文
論文頁數:49
中文關鍵詞:XML資料庫管理系統鎖定式並行控制機制XPath模型ID/IDREF有向非循環圖形
外文關鍵詞:XML database management systemslock-based concurrency control protocolXPath modelID/IDREFDAG
相關次數:
  • 被引用被引用:0
  • 點閱點閱:170
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
XML為網路上進行資訊交換的重要格式之一。由於XML的發展,使得XML資料庫管理系統(XDBMSs)的發展變得日益重要。XML資料庫管理系統(XDBMSs)可儲存和管理XML文件,並提供使用者對XML文件進行存取。為提升存取效能,XML資料庫管理系統透過並行控制機制的管理,允許多筆交易並行執行。然而,目前雖有許多適用於XML資料庫管理系統的並行控制機制被提出,但這些機制並未考慮到ID/IDREF與XLink的存取行為對並行控制機制的影響。
在存取XML文件時,使用者可透過XPath、ID/IDREF及XLink對XML文件進行查詢及過濾。XPath是以樹狀結構為基礎的路徑查詢語言。ID/IDREF與XLink則可建構節點間的連結關係。一般而言,XPath的存取行為由樹狀結構的根節點開始往葉節點方向進行存取。而ID/IDREF與XLink的存取行為則可透過連結直接連到欲參考的節點或文件進行存取。然而,ID/IDREF與XLink的存取行為可能會產生有向非循環圖(direct acyclic graph, DAG)與迴圈圖形(cyclic graph),造成傳統的並行控制機制無法正常運作。當交易產生有向非循環圖時,ID/IDREF和XLink參考節點的祖先節點不一定先被同筆交易存取過,可能會導致並行交易的執行結果發生錯誤,因此需要新的並行控制機制。另一方面,當交易產生迴圈圖形時,則可能導致死結的發生。
因此,本研究將在XPath存取模型下,分析XPath、ID/IDREF與XLink的存取行為並設計新的鎖定式並行控制機制。本機制將以XML文件的索引結構為鎖定主體,進而迅速取得被參考節點的所有祖先節點的鎖定權限;同時,本機制亦將針對XPath的存取運算,訂定出鎖定模型與鎖定相容矩陣,以解決有向非循環圖與迴圈圖形可能造成的並行執行之資料錯誤。另一方面,本研究亦將建立模擬實驗,觀察本機制的執行效能。


XML is one of the data exchange formats on the internet. Providing efficient access to XML documents, XML database management systems have become more and more important. XML database management systems (XDBMSs) can help users to access and manage XML documents. In XDBMSs, the concurrency control module is one of the most important factors to improve systems efficiency. The concurrency control module allows concurrent execution of transactions. Although many concurrency control protocols for XDBMSs were proposed, no protocols consider the access behaviors of ID/IDREF and XLink.
XPath, ID/IDREF and XLink can be used to query and filter XML documents. XPath is a path query language based on XML tree structures. In general, the access behaviors provided by the XPath language begin from the root node to the leaf nodes. On the other hand, ID/IDREF and XLink can link nodes in the XML document itself or in other XML documents. Therefore, the access behaviors of ID/IDREF and XLink may generate direct acyclic graphs (DAG) or cyclic graphs, which may cause traditional concurrency control protocols fail. In addition, dead locks may frequently occur owing to the access behaviors which form cyclic graphs.
The thesis proposes a new lock-based concurrency control protocol, which considers the access behaviors of XPath, ID/IDREF and XLink in the XPath model. This new protocol locks on the index structures of XML documents. Locking model and lock compatibility matrix are proposed as well. In addition, a simulator is developed for the experimental purpose to evaluate the performance of our protocol.


第一章 緒論 1
1.1 研究背景 1
1.1.1 XML 1
1.1.2 XML資料庫管理系統(XDBMSs) 4
1.1.3 並行控制機制 5
1.2 研究目的與方法 7
1.3 論文架構 8
第二章 相關研究 9
2.1 傳統資料庫之並行控制機制 9
2.1.1 兩階段鎖定協定(Two-phase locking protocol) 9
2.1.2 多層級鎖定協定(Multigranularity locking protocol) 10
2.1.3 圖形鎖定協定(Graph-based locking protocol) 10
2.2 XML資料庫管理系統之並行控制機制 12
2.2.1 DOM模型之並行控制機制 12
2.2.2 DataGuide模型之並行控制機制 14
2.2.3 XPath模型之並行控制機制 16
2.2.4 並行控制機制的鎖定主體 18
第三章 研究問題與分析 19
3.1 符號定義 19
3.2 XPath存取模式分析 21
3.2.1 XPath、ID/IDREF與XLink的存取特性 21
3.2.2 文件內存取模型與跨文件存取模型 22
3.3 XPath的運算衝突分析 24
第四章 並行控制機制設計 27
4.1 建立索引結構 27
4.2 鎖定模型與鎖定相容表 28
4.3 演算法 30
4.4 範例說明 33
第五章 實驗評估 39
5.1 實驗安裝與設計 39
5.2 實驗結果與分析 41
5.2.1並行交易筆數對執行效能之影響 41
5.2.2 mpl對執行效能之影響 41
5.2.3讀寫比率對執行效能之影響 43
5.2.4文件大小對執行效能之影響 43
第六章 結論 45
References 46


[1] R. Agrawal, M. Carey, and M. Livny, “Concurrency Control Performance Modeling: Alternatives and Implications,” ACM Transactions on Database Systems, Vol. 12, No. 4, pages 609-654, 1987.
[2] P. Bernstein, V. Hadzilacos, and N. Goodman, Concurrency Control and Recovery in Database Systems, Addison-Wesley, 1987.
[3] S.-Y. Chen, A High Concurrency Locking Protocol for XPath-based Languages in XML Database Systems, Ph.D. Dissertation, Institute of Computer Science, National Chung-Hsing University, Taiwan, R.O.C., 2006.
[4] J. Clark and S. DeRose, “XML Path Language (XPath) Version 1.0,” World Wide Web Consortium (W3C) Recommendation, 1999; available at http://www.w3.org/TR/XPath.
[5] S. Dekeyser and J. Hidders, “Path Locks for XML Document Collaboration,” Proceedings of the 3rd International Conference on Web Information Systems Engineering, pages 105–114, 2002.
[6] S. Dekeyser and J. Hidders, “A Commit Scheduler for XML Databases,” Proceedings of the 5th Asia Pacific Web Conference, pages 83–88, 2003.
[7] S. Dekeyser and J. Hidders, “Conflict Scheduling of Transactions on XML Documents,” Proceedings of the 15th Australasian Database Conference, pages 395–403, 2004.
[8] S. Dekeyser, J. Hidders, and J. Paredaens, “Instance Independent Concurrency Control for Semistructured Databases,” Proceedings of the 11th Italian Symposium on Advanced Database Systems, pages 323-334, 2003.
[9] S. Dekeyser, J. Hidders, and J. Paredaens, “A Transaction Model for XML Databases,” World Wide Web: Internet and Web Information Systems, Vol. 7, No. 1, pages 29–57, 2004.
[10] S. Dekeyser, J. Hidders, J. Paredaens, and R. Vercammen, “Instance-Independent View Serializability for Semistructured Databases,” ArXiv Computer Science E-prints, 2005, available at http://arxiv.org/abs/cs/0505074.
[11] R. Goldman, J. Widom, DataGuides: Enabling query formulation and optimization in semistructued databases, Proceedings of the 23rd International Conference on VLDB, 1997, pp. 436–455.
[12] T. Grabs, K. Bohmn, and H.-J. Schek, XMLTM: High-Performance XML Extensions for Commercial Database Systems, Technical Report, Institute of Information Systems, University of Mannheim, Germany, 2001.
[13] J. Gray and R. Lorie, “Granularity of Locks in A Large Shared Databases,” Proceeding of the International Conference on Very Large Databases, pages 428-451, 1975.
[14] J. Gray, A. Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, Los Altos, CA, 1993.
[15] M. Haustein and T. Harder, “A Synchronization Concept for The DOM API,” Proceedings of the GI-Workshop, pages 80-84, 2003.
[16] M. Haustein and T. Harder, “Adjustable Transaction Isolation in XML Databases,” Proceedings of the 2nd International XML Database Symposium on Database and XML Technologies, pages 173-188, 2004.
[17] M. Haustein and T. Harder, “A Lock Manager for Collaborative Processing of Natively Stored XML Documents,” Proceedings of the Brazilian Symposium on Databases, pages 230-244, 2004.
[18] M. Haustein, T. Harder, and K. Luttenberger, “Contest of XML Lock Protocols,” Proceeding of the International Conference on Very Large Databases, pages 523-534, 2006.
[19] M. Haustein and T. Harder, “Optimizing Lock Protocols for Native XML Processing,” Data &; Knowledge Engineering, Vol.65, pages 147-173, 2008.
[20] S. Helmer, C.-C. Kanne, and G. Moerkotte, Isolation in XML Bases, Technical Report, TR-2001-015, Department for Mathematics and Computer Science, University of Mannheim, 2001.
[21] S. Helmer, C.-C. Kanne, and G. Moerkotte, “Lock-based Protocols for Cooperation on XML Documents,” Proceedings of Workshop on Web Based Collaboration, pages 230-234, 2003.
[22] S. Helmer, C.-C. Kanne, and G. Moerkotte, “Evaluating Lock-based Protocols for Cooperation on XML Documents,” SIGMOD Record, Vol. 33, No. 1, pages 58-63, 2004.
[23] S. Helmer, C.-C. Kanne, G. Moerkotte, J. Neumann, and R. Schiele, “Natix: A Technology Overview,” Proceedings of the Web and Database-Related Workshops, pages 12-33, 2002.
[24] Y.-F. Huang, An Ascending Order Locking Protocol and Its Performance Evaluation, Ph.D. Dissertation, Institute of Computer &; Decision Science, National Tsing-Hua University, Taiwan, R.O.C., 1988.
[25] K.-F. Jea, S.-Y. Chen, and S.-H. Wang, “Ctabases: XPath Locking Protocol,” Proceedings of he 9th International Conference on Parallel and Distributed Systems, IEEE Computer Society Press, pages 551-556, 2002.
[26] K.-F. Jea and S.-Y. Chen, “A High Concurrency XPath-based Locking Protocol for XML Databases,” Information and Software Technology, Vol.48, No. 8, pages 708-716, 2006.
[27] K.-F. Jea, S.-Y. Chen, and S.-H. Wang, “Locked-based Concurrency Control for XML Document Models,” Proceedings of the 2002 International Computer Symposium, pages 165-172, 2002.
[28] D.-D. Kha, M. Yoshikawa, and S. Uemura, “An XML Indexing Structure with Relative Region Coordinate,” Proceedings of the 17th IEEE International Conference on Data Engineering, pages 313-320, 2001.
[29] H. F. Korth, The Optimal Locking Problem in a Directed Acyclic Graph, Technical Report, Department of Computer Science, Stanford University, Stanford, 1981.
[30] P. Pleshachkov and P. Chardin, “A Locking Protocol for Scheduling Transactions on XML Data,” Proceedings of the Spring Young Researcher’s Colloquium on Database and Information Systems, pages 9-15, 2005.
[31] P. Pleshachkov, P. Chardin, and S. Kuznetsov, “A Locking Based Scheduler for XML Databases,” Proceedings of the Thirteenth Italian Symposium on Advanced Database Systems, pages 356-367, 2005.
[32] P. Pleshachkov, P. Chardin, and S. Kuznetsov, “A DataGuide-Based Concurrency Control Protocol for Cooperation on XML Data,” Proceedings of the 9th Conference on Advances in Databases and Information Systems, pages 268-282, 2005.
[33] A. Silberschatz and Z. Kedemh, “Consistency in Hierarchical Database Systems,” Journal of the ACM, Vol. 27, No. 1, pages 72-80, 1980.
[34] A. Silberschatz, H. Korth, S. Sudarshan, Database System Concepts, Chapter 16, 4th ed., McGraw-Hill, 2001.
[35] W. Zhang, D. Liu, and W. Sun, “XR-Lock: Locking XML Data for Efficient Concurrency Control,” Proceedings of the 5th World Congress on Intelligent Control and Automation, pages 3921-3925, 2004.
[36] 4Suite, http://4Suite.org/index.xhtml.
[37] Document Object Model, http://www.w3.org/DOM
[38] Natix, http://www.data-ex-machina.com/natix.html.
[39] Tamino, http://www.softwareag.com/corporate/products/wm/tamino/
[40] W3C, http://www.w3.org
[41] Xindice, http://xml.apache.org/xindice.
[42] XLink, http://www.w3.org/TR/xlink/
[43] XML Query, http://www.w3.org/TR/xquery/.
[44] XML, http://www.w3.org/XML.
[45] XMark Project, http://www.xml-benchmark.org


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔