Ranita works as an Assistant Professor at the Computer Science and Engineering Department at IIT Roorkee. She has completed her PhD from the Computer Science and Engineering Department at IIT Kharagpur. Before that, she has done her MTech from IIEST Shibpur, and got job offers from companies like Amazon, Samsung Labs etc. However, she preferred to pursue higher studies to stay in the field of academics and teaching. She believes in the motto of free education and contribution.


Alma Mater:

IIT Kharagpur
2012 to 2016
Master of Engineering
Indian Institute of Engineering Science and Technology, Shibpur
2010 to 2012
Bachelor of Technology
Kalyani Government Engineering College
2005 to 2009


Assistant Professor
Indian Institute of Technology Roorkee
Project Linked Personnel
Indian Statistical Institute, Kolkata
2009 to 2010
7 months 1 week ago

The correct answer is (b) remains same. To understand this, let us revise the informal algorithm for Timestamp based protocol for concurrency control (copied from Wikipedia, you can also refer to the formal version of the algorithm there):

1) If a transaction wants to read an object,

a) but the transaction started before the object's write timestamp it means that something changed the object's data after the transaction started. In this case, the transaction is canceled and must be restarted.
b) and the transaction started after the object's write timestamp, it means that it is safe to read the object. In this case, if the transaction timestamp is after the object's read timestamp, the read timestamp is set to the transaction timestamp.
2) If a transaction wants to write to an object,

a) but the transaction started before the object's read timestamp it means that something has had a look at the object, and we assume it took a copy of the object's data. So we can't write to the object as that would make any copied data invalid, so the transaction is aborted and must be restarted.
b) and the transaction started before the object's write timestamp it means that something has changed the object since we started our transaction. In this case, we use the Thomas write rule and simply skip our write operation and continue as normal; the transaction does not have to be aborted or restarted
c) otherwise, the transaction writes to the object, and the object's write timestamp is set to the transaction's timestamp.

Now consider the following example schedule:

T1      T2      T3      T4

Consider that after the execution of the last R(A), T4 needs to rollback (as given in the question). So, RTS(A) was 4 and now we need to decide what should be the new RTS for A. Note that, the schedule at hand now is something like the following:

T1      T2      T3

Independent of T4, this schedule will have RTS(A) = 3 when T2 tries to write and hence T2 should be aborted by rule 2(a).

Now, after rollback of T4, consider option (a) i.e. changing the RTS(A) to 0. This will certainly allow W(A) by T2 to execute without any problem as it falls under rule 2(c) and hence violates concurrency by allowing T2 to write a data already read by T3.

Consider option (c) i.e. RTS(A) becomes equal to the timestamp of the transaction which read 'A' just before T4, in this example then RTS(A) becomes 1. And hence the same problem arises as choosing option (a).

Therefore, if we choose option (b) and keep the RTS(A) same as before i.e. 4, then W(A) by T2 will fall under rule 2(a) and hence will be aborted. So, option (b) is the correct answer.

This is why RTS is kept as the largest of the timestamps of the transactions which has read the data, and not the recent timestamp.

Example text
8 months 3 weeks ago

