臺灣博碩士論文加值系統

本文提出一個新的方法，使用具時間特性之著色派翠網路（CTPN），模塑分散式關連資料庫查詢效率之雛型設計。首先，轉換框架式查詢定義為 SQL-Based 邏輯查詢計畫、設計成本函數嵌入CTPN 及應用 CTPN 擴充傳統查詢計畫樹結構。最後使用模擬工具-Design/CPN 觀察查詢效率之門檻值。除此，以排隊理論為基礎，設計合理的通訊成本及系統負載機制。上述之 CTPN 模塑，適用於描述平行式查詢運算及系統動態行為。因此，在不需修改查詢最佳化模組之前題，本研究方法於邏輯分散式資料庫系統設計階段，可被視為查詢最佳化之前處理，以期降低發展分散式資料庫系統查詢之成本。

In this paper, a new application of coloured timed Petri net (CTPN) based methodology for distributed heterogeneous relational database queries modeling and corresponding simulation is addressed. This work, first based on parsed query definitions, converts logical query plans into designed CTPN models. Later, the improved cost-based functions are then established and appended to CTPN with a general purpose CPN simulator-Design/CPN to observe the thresholds of query operations. The propose CTPN can be used in the design phase as an experimental prototype to automatically simulate distributed database query processing which, in turn, may considerably reduce the load of developing the actual query processing software in the logical design phase of a distributed database system. Also, since all the essential details of query processing in CTPN have been simulated, the results of this study can be closely related to real world applications.

第一章 緒論
1.1 研究動機與目的..............................................1
1.2 相關研究....................................................3
1.2.1分散式資料庫查詢....................................4
1.2.2著色派翠網路模塑....................................5
第二章 分散式關連資料庫查詢設計與模塑架構.......................7
2.1分散式關連資料庫查詢.....................................7
2.1.1分散式關連資料庫查詢之描述..........................7
　　　 2.1.2資訊參考模組........................................8
　　　 2.1.3查詢程序模組.......................................13
2.2查詢計畫的轉換與平衡....................................15
2.2.1由上至下演算法.....................................16
2.2.2由下至上演算法............................................20
2.3模塑架構................................................22
第三章 著色派翠網路於分散式關連資料庫查詢之模塑................23
3.1著色派翠網路結構............................................23
3.1.1著色派翠網路概述.......................................23
　　　 3.1.2著色派翠網路定義...................................24
　　　 3.1.3著色派翠網路性質...................................27
3.2分散式關連資料庫運算子模塑..................................30
第四章 分散式關連資料庫查詢之成本函數設計及工作負載測量........37
4.1成本函數之設計..........................................37
4.2查詢及資料運送配置......................................41
4.3工作負載之測量..........................................46
第五章 分散式關連資料庫查詢之系統模擬..........................49
5.1系統模擬設計................................................49
5.1.1使用者查詢介面............................................49
5.1.2 假設條件及相關參數設定.................................52
5.1.3 著色派翠網路模擬工具簡介...............................57
5.2查詢效率評估................................................58
5.2.1 模擬程序...............................................59
5.2.2 範例說明...............................................60
5.3模擬結果分析................................................69
第六章 結論....................................................73
參考文獻.......................................................75
附錄 A、子查詢Query1及Query2的模擬結果.........................81
附錄 B、Design/CPN操作.........................................86
作者簡介.......................................................90
個人著作.......................................................91

[1] A. Ip, W. Rahayu, and S. Singh,”Query Optimisation in a Non-Uniform Bandwidth Distributed Database System,” Proc. of Fourth IEEE International Conference on High Performance Computing, Vol. 2, pp. 818-823(2000).

[2]B.J. Oommen, M. Thiyagarajah,”Query Result Size Estimation Using a Novel Histogram-like Technique: The Rectangular Attribute Cardinality Map,” Proc. of International Symposium on Database Engineering and Applications, pp. 3-15(1999).

[3]B.J. Oommen, M. Thiyagarajah,”Query Result Size Estimation Using the Trapezoidal Attribute Cardinality Map,” Proc. of International Symposium on Database Engineering and Applications, pp. 236-242(2000).

[4]B. Lindstrom,”Web Based Interfaces For Simulation of Coloured Petri Net Models,” Proc. of International Conference on Application and Theory of Petri Nets, pp. 15-33(2000).

[5]C.H. Kuo, and H.P. Huang,“Distributed Performance Evaluation of a Controlled IC Fab, ”IEEE Trans. on Robotics and Automation, Vol. 19, No. 6, pp. 1027-1033(2003).

[6]C.H. Lee, and M.S. Chen,”Distributed Query Processing in the Internet: Exploring Relation Replication and Network Characteristics,” Proc. of International Conference on Distributed Computing Systems, pp. 439-446(2001).

[7]C.P. Wang, M.S. Chen,”On the Complexity of Distributed Query Optimization,”IEEE Trans. Knowledge and Data Eng., Vol. 8, No.4, pp. 650-662(1996).

