But while looking for the all vertices connected to a given vertex, the number of cartesian products of the table depends on the number of vertices in the graph (number of tuples at max) in the table, which is unknown.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+29 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?

- List 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

+33 votes

Best answer

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

+8

Cycle of length 2 can be found by cartesian product of Adj tables renamed as A and B and then applying the select condition -> A.x=B.y and A.y=B.x. We can simply find cycles of length n with given n in input. Here, the number of cartesian products is based on input n.

But while looking for the all vertices connected to a given vertex, the number of cartesian products of the table depends on the number of vertices in the graph (number of tuples at max) in the table, which is unknown.

But while looking for the all vertices connected to a given vertex, the number of cartesian products of the table depends on the number of vertices in the graph (number of tuples at max) in the table, which is unknown.

+2

Constant length means it has specific value and value cannot go upto infinite

Here we can think of adjacency matrix

(D) is telling in it's row, if A to B=1

B to C=1

C to D=1

D to E=1 etc etc ,

but , there can be many path like for path A to D

we can go A-B-D

or A-E-D

or, A-C-B-D

etc

So, cannot measure in constant length

Here we can think of adjacency matrix

(D) is telling in it's row, if A to B=1

B to C=1

C to D=1

D to E=1 etc etc ,

but , there can be many path like for path A to D

we can go A-B-D

or A-E-D

or, A-C-B-D

etc

So, cannot measure in constant length

+2 votes

Suppose following is the given table Graph:

1. $ π._{Y}(\sigma_X='vertex-number'(GRAPH))$ // vertex adjacent to a given vertex

2. $ π._{Y}(\sigma_X=y(GRAPH))$ //vertices with self loop

3. If we look into the table, $1->2, 2->1$, it's a cycle of length 2, which contains vertices less than $3 (<=2)$, it also needs a constant length RA query, which is quite complex to be written, but we can take the cross product between the two instances of the same table and can find it.

4. not possible with constant length query, for example $1->2, 2->3, 3->4$, and so on.. 2,3,4 and so on are reachable from vertex 1, and this list can go further.

Hence (D) is the correct option!

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 553
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,903 questions

52,285 answers

182,209 comments

67,715 users