This is an example of fan trap and chasm trap and how to resolve these scenarios. The following brief explanation may help you in understanding the concept which is usually found to be dubious across the web. This explanation is made in parity with the concept explained in Wikipedia (https://en.wikipedia.org/wiki/Entity–relationship_model#Model_usability_issues). You can also refer to https://db.grussell.org/section005.html to understand in detail.

Example text
10 months 1 week ago

You are very close to the answer. But, there is one catch; the first row of pixels (at y = 0) and the last row of pixels (at y = 37) are not full length. You may try to modify the approach accordingly to get to the correct answer. Very good presentation, by the way.

Example text
10 months 2 weeks ago

Consider the attribute set ABCDEG and the FD set
AB → C, AC → B, AD → E, B → D, BC → A, E → G
Is the following decomposition of R(ABCDEG)
(a) dependency-preserving?
(b) lossless-join?
Give proper justification for your answer.

jayantachakr's picture
Jayanta Chakraborty
innovwelt's picture
arvind.rawat's picture
Arvind Rawat
pritam's picture
Pritam Prasun
techtud's picture
Techtud Admin
pritam's picture
Pritam Prasun
vivek14's picture
Vivek Vikram Singh
pashupati's picture
Pashupati Jha
priyesh's picture
Priyesh Priyatam
girraj's picture
shreyans's picture
Shreyans Dhankhar
ribhu122's picture
Ribhu Ranjan
prafull's picture
Prafull Ranjan
antonio's picture
Antonio Anastasio Bruto da Costa
shabinmuhammed's picture
Shabin Muhammed
shuvankarchakraborty's picture


28 Oct 2015 - 11:49pm

I am not being able to find any occurrence of g(a2). Can you please point out to the exact line you are referring to?

more less
28 Oct 2015 - 12:15pm

It is an interesting problem.
You may find the solution with explanation here: http://math.stackexchange.com/questions/1499757/an-encoding-of-non-empty...
Let me know if there is any difficulty in understanding.

more less
28 Oct 2015 - 11:57am

For both the questions answers should be Option (D).
The line

i = T->left && T->middle && T->right ? 1 : 0

gives you 1 in i if all the 3 children are present, otherwise 0.
Now, you need to add up this 1 or 0 with the counts obtained from all the subtrees, as there can be at most three subtrees from a node we should write the recursive call in the next line as follows:

i + find3Child T->left + find3Child T->middle + find3Child T->right

which basically sums up i with return values obtained from all three function calls, you must be careful to realize that even if there are no parentheses, those are function calls in the given pseudo code (possibly a printing mistake).

For the second part, as the find3Child function is being executed one time for each node and contains constant time executable code inside it, the complexity is O(n) for n number of given nodes.

more less
17 Oct 2015 - 3:58pm

The correct answer is 2,2,2... all the options give [a1, c1] as output.
As the confusion is with the second choice, I am explaining that part only.
T1 contains [a1, b1, b2, b3, c1]; therefore, (S×T1) − R gives us [(b1,x2), (b2,x1), (b2,x2), (b3,x1), (b3,x2)]
Therefore project operation gives ΠA((S×T1) − R) = [b1, b2, b3]
Now, I am quite sure that the next line T ← T1 − T2 is part of the second option, which gives us
T = [a1, c1]. Therefore, number of tuples in T = 2.

more less
17 Oct 2015 - 3:36pm

@Banti Arya, please ask your new query as a separate doubt in the doubt section selecting relevant topic from the hierarchical drop-down lists. This way, experts from that subject/topic will get notified, and you will get the best answer quickly.

more less
17 Oct 2015 - 3:02pm

Degree matrix of the given graph
\(D = \begin{bmatrix}
3 & 0 & 0 & 0 & 0\\
0 & 4 & 0 & 0 & 0\\
0 & 0 & 3 & 0 & 0\\
0 & 0 & 0 & 4 & 0\\
0 & 0 & 0 & 0 & 2

Adjacency matrix of the given graph
\(A = \begin{bmatrix}
0 & 1 & 1 & 1 & 0\\
1 & 0 & 1 & 1 & 1\\
1 & 1 & 0 & 1 & 0\\
1 & 1 & 1 & 0 & 1\\
0 & 1 & 0 & 1 & 0

Therefore, Laplacian matrix of the given graph
\(Q = D - A = \begin{bmatrix}
3 & 0 & 0 & 0 & 0\\
0 & 4 & 0 & 0 & 0\\
0 & 0 & 3 & 0 & 0\\
0 & 0 & 0 & 4 & 0\\
0 & 0 & 0 & 0 & 2
\end{bmatrix} - \begin{bmatrix}
0 & 1 & 1 & 1 & 0\\
1 & 0 & 1 & 1 & 1\\
1 & 1 & 0 & 1 & 0\\
1 & 1 & 1 & 0 & 1\\
0 & 1 & 0 & 1 & 0
\end{bmatrix} = \begin{bmatrix}
3 & -1 & - 1 & -1 & 0\\
-1 & 4 & -1 & -1 & -1\\
-1 & -1 & 3 & -1 & 0\\
-1 & -1 & -1 & 4 & -1\\
0 & -1 & 0 & -1 & 2

Kirchoff’s Matrix-Tree Theorem says that the number of spanning trees in a simple graph G, is the absolute value of any cofactor of the Laplacian Matrix of G. Cofactor of Q can be computed by removing an arbitrary row and an arbitrary column from the matrix and then taking the determinant of it. So, we remove last row and last column from G and get our count of spanning trees of G i.e τ(G) as follows.
\(\tau(G) = \det\left(\begin{bmatrix}
3 & -1 & - 1 & -1\\
-1 & 4 & -1 & -1\\
-1 & -1 & 3 & -1\\
-1 & -1 & -1 & 4\\
\end{bmatrix}\right) = 40\)

Therefore, the number of spanning trees of the given graph G is 40.
For detailed methods on how to count spanning trees you can go through this tutorial starting from page 26 : http://www.techtud.com/resource-share/graph-theory-suppementary-material...

more less

As there is only one leaf node, it is understandable that the tree will be like a path with h+1 nodes. However, starting from the root, at each stage you need to decide the next node to be the parent's left or right child. So, we get a counting problem where we have h times to decide Left or Right, that means we can have 2h different binary trees of height h with exactly one leaf node.

more less
2 Oct 2015 - 4:45pm

I don't think Cartesian product can be represented using Venn diagrams. You can try the methods proposed in this link to prove the given expression without using examples.

more less
1 Oct 2015 - 6:18pm

Sorry for the delayed reply, I just ran the query.
Here I am attaching the screenshot.

I missed the aliasing last time, otherwise it is working fine.
Hope this helps.

more less
1 Oct 2015 - 1:11pm

Can you please upload the Triangle table by exporting and zipping it?

more less