Now in the real world, a lot of information is stored in the relational database. People store information and use it when they need. A lot of data are used everyday. “SQL is the standard programming language for creating, manipulating, and retrieving information stored in relational databases.”(Rachel Singer Gordon, 2006) People use SQL operate database for query.
But for one SQL statement, database management system (DBMS) can follow many plans to process it and produce the result. All plans would produce the same result, but their costs are different such as the amount of time of processing. Which plan is the best choice and how we find it? Query Optimization is very necessary and important in DBMS. (Yannis E. Ioannidis)
“There has been extensive work in query optimization since the early 70s.” (Surajit Chaudhuri) Query optimization was researched for such a long time, it still need to improve as there are a lot of factors need to think about such as Search Space, I/O Cost and CUP Cost and so on. These factors may affect the performance of query such as speed of query and resource used. (John G. Hughes, 1988, p 177)
“The query optimization phase in query processing plays a crucial role in choosing the most efficient strategy for executing a query.”(David Taniar, Hui Yee Khaw, Haorianto Cokrowijoyo Tjioe & Eric Pardede, 2007)
Friday, 18 April 2008
about deadlock
Petri nets can be used to many areas. They are mathematical stuff. They can define, model, simulate many different system. They have been used to model and analyse some types of processes which including protocols, manufacturing systems, and business processes (Aalst 1999). For the distributed database systems, Petri nets are very useful as Petri nets can describe by modeling a finite concurrent system in many states.
“Petri nets are a widely used model for analyzing concurrent and distributed systems. Often such a system must exhibit reactive, non-terminating behavior, and one of the key analysis problems is that of deadlock-freedom: Do all reachable global states of the system (markings of the net) enable some action (net transition)?” (Keijo Heljanko, 1999) Petri net is very common and useful for distributed database systems. The hardest thing for using Petri net to prevent the deadlock is how to design a finite system. For a distributed database system, there must be many states. We can design a system model, but we can not make sure the system model is fully correct. There may be some condition we forget. For each state, whether deadlock happen will happen and how to prevent? That should be mostly considered. So it is not easy to design a finite system with analysis.
Using Petri net to prevent the deadlock must consider how the deadlock can not happen. So the four conditions of deadlock can not be happened at the same time. But as do not request while holding resource and lineate requests cause more waiting and the resources can not be used well, there are still a problem: how to improve the performance of the system? How to let the resources fully be used? Those are difficult.
Using Petri net to design a system to prevent the deadlock, we can check whether the deadlock happens at design time instead of to check at running time. It may let the system faster as there is no checking when system is running.
Using Petri net to design a finite system to prevent the deadlock, when the size of the system is very big, the number of the places, transitions and tokens may increase to a big number. We can not image how many there are, so it is difficult to design it and analyse it.
Therefore, some people make some other Petri net such as Colored Petri Net, Predicate/Transition Net, Adaptive Colored Petri Net, and Object Oriented Colored Petri Net and so on to fit many different systems and make design and analysis easy.
“Petri nets are a widely used model for analyzing concurrent and distributed systems. Often such a system must exhibit reactive, non-terminating behavior, and one of the key analysis problems is that of deadlock-freedom: Do all reachable global states of the system (markings of the net) enable some action (net transition)?” (Keijo Heljanko, 1999) Petri net is very common and useful for distributed database systems. The hardest thing for using Petri net to prevent the deadlock is how to design a finite system. For a distributed database system, there must be many states. We can design a system model, but we can not make sure the system model is fully correct. There may be some condition we forget. For each state, whether deadlock happen will happen and how to prevent? That should be mostly considered. So it is not easy to design a finite system with analysis.
Using Petri net to prevent the deadlock must consider how the deadlock can not happen. So the four conditions of deadlock can not be happened at the same time. But as do not request while holding resource and lineate requests cause more waiting and the resources can not be used well, there are still a problem: how to improve the performance of the system? How to let the resources fully be used? Those are difficult.
Using Petri net to design a system to prevent the deadlock, we can check whether the deadlock happens at design time instead of to check at running time. It may let the system faster as there is no checking when system is running.
Using Petri net to design a finite system to prevent the deadlock, when the size of the system is very big, the number of the places, transitions and tokens may increase to a big number. We can not image how many there are, so it is difficult to design it and analyse it.
Therefore, some people make some other Petri net such as Colored Petri Net, Predicate/Transition Net, Adaptive Colored Petri Net, and Object Oriented Colored Petri Net and so on to fit many different systems and make design and analysis easy.
Monday, 25 February 2008
Petri-net solves deadlock
Using Petri net design a system usually in some ways:
1) Deny mutual exclusion
It changes the properties of the resources to let them be sharable. For example, printer spooler provides a sharable buffer which is a temporary working area to keep the documents. And then printer pulls off the documents from the buffer to print them one by one. So users do not need to wait for printing and they can do some other operations on computer. Also if there are a lot of jobs need to print, the jobs will in a queue in the buffer. Users do not need to wait for to print next one by themselves.
But changing properties of resources is mostly impossible.
2) Deny no pre-emption of allocated resources
In a system, if any items can not be obtained, release all the resources it holds. And then transaction waits and tries again to obtain the items it needs and locks them. This is to let other transactions finish their jobs first. Obviously, this limits concurrency.
3) Do not request while holding resources
A transaction can request the resources successfully if it holds no resources. This requests all transaction must release the resources which are held by them before they request a new one. Obviously, a transaction can not hold more than one resource. So, in the system, many transactions must waiting for the resource they need. If one kind of resources are very popular in the system that means many transactions need them or transactions need many of those resources, these resources must be waited for a long time or they must very often to wait for them. It may occur a problem – starvation (a transaction can not proceed for an indefinite period of time because it can not gain the resources).
4) Lineate requests - breaks cycles
All transactions using resources must be in order. For example in Figure 3, if A and B want to record and request CD and recorder, they must at first request CD, if successful, request recorder next. So there would not be deadlock happen.
In prevention, denying mutual exclusion and no pre-emption of allocated resources are not usually possible. Because there are not many resources can be changed property and no pre-emption is either few. Do not request while holding resource and lineate requests cause more waiting and the resources can not be used well. However, there is no deadlock.
1) Deny mutual exclusion
It changes the properties of the resources to let them be sharable. For example, printer spooler provides a sharable buffer which is a temporary working area to keep the documents. And then printer pulls off the documents from the buffer to print them one by one. So users do not need to wait for printing and they can do some other operations on computer. Also if there are a lot of jobs need to print, the jobs will in a queue in the buffer. Users do not need to wait for to print next one by themselves.
But changing properties of resources is mostly impossible.
2) Deny no pre-emption of allocated resources
In a system, if any items can not be obtained, release all the resources it holds. And then transaction waits and tries again to obtain the items it needs and locks them. This is to let other transactions finish their jobs first. Obviously, this limits concurrency.
3) Do not request while holding resources
A transaction can request the resources successfully if it holds no resources. This requests all transaction must release the resources which are held by them before they request a new one. Obviously, a transaction can not hold more than one resource. So, in the system, many transactions must waiting for the resource they need. If one kind of resources are very popular in the system that means many transactions need them or transactions need many of those resources, these resources must be waited for a long time or they must very often to wait for them. It may occur a problem – starvation (a transaction can not proceed for an indefinite period of time because it can not gain the resources).
4) Lineate requests - breaks cycles
All transactions using resources must be in order. For example in Figure 3, if A and B want to record and request CD and recorder, they must at first request CD, if successful, request recorder next. So there would not be deadlock happen.
In prevention, denying mutual exclusion and no pre-emption of allocated resources are not usually possible. Because there are not many resources can be changed property and no pre-emption is either few. Do not request while holding resource and lineate requests cause more waiting and the resources can not be used well. However, there is no deadlock.
Monday, 11 February 2008
Deadlock in database
Deadlock can happen in any databases which permit concurrency execution of transactions using synchronization schemes such as locking protocols which are widely used in distributed database systems today. Deadlock usually in the distributed database systems as it produces concurrent problem. Solving deadlock is very important as the system can not proceed with deadlock. Petri nets and banker algorithm are the method to solve deadlock in the distributed database systems.
Tuesday, 22 January 2008
Subscribe to:
Posts (Atom)
