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.
- SR $\supset$ CSR. In other words, if a history $h$ is CSR, it must be SR; however, the converse is not valid.
The Serializability Theorem is for CSR (although it is called Serializability Theorem):
A history $h$ is CSR $\iff$ SG(h) is acyclic.
For SR: a history $h$ is SR $\iff$ PG(h) is acyclic.
- 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).