[8]C. Surajit and S. Kyuseok,“Optimization of Queries with User-Defined Predicates,”ACM Trans. On Database Systems, Vol. 24, No. 2, pp. 177-228(1999).

[9]D. Bell, and J. Grimson, Distributed Database Systems. Addison-Wesley(1992).

[10]D. Kossmann,”The State of the Art in Distributed Query Processing,”ACM Computing Survey, Vol. 32, No. 4, pp. 422-469(2000).

[11]D. Soo, T. Snodgrass, and S. Jensen,”Efficient Evaluation of the Valid-Time Natural Join,” Proc. of International Conference on Data Engineering, pp. 282-292, 14-18(1994).

[12]D. Tutsch and J. Sokol,“Petri Net Based Performance Evaluation of USAIA's Bandwidth Partitioning for the Wireless Cell Level,” Proc. of International Conference on Petri Nets and Performance Models, pp. 49-58(2001).

[13]F. Najjar, and Y. Slimani,”Cardinality Estimation of Distributed Join Queries,” Proc. of International Conference on Database and Expert Systems Applications, pp. 66-70(1999).

[14]F. Sandra, S. Mendes, W.P. Norman, S. Jim, and W. Paul,“Validated Cost Models for Parallel OQL Query Processing,” Proc. of International Conference on Object-Oriented. Information Systems, pp. 60 -75(2002).

[15]G. Chiola, and A. Ferscha,” Distributed Simulation of Petri Nets,”IEEE Parallel and Distributed Technology, Vol. 1, Issue 3, pp. 33-50(1993).

[16]H. Clausen, and R. Jensen,”Validation and Performance Analysis of Network Algorithms by Coloured Petri Nets,” Proc. of International Conference on Petri Nets and Performance Models, pp. 280-289(1993).

[17]J.L. Peterson, Petri Net Theory and The Modeling of Systems. Prentice-Hall(1981).

[18]J.M. Morrissey, and O. Ogunbadejo,”Combining Semijoins and Hash-semijoins in a Distributed Query Processing Strategy,” Proc. of IEEE Conference on Electrical and Computer Eng., pp. 122-126(1999).

[19]J.M. Morrissey, W.K. Osborn, and Y. Liang,”Collisions and Reduction Filters in Distributed Query Processing,” Proc. of International Conference on Electrical and Computer Engineering, Vol. 1, pp. 240-244(2000).

[20]J.D. Ullman, and J. Widom, A First Course in Database Systems, 2nd Ed. Prentice-Hall(2002).

[21]J. Chen, D.J. DeWitt, and J.F. Naughton,”Design and Evaluation of Alternative Selection Placement Strategies in Optimizing Continuous Queries,” Proc. of International Conference on Data Engineering, pp. 345-356(2002).

[22]K. Jensen, Coloured Petri Nets: Basic Concepts, Analysis Methods and Practical Use, 2nd Ed, Volume 1. Springer-Verlag Berlin Heidelberg(1996).

[23]K. Voss,”Prototyping and Verifying Distributed Database Systems using Executable High-Level Petri Net Models,” Proc. of IEEE International Conference on Systems, Man, and Cybernetics, Vol. 4, pp. 3395-3400(1997).

[24]K. Donald, B. Reinhard, and K. Alfons,“Data Engineering, Integrating Semi-join-reducers into State-of-the-art Query Processors,” Proc. of International Conference on Data Engineering, pp. 575-584(2001).

[25]L. Wells, S. Christensen, L.M. Kristensen, and K.H. Mortensen,”Simulation Based Performance Analysis of Web Servers,” Proc. of International Workshop on Petri Nets and Performance Models, pp. 59-68(2001).

[26]L. Lorentsen,”Modelling and Analysis of a Flowmeter System,” Proc. of International Workshop on Practical Use of Coloured Petri Nets and Design/CPN, pp. 173-190(1999).

[27]L. Zhining, L. Weiru., H. Jun,“Analysing the Effect of Network States in Query Cost Estimation over the Internet,” Proc. of International Symposium on Database Engineering and Application, pp. 462-464(2004).

[28]M. Elliot, J. Billington, and L.M. Kristensen,”Using Design/CPN to Design a Visualisation Extension for Design/CPN,” Proc. of International Conference on Practical Use of Coloured Petri Nets and the CPN Tools, pp. 21-37(2002).

[29]M. Franklin, B. J'onsson, and D. Kossmann,”Performance Tradeoffs for Client-server Query Performance,” Proc. of ACM SIGMOD International Conference on Management of Data, pp. 149- 160(1996).

[30]M.P. Fanti,“A Deadlock Avoidance Strategy for AGV Systems Modeled by Coloured Petri Nets, ” Proc. of IEEE International Conference on Discrete Event Systems, pp. 61-66(2002).

