# Can a schedule with cyclic precedence graph still be serialisable?

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?

• Could you please add the definition of the "precedence graph"? I just cannot open the link (don't know why). Anyway, for conflict serializability, there exists a serialization graph ($SG$) whose nodes are the committed transactions and whose edges are all $T_i \to T_j$ ($i \neq j$) such that one of $T_i$'s operations precedes and conflicts with one of $T_j$'s operations. The Serializability Theorem says that a history $H$ is serializable iff $SG(H)$ is acyclic. Hope it helps. Refer to the book chapter for details. Dec 8 '14 at 14:41
• DEar @hengxin, Please See cburch.com/cs/340/reading/serial/index.html , it's say all serializable schedules is not conflict-serializable. so testing for conflict serialize is done with directed graph, so as a result if a graph has a cycle is not conflict serializable and may be not serializable. am i right? Dec 8 '14 at 17:26
• So are you looking for the necessary and sufficient condition for serializability (especially in your EDIT part)? I think we have reached an agreement on conflict serializability. For serializability, it is quite complex: It is NP-complete to test whether a history is serializable. (IMO) That is why the html article does not provide a (polynomial) algorithm. The proof for NP-complete can be found here; Theorem 1. It also involves a graph called polygraph, but it does not suggest an efficient test (as SG does for conflict serializability). Dec 9 '14 at 1:46
• Dear @hengxin, thanks a lot for your effort. i completely edit my question to better understand my question. i'm waiting for your idea. thanks. Dec 9 '14 at 8:20
• Yes. You cannot infer that a history is not serializable just because it is not conflict-serializable. Dec 9 '14 at 12:21

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).