Data Protection - Lecture Note VII (Concurrency)

• Database concurrency and recovery are two inter-related subjects, both being parts of the more general topic of transaction processing.
• Database systems typically provide multi-user access to a shared database. As such concurrency control is critical in ensuring that concurrent operations are carried out correctly and efficiently.

Concurrency Problems
There are three concurrency problems, that is three types of potential mistakes which could occur if concurrency control is not properly enforced in the database system.

The Lost Update Problem
This relates to a situation where two concurrent transactions, say A and B are allowed to update an uncommitted change on the same data item, say X. The second update by transaction B replaces the value of the first update by transaction A. consequently, the updated value of X by A is lost following the second update by B.

Uncommitted Dependency

• The uncommitted dependency problem arises if a transaction is allowed to retrieve or, worse, update - a tuple that has been updated by another transaction but has not yet been committed by that other transaction.
• Therefore if it has not yet been committed, there is always a possibility that it never will be committed but will be rolled back instead - in which case the first transaction will have seen some data that now no longer exist
• According to the above diagram transaction A sees an uncommitted update at time T2. That update is then undone at time T3. Transaction A is therefore operating on a false assumption - namely, the assumption that tuple P has the value seen at time T2, where as in fact it has whatever value it had prior to time T1. As a result transaction A might well produce incorrect output
• Here the Roll Back of transaction B might be due to no fault of B's, it might for example be the result of a system crash. (and transaction A might already have terminated by that time, in which case the crash would not cause a Roll Back to be issued for A also.)
• The second example is even worse. Not only does transaction A becomes dependent on an uncommitted change at time T2, but it actually loses an update at time T3 - because Roll Back at time T3 causes tuple P to be restored to its value prior to time T'1. This is another version of lost update problem.

Locking
Locking is the most common mechanism of concurrency control. The idea of locking is quite simple when a transaction item will not change during the course of processing, it requires a lock, which locks other transactions out of the item preventing them changing it. The first transaction knows that the data item remains stable for its duration.

Locking granularity:- The size of the object to be locked is referred to as the degree of granularity (locking granularity). It could be:

• The entire database
• A disk block
• A database relation
• A tuple in a relation, or field of a tuple.

The larger the data item the lower is the degree of concurrency, the fewer the number of locks to be set, and the lower the processing overhead.

Two types of locks

There are two types of locks available

• Exclusive locks. (X locks, or write locks):
• Grant read/write access to the transaction which holds the lock.
• Prevent any other transactions reading or writing the data.
• Shared locks (S locks, or read locks):
• Give read-only access to the transaction which holds the lock.
• Prevent any transaction writing the data.
• Several transactions may hold a shared lock on an item.

Locking protocol:

• A transaction must acquire an S lock on the data item it wishes to retrieve.
• A transaction must acquire an X lock on the data item it wishes to update.
• If a lock request is denied, the transaction goes into Wait State.
• A transaction in Wait State resumes operation only when the lock request is released.
• X locks are held until commit or Roll Back, S locks are normally the same.

Dead lock problem

A system is in a state of dead lock if there exists a set of transactions as such that every transaction in the set is waiting for another transaction in the set.

In other words there exist a set of waiting transactions (Ts, T1 ,Tz, - - Tn) such that T0 is waiting for a data item which is held by T,, Tr is waiting for a data item held by Tz and Tn is waiting for a data item held by T0.

Data Protection - Part III (Database Integrity)

Data integrity deals with the integrity part of the relational model. lt should not be confused with the security issue of databases, although there are some similarities between them. The relational model specifies three main types of integrity:

1. Domain Integrity;
2. Entity Integrity
3. Referential Integrity.

Each of the above integrity rules applies to a particular set of potential problems in a relational database system. This session will describe these rules and explain when and how they are applied, as well as the adverse effect if these integrity constraints are not vigorously enforced in the system.

Relational Integrity
An integrity constraint can be regarded as a condition that all correct state of the database is required to satisfy. Integrity is enforced via integrity rules.

There are three main types of integrity specified in the relational model:

Domain integrity: Domain integrity is concerned with the values that may be concerned within a particular column of relations.

Entity integrity: Entity integrity is concerned with the primary keys of relations.

Referential integrity: Referential integrity is concerned with the foreign keys of relations

Domain Integrity