[31]M.T. Ozsu, Distributed Database System, 2nd Edition. Prentice-Hall, pp. 581-588(1999).

[32]N.N. Dalvi, S.K. Sanghai, P. Roy, and S. Sudarshan,” Pipelining in Multi-Query Optimization,” Proc. of ACM SIGMOD- SIGACT-SIGART Symposium on Principles of Database Systems, pp. 59-70(2001).

[33]O.H. Bray, Distributed Database Management Systems, Lexington Books(1982).

[34]O. Wolfson, S. Jajodia, and Y. Huang,“An Adaptive Data Replication Algorithm,”ACM Trans. on Database Systems, Vol. 22, No. 42, pp. 255-314(1997).

[35]P.T. Chen, Y.T. Chen, and C.C. Yang,“A Coloured Timed Petri Net Modeling and Simulation of Distributed Database Queries,” Proc. of International Conference on Software Engineering and Application, pp. 54-59(2005).

[36]P.T. Chen, Y.T. Chen and C.C. Yang,“Coloured Petri Net-Based Modeling for Distributed Relational Database Queries,”J. of Chinese Institute of Engineers, Vol. 29, No. 6, pp. 1029-1039(2006).

[37]P.T. Chen, Y.T. Chen, and C.C. Yang, “Query Evaluation of Heterogenous Multidatabase Systems using Coloured Petri Nets,”J. of INFORMATION, Vol. 10, No. 1, pp. 77-94(2007).

[38]Q. Wang, A Cost Model for OQL Query Optimization, Oregon Graduate Institute, RPE paper(1997).

[39]R. Ramakrishnan, Database Management Systems, International Ed. McGraw-Hill(1998).

[40]R. Haraty, and R. Fany, ”Distributed Query Optimization Using PERF Joins,” Proc. of ACM International Symposium on Applied computing, pp. 284-288(2000).

[41]R.J. Schalkoff, Artificial Intelligence: An Engineering Approach. McGraw-Hill, pp. 513-529(1990).

[42]R. Zurawski and M.C. Zhou.,“Petri Nets and Industrial Applications: A Tutorial,”IEEE Trans. Industrial Electronics, Vol. 41., No. 6, pp. 567-583(1994).

[43]S.B. Hong, and K. Kim,“A Reliability Analysis of Distributed Programs with Coloured Petri Nets,” Proc. of International Conference on System, Man, and Cybernetics, pp. 3975-3980(1997).

[44]S. Bandyopadhyay, Q. Fu, and A. Sengupta,”A cyclic Multi-relation Semijoin Operation for Query Optimization in Distributed Databases,” Proc. of IEEE International Conference on Performance, Computing, and Communications, pp. 101-107(2000).

[45]S.M. Tsai, and L.P. Chen,”Optimizing Queries with Foreign Functions in a Distributed Environment,”IEEE Trans. Knowlwdge and Data Eng., Vol. 14, No. 4, pp. 809-824(2002).

[46]S. Padmanabhan, T. Malkemus, R. Agarwal, and A. Jhingran,”Block oriented processing of Relational Database operations in modern Computer Architectures,” Proc. of International Conference on Data Engineering , pp. 567-574(2001).

[47]T. Murata,“Petri Nets: Properties, Analysis and Applications, ” Proc. of of the IEEE, Vol. 4, No. 77, pp. 541-580(1989).

[48]T. Xu, A. Desrochers, and R.J. Graves“Performance Modeling of Dynamic Network-based Decision Systems,” Proc. of IEEE International Conference on System, Man and Cybernetics, pp. 2751-2756(2003).

[49]W. Du, M.C. Shan, and U. Dayal,“Reducing Multidatabase Query Response Time by Tree Balancing,” Proc. of ACM SIGMOD International Conference on Management of Data, pp. 293-303(1995).

[50]W.M. Zuberek, “Performance Study of Distributed Generation of State Spaces using Colored Petri Nets, ” Proc. of International Workshop on on Practical Use of Coloured Petri Nets and the CPN Tools, pp. 81-98(2002).

[51]Y. Chen, and W. Benn,”A Systematic Method for Query Evaluation in Distributed Heterogeneous Databases,”J. of Information Science and Engineering Vol. 16, pp. 463-497(2000).

[52]Y.E. Ioannidis,” Query Optimization, ”ACM Computing Surveys, Vol. 28, No. 1, pp. 121-123(1996).

[53]Y.H., B. Kerherve, G.V. Bochmann, and V. Oria,“Pushing Quality of Service Information and Requirements into Global Query Optimization,” Proc. of International Conference on Database Engineering and Applications, pp. 170-179(2003).

[54]簡璿哲，灰關聯度導入框架式電子商務資訊平台，國立臺灣科技大學電子工程研究所碩士論文，第18~23頁，民國九十年。

[55]陳建宏，伺服器叢集系統的允入控制與負載平衡機制，國立中山大學電機工程研究所碩士論文，第4-24頁，民國九十二年。