How do we distribute the elements into schedules?

  • Context: MHB 
  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Elements
Click For Summary

Discussion Overview

The discussion revolves around the distribution of database elements into schedules involving transactions. Participants explore how to create three distinct schedules: a serial schedule, a conflict serializable schedule, and a non-conflict serializable schedule, while also considering the implications of transaction operations and their order.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant suggests defining the transactions arbitrarily before creating the schedules, questioning how to distribute the twenty elements among the seven transactions.
  • Another participant proposes a specific serial schedule and asks if it meets the criteria for a serial schedule.
  • There is a discussion about the nature of conflict serializability, with participants debating whether swapping non-conflicting operations can yield a conflict serializable schedule.
  • Concerns are raised about maintaining the atomicity of transactions when swapping operations, with emphasis on the order of conflicting operations within the same transaction.
  • Participants explore the possibility of creating a non-conflict serializable schedule and discuss the conditions under which this can be achieved.
  • One participant questions whether simply swapping certain operations is sufficient to achieve a conflict serializable schedule or if more swaps are necessary.
  • There is a suggestion that transactions should follow a specific form (R-W or R-W-R-W) and a proposal for how the transactions should be structured is made.
  • Another participant presents a series of schedules and discusses the potential swaps that could be made to achieve the desired properties of each schedule.

Areas of Agreement / Disagreement

Participants express differing views on the correct approach to defining transactions and schedules, with no consensus reached on the specific schedules or the validity of proposed swaps. The discussion remains unresolved regarding the exact nature of the schedules and the conditions for conflict serializability.

Contextual Notes

Participants highlight limitations regarding the assumptions made about the operations within transactions and the need for clarity on the definitions of serial, conflict serializable, and non-conflict serializable schedules. The discussion includes unresolved mathematical steps and varying interpretations of atomicity and transaction behavior.

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :giggle:

The transactions $T_1, T_2,\ldots , T_7$, the database elements $A, B, C, D, E$ and the below multiset are given
1639981654573.png


Now distribute the twenty elements from $M$ in three different ways so that three different schedules $S_1$, $S_2$ and $S_3$ arise. Also make sure that $S_1$ is a serial schedule, $S_2$ is a conflict serializable schedule, and $S_3$ is a non-conflict serializable schedule. Give the dependency graphs on S2 and S3.Do we distribute the elements of $M$ to the transactions $T_i$ arbitrarily ? :unsure:
 
Last edited by a moderator:
Physics news on Phys.org
Can we first define arbitrarily the seven transactions and then define the three schedules so that $S_1$ is a serial schedult, $S_2$ is conflict serializableand $S_3$ is non-conflict serializable?

We have twenty elements and seven transactions, so should each transaction contain two elements and the six of the transactions have also a third element?

Do we define the transaction for example as follows ?
\begin{align*}&T_1 : ((R, A),(W, A)) \\ &T_2: ((R, A),(W, A)(R, A)) \\ &T_3 : ((W, A),(R, B),(W, B)) \\ &T_4 : ((R, B),(W, B),(R, C)) \\ &T_5: ((W, C), (R, C),(W, C)) \\ &T_6: ((R, D),(W, D),(R, E)) \\ &T_7 : ((W, E),(R, E),(W, E))\end{align*}
Is then a serial schedule \begin{align*}S_1&=((T_1, R, A),(T_1, W, A),(T_2, R, A),(T_2, W, A),(T_2, R, A),\\ & (T_3, W, A),(T_3, R, B),(T_3, W, B),(T_4, R, B),(T_4, W, B),(T_4, R, C),\\ & (T_5, W, C), (T_5, R, C),(T_5, W, C),(T_6, R, D),(T_6, W, D),(T_6, R, E),\\ & (T_7, W, E),(T_7, R, E),(T_7, W, E))\end{align*} ?

:unsure:
 
Hey mathmari!

After reading you notes in your other thread, I believe you are correct. (Nod)
 
Klaas van Aarsen said:
After reading you notes in your other thread, I believe you are correct. (Nod)

A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations.

So we take $S_1$ and we swap at least two non-conflicting operations to get $S_2$. Is that correct?

So do we get the following ?
\begin{align*}S_2&=((T_7, W, E),(T_1, W, A),(T_2, R, A),(T_2, W, A),(T_2, R, A),\\ & (T_3, W, A),(T_3, R, B),(T_3, W, B),(T_4, R, B),(T_4, W, B),(T_4, R, C),\\ & (T_5, W, C), (T_5, R, C),(T_5, W, C),(T_6, R, D),(T_6, W, D),(T_6, R, E),\\ & (T_1, R, A) ,(T_7, R, E),(T_7, W, E))\end{align*} (I swapped the first element of the first line with the first element of the last line) Is that a conflict serializable schedule ? The result is not unique, is it? :unsure: For $S_3$ we have to consider a schedule at which even when we swap non-conflicting operations we don't get a serial schedule, right? :unsure:
 
I'm afraid that is not correct. (Shake)

In transaction $T_1$ we first read from A, and then we write to A.
When we put that read operation near the end, we will read what we (or some other transaction) wrote before, instead of what was there before we wrote.
In other words, the conflicting operations in the same transaction must remain in the same order. 🤔

I believe that we can also not put $(T_7, W, E)$ at the beginning, since then $T_7$ is not atomic any more. Other transactions will read the changed value in E while transaction $T_7$ has not been completed yet, and it will still read and write yet again to E. 🤔

