Suppose the adjacency relation of vertices in a graph is represented in a table Adj (X,Y). Which of the following queries cannot be expressed by a relational algebra expression of constant length?
Answer is D.
(A) :-> This is simple select query query.
(B) :-> This is simple query we need to check X=Y in where clause.
(C) :-> Cycle $< 3$ . Means cycle of length $1$ & $2$. Cycle of length 1 is easy., same as self loop. Cycle of length $2$ is also not too hard to compute. Though it'll be little complex, will need to do like $(X,Y)$ & $(Y, X )$ both present & $X != Y$,. We can do this with constant RA query.
(D) :-> This is most hard part. Here we need to find closure of vertices. This willl need kind of loop. If the graph is like skewed tree, our query must loop for $O(N)$ times. We can't do with constant length query here.
Answer :-> D
C wouldn't have been expressed had there been $n$ instead of $3$. Similarly, D could also be expressed had the number of vertices been given.
(A) The query will be "Select X from Adj(X,Y) where Y='A' "
here we are finding all nodes adjacent to A