4,600 views

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

### 1 comment

Both relational algebra and TRC cannot be used to perform queries that are transitive closures.

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.

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.
What is meant by Relational Algebra expression of constant length?
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

C wouldn't have been expressed had there been $n$ instead of $3$. Similarly, D could also be expressed had the number of vertices been given.

(A) The query will be "Select X from Adj(X,Y) where Y='A'  "

here we are finding all nodes adjacent to A

RA will face problem when we calculate length of self loops as the query will keep on executing on one tuple itself.

Till length 3 cycles can be found using relational algebra. D should be the answer here.
Thanks @Akash and @Arjun sir for clearification
what if the question is asking cycle of length of 100? Is it also constant?
ans is C.

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

but we cannot find C in O(n)
by

Can we compare like this ..i.e time complexity with relational algebra of constant length...?
What does a constant length query mean in this question ?