臺灣博碩士論文加值系統

　　由於網際網路普及，XML文件的應用愈來愈普遍，如何增進XML文件存取效能已成為現今重要的研究方向。並行控制是資料庫系統中改善效能最重要的方法之一，然而目前的並行控制機制大多以關聯式資料庫及物件導向資料庫為基礎，較少針對XML文件資料庫所設計的並行控制機制。
　　本研究提出二套適用於XML文件資料庫的並行控制機制：XLP與EXLP。XLP以鎖定法及XPath定址語言為基礎，針對存取XML文件的交易之指令動作設計出合適的鎖定模式，藉以提高交易間的並行程度。EXLP延續XLP之基本精神，同時以預先解析交易定址結果的方式，重新排列資料項鎖定順序，預防交易間死結現象的發生。
　　本論文證明XLP與EXLP均滿足serializability特性，並與傳統的鎖定式並行控制機制做一分析與比較。為求客觀性，我們同時作模擬實驗，實驗結果顯示，XLP與EXLP在不同環境的XML文件資料庫中均能獲得較高的並行程度。

1. 導論 1
2. 相關研究 5
2.1. XML（Extensible Markup Language）簡介 5
2.1.1. XML文件 5
2.1.2. XML Path Language (XPath) 7
2.2. 鎖定式並行控制機制 12
2.2.1. Two-Phase Locking Protocol 12
2.2.2. Tree Locking Protocol 14
2.2.3. Multiple Granularity Locking Protocol 16
2.2.4. 死結 18
2.3. 其它應用於XML之並行控制機制 20
3. XML文件資料庫之並行控制 23
3.1. 研究動機與目的 23
3.2. 方法及構想 26
4. XPath Locking Protocol (XLP) 28
4.1. 目標節點與過程節點 28
4.2. XLP鎖定模式 29
4.3. XLP存取規則 31
4.4. 舉例說明 32
5. Extended XPath Locking Protocol (EXLP) 35
5.1. 重組交易鎖定順序 35
5.2. EXLP鎖定模式 36
5.3. EXLP存取規則 38
5.4. 舉例說明 40
6. 分析與比較 43
6.1. XLP之正確性證明 43
6.2. EXLP之正確性證明 45
6.3. 綜合分析及比較 50
6.3.1. XLP之優缺點 50
6.3.2. EXLP之優缺點 51
6.3.3. XLP、EXLP與其它並行控制機制比較 53
7. 模擬實驗與分析 56
7.1. 實驗環境 56
7.2. 實驗方法 56
7.3. 模擬實驗與結果分析 59
7.3.1. 「XML文件大小」對效能之影響 60
7.3.2. 「交易中指令read/write比值」對效能之影響 62
7.3.3. 「死結發生與否」對效能之影響 64
7.4. 實驗結論 69
8. 結論與未來方向 70
參考文獻 72

