Find read-write conflicts among given database transactions
Given a list of database transactions, find all read-write conflicts among them. Assume that there is no strict two-phase locking (Strict 2PL) protocol to prevent read-write conflicts.
Each database transaction is given in the form of a tuple. The tuple ('T', 'A', 't', 'R') indicates that a transaction T accessed a database record A at a time t, and a read operation is performed on the record.
Assume that a data conflict happens when two transactions access the same record in the database within an interval of 5 units. At least one write operation is performed on the record.
For example,
(T1, A, 0, R)
(T2, A, 2, W)
(T3, B, 4, W)
(T4, C, 5, W)
(T5, B, 7, R)
(T6, C, 8, W)
(T7, A, 9, R)
Output:
Transaction T1 and T2 are involved in RW conflict
Transaction T3 and T5 are involved in WR conflict
Transaction T4 and T6 are involved in WW conflict
Brief Overview on Read–Write conflicts
In databases, data conflict may arise during a read or write operation by the different transactions on the same data during the transaction’s life, leading to an inconsistent final database state. There are three types of data conflicts involved in the database transaction.
- Write–Read (WR) Conflict (Dirty Read)
This conflict occurs when a transaction reads the data which is written by the other transaction, but not yet committed.
- Read–Write (RW) Conflict
This conflict occurs when a transaction writes the data which is previously read by the other transaction.
- Write–Write (WW) Conflict (Blind Write Operation)
This conflict occurs when the data updated by a transaction is overwritten by another transaction which might lead to data update loss.
Note that there is no Read–Read (RR) conflict in the database since no information is updated in the database during the read operation.
Back to our Problem…
The idea is to sort all transactions in increasing order of database records and record access time. For each database record, consider all transaction pairs that have accessed the current record within an interval of 5 units. Finally, print all the conflicting transaction pairs for which at least one write operation is performed on the current record.
This can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Data structure to store transaction details struct Transaction { string name; // Transaction name string record; // Data object from the database int timestamp; // Timestamp of the current transaction char operation; // Operation type: Read/Write }; // Function to find read-write conflicts among given database transactions void findConflicts(vector<Transaction> t) // no-ref, no-const { // Sort the transactions by database records. For the same database record, // sorting should be done in increasing order of access time sort(t.begin(), t.end(), [](const Transaction &x, const Transaction &y) { // compare database records first if (x.record != y.record) { return x.record < y.record; } // compare based on access time when database records are equal return x.timestamp < y.timestamp; }); // Consider each transaction and find their conflicting past transactions for (int i = 0; i < t.size(); i++) { // Start from the previous transaction int j = i - 1; // Consider all past transactions which have accessed the same // database record within an interval of 5 units while (j >= 0 && t[i].record == t[j].record && t[i].timestamp <= t[j].timestamp + 5) { // At-least one write operation 'W' is performed on the record if (t[i].operation == 'W' || t[j].operation == 'W') { cout << "Transaction " << t[j].name << " & " << t[i].name << " are involved in " << t[j].operation << t[i].operation << " conflict" << endl; } // move to the next previous transaction j--; } } } int main() { vector<Transaction> t = { { "T1", "A", 0, 'R' }, { "T2", "A", 2, 'W' }, { "T3", "B", 4, 'W' }, { "T4", "C", 5, 'W' }, { "T5", "B", 7, 'R' }, { "T6", "C", 8, 'W' }, { "T7", "A", 9, 'R' } }; findConflicts(t); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
import java.util.Arrays; import java.util.List; // A class to store transaction details class Transaction { String name; // Transaction name String record; // Data object from the database int timestamp; // Timestamp of the current transaction char operation; // Operation type: Read/Write public Transaction(String name, String record, int timestamp, char operation) { this.name = name; this.record = record; this.timestamp = timestamp; this.operation = operation; } } class Main { // Function to find read-write conflicts among given database transactions public static void findConflicts(List<Transaction> t) { // Sort the transactions by database records. For the same database record, // sorting should be done in increasing order of access time t.sort((x, y) -> { // compare database records first if (!x.record.equals(y.record)) { return x.record.compareTo(y.record); } // compare based on access time when database records are equal return x.timestamp - y.timestamp; }); // Consider each transaction and find their conflicting past transactions for (int i = 0; i < t.size(); i++) { // Start from the previous transaction int j = i - 1; // Consider all past transactions that have accessed the same // database record within an interval of 5 units while (j >= 0 && t.get(i).record.equals(t.get(j).record) && t.get(i).timestamp <= t.get(j).timestamp + 5) { // At-least one write operation 'W' is performed on the record if (t.get(i).operation == 'W' || t.get(j).operation == 'W') { System.out.println("Transaction " + t.get(j).name + " & " + t.get(i).name + " are involved in " + t.get(j).operation + t.get(i).operation + " conflict"); } // move to the next previous transaction j--; } } } public static void main(String[] args) { List<Transaction> t = Arrays.asList( new Transaction("T1", "A", 0, 'R'), new Transaction("T2", "A", 2, 'W'), new Transaction("T3", "B", 4, 'W'), new Transaction("T4", "C", 5, 'W'), new Transaction("T5", "B", 7, 'R'), new Transaction("T6", "C", 8, 'W'), new Transaction("T7", "A", 9, 'R')); findConflicts(t); } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
from operator import attrgetter # A class to store transaction details class Transaction: def __init__(self, name, record, timestamp, operation): self.name = name # Transaction name self.record = record # Data object from the database self.timestamp = timestamp # Timestamp of the current transaction self.operation = operation # Operation type: Read/Write # Function to find read-write conflicts among given database transactions def findConflicts(t): # Sort the transactions by database records. For the same database record, # sorting should be done in increasing order of access time # compare database records first # compare based on access time when database records are equal t.sort(key=attrgetter('record', 'timestamp')) # Consider each transaction and find their conflicting past transactions for i in range(len(t)): # Start from the previous transaction j = i - 1 # Consider all past transactions that have accessed the same # database record within an interval of 5 units while j >= 0 and t[i].record == t[j].record and \ t[i].timestamp <= t[j].timestamp + 5: # At-least one write operation 'W' is performed on the record if t[i].operation == 'W' or t[j].operation == 'W': print(f'Transaction {t[j].name} & {t[i].name} are involved in ' f'{t[j].operation}{t[i].operation} conflict') # move to the next previous transaction j -= 1 if __name__ == '__main__': t = [ Transaction('T1', 'A', 0, 'R'), Transaction('T2', 'A', 2, 'W'), Transaction('T3', 'B', 4, 'W'), Transaction('T4', 'C', 5, 'W'), Transaction('T5', 'B', 7, 'R'), Transaction('T6', 'C', 8, 'W'), Transaction('T7', 'A', 9, 'R') ] findConflicts(t) |
Transaction T1 & T2 are involved in RW conflict
Transaction T3 & T5 are involved in WR conflict
Transaction T4 & T6 are involved in WW conflict
The time complexity of the above solution is O(n.log(n)), where n is the total number of transactions. The time complexity appears to be O(n2) on the first look as a nested loop is involved. However, since the inner loop runs a maximum of 5 times (a constant value), the nested loop executes linearly.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)