Concurrency Control:Insert and Delete Operations

By -

Insert and Delete Operations

Until now, we have restricted our attention to read and write operations. This restriction limits transactions to data items already in the database. Some transactions require not only access to existing data items, but also the ability to create new data items. Others require the ability to delete data items. To examine how such transactions affect concurrency control, we introduce these additional operations:

• delete(Q) deletes data item Q from the database.

• insert(Q) inserts a new data item Q into the database and assigns Q an initial value.

An attempt by a transaction Ti to perform a read(Q) operation after Q has been deleted results in a logical error in Ti. Likewise, an attempt by a transaction Ti to perform a read(Q) operation before Q has been inserted results in a logical error in Ti. It is also a logical error to attempt to delete a nonexistent data item.

Deletion

To understand how the presence of delete instructions affects concurrency control, we must decide when a delete instruction conflicts with another instruction. Let Ii and Ij be instructions of Ti and Tj , respectively, that appear in schedule S in consecutive order. Let Ii = delete(Q). We consider several instructions Ij .

image

image

Insertion

We have already seen that an insert(Q) operation conflicts with a delete(Q) operation. Similarly, insert(Q) conflicts with a read(Q) operation or a write(Q) operation; no read or write can be performed on a data item before it exists.

Since an insert(Q) assigns a value to data item Q, an insert is treated similarly to a write for concurrency-control purposes:

• Under the two-phase locking protocol, if Ti performs an insert(Q) operation, Ti is given an exclusive lock on the newly created data item Q.

• Under the timestamp-ordering protocol, if Ti performs an insert(Q) operation, the values R-timestamp(Q) and W-timestamp(Q) are set to TS(Ti).

The Phantom Phenomenon

Consider transaction T29 that executes the following SQL query on the bank database:

image

Let S be a schedule involving T29 and T30. We expect there to be potential for a conflict for the following reasons:

• If T29 uses the tuple newly inserted by T30 in computing sum(balance), then T29 read a value written by T30. Thus, in a serial schedule equivalent to S, T30 must come before T29.

• If T29 does not use the tuple newly inserted by T30 in computing sum(balance), then in a serial schedule equivalent to S, T29 must come before T30.

The second of these two cases is curious. T29 and T30 do not access any tuple in common, yet they conflict with each other! In effect, T29 and T30 conflict on a phantom tuple. If concurrency control is performed at the tuple granularity, this conflict would go undetected. This problem is called the phantom phenomenon.

To prevent the phantom phenomenon, we allow T29 to prevent other transactions from creating new tuples in the account relation with branch-name = “Perryridge.”

To find all account tuples with branch-name = “Perryridge”, T29 must search either the whole account relation, or at least an index on the relation. Up to now, we have assumed implicitly that the only data items accessed by a transaction are tuples. However, T29 is an example of a transaction that reads information about what tuples are in a relation, and T30 is an example of a transaction that updates that information.

Clearly, it is not sufficient merely to lock the tuples that are accessed; the information used to find the tuples that are accessed by the transaction must also be locked.

The simplest solution to this problem is to associate a data item with the relation; the data item represents the information used to find the tuples in the relation. Transactions, such as T29, that read the information about what tuples are in a relation would then have to lock the data item corresponding to the relation in shared mode.

Transactions, such as T30, that update the information about what tuples are in a relation would have to lock the data item in exclusive mode. Thus, T29 and T30 would conflict on a real data item, rather than on a phantom.

Do not confuse the locking of an entire relation, as in multiple granularity locking, with the locking of the data item corresponding to the relation. By locking the data item, a transaction only prevents other transactions from updating information about what tuples are in the relation. Locking is still required on tuples. A transaction that directly accesses a tuple can be granted a lock on the tuples even when another transaction has an exclusive lock on the data item corresponding to the relation itself.

The major disadvantage of locking a data item corresponding to the relation is the low degree of concurrency— two transactions that insert different tuples into a relation are prevented from executing concurrently.

A better solution is the index-locking technique. Any transaction that inserts atuple into a relation must insert information into every index maintained on the relation. We eliminate the phantom phenomenon by imposing a locking protocol for indices. For simplicity we shall only consider B+-tree indices.