[1]R. Agrawal and D. Dewitt, “Integrated Concurrency Control and Recovery Mechanisms: Design and Performance Evaluation,” ACM Transactions on Database Systems, Vol. 10, No. 4, pp. 529-564, 1985.
[2]P. Bernstein, V. Hadzilacos and N. Goodman, Concurrency Control and Recovery in Database System, Addison-Wesley, 1987.
[3]P. Bernstein, D. Shipman and W. Wong, “Formal Aspects of Serializability in Database Concurrency Control,” IEEE Transactions on Software Engineering, Vol. 5, No. 3, pp. 203-216, 1979.
[4]J. Clark and S. DeRose, “XML Path Language (XPath) Version 1.0,” World Wide Web Consortium (W3C) Recommendation, Nov. 1999; available at http://www.w3.org/TR/xpath.
[5]K. Eswaran, J. Gray, R. Lorie and I. Traiger, “The Notions of Concurrency and Predicate Locks in a Database System,” Communications of the ACM, Vol. 19, No. 11, pp. 642-633, 1976.
[6]J. Garza and W. Kim, “Transaction Management in an Object-Oriented Data Model,” ACM Computing Surveys, Vol. 22, No. 4, pp. 375-408, 1990.
[7]J. Gray, R. Lorie, G. Putzolu and I. Traiger, “Granularity of Locks and Degrees of Consistency in a Shared Database,” Modeling in DataBase Management System, G. Nijssen, Elsevier North-Holland, pp. 365-395, 1976.
[8]R. Holt, “Some Deadlock Properties in Computer System,” ACM Computing Surveys, Vol. 4, No. 3, pp. 179-196, 1972.
[9]E. Hye Choi and T. Kanai, “XPath-based Concurrency Control for XML Data,” Proceedings of the 14th Data Engineering Workshop, March, 2003.
[10]K. Jea, S. Chen and S. Wang, “Concurrency Control in XML Document Databases: XPath Locking Protocol,” Proceedings of 2002 International Conference on Parallel and Distributed Systems, pp. 551-556, 2002.
[11]Z. Kedem and A. Silberschatz, “A Characterization of Database Graphs Admitting a Simple Locking Protocol,” Acta Informatica, Vol. 16, pp. 1-13, 1981.
[12]H. Korth, “Deadlock Freedom Using Edge Locks,” ACM Transactions on Database Systems, Vol. 7, No. 4, pp. 632-652, 1982.
[13]H. Korth, “Locking Primitives in a Database System,” Journal of the Association for Computer Machinery, Vol. 30, No. 1, pp. 55-79, 1983.
[14]H. Kung and J. Robinson, “On Optimistic Methods for Concurrency Control,” ACM Transactions on Database Systems, Vol. 6, No. 2, pp. 213-226, 1981.
[15]S. Lee and R. 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, pp. 158-167, 1992.
[16]A. Silberschatz and Z. Kedem, “Consistency in Hierarchical Database Systems,” Journal of the ACM, Vol. 27, No. 1, pp. 72-80, 1980.
[17]A. Silberschatz, H. Korth and S. Sudarshan, Database System Concepts, 4th ed., McGraw-Hill, 2001.
[18]A. Thomasian, “Concurrency Control: Methods, Performance, and Analysis,” ACM Computing Surveys, Vol. 30, No. 1, pp. 70-119, 1998.
[19]P. Wadler, Two semantics for XPath, Technical Report, Software Technology Research Department, Avaya Labs Research, 2000, http://www.research.avayalabs.com/user/wadler/papers/xpath-semantics.
[20]賈坤芳, 王聖賢, 陳世穎, “適用在XML文件上的並行控制機制: XPath Locking Protocol,” Proceedings of 2002 Symposium on Digital Life and Internet Technologies (Abstract Collections), pp. 112, 2002.
[21]賈坤芳, 王聖賢, 陳世穎, “適用在XML文件上的驗證式並行控制協定: Extended Optimistic Concurrency Control,” Proceedings of the 13th Workshop on Object-Oriented Technology and Applications (Abstract Collections), pp. 50, 2002.
[22]賈坤芳, 王聖賢, 陳世穎, “適用在XML文件上預防死結之並行控制協定：EXLP（Extended XPath Locking Protocol）,” Proceedings of 2003 Symposium on Digital Life and Internet Technologies, 2003.
[23]“Document Object Model (DOM),”
http://www.w3.org/DOM/.
[24]“Extensible Markup Language (XML),”
http://www.w3.org/XML/.
[25]“Frequently Asked Questions about the Extensible Markup Language,” http://www.ucc.ie/xml.
[26]“Gartner,”
http://www.gartner.com.
[27]“The SGML/XML Web Page,”
http://www.Oasis-open.org/cover/.
[28]“XML Linking Language (XLink),”
http://www.w3.org/XML/Linking.
[29]“XML Query,”
http://www.w3.org/XML/Query.
[30]“The World Wide Web Consortium,”
http://www.w3.org/.