Domain integrity is concerned with the values that may be contained with in a particular column. The domain integrity rule states that every attribute is required to specify the constraint that its values are drawn from the relevant domain. All columns have an implicit domain derived from their data types (for example, a telephone number rs made up of 10 numeric digits). However, more explicit domain integrity can also be defined (for example, each telephone number is preceded by the digits 071).

Ideally commands should be available within the database system to allow the user to define domain specifications when the database is created - not all systems currently allow this. lt would also be helpful to have some type of domain constraint. For example, a CHECK clause could be used to specify the gender column as CHECK (gender IN ('M','F')). This would be more useful than just being able to specify, the column as type character - which would, allow any character.

Entity Integrity

Entity integrity is concerned with primary keys.

The entity integrity rule states that every base relation must have a primary key and no component of the primary key is allowed to accept null values.

Null values - Null values here mean that information is missing for some reason (for example, the property is non-applicable), or the value is unknown.

The function of primary keys - Primary keys perform the unique identification functions in the relational model.

Primary keys provide the basic tuple-level addressing mechanism because the only system guaranteed way of pinpointing a specific tuple is by its primary key value. Therefore, each primary key value must identify one and only one tuple.

Implication for primary keys accepting nulls - Suppose a relational customer included a tuple for which the name value was null. That would be like saying that there was a customer who had no identity.

If that null means property does not apply, then the tuple makes no sense. If it means value is unknown, then confusion will arise and queries using that attribute may get a "don't know" as their reply.

Therefore, the entity integrity rule is sometimes stated that in a relational database, we never record information about something we cannot identify.

Referential Integrity

Referential integrity is concerned with foreign keys.

The referential integrity rule states that the database must not contain any unmatched foreign key values. In other words, the referential integrity rule simply says that if B references A, then A must exist.

Referencing vs. referenced - A foreign key is an attribute of one relation F12 whose values are required to match those of the primary key of some relation R1. We refer to the relation that contains the foreign key as the referencing relation and the relation that contains the corresponding primary key as the referenced or target relation. A given relation can, of course, be both a referenced relation and a referencing relation.

Domain requirement - A foreign key value represents a reference to the tuple containing the matching primary key value (the referred tuple or target tuple). Therefore, a given foreign key and the corresponding primary key should be defined on the same underlying domain.

Possible cases for null values - unlike Primary keys, Foreign keys do some times have to accept null values. ln most cases, the reasons for using nulls are likely to fall in the value does not exist category, rather than the value unknown category. For example, in the case of the department-and-employees database, it might be possible for some employee to be currently assigned to no department at all.

Maintaining Referential Integrity
Any state of the database which does not satisfy the referential integrity rule is by definition incorrect, but the rule itself does not specify how such incorrect states can be avoided!

• Two Possibilities - There are usually two possibilities available:
• The system could simply reject any operation that, if executed, would result in an illegal state.
• In many cases, a preferable alternative would be for the system to accept the operation but to perform certain additional compensating operations (if necessary) in order to guarantee that the overall result is still a legal state.

There are two basic questions which will arise when providing such an alternative:

Deletion - What should happen on an attempt to delete the target of a foreign key reference? For example, an attempt to delete a customer for which there exists at least one matching Order?

In general there are at least three possibilities:

• Restricted - the delete operation is restricted to the case where there are such matching orders

For example, the deletion of a parent row will be disallowed if there are any dependent rows.

• Cascades - the delete operation cascade to delete those matching orders also For example, if a parent row is deleted, then the system will automatically deleted the dependent rows.

• Nullifies - the foreign key is set to null in all such matching orders and the customer is the deleted.

For example, when a parent row is deleted, all dependent foreign keys are set to null.

• Updating - What should happen on an attempt to update the primary key of the target of a foreign key reference? For example, an attempt to update the name for a customer for which there exists at least one matching order.

Again there are three possibilities:

• Restricted - the update operation is restricted to the case where there are matching orders.

For example, if an update command changes the primary key of a parent row and if dependent exists for that row, the update is disallowed.

• Cascades - the delete operation cascades to update those matching orders also.

For example, if an update commands changes the primary key of a parent row, all of its dependent rows will have their foreign key updated to the same value.

• Nullifies - the foreign key is set to null in all such matching orders and the customer is then updated.

For example, when an update command changes the primary key of a parent row, all of its dependent rows will have their foreign key set to null.