Serializability and Recoverability

Unit-1 Introduction to Databases: Introduction,  Traditional File-Based Systems, Database Approach,  Roles in the Database Environment,  Advantages and Disadvantages of DBMSs, The Three-Level ANSI-SPARC Architecture, Database Languages, Data Models,  Functions of a DBMS, Components of a DBMS. Relational Model: Introduction,  Terminology,  Integrity Constraints,  Views. The Relational Algebra: Unary Operations,  Set Operations, Join Operations, Division Operation, Aggregation and Grouping Operations.	Serializability and Recoverability The objective of a concurrency control protocol is to schedule transactions in such a way as to avoid any interference between them and to prevent the problem. One obvious solution is to allow only one transaction to execute at a time: one transaction is committed before the next transaction is allowed to begin. Schedule A sequence of the operations by a set of concurrent transactions that preserves the order of the operations in each of the individual transactions. A schedule S consists of a sequence of the operations from a set of n transactions T1, T2, . . . , Tn, and the order of operations for each transaction is preserved in the schedule.  Serial Schedule A schedule where the operations of each transaction are executed consecutively without any interleaved operations from other transactions. For example, if we have two transactions T1 and T2, serial order would be T1 followed by T2, or T2 followed by T1. Thus, in serial execution there is no interference between transactions, because only one is executing at any given time. Nonserial Schedule A schedule where the operations from a set of concurrent transactions are interleaved. If a set of transactions executes concurrently, we say that the (nonserial) schedule is correct if it produces the same result as some serial execution. Such a schedule is called serializable. In serializability, the ordering of read and write operations is important: • If two transactions only read a data item, they do not conflict and order is not important. • If two transactions either read or write completely separate data items, they do not conflict and order is not important. • If one transaction writes a data item and another either reads or writes the same data item, the order of execution is important. Figure .7 Equivalent schedules: (a) nonserial schedule S1; (b) nonserial schedule S2 equivalent to S1; (c) serial schedule S3, equivalent to S1 and S2. Consider the schedule S1 shown in Figure 7(a) containing operations from two concurrently executing transactions T7 and T8. Because the write operation on balx in T8 does not conflict with the subsequent read operation on baly in T7, we can change the order of these operations to produce the equivalent schedule S2 shown in Figure .7(b). If we also now change the order of the following non-conflicting operations, we produce the equivalent serial schedule S3 shown in Figure 7(c): • Change the order of the write(balx) of T8 with the write(baly) of T7. • Change the order of the read(balx) of T8 with the read(baly) of T7. • Change the order of the read(balx) of T8 with the write(baly) of T7. Schedule S3 is a serial schedule and, because S1 and S2 are equivalent to S3, S1 and S2 are serializable schedules. This type of serializability is known as conflict serializability. Testing for conflict serializability  Under the constrained write rule (that is, a transaction updates a data item based on its old value, which is first read by the transaction),a precedence (or serialization) graph can be produced to test for conflict serializability. For a schedule S, a precedence graph is a directed graph G = (N, E) that consists of a set of nodes N and a set of directed edges E, which is constructed as follows: • Create a node for each transaction. • Create a directed edge Ti → Tj, if Tj reads the value of an item written by Ti. • Create a directed edge Ti → Tj, if Tj writes a value into an item after it has been read by Ti. • Create a directed edge Ti → Tj, if Tj writes a value into an item after it has been written by Ti. If the precedence graph contains a cycle, the schedule is not conflict serializable. Example : Nonconflict serializable schedule Consider the two transactions shown in Figure 8. Transaction T9 is transferring £100 from one account with balance balx to another acount with balance baly, while T10 is increasing the balance of these two accounts by 10%. The precedence graph for this schedule, shown in Figure 9, has a cycle and so is not conflict serializable. Figure 8 Two concurrent update transactions that are not conflict serializable. Figure 9 Precedence graph for Figure 8 showing a cycle, so schedule is not conflict serializable. View serializability Two schedules S1 and S2 consisting of the same operations from n transactions T1, T2, . . . , Tn are view equivalent if the following three conditions hold: • For each data item x, if transaction Ti reads the initial value of x in schedule S1,then transaction Ti must also read the initial value of x in schedule S2. • For each read operation on data item x by transaction Ti in schedule S1, if the value read by Ti has been written by transaction Tj, then transaction Ti must also read the value of x produced by transaction Tj in schedule S2. • For each data item x, if the last write operation on x was performed by transaction Ti in schedule S1, the same transaction must perform the final write on data item x in schedule S2. Every conflict serializable schedule is view serializable, although the converse is not true Figure 10 View serializable schedule that is not conflict serializable. For example, the schedule shown in Figure 10 is view serializable, although it is not conflict serializable. In this example, transactions T12 and T13 do not conform to the constrained write rule,in other words, they perform blind writes. It can be shown that any view serializable schedule that is not conflict serializable contains one or more blind writes. Testing for view serializability Precedence graph corresponding to the schedule given in Figure 10 will be in Figure 11. This graphcontains a cycle indicating that the schedule is not conflict serializable; that it is view serializable, as it is equivalent to the serial schedule T11 followed by T12 followed by T13. When we examine the rules for the precedence graph given previously, we can see that the edge T12 → T11 should not have been inserted into the graph, as the values of balx written by T11 and T12 were never used by any other transaction because of the blind writes. Recoverability Recoverabilty of a transaction can be stated as If a transaction fails, the atomicity property undo the effects of the transaction. In addition, the durability property states that once a transaction commits, its changes cannot be undone. Recoverable Schedule A schedule in which for each pair of transactions Ti and Tj, if Tj reads a data item previously written by Ti, then the commit operation of Ti precedes the commit operation of Tj Concurrency control techniques The two main concurrency control techniques are locking and timestamping. These are conservative (or pessimistic) approaches in that they cause transactions to be delayed in case they conflict with other transactions at some time in the future.    4.1.6  Locking Methods Locking When one transaction is accessing the database, a lock may deny access to other transactions to prevent incorrect results. Locking methods are the most widely used approach to ensure serializability of concurrent transactions. Shared lock If a transaction has a shared lock on a data item, it can read the item but not update it. The read operations cannot conflict, it is permissible for more than one transaction to hold shared locks simultaneously on the same item. Exclusive lock If a transaction has an exclusive lock on a data item, it can both read and update the item. On the other hand, an exclusive lock gives a transaction exclusive access to that item. Thus, as long as a transaction holds the exclusive lock on the item, no other transactions can read or update that data item. Data items of various sizes, ranging from the entire database  to a field, may be locked. The size of the item determines the fineness, or granularity, of the lock. Locks are used in the following way: • Any transaction that needs to access a data item must first lock the item, requesting a shared lock for read-only access or an exclusive lock for both read and write access. • If the item is not already locked by another transaction, the lock will be granted. • If the item is currently locked, the DBMS determines whether the request is compatible with the existing lock. If a shared lock is requested on an item that already has a shared lock on it, the request will be granted; otherwise, the transaction must wait until the existing lock is released. • A transaction continues to hold a lock until it explicitly releases it either during execution or when it terminates (aborts or commits). In addition to these rules, some systems permit a transaction to issue a shared lock on an item and then later to upgrade the lock to an exclusive lock. This in effect allows a transaction to examine the data first and then decide to update it. Some systems also permit a transaction to issue an exclusive lock and then later to downgrade the lock to a shared lock. Using locks in transactions does not guarantee serializability of schedules by themselves, To guarantee serializability, we must follow an additional protocol concerning the positioning of the lock and unlock operations in every transaction. The best known protocol is two-phase locking (2PL).
Unit – II SQL: Introduction, Data Manipulation–Simple Queries,  Sorting Results,  Using the SQL Aggregate Functions, Grouping Results,  Sub-queries,  ANY and ALL, Multi-table Queries,  EXISTS and NOT EXIST, Combining Result Tables,  Database Updates. SQL: The ISO SQL Data Types,  Integrity Enhancement Feature–Domain Constraints, Entity Integrity, Referential Integrity, General Constraints, Data Definition–Creating a Database,  Creating a Table,  Changing a Table Definition,  Removing a Table,  Creating an Index,  Removing an Index,  Views–Creating a View, Removing a View,  View Resolution,  Restrictions on Views,  View Updatability,  WITH CHECK OPTION, Advantages and Disadvantages of Views, View Materialization, Transactions,  Discretionary Access Control–Granting Privileges to Other Users,  Revoking Privileges from Users. Advanced SQL: The SQL Programming Language–Declarations,  Assignments, Control Statements,  Exceptions, Cursors,  Subprograms, Stored Procedures,  Functions, and Packages, Triggers,  Recursion.
Unit – III Entity–Relationship Modeling:  Entity Types, Relationship Types,  Attributes,  Keys,  Strong and Weak Entity Types,  Attributes on Relationships, Structural Constraints, Problems with ER Models–Fan Traps,  Chasm Traps. Enhanced Entity–Relationship Modeling: Specialization/Generalization, Aggregation, Composition. Functional–Dependencies: Anomalies, Partial Functional Dependency,  Transitive Functional Dependency, Multi Valued Dependency, Join Dependency. Normalization: The Purpose of Normalization,  How Normalization Supports Database Design,  Data Redundancy and Update Anomalies, Functional Dependencies in brief,  The Process of Normalization, 1NF, 2NF,  3NF,  BCNF.  The Database Design Methodology for Relational Databases (Appendix–D).
Unit – IV Transaction Management: Transaction Support–Properties of Transactions, Database Architecture, Concurrency Control–The Need for Concurrency Control, Serializability and Recoverability,  Locking Methods, Deadlock,  Time Stamping Methods, Multi-version Timestamp Ordering,  Optimistic Techniques, Granularity of Data Items,  Database Recovery–The Need for Recovery,  Transactions and Recovery, Recovery Facilities, Recovery Techniques,  Nested Transaction Model. Security: Database Security–Threats,  Computer-Based Controls–Authorization,  Access Controls,  Views, Backup and Recovery, Integrity,  Encryption,  RAID.