Other than that, yes, we can just swap 2 operations, as long as we make sure that the transactions remain atomic and consistent. 🤔
 
Klaas van Aarsen said:
In transaction $T_1$ we first read from A, and then we write to A.
When we put that read operation near the end, we will read what we (or some other transaction) wrote before, instead of what was there before we wrote.
In other words, the conflicting operations in the same transaction must remain in the same order. 🤔

So when we move $(T_1, R,A)$ do we have to move also $(T_1, W, A)$ so that is again after $(T_1, R, A)$ ? :unsure:
Klaas van Aarsen said:
I believe that we can also not put $(T_7, W, E)$ at the beginning, since then $T_7$ is not atomic any more. Other transactions will read the changed value in E while transaction $T_7$ has not been completed yet, and it will still read and write yet again to E. 🤔

What do you mean by atomic? I got stuck right now. :unsure:
 
If we just swap $(T_5, W, C)$ and $(T_6, R, D)$, do we get a conflict serializable schedule or do we have to do more swaps ? \begin{align*}&((T_1, R, A),(T_1, W, A),(T_2, R, A),(T_2, W, A),(T_2, R, A),\\ & (T_3, W, A),(T_3, R, B),(T_3, W, B),(T_4, R, B),(T_4, W, B),(T_4, R, C),\\ & (T_5, W, C), (T_5, R, C),\textbf{(T_6, R, D)},\textbf{(T_5, W, C)},(T_6, R, D),(T_6, W, D),(T_6, R, E),\\ & (T_7, W, E),(T_7, R, E),(T_7, W, E))\end{align*}
:unsure:
 
In general the transactions should always be in the form R-W or R-W-R-W ?

Then should the transactions be as follows ?
\begin{align*}&T_1 : ((R, A),(W, A), (R, A),(W, A)) \\ &T_2: ((R, A),(W, A)) \\ &T_3 : ((R, B),(W, B),(R, B),(W, B)) \\ &T_4 : ((R, C),(W, C)) \\ &T_5: ( (R, C),(W, C)) \\ &T_6: ((R, D),(W, D)) \\ &T_7 : ((R, E),(W, E),(R, E),(W, E))\end{align*}

:unsure:
 
Then we have :
\begin{align*}S_1 : &((T_1,R, A),(T_1,W, A), (T_1,R, A),(T_1,W, A), \\ &(T_2,R, A),(T_2,W, A), (T_3,R, B),(T_3,W, B),(T_3,R, B),(T_3,W, B), \\ &(T_4,R, C),(T_4,W, C), (T_5,R, C),(T_5,W, C), (T_6,R, D),(T_6,W, D), \\ &(T_7,R, E),(T_7,W, E),(T_7,R, E),(T_7,W, E))\end{align*} We can swap $(T_5,W, C), (T_6,W, D)$ since they have different objects, so they are not in conflict.
\begin{align*} &((T_1,R, A),(T_1,W, A), (T_1,R, A),(T_1,W, A), \\ &(T_2,R, A),(T_2,W, A), (T_3,R, B),(T_3,W, B),(T_3,R, B),(T_3,W, B), \\ &(T_4,R, C),(T_4,W, C), (T_5,R, C),(T_6,W, D), (T_6,R, D),(T_5,W, C), \\ &(T_7,R, E),(T_7,W, E),(T_7,R, E),(T_7,W, E))\end{align*}
We can also swap $(T_1,R, A), (T_2,R, A)$ since they are both R, so they are not in conflict.
So we get:
\begin{align*}S_2 : &((T_1,R, A),(T_1,W, A), (T_2,R, A),(T_1,W, A), \\ &(T_1,R, A),(T_2,W, A), (T_3,R, B),(T_3,W, B),(T_3,R, B),(T_3,W, B), \\ &(T_4,R, C),(T_4,W, C), (T_5,R, C),(T_6,W, D), (T_6,R, D),(T_5,W, C), \\ &(T_7,R, E),(T_7,W, E),(T_7,R, E),(T_7,W, E))\end{align*} We can swap $(T_1,R, A),(T_1,W, A)$ since they are in conflict
\begin{align*} &((T_1,R, A),(T_1,W, A),(T_1,W, A), (T_1,R, A), \\ &(T_2,R, A),(T_2,W, A), (T_3,R, B),(T_3,W, B),(T_3,R, B),(T_3,W, B), \\ &(T_4,R, C),(T_4,W, C), (T_5,R, C),(T_5,W, C), (T_6,R, D),(T_6,W, D), \\ &(T_7,R, E),(T_7,W, E),(T_7,R, E),(T_7,W, E))\end{align*}
We can swap also $(T_1,R, A),(T_2,W, A)$ since they are in conflict
\begin{align*}S_3 : &((T_1,R, A),(T_1,W, A),(T_1,W, A), (T_2,W, A), \\ &(T_2,R, A),(T_1,R, A), (T_3,R, B),(T_3,W, B),(T_3,R, B),(T_3,W, B), \\ &(T_4,R, C),(T_4,W, C), (T_5,R, C),(T_5,W, C), (T_6,R, D),(T_6,W, D), \\ &(T_7,R, E),(T_7,W, E),(T_7,R, E),(T_7,W, E))\end{align*} Are these schedules correct? :unsure:
 

Similar threads

MHB Transactions & schedules - Dependency relations
  • · Replies 1 ·
Replies
1
Views
948
Undergrad Enumerating a Large Ordinal: Can We Find a Limit to the Continuum?
  • · Replies 27 ·
Replies
27
Views
4K