Word Files
Reference for Downloading Educational Files
  2. Computer Engineering
  3. Evaluation of some concurrency control algorithms in the database management system, through Petri modeling

Evaluation of some concurrency control algorithms in the database management system, through Petri modeling

Number of pages: 120 File Format: word File Code: 31023
Year: 2014 University Degree: Master's degree Category: Computer Engineering
Tags/Keywords: Algorithm - Colored Petri net - Concurrency control - Concurrency control algorithms - Database management - Database management system - Databases - Petri modeling - Sorting algorithm
  • Part of the Content
  • Contents & Resources

  • Summary of Evaluation of some concurrency control algorithms in the database management system, through Petri modeling

    Master's Thesis of Technical and Engineering Faculty

    Computer Department

    Abstract:

    The issue of concurrency control in databases is a necessary and important matter. Asynchronous execution of transactions in a database management system may lead to inconsistencies. Inconsistency is caused by incorrect values ??for existing data, due to conflict and interference of transaction execution. Concurrency control algorithms are designed to ensure the concurrent execution of multiple transactions that work concurrently with shared data. In the field of database concurrency control, a lot of research has been done, the result of which is various concurrency control algorithms. Considering the various algorithms in this field and the fact that their importance is increasing day by day, there is much room for work in the evaluation of concurrency control algorithms.

    In this thesis, the basic two-stage locking concurrency control algorithms as well as the wound-wait and wait-die techniques, which are part of the deadlock prevention techniques, have been modeled. Because the colored Petri net has high modeling capabilities and is one of the best methods for analyzing the control mechanisms of convergence; Modelings are presented using Petri dishes and CPN Tools software. A simple case study is presented as an example for better understanding, the mentioned example includes three transactions and two resources. Then the mentioned algorithms have been evaluated. The evaluation is based on parameters and criteria such as the number of transactions entering the system, the number of commands per transaction, the number of shared and non-shared data between transactions, and the number of shared data in transactions without non-shared data. The tests were repeated several times and the results were averaged. By comparing and conducting investigations, it was concluded that in general, the wounding-waiting algorithm has a better execution time than the other two algorithms. The wait-to-die algorithm is significantly worse than the other two algorithms in terms of execution time, and the basic two-stage locking algorithm has many problems due to the possibility of deadlocks.

    Keywords: Concurrency control, colored Petri net, evaluation, basic two-stage locking, wound-wait, wait-die, deadlock, deadlock prevention

    Chapter 1

     

     

    1-1-       Introduction

    Concurrent execution of transactions in databases faces many problems. Concurrency control mechanisms are used to maintain isolation and non-interference of execution among conflicting transactions and maintain database consistency (a-Pashazadeh, 2012), (b-Pashazadeh, 2012) and (Shu, and Young, 2002). In other words, concurrency control algorithms are algorithms that make the concurrent execution of multiple transactions and its sequential execution equivalent. The issue of concurrency control in databases is a necessary and important issue (Shu, and Young, 2002). In this field, many studies and researches have been done, the result of which is the emergence of various algorithms of convergence control. Also, due to the ever-increasing expansion of all types of databases around the world, the need to examine database concurrency control protocols becomes more apparent. Formal modeling[1] of concurrency control algorithms is very useful in studying their various characteristics (a-Pashazadeh, 2012) and (b-Pashazadeh, 2012). Studies show that Petri nets (PNs) [2] are a suitable method for formal modeling of convergence control mechanisms. There are different types of Petri nets, one of which is the colored Petri net (CPN) [3]. Colored Petri nets are one of the best tools for modeling concurrency control algorithms (a-Pashazadeh, 2012) and (b-Pashazadeh, 2012). For this reason, this method will be used for modeling in this thesis.

    One of the main concurrency control mechanisms is the basic two-stage locking technique (2PL)[4]. This concurrency control technique is performed through data locking. Locking on data is done gradually as the need to access them arises, and unlocking them will occur after all transaction locks have been obtained. In this technique, there is a possibility of deadlock, for this reason, two deadlock prevention mechanisms are also investigated.In this technique, it is possible for a deadlock to occur, for this reason, two deadlock prevention mechanisms will also be examined.

    Wait-to-die mechanism (WD) [5] is one of the deadlock prevention algorithms in which the time priority of transactions based on the time stamp and the moment of their entry into the system is not respected. That is, in the WD mechanism, there is no rule that the transaction that entered the system earlier has a higher priority to get the locks it needs earlier, that is why it is called a non-blocking algorithm. On the opposite side, there is the Wound-Waiting (WW) mechanism [6], which is one of the deadlock prevention algorithms in which the time priority of transactions is respected based on the timestamp and moment of their entry into the system. That is, in the WW mechanism, the transaction that entered the system earlier has a higher priority to get the locks it needs earlier, that's why it is called the blocking algorithm.

    In this thesis, the attempt is to provide the possibility of examining the execution of transactions from different perspectives and aspects by modeling the 2PL, WD and WW mechanisms. Then, let's evaluate these algorithms and check them using different parameters mentioned in Table 1-1. In this table, the first column shows the parameters based on which we are going to evaluate the models in this thesis. Then, in the next columns, you will see the names of the algorithms that have already been evaluated by these parameters, how they are implemented or modeled, as well as their references. Parameter Algorithm(s) Implementation or Modeling Reference Number of incoming transactions Comparison of a secure algorithm and an insecure algorithm for real-time databases Small-scale implementation (Hedayati, Kamali, Shakerian and Rahmani, 2010) Size of each transaction (number of instructions per transaction) Basic Timestamp Sorting Algorithm Modeling by Markov model (Singhal, 1991) and (Rohani Rankohi, 1386) Number of shared and non-shared data of transactions A mechanism based on two-stage locking Small-scale implementation (Al-Jumah, Hossam, and El-Sharkawi, 2000) Number of shared data in Transactions without non-shared data A mechanism based on two-phase locking Small-scale implementation (Al-Jumah, et al., 2000)

     

     

    When modeling a simple case study An example is provided for better understanding. The mentioned example includes three transactions and two resources.

    Modelings are presented using colored Petri dish and CPN Tools software. Finally, all three algorithms have been evaluated and the algorithms have been evaluated with the criteria stated above. The experiments were repeated several times and the average values ??were calculated. The necessary diagrams have also been drawn and reviewed for easier comparison. 1-1- Thesis structure This thesis is organized in the following form. In the second chapter, the research background and related materials are given. In this chapter, we will have a general overview of the subject, objectives, research background and other works done in this field. In the background of the research, we will discuss what algorithms have been presented so far, the evaluation through which methods and the like. We will also examine a number of parameters and evaluation criteria of convergence control algorithms

  • Contents & References of Evaluation of some concurrency control algorithms in the database management system, through Petri modeling

    List:

    Chapter One: Introduction

    1-1- Introduction. 2

    1-2- Thesis structure. 4

    Chapter Two: Research Background

    Introduction. 7

    2-1- Importance of database concurrency control algorithms 7

    2-2- Some types of databases 8

    3-2- Types of implementation and modeling methods of concurrency control algorithms. 9

    2-3-1- Implementation on a small scale. 9

    2-3-2- Modeling and simulation by Markov model. 11

    2-3-3- Modeling and simulation by Petri nets. 12

    2-4- Evaluation parameters. 14

    2-4-1- parameters of system resources. 14

    2-4-2- Workload parameters. 15

    2-5- The parameters and tests performed 16

    2-6- Some advantages and disadvantages of modeling and simulation methods. 18

    2-7- Necessity of doing research. 20

    Chapter Three: Concurrency Control Techniques

    Introduction. 22

    3-1- Concurrency control techniques and their types 22

    3-2- Locking techniques and their types 23

    3-2-1- Lock definition. 24

    3-2-2- Lockable unit sizes. 24

    3-2-3- lock structure. 25

    3-2-4- An example for the necessity of locking. 26

    3-2-5- The lock manager and steps taken for locking. 27

    3-2-6- How to provide the lock by the lock administrator. 28

    3-2-7- multi-style lock. 28

    3-2-7-1- Homogeneity matrix or compatibility of multi-style locks. 28

    3-2-7-2- multi-style locking protocol for a transaction. 29

    3-2-7-3- lock change. 30

    3-2-7-4- multi-style locking and sequencing. 30

    3-2-7-5- Features of multi-style lock. 30

    3-2-8- basic two-step locking technique. 30

    3-2-8-1- Uncontrolled interference problems 31

    3-2-8-2- Basic 2PL characteristics and problems. 32

    3-2-8-3- Lock change in 2PL protocol. 33

    3-2-8-4- The effect of insertion operations in concurrency control. 33

    3-2-8-5- The effect of deletion operations in concurrency control. 33

    3-3- Deadlock. 34

    3-3-1- Solutions to the deadlock problem. 35

    3-3-2- Time stamp techniques. 36

    3-3-2-1- WD algorithm. 37

    3-3-2-2-WW algorithm. 37

    3-3-2-3- Features of WD and WW algorithm. 37

    Chapter Four: Petri Nets

    Introduction. 39

    4-1- Brief about Petri nets. 39

    4-2- The difference between UML and Petri. 39

    4-3- History of Petri nets. 40

    4-4- Characteristics of Petri nets. 40

    4-5- Petri net components. 40

    4-5-1- Definition of Petri net components. 41

    4-5-2- Functions of Petri net components. 41

    4-6- Four definition of Petri nets. 42

    4-7- Petri net graph. 42

    4-8- Some examples of Petri net graph. 43

    4-9- Behavior of Petri nets. 43

    4-10- Powerful transition 44

    4-11- An example of running a Petri net. 44

    4-12- Rules related to transition firing in Petri net. 45

    4-13- Deadlocked Petri nets, living and non-living 46

    4-14- Types of Petri nets and how to mark them 47

    4-15- Flowcharts and Petri nets. 47

    4-16- Types of Petri. 48

    4-16-1- Color Petri net. 48

    4-16-2- Time Petri net. 49

    4-16-3- Hierarchical Petri net. 50

    Chapter Five: How to Model 2PL, WW and WD Mechanisms with Color Petri

    Introduction. 52

    5-1- Brief about the modeling of 2PL, WW and WD mechanisms. 52

    5-1-1- 2PL model. 52

    5-1-2- WW and WD models. 53

    5-2- Color sets. 53

    5-2-1- Color sets in 2PL model. 53

    5-2-2- Color sets in WW and WD models. 54

    5-2-3- Description of color sets. 55

    5-3- Initial marking. 58

    5-3-1- Initial marking in 2PL model. 58

    5-3-2- Initial marking in WW and WD models. 59

    5-3-3- Description of initial marking. 59

    5-4- Variables 61

    5-4-1- Variables of 2PL model. 61

    5-4-2- Variables of WW and WD models. 62

    5-5- Description of model functions and their functions 62

    5-5-1- Description of common functions between 2PL, WW and WD models. 63

    5-5-2- Description of 2PL model functions. 63

    5-5-3- Description of functions of WW and WD models. 76

    5-6- Certain priorities. 76

    5-6- The priorities set to determine the firing of the desired transition from among the active transitions. 72

    5-7- How to model 73

    5-7-1- How to model 2PL model. 73

    5-7-2- How to model WW and WD models. 75

    Chapter 6: Evaluation of 2PL, WW and WD models

    Introduction. 79

    6-1- Brief about the importance of database evaluation 79

    6-2- The parameter of the number of transactions entering the system. 80

    6-2-1- Examining the 2PL model. 80

    6-2-2- Review of WW model. 80

    6-2-3- Checking the WD model. 81

    6-2-4- Comparison of 2PL, WW and WD models based on the number of transactions parameter 82

    6-3- Parameter of the number of orders per transaction. 83

    6-3-1- Examining the 2PL model. 83

    6-3-2- Review of WW model. 84

    6-3-3- Checking the WD model. 85

    6-3-4- Comparison of 2PL, WW and WD models based on the parameter of the number of transaction commands 86

    6-4- The parameter of the number of shared and non-shared data of transactions 88

    6-4-1- Review of the 2PL model. 88

    6-4-2- Review of WW model. 89

    6-4-3- Checking the WD model. 90

    6-4-4- Comparison of 2PL, WW and WD models based on the parameter of the number of shared and non-shared data of transactions 91

    6-5- The parameter of the number of shared data in transactions without non-shared data. 92

    6-5-1- Examining the 2PL model. 92

    6-5-2- Review of WW model. 93

    6-5-3- Checking the WD model. 94

    6-5-4- Comparison of 2PL, WW and WD models based on the parameter of the number of shared data in transactions without non-shared data. 96

    6-6- Conclusion. 97

    6-7- Suggestions. 100

    references. 102

     

    Source:

    Latin references:

    Al-Jumah, N. B., Hossam, S. H. and El-Sharkawi, M., (2000), Implementation and modeling of two-phase locking concurrency control—a performance study, Information and Software Technology, Vol. 42, No. 4, pp. 257-273.

    Chen, J., Wang, Y. F. and Wang, J. P., (2011), Concurrency control protocol for real-time database and the analysis based on petri net, Advanced Materials Research, Vols. 143-144, pp. 12-17.

    Devillers, R. and Best, E., (1987), Sequential and concurrent behavior in petri net theory, Theoretical computer science, Vol. 55, No. 1, pp. 87-136.

    Gilmore, S., (1997), Programming in standard ML'97: A tutorial introduction, Edinburgh, Laboratory for Foundations of Computer Science the University of Edinburgh.

    Halder, A., (2006), A study of petri nets modeling, analysis and simulation, India, India Aerospace Engineering University.

    Han, Y., Jiang, C. and Luo, X., (2004), A study of concurrency control in web-based distributed real-time database system using extended time petri nets, Parallel Architectures, Algorithms and Networks (ISPAN'04), in Proceedings of the 7th International Symposium on IEEE, pp. 67-72.

    Harper, R., (2001), Programming in standard ML, Pittsburgh United States, Carnegie Mellon University.

    Harper, R., Rothwell, N. and Mitchell, K., (1989), Introduction to standard ML, Pittsburgh United States, School of Computer Science Carnegie Mellon University. (2010), Evaluation of performance concurrency control algorithm for secure firm real-time database systems via simulation model, Networking and Information Technology (ICNIT), International Conference on IEEE, pp. 260-264.

    Jenq, B-C., Twichell, B. C. and Keller, T. W., (1989), Locking performance in a shared nothing parallel database machine, Knowledge and Data Engineering, Transactions on IEEE, Vol. 1, No. 4, pp. 530-543.

    Jensen, K., Kristensen, L. M. and Wells, L., (2010), Colored petri nets and CPN tools for modeling and validation of concurrent systems, International Journal on Software Tools for Technology Transfer, Vol. 9, Nos. 3-4, pp 213-254.

    Jie, H., Fengying, L. and Huijiao, W., (2010), Petri net based model for concurrent control of database system, International Conference on Intelligent Computing and Integrated Systems (ICISS), pp. 813-815.

    Lee, J.

Evaluation of some concurrency control algorithms in the database management system, through Petri modeling
How To Access The File
Related Contents:
Number of pages: 131 Category: Computer Engineering

Thesis for obtaining a master's degree in the field: computer, software, abstract. In a sensor network, which is a pervasive distributed system, communication synchronization is one of the discussed cases. One of the main tasks of synchronizing processes is mutual exclusivity. The new algorithms provided are more fair compared to the old algorithms. In this thesis, we present a ...

Number of pages: 126 Category: Computer Engineering

Dissertation for obtaining a master's degree in computer engineering - software orientation. Abstract In all the projects that are carried out today, the discussion of management is a very decisive issue. Software projects are no exception to this rule. One of the most important aspects of software development is time and cost management. Considering that in the early stages of ...

Number of pages: 82 Category: Computer Engineering

Master's Thesis in Computer Engineering-Artificial Intelligence Abstract Identifying Overlapping Organizations in Dynamic Networks Many complex natural and social structures can be considered as networks [1]. Roads, Internet sites, social networks, organizational communication, kinship relationships, electronic mail exchange, telephone calls and financial transactions are just a ...

Number of pages: 105 Category: Management

Dissertation for Master's Degree (M.A.) Orientation: ""Strategic"" Introduction Today, the need for proper planning is clear in order to correctly estimate the time and cost of the project and the amount of resources required in a project, which have a direct impact on the implementation, administration and proper exploitation of projects such as dam construction and building. ...

Number of pages: 129 Category: Management

Dissertation for Master's Degree in Industrial Management - Industrial Production Abstract Currently, the ever-increasing complexity and dynamism of production environments, the use of analytical models in their evaluation and decision-making has faced significant limitations. Therefore, the use of computer simulation as a tool that has a wide capability in formulating the above ...

Number of pages: 102 Category: Industrial Engineering

Master's thesis in the field of automation engineering and precision instruments, abstract presenting a new method in information clustering using a combination of bat algorithm and Fuzzy c-means. The similarity between data within each cluster is maximum and the similarity between data within different clusters is minimum. Fuzzy c-means is also a fuzzy clustering technique that ...

Number of pages: 104 Category: Computer Engineering

Master's Thesis in Computer Engineering Major: Software Abstract: Cloud processing and cloud environment and cloud databases are the place to store information on the web and the best solution should be used to increase their security. Our problem here is the classification of confidential and top-secret data and then their encryption for storage in the cloud. For this, speed ...

Number of pages: 79 Category: Computer Engineering

Master's Thesis Field: Computer Engineering Major: Software Abstract Expensiveness of information is a major problem in the current web. To deal with this problem, web personalization systems have been provided that adapt the content and services of a website to people based on their interests and browsing behavior. A fundamental component of any web personalization system is ...

Number of pages: 139 Category: Biology - Environment

Master's thesis abstract shows the necessity of having a healthy environment and raising the health level of the society, the need to have proper planning to reduce the sources of air pollutants production and predicting these pollutants to prevent its harmful effects is inevitable. Prediction of pollutants can be useful in air pollution management and control. In this research, ...

Number of pages: 193 Category: Electronic Engineering

Master's Thesis Electricity- Pollution power of big cities has become an acute issue for years. Expert research shows that the main cause of pollution in cities are cars with internal combustion engines. Combustion vehicles have many disadvantages, among which we can mention things such as dependence on a specific type of energy (oil), production of greenhouse gases, production ...