558 views
2 votes
2 votes

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?

A

List of all vertices adjacent to a given vertex

B

List all vertices which have self loops

C

List all vertices which belong to cycles of less than three vertices

D

List all vertices reachable from a given vertex

1 Answer

1 votes
1 votes

Answer is option (D).

  1. List of all vertices adjacent to a given vertex $X$ can be easily found from $Adj(X,Y)$.
  2. Listing all vertices having self-loops is easy. Just find $Adj(X,X)$.
  3. Listing all vertices involved in cycles of length 1 or 2 can be accomplished without much difficulty. Cycles of length 1 are same as self-loops. Finding cycles of length 2 requires examining $Adj(X,Y)$ and $Adj(Y,X)$. This is not that easy, but achievable using a constant length relational algebra expression.
  4. Listing all vertices reachable from a given vertex requires us to find the vertex cover which is difficult to implement using a constant length relational algebra expression.

Related questions

7 votes
7 votes
3 answers
2
go_editor asked Feb 8, 2018
1,986 views
Consider a relation examinee (regno, name, score), where regno is the primary key to score is a real number.Write an SQL query to list the regno of examinees who have a s...