UoL CS Notes
Menu

Schedules

COMP207 Lectures

Translating SQL into Low-Level Operations

In our example table with the following schema:

Emplyees(e_id, first_name, last_name, birth_day, salary)

From this we could run the following two statements:

SELECT salary
FROM Employees
WHERE e_id = 1234;

UPDATE Employees
SET salary = salary * 1.1
WHERE e_id = 1234;

These statement could be made into the following three transaction operations:

  1. read(e_id = 1234, salary)
  2. salary = salary * 1.1
  3. write(e_id = 1234, salary)

There are two database operations (read() and write()) and a calculation.

Basic Operations

There are two basic operations of database transactions:

  • read(X) - Reads a database item X into a program variable, also called X:
    1. Find the address of the disk block that contains item X.
    2. Copy that disk block into a buffer in main memory.
      • Provided that disk block isn’t already in some main memory buffer.
    3. Copy item X from the buffer to the program variable X.
  • write(X) - Writes the value of program variable X into the database item named X:
    1. Find the address of the disk block that contains item X.
    2. Copy that disk block into a buffer in main memory.
      • If that disk block is not already in some main memory buffer.
      • Copy item X from the program variable X into its correct location in the buffer.
      • Store the updated block from the buffer back to disk either immediately or at some later point in time.

Schedules

Schedules hold many transactions for execution. The operations making up the transaction are then executed by the schedule in the date order:

  • It must preserve that the operation in each transaction happen in the right order.

There are two types:

  • Serial Schedules - Executes the transactions one after another.
  • Concurrent Schedules - Can interleave operations from the transactions in the schedule.

Serial Schedule Example

Consider the following two transactions:

Begin(T1)
	read(X);
	X := X + 100;
	write(X);
	read(Y);
	Y := Y + 50
	write(Y);
	commit;
End(T1)

Begin(T2)
	read(X);
	read(Y);
	X := X + Y;
	write(X);
	commit;
End(T2)

Shorthand

We could write this as the following shorthand:

\[S_a:r_1(X);w_1(X);r_1(Y);w_1(Y);c_1; r_2(X); r_2(Y); w_2(X); c_2;\]

The following symbols are used:

  • $S_{\text{id}}$ = Schedule (id is the schedule ID)
  • $r_i(X)$ = read(X) in transaction i
  • $w_i(X)$ = write(X) in transaction i
  • $c_i$ = commit in transaction i
  • $a_i$ = abort (rollback) in transaction i

Concurrent Schedule Example

The following transactions:

Begin(T1)
	read(X);
	X := X + 100;
	write(X);
	read(Y);
	Y := Y + 50
	write(Y);
	commit;
End(T1)

Begin(T2)
	read(X);
	read(Y);
	X := X + Y;
	write(X);
	commit;
End(T2)

can be represented in many ways in a concurrent schedule:

\[S_b: r_1(X); w_1(X); r_2(X); r_1(Y); w_1(y); c_1; r_2(Y); w_2(X); c_2;\]

In addition all serial schedules are types of concurrent schedules.

The order of operations must still reflect that of the order of the underlying transactions.