edited by
7,794 views
54 votes
54 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?

  1. List all vertices adjacent to a given vertex
  2. List all vertices which have self loops
  3. List all vertices which belong to cycles of less than three vertices
  4. List all vertices reachable from a given vertex
edited by

4 Answers

Best answer
61 votes
61 votes

The answer is D.

  1. This is a simple select query.
  2. This is the simple query we need to check $X=Y$ in the where clause.
  3. Cycle $< 3$ . Means cycles of lengths $1$ and $2$. The cycle of length $1$ is easy., the same as self-loop. The cycle of length $2$ is also not too hard to compute. Though it'll be a bit more complex, will need to do like $(X,Y)\; \&\; (Y, X )$ both present and $ X != Y$. We can do this with a constant length (not depending on the number of tuples) RA query.
  4. This is the hardest part. Here we need to find closure of vertices. This will need a kind of loop. If the graph is like a skewed tree, our query must loop for $O(N)$ times. We can't do this with a constant length query here.

Answer: D.

edited by
0 votes
0 votes
A possible relational algebra query for option C :

 

$\pi _{\text{ u1, v1}} [ \sigma _{\text{ (v1 = u2 AND v2 = u1) OR (u1 = v1 AND u2 = u1 AND u2 = v2) }} ( \xi _{\text{ u1, v1}} Adj \times \xi _{\text{ u2, v2}} Adj ) ]$

 

Cycles of with atmost two vertices.
–3 votes
–3 votes
Answer: C

RA will face problem when we calculate length of self loops as the query will keep on executing on one tuple itself.
–5 votes
–5 votes
ans is C.

we can find A,B,D in O(n) time.

but we cannot find C in O(n)
Answer:

Related questions

52 votes
52 votes
3 answers
1
Kathleen asked Sep 14, 2014
7,258 views
Let r and s be two relations over the relation schemes R and S respectively, and let A be an attribute in R. The relational algebra expression $\sigma_{A=a}(r \bowtie s)...
46 votes
46 votes
6 answers
2
Kathleen asked Sep 14, 2014
8,531 views
Which of the following relational calculus expression is not safe?$\left\{t \mid \exists u \in R_1\left(t[A] = u[A]\right) \land \neg \exists s \in R_2 \left(t[A] = s[A]\...
7 votes
7 votes
3 answers
3
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...