As we saw in Chapter 12, every search-key value is associated with an index leaf node. A query will usually use one or more indices to access a relation. An insert must insert the new tuple in all indices on the relation. In our example, we assume that there is an index on account for branch-name. Then, T30 must modify the leaf containing the key Perryridge. If T29 reads the same leaf node to locate all tuples pertaining to the Perryridge branch, then T29 and T30 conflict on that leaf node.

The index-locking protocol takes advantage of the availability of indices on a relation, by turning instances of the phantom phenomenon into conflicts on locks on index leaf nodes. The protocol operates as follows:

• Every relation must have at least one index.

• A transaction Ti can access tuples of a relation only after first finding them through one or more of the indices on the relation.

• A transaction Ti that performs a lookup (whether a range lookup or a point lookup) must acquire a shared lock on all the index leaf nodes that it accesses.

• A transaction Ti may not insert, delete, or update a tuple ti in a relation r without updating all indices on r. The transaction must obtain exclusive locks on all index leaf nodes that are affected by the insertion, deletion, or update. For insertion and deletion, the leaf nodes affected are those that contain (after insertion) or contained (before deletion) the search-key value of the tuple. For updates, the leaf nodes affected are those that (before the modification) contained the old value of the search-key, and nodes that (after the modification) contain the new value of the search-key.

• The rules of the two-phase locking protocol must be observed.

Variants of the index-locking technique exist for eliminating the phantom phenomenon under the other concurrency-control protocols presented in this chapter.

Comments

Post a Comment

Popular posts from this blog

Concurrency Control:Shadow Paging

By -
Image
Shadow Paging An alternative to log-based crash-recovery techniques is shadow paging . The shadow-paging technique is essentially an improvement on the shadow-copy technique that we saw in Section 15.3. Under certain circumstances, shadow paging may require fewer disk accesses than do the log-based methods discussed previously. There are, however, disadvantages to the shadow-paging approach, as we shall see, that limit its use. For example, it is hard to extend shadow paging to allow multiple transactions to execute concurrently. As before, the database is partitioned into some number of fixed-length blocks, which are referred to as pages . The term page is borrowed from operating systems, since we are using a paging scheme for memory management. Assume that there are n pages, numbered 1 through n . (In practice, n may be in the hundreds of thousands.) These pages do not need to be stored in any particular order on disk (there are many reasons why they do not, as we saw in Chapter 1
Read more

Entity-Relationship Model part2

By -
Image
Refining the COMPANY database schema by introducing relationships By examining the requirements, six relationship types are identified. All are binary relationships( degree 2) Listed below with their participating entity types: WORKS_FOR (between EMPLOYEE, DEPARTMENT) MANAGES (also between EMPLOYEE, DEPARTMENT) CONTROLS (between DEPARTMENT, PROJECT) WORKS_ON (between EMPLOYEE, PROJECT) SUPERVISION (between EMPLOYEE (as subordinate), EMPLOYEE (as supervisor)) DEPENDENTS_OF (between EMPLOYEE, DEPENDENT) ER DIAGRAM – Relationship Types are: WORKS_FOR, MANAGES, WORKS_ON, CONTROLS, SUPERVISION, DEPENDENTS_OF R elationship Types In the refined design, some attributes from the initial entity types are refined into relationships: Manager of DEPARTMENT -> MANAGES Works_on of EMPLOYEE -> WORKS_ON Department of EMPLOYEE -> WORKS_FOR etc In general, more than one relationship type can exist between the same participating entity types MANAGES and WORKS_FOR are distinct relationshi
Read more

XML Document Schema

By -
Image
XML Document Schema Databases have schemas, which are used to constrain what information can be stored in the database and to constrain the data types of the stored information. In contrast, by default, XML documents can be created without any associated schema: An el- ement may then have any subelement or attribute. While such freedom may occasionally be acceptable given the self-describing nature of the data format, it is not generally useful when XML documents must be processesed automatically as part of an application, or even when large amounts of related data are to be formatted in XML. Here, we describe the document-oriented schema mechanism included as part of the XML standard, the Document Type Definition , as well as the more recently defined XML S chema . Document Type Definition The document type definition ( D TD ) is an optional part of an XML document. The main purpose of a DTD is much like that of a schema: to constrain and type the information present in the docume
Read more