Database Security Lecture 2: Serializability Theory PDF

Database Security LECTURE (2) SERIALIZABILITY THEORY DR.MURTADA MALIK ADAM ELHAJ ASSISTANT PROFESSOR – IT DEPARTMENT Dr.Murtada-Serializability theory- lectrue 02 1 Janu...

Database Security LECTURE (2) SERIALIZABILITY THEORY DR.MURTADA MALIK ADAM ELHAJ ASSISTANT PROFESSOR – IT DEPARTMENT Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Lecture Objectives 2  Serializability Theory & Concepts.  Serializability Examples.  Serializability in Centralized Database.  Enforcing Serializability in Centralized Database.  Serializability in Distributed Database.  Enforcing Serializability in Distributed Database.  Serializability Techniques Comparison.  Serializability Techniques General Structure. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Serializability Concept 3  Basic Assumption – Each transaction preserves database consistency.  Thus serial execution of a set of transactions preserves database consistency.  Other Concepts: 1. Serial schedule (Nonserial schedule). 2. Serializable schedule. 3. Equivalent serial schedule. 4. Conflict serializable schedule(Not conflict serializable schedule). 5. Precedence (or Serialization) Graph. 6. conflict serializability. 2. view serializability. 3. Recoverable schedule(Nonrecoverable schedule). Dr.Murtada-Serializability theory- lecture 02 1 January 2025  Serializability Theory Examples 4 Dr.Murtada-Serializability theory- lecture 02 1 January 2025  Serializability Theory Examples 5 Dr.Murtada-Serializability theory- lecture 02 1 January 2025  Serializability in Centralized Database-SCD 6  Serializability in single site Database system.  Serializability theory deals with the correctness of a set of concurrent transactions.  It also provides a guiding principles of design concurrency control algorithms(now Called Techniques or Methods): 1. Locking. 2. Timestamping. 3. Optimistic methods. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025 Enforcing Serializability in Centralized Database. 7  Meaning that by Appling techniques: 1. Locking. 2. Timestamping. 3. Optimistic methods. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Locking Methods of SCD 8  Locking is A procedure used to control concurrent access to data. 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.  T must claim a shared (read) or exclusive (write) lock on a data item before the corresponding database read or write operation. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Locking Methods of SCD 9  The lock prevents another transaction from modifying the item or even reading it, in the case of an exclusive lock.  The size of the item determines the fineness, or granularity, of the lock.  The best-known protocol is two-phase locking (2PL).  Other protocol : Strict 2 Phase Locking (S2PL).  May lead to deadlock. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Locking Methods of SCD 10 Lock-point Locks held till trans action completion Number of locks Locks acquired Locked data items used Transaction Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Timestamping of SCD 11  Timestamp is A unique identifier created by the DBMS that indicates the relative starting time of a transaction.  Serializability uses transaction timestamps to order transaction execution for an equivalent serial schedule.  No locks , and therefore there can be no deadlock.  There is no waiting : transactions involved in conflict are simply rolled back and restarted. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Timestamping of SCD 12  It can be generated by system clock, or by incrementing a logical counter at the time the transaction started.  Older transactions (with smaller timestamp) get priority in the event of conflict.  data item contains a read_timestamp and a write_timestamp.  Another protocol: Multiversion Timestamp Ordering (used to increase concurrency). Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Timestamping of SCD 13  The basic timestamp ordering protocol assumes that only one version of a data item exists, and so only one transaction can access a data item at a time.  Note that with  On the other protocol a read operation never fails.  Versions can be deleted once they are no longer required Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Optimistic Methods of SCD 14  Optimistic techniques are based on the assumption that conflict is rare.  more efficient to allow transactions to proceed without imposing delays to ensure serializability.  When a transaction wishes to commit, a check is performed to determine whether conflict has occurred.  If there has been a conflict, the transaction must be rolled back and restarted. Since the premise is that conflict occurs very infrequently, rollback will be rare.  allow greater concurrency than traditional protocols.  Two or Three phases(read, validation, and write).  If rollback occurs often, it is an indication that the optimistic method is a poor choice for concurrency control in that particular environment. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Serializability in Distributed Database- SDD 15  Serializability Theory extended to Distributed Database.  Distributed Processing (Centralized remote Database).  Fragmentation  Horizontal  Vertical  Hybrid  Replication  Synchronous Replication  ROWA Protocol  Voting  Asynchronous Replication Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Serializability in Distributed Database- SDD 16  Serializability In Distributed Database System.  Data objects are often replicated at different sites.  A data object and its copies called logical data object and physical data object respectively.  System use translation function ti to translate logical operations to physical operations.  The execution of a set of transactions with replicated data object can be modeled of replicated schedule which contain physical operations.. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Serializability in Distributed Database- SDD 17  Conditions: 1. Physical operation results from logical operation submitted by transaction. So schedule represents a set of physical operations not logical operations like in singe database. 2. Schedule preserves the order of operations of each transaction. 3. The order of conflicting operations must be specified. 4. Each copy read in schedule should have been given some value, after completion of execution, only one value for each logical data object updated in schedule can be read by any subsequent read operation. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Serializability in Distributed Database- SDD 18  The serial replicated schedule for a copy called 1 copy serial schedule (or 1c serial schedule). And include the same concepts: 1. Equivalent replicated schedule. 2. Serializable replicated schedule. 3. Not Equivalent serial schedule  A replicated schedule is serializable if it is equivalent to 1c serial schedule over the same set of transactions as in case of single database. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Serializability in Distributed Database- SDD 19  So the concept of serializability in centralized database can be extended for the distributed environment to cater for data distribution.  If the schedule of transaction execution at each site is serializable, then the global schedule (the union of all local schedules) is also serializable provided local serialization orders are identical.  The solutions to concurrency control in a distributed environment are based on the two main approaches(called algorithms, techniques , or methods ), but are extends : 1. Distributed locking. 2. Distributed Timestamping. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Enforcing Serializability in Distributed Database. 20  Meaning Appling extends concurrency control techniques : 1. Distributed locking(four locking schemas). 2. Distributed Timestamping. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Distributed Locking of SDD 21  Distributed locking guarantees that the concurrent execution is equivalent to some (unpredictable) serial execution of those transactions  If the database is either centralized or fragmented, but not replicated, so that there is only one copy of each data item, and all transactions are either local or can be performed at one remote site, then the centralized protocols or methods.  However(replicated), these protocols have to be extended if data is replicated or transactions involve data at more than one site. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Distributed Locking of SDD 22  If we adopt a locking-based protocol then we have to provide a mechanism to handle deadlock.  So Generally and specially for replication, the two-phase locking (2PL) protocol is extended to : 1. C2PL. 2. PC2PL. 3. D2PL. 4. M2PL. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Distributed Locking of SDD 23  If we adopt a locking-based protocol then we have to provide a mechanism to handle deadlock.  So Generally and specially for replication, the two-phase locking (2PL) protocol is extended to : 1. C2PL. 2. PC2PL. 3. D2PL. 4. M2PL. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Distributed Timestamping of SDD 24  Distributed Timestamping guarantees that the concurrent execution is equivalent to a specific serial execution of those transactions, corresponding to the order of the timestamps.  Objective is to order transactions globally so older transactions (smaller timestamps) get priority in event of conflict.  In distributed environment, need to generate unique timestamps both locally and globally.  System clock or incremental event counter at each site is unsuitable.  Concatenate local timestamp with a unique site identifier:. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Comparison of Methods 25 Dr.Murtada-Serializability theory- lectrue 02 1 January 2025 General Structure: Serializability Techniques 26 Concurrency Control algorithms Pessimistic Optimistic Timestamp Locking Timestamp Hybrid Locking ordering ordering Centralized Centralized Primary Multi- copy version Distributed Conservative Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  References and Resources 27  Thomas Connolly,Carolyn Begg - database systems, A Practical Approach to Design,Implementation, and Management - 4th edition ,2005.  Davied Wai-lok Cheung, PHD research: A study of availability and Serializability in Distributed Database System, Department of Applied Mathematics and Physics - kyoto University, Japan, 1988.  Rishikesh Mandvikar, lectures notes , engr.smu.edu , https://s2.smu.edu/~mhd/8330sp04/mandvikar.ppt , retrieved 05- aprial-2019 10:30 pm. Dr.Murtada-Serializability theory- lectrue 02 1 January 2025  Thank,,, 28 ANY QUESTIONS OR DISCUSSION? Dr.Murtada-Serializability theory- lectrue 02 1 January 2025