GATE CS 2001 Q1.24 — Relational Model: Relational Algebra

To determine which query cannot be expressed by a relational algebra (RA) expression of constant length, let's analyze each option:

• Option A: List all vertices adjacent to a given vertex $v$
  This requires a simple selection and projection: $$\pi_{Y}(\sigma_{X = v}(\text{Adj}))$$ This is of constant length.
• Option B: List all vertices which have self-loops
  A self-loop occurs when a vertex is adjacent to itself ($X = Y$): $$\pi_{X}(\sigma_{X = Y}(\text{Adj}))$$ This is of constant length.
• Option C: List all vertices which belong to cycles of less than three vertices
  Cycles of length less than 3 can only be of length 1 (self-loops) or length 2 (where $u \to v$ and $v \to u$ with $u \neq v$).
  • Cycles of length 1: $C_1 = \pi_{X}(\sigma_{X=Y}(\text{Adj}))$.
  • Cycles of length 2: $C_2 = \pi_{X}(\sigma_{X = Y_1 \land Y = X_1 \land X \neq Y}(\text{Adj}(X, Y) \bowtie \rho_{\text{Adj1}(X_1, Y_1)}(\text{Adj})))$.
  The union $C_1 \cup C_2$ gives the desired set, which is of constant length.
• Option D: List all vertices reachable from a given vertex
  Finding all reachable vertices in an arbitrary graph requires computing the transitive closure of the adjacency relation. Since the number of vertices $n$ is not fixed, the path length can be arbitrarily large. Standard relational algebra lacks recursion or looping constructs, meaning we cannot write a single, fixed-length expression to compute transitive closure for graphs of arbitrary size.

Therefore, reachability (Option D) cannot be expressed by a relational algebra expression of constant length.