Database-Management-System
February 13, 2024GATE 2000
February 13, 2024GATE 2001
|
Question 24
|
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 all vertices which have self loops
|
|
|
List all vertices which belong to cycles of less than three vertices
|
|
|
List all vertices reachable from a given vertex
|
Question 24 Explanation:
(a) Finding a adjacency vertex for the given vertex is too simple i.e., Adj(X,Y).
(b) Finding a self loop is also simple (Oop(X,X))
(c) If a → b, b → c then c!=a, finding this is also simple.
(d) List all the elements reachable from a given vertex is too difficult in Relational Algebra.
(b) Finding a self loop is also simple (Oop(X,X))
(c) If a → b, b → c then c!=a, finding this is also simple.
(d) List all the elements reachable from a given vertex is too difficult in Relational Algebra.
Correct Answer: D
Question 24 Explanation:
(a) Finding a adjacency vertex for the given vertex is too simple i.e., Adj(X,Y).
(b) Finding a self loop is also simple (Oop(X,X))
(c) If a → b, b → c then c!=a, finding this is also simple.
(d) List all the elements reachable from a given vertex is too difficult in Relational Algebra.
(b) Finding a self loop is also simple (Oop(X,X))
(c) If a → b, b → c then c!=a, finding this is also simple.
(d) List all the elements reachable from a given vertex is too difficult in Relational Algebra.