-
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?
-
- List of all vertices adjacent to a given vertex
- List of all vertices which have self loops
- List of all vertices which belong to cycles of less than three vertices
- List of all vertices reachable from a given vertex
- List of all vertices adjacent to a given vertex
Correct Option: 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 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.
