[Solved]: Can a schedule with cyclic precedence graph still be serialisable?

Problem Detail: 

We know Every conflict serializable schedule is serializable, but not all serializable schedules conflict-serializable. (*) so it means there is at least one serializable schedule that not conflict serializable.

One way of Testing conflict serializability is using Directed graph as mentioned http://www.cburch.com/cs/340/reading/serial/index.html

So if a graph for a schedule has a cycle, this schedule is not conflic serializable. so by using (*) we can say maybe this schedule be a serializable . (i.e we cannot surely determine it's serilizabe or not, just we know it's not conflict serializable)

My inference is right? any idea?

Asked By : Maryam Panahi

Answered By : hengxin

So if a graph for a schedule has a cycle, this schedule is not conflic serializable. so by using (*) we can say maybe this schedule be a serializable

Yes. You cannot infer that a history is not serializable just because it is not conflict-serializable.

so as a conclusion, it's contradict to Serializability Theorem that says that a history H is serializable iff SG(H) is acyclic.

No. You are talking about two different graphs and two different serializability criteria. And you are confusing them. See my explanation below.

---

The key point here is to tell serializability (SR, for short) from conflict-serializability (CSR, for short) and the polygraph (PG, for short) from serializability graph (SG, for short).

The definition for PG can be found in this paper. The results about SR and polygraph below are also in this paper.

The definition for SG and CSR can be found in this book chapter.

In the following, I list some key points on your questions.

1. SR $\supset$ CSR. In other words, if a history $h$ is CSR, it must be SR; however, the converse is not valid.

2. The Serializability Theorem is for CSR (although it is called Serializability Theorem):

   A history $h$ is CSR $\iff$ SG(h) is acyclic.

3. For SR: a history $h$ is SR $\iff$ PG(h) is acyclic.

4. For a history $h$, SG(h) is more restrictive than PG(h) and leads to an efficient test for CSR. Specifically, we have the following complexity results:
   • Testing whether a history $h$ is CSR (or equivalently, whether SG(h) is acyclic) is polynomial.
   • Testing whether a history $h$ is SR (or equivalently, whether PG(h) is acyclic) is NP-complete.

Notice that the polygraph for a history for SR is quite different from the traditional graphs we learn in class. So don't assume that it is polynomial to test its acyclicity (actually it is not).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33968