What is the difference between "conflict serializable" and "conflict equivalent"?

Question

In database theory, what is the difference between "conflict serializable" and "conflict equivalent"?

My textbook has a section on conflict serializable but glosses over conflict equivalence. These are probably both concepts I am familiar with, but I am not familiar with the terminology, so I am looking for an explanation.

Tropous

Answer 1

Just two terms to describe one thing in different ways.

Conflict equivalent: you need to say Schedule A is conflict equivalent to Schedule B. it must involve two schedules

Conflict serializable: Still use Schedule A and B. we can say Schedule A is conflict serializable. Schedule B is conflict serializable.

We didn't say Schedule A/B is conflict equivalent

We didn't say Schedule A is conflict serializable to Schedule B

Keg

So you are emphasizing the difference in specific terminology? To use "conflict equivalence" one must refer to two separate schedules, which maintain conflict equivalence with each other? And to use "conflict serializable" one must refer to a single schedule that has the property of being conflict equivalent to at least one other schedule? So "conflict equivalence" refers to at least two schedules, each of which is "conflict serializable"? – Tropous

Yes, It's what I just learned in my Transaction Processing class. And should be right. – Keg

Answer 2

Conflict in DBMS can be defined as two or more different transactions accessing the same variable and atleast one of them is a write operation.

For example:

T1: Read(X)   
T2: Read (X)

In this case there's no conflict because both transactions are performing just read operations.

But in the following case:

T1: Read(X)   
T2: Write(X)

there's a conflict.

Lets say we have a schedule S, and we can reorder the instructions in them. and create 2 more schedules S1 and S2.

Conflict equivalent: Refers to the schedules S1 and S2 where they maintain the ordering of the conflicting instructions in both of the schedules. For example, if T1 has to read X before T2 writes X in S1, then it should be the same in S2 also. (Ordering should be maintained only for the conflicting operations).

Conflict Serializability: S is said to be conflict serializable if it is conflict equivalent to a serial schedule (i.e., where the transactions are executed one after the other).

Wallas

You said in your unedited answer that you would post pictures if it wasn't clear. Could you please do it anyway? – Meshach

Answer 3

From Wikipedia.

Conflict-equivalence

The schedules S1 and S2 are said to be conflict-equivalent if the following conditions are satisfied:

1. Both schedules S1 and S2 involve the same set of transactions (including ordering of actions within each transaction).

2. The order of each pair of conflicting actions in S1 and S2 are the same.

Conflict-serializable

A schedule is said to be conflict-serializable when the schedule is conflict-equivalent to one or more serial schedules.

Another definition for conflict-serializability is that a schedule is conflict-serializable if and only if its precedence graph/serializability graph, when only committed transactions are considered, is acyclic (if the graph is defined to include also uncommitted transactions, then cycles involving uncommitted transactions may occur without conflict serializability violation).

Armandinaarmando

I know, I have read the Wiki...I just don't see how these two things are actually different. – Tropous

Answer 4

If a schedule S can be transformed into a schedule S´ by a series of swaps of non-conflicting instructions, we say that S and S´ are conflict equivalent.

We say that a schedule S is conflict serializable if it is conflict equivalent to a serial schedule.

Pyongyang

Answer 5

Conflict serializable means conflict equuivalent to any serial schedule.

Response

Answer 6

Conflict Equivalent Schedules: if a Schedule S can be transformed into a schedule S' by a series of swaps of non conflicting instructions, we say that schedule S & S' are conflict equivalent.

Conflict Serializable Schedule: Schedule S is conflict serializable if it is conflict equivalent to a serial schedule.

Sandarac

Answer 7

Definitions have already been explained perfectly, but I feel this will be very useful to some.

I've developed a small console program (on github) which can test any schedule for conflict serializability and will also draw a precedence graph.

Winer

Answer 8

If there is at least one conflict equivalent schedule for considered transaction schedule, it is conflict serializable.

Turnedon