In a database system, say there are $N$ transactions each having $m_1,m_2,\dots,m_N$ operations. How many concurrent schedules are possible?

$(m_1+m_2+....+m_n)!$ is the number of possible interleavings.
Is this number equal to number of concurrent schedules? Serial schedules have to be discarded from the total number?

  • 1
    $\begingroup$ I suspect that if you read the definitions carefully, this is elementary combinatorics. $\endgroup$ – Raphael Jan 13 '14 at 19:37
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it is pure math problem dump and user is long gone. $\endgroup$ – Evil Jan 20 '16 at 1:42
  • $\begingroup$ @EvilJS Disagree. The question contains conceptual questions about computer science and the asker has logged in within the last three months. $\endgroup$ – David Richerby Jan 20 '16 at 2:40

Number of possible Concurrent schedules are


We need to maintain order of operations of an individual transaction.
Total no of Serial Schedule = n!
Total no of Non-serial Schedule = (Concurrent Schedule - Serial Schedule)

For Example: Consider 4 transactions T1,T2,T3 and T4 having 2,2,3 and 4 operations respectively.
Total operations = 2+2+3+4=11
Total no. of concurrent schedules : $$^{11}C_2*^9C_2*^7C_3*^4C_4 = 69300$$
Out of the 11 possible positions we choose 2 places for T1 and place it operations sequentially , again we choose 2 places for T2 and place its operation sequentially , again we choose 3 places for T3 and place its operation sequentially , The remaining 4 places are used for T4.


First of all let's permute everything; all operations of every transaction. Doing this will result in $(m_1 + m_2 + m_3 + ... + m_k)!$

Now since we cannot change the relative order of execution of operations within individual transactions, therefore, to remove the permutations of internal operations of transaction $T_1$,so we need to divide the above expression by $m_1!$. Same goes for all remaining transactions. Thus we get the expression

$ \dfrac{(m_1 + m_2 + m_3 + ... + m_k)!}{m_1! m_2! ... m_k!}$

  • $\begingroup$ @raphael this includes serial schedules also, so I think we need to subtract it (m!). Correct me if I am wrong $\endgroup$ – Priyesh Kumar Nov 15 '19 at 8:11

Total number of schedules = (m1+m2+m3+....+mk)! / (m1!*m2!m3!...*mk!)
Total serial schedules = N!
So, total concurrent schedules = (m1+m2+m3+....+mk)!/(m1!*m2!m3!...*mk!) - N!

  • 4
    $\begingroup$ This contradicts the earlier answer but neither of you explains why your answer should be considered as correct. $\endgroup$ – David Richerby Jan 6 '18 at 23:31

Number of Concurrent schedules possible are

$\qquad\displaystyle \frac{(m_1 + m_2 + m_3 + \dots + m_k)!}{m_1! \cdot m_2! \cdot m_3! \cdot \dots \cdot m_k!}$

  • 3
    $\begingroup$ Your answer misses a crucial element: why? $\endgroup$ – Raphael Jan 13 '14 at 19:38
  • $\begingroup$ @Raphael : what is the missing crucial element ? $\endgroup$ – vikkyhacks May 3 '15 at 15:49
  • $\begingroup$ @vikkyhacks he did not show why this is true $\endgroup$ – miracle173 Jan 16 '17 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.