Suppose the adjacency relation of vertices in a graph is represented in a…
2001
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
Attempted by 16 students.
Show answer & explanation
Correct answer: D
To find if vertex B is reachable from vertex A, you have to check for paths of length 1, length 2, length 3, and so on, up to length n-1 (where n is the total number of vertices).
To find paths of length 1: Adj
To find paths of length 2: π X,Z (Adj (X,Y) ⋈ Adj(Y,Z))
To find paths of length 3: You need to join the table three times.
If a graph has 5 vertices, you need an expression with up to 4 joins. If a graph has 10,000 vertices, you need an expression with up to 9,999 joins.
Conclusion: Because the number of operations depends entirely on the number of vertices in the database instance, it is mathematically impossible to write a single, fixed-length standard relational algebra expression that can calculate reachability for any arbitrary graph.
(Note: To handle this limitation in real-world systems, SQL uses Recursive Common Table Expressions (CTEs), and extended relational algebra includes a specific Transitive Closure operator ( α ), but neither of these are part of basic, constant-length relational algebra).