Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19392
標題: 支援XPath語言的高並行性XML資料庫系統鎖定機制
A High Concurrency Locking Protocol for XPath-based Languages in XML Database Systems
作者: 陳世穎
Chen, Shih-Ying
關鍵字: XML document databases
XML文件資料庫
concurrency control
locking protocol
XPath
XUpdate
light-weighted locks
conflict analysis
並行控制
鎖定式協定
XPath模型
XUpdate語言
輕量化鎖定
存取衝突分析
出版社: 資訊科學系所
引用: [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] K. Chakrabarti and S. Mehrotra, “Dynamic Granular Approach to Phantom Problem Protection in R-Trees,” Proceedings of International Conference on Data Engineering, pages 223-234, 2003. [4] E.-H. Choi and T. Kanai, “XPath-based Concurrency Control for XML Data,” Proceedings of the 14th Data Engineering Workshop, pages 302-313, 2003. [5] Y. Choi and S. Moon, “Lightweight Multigranularity Locking for Transaction Management in XML Database Systems,” Journal of Systems and Software, Vol. 78, Issue 1, pages 37-46, 2005. [6] 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. [7] 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. [8] S. Dekeyser and J. Hidders, “A Commit Scheduler for XML Databases,” Proceedings of the 5th Asian-Pacific Web Conference, pages 83-88, 2003. [9] S. Dekeyser and J. Hidders, “Conflict Scheduling of Transactions on XML Documents,” Proceedings of the 15th Australasian Database Conference, pages 395-403, 2004. [10] 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. [11] 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. [12] 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. [13] K. Eswaran, J. Gray, R. Lorie, and I. Traiger, “The Notions of Consistency and Predicate Locks in a Database System,” Communications of the ACM, Vol. 19, No. 11, pages 624-633, 1976. [14] H. Garcia-Molina, J. Ullman, and J. Windom, Database Systems: The Complete Book, Prentice Hall, 2002. [15] R. Goldman and J. Widom, “DataGuides: Enabling Query Formulation and Optimization in Semistructued Databases,” Proceedings of the 23rd International Conference on VLDB, pages 436-455, 1997. [16] 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. [17] 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. [18] J. Gray, R. Lorie, G. Putzolu, and I. Traiger, “Granularity of Locks and Degrees of Consistency in a Shared Database,” Readings in Database Systems, 2nd ed., Morgan Kaufmann Publishers, pages 181-208, 1994. [19] J. Gray and A. Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1993. [20] M. Haustein and T. Harder, “taDOM: A Tailored Synchronization Concept with Tunable Lock Granularity for The DOM API,” Proceedings of the 7th Conference on Advances in Databases and Information Systems, pages 88-102, 2003. [21] 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. [22] 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. [23] M. Haustein and T. Harder, “A Synchronization Concept for The DOM API,” Proceedings of the GI-Workshop, pages 80-84, 2003. [24] 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. [25] 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. [26] 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. [27] 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. [28] S. Helmer, T. Fiebig, 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. [29] 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. [30] 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. [31] K.-F. Jea, S.-Y. Chen, and S.-H. Wang, “Concurrency Control in XML Document Databases: XPath Locking Protocol,” Proceedings of the 9th International Conference on Parallel and Distributed Systems, IEEE Computer Society Press, pages 551-556, 2002. [32] 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. [33] 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. [34] H. Korth, “Deadlock Freedom Using Edge Locks,” ACM Transactions on Database System, Vol. 7, No. 4, pages 632-652, 1982. [35] H. Korth, “Locking Primitives in a Database System,” Journal of the ACM, Vol. 30, No. 1, pages 55-79, 1983. [36] S.-Y. Lee and R.-L. Liou, “A Multi-granularity Locking Model for Concurrency Control in Object-oriented Database Systems,” Proceedings of the 2nd FAR-FAST Workshop on Future Database Systems, pages 158-167, 1992. [37] P. Lewis, A. Bernstein, and M. Kifer, Databases and Transaction Processing, 1st ed., Addison Wesley, 2001. [38] 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. [39] P. Pleshachkov, P. Chardin, and S. Kuznetsov, “XDGL: XPath-Based Concurrency Control Protocol for XML Data,” Lecture Notes in Computer Science, Vol. 3567, pages. 145-156, 2005. [40] 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. [41] 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. [42] R. Ramakrishnan and J. Gehrke, Database Management Systems, 2nd ed., McGraw-Hill, 2000. [43] A. Silberschatz and Z. Kedemh, “Consistency in Hierarchical Database Systems,” Journal of the ACM, Vol. 27, No. 1, pages 72-80, 1980. [44] A. Silberschatz, H. Korth, and S. Sudarshan, Database System Concepts, Chapter 16, 4th ed., McGraw-Hill, 2001. [45] K.-M. Win, W.-K. Ng, Q. Liu, and E.P. Lim, “XStamps: a Multiversion Timestamps Concurrency Control Protocol for XML Data,” Proceedings of the Joint Conference of the 4th International Conference on Information, Communications and Signal Processing, and the 4th Pacific Rim Conference on Multimedia, pages 1650-1654, 2003. [46] M. Yannakakis, “Serializability by Locking,” Journal of the ACM, Vol. 31, No. 2, pages 227-244, 1984. [47] 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. [48] 4Suite, http://4suite.org/index.xhtml. [49] Berkeley DB XML, http://www.sleepycat.com/products/xml.shtml. [50] DB2, http://www-306.ibm.com/software/data/. [51] dbXML, http://www.dbxmlgroup.com/. [52] Document Object Model, http://www.w3.org/DOM. [53] ebXML, http://xml.coverpages.org/ebXML.html. [54] Java XPath API, http://www.ftponline.com/channels/java/2005_01/kjones_01_14_05/ default_pf.aspx. [55] MathML, http://www.w3.org/Math/. [56] Natix, http://www.data-ex-machina.com/natix.html. [57] Ozone, http://www.ozone-db.org/. [58] Tamino, http://www.softwareag.com/corporate/products/tamino. [59] ToX: Toronto XML Server, http://www.cs.toronto.edu/tox/. [60] World Wide Web Consortium, http://www.w3c.org. [61] Xindice, http://xml.apache.org/xindice. [62] XML, http://www.w3.org/XML. [63] XMark Project, http://www.xml-benchmark.org/. [64] XML Query, http://www.w3.org/XML/Query. [65] XPath, http://www.w3.org/TR/XPath.html. [66] XPath API, http://lists.xml.org/archives/xml-dev/200103/msg00178.html. [67] XPath API, http://lists.w3.org/Archives/Public/www-dom-xpath. [68] XPointer and XLink, http://www.w3.org/XML/Linking. [69] XQuery Update Facility, http://www.w3.org/TR/xqupdate/. [70] XSLT, http://www.w3.org/TR/2005/WD-xslt20-20050404. [71] XUpdate, http://xmldb-org.sourceforge.net/xupdate/.
摘要: 由於XML資料庫管理系統能有效儲存與查詢XML文件,且越來越多應用以XML格式表示其文件,因此XML資料庫管理系統越顯重要。對於支援XML文件之讀取、寫入、新增、刪除、更名等操作,目前以XPath文件模型為基礎的XUpdate查詢語言最廣為使用。另一方面,為了提升系統效能,資料庫管理系統常採用並行控制技術讓交易得以並行執行,並保證資料的一致性。當使用XUpdate語言存取XML文件時,除了傳統資料庫系統會發生的資料值存取衝突外,交易間也可能產生文件結構及元素順序上的存取衝突。因此,XML資料庫管理系統上的並行控制協定必須解決這三類的存取衝突,以保證並行的交易必產生正確的資料。目前雖然有許多適用於XML資料庫管理系統的並行控制協定被提出,但尚無以XUpdate語言為基礎的協定。本論文提出一個鎖定式並行控制協定,稱為XUpdate Locking Protocol (XULP)。XULP是一個高並行性的控制協定,可解決XML資料庫管理系統中資料值、文件結構、和元素順序的存取衝突。為了達到高並行性的目標,XULP協定提供豐富的鎖定模式、輕量化的鎖定(P-locks)、以及提前釋放鎖定的機制。本論文亦提出另外一種適用於較簡單之XML應用的鎖定式並行控制協定XPath Locking Protocol (XLP)。XULP與XLP協定均可產生序列化的交易結果,以保證資料的一致性。本論文設計了模擬實驗,用於觀察XULP之效能,並比較XULP與另外兩種並行控制協定:PL-PROP與XR-Lock。
XML database management systems (XDBMSs) have gained a lot of attention owing to the great demand for efficient access to XML documents. To improve system performance, concurrency control techniques are employed to execute transactions concurrently. On the other hand, XUpdate, which addressed data based on the XPath model, is one of the most important query languages supporting manipulation operations on XML documents. Although an increasing number of concurrency control protocols for XDBMSs were proposed, no protocols deal with the XUpdate language. In addition to traditional data-value conflicts, XUpdate introduces two new types of conflicts on XML documents, i.e., conflicts on document structures and element orders. Concurrency control protocols for XDBMSs must resolve these three types of conflicts. Our research is motivated by a need of high concurrency protocol based on XUpdate for XDBMSs and a necessity of resolving the data-value, structural, and element-order conflicts on XML documents. We thus propose a lock-based concurrency control protocol, namely XULP. XULP has the features of rich lock modes, light-weighted locks (P-locks), and early release of locks to achieve high concurrency. Another lock-based protocol XLP is also proposed for simpler XML applications. Both XULP and XLP ensure conflict serializability. Simulation experiments on the performance of XULP and that between XULP, PL-PROP, and XR-Lock protocols are illustrated in this study.
URI: http://hdl.handle.net/11455/19392
其他識別: U0005-2707200623020100
文章連結: http://www.airitilibrary.com/Publication/alDetailedMesh1?DocID=U0005-2707200623020100
Appears in Collections:資訊科學與工程學系所

文件中的檔案:

取得全文請前往華藝線上圖書館

Show full item record
 
TAIR Related Article
 
Citations:


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.