XML資料庫系統之並行控制機制設計

Concurrency Control Design in XML Database Management Systems

洪一景(Yi-Ching Hung)

指導教授 ： 陳世穎

國立臺中科技大學/資訊學群/資訊科技與應用研究所/碩士(2010年)

https://doi.org/10.6826/NUTC.2010.00027

摘要

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資料庫管理系統 ； 鎖定式並行控制機制 ； XPath模型 ； ID/IDREF ； 有向非循環圖形

並列摘要

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.

並列關鍵字

XML database management systems ； lock-based concurrency control protocol ； XPath model ； ID/IDREF ； DAG

參考文獻

[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.

[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.

[19] M. Haustein and T. Harder, “Optimizing Lock Protocols for Native XML Processing,” Data & Knowledge Engineering, Vol.65, pages 147-173, 2008.

[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.