# Number of concurrent schedules in database

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?

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

Number of possible Concurrent schedules are

$$^{m_1+m_2+m_3+...+m_n}C_{m_1}*^{m_2+m_3+...+m_n}C_{m_2}*^{m_3+...+m_n}C_{m_3}*...*^{m_n}C_{m_n}$$

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!}$

• @raphael this includes serial schedules also, so I think we need to subtract it (m!). Correct me if I am wrong – 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!

• This contradicts the earlier answer but neither of you explains why your answer should be considered as correct. – 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!}$

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