A method, system and computer program product are disclosed for determining a shortest path between two nodes of a graph, where the graph is represented in one or more tables of a relational database as a plurality of records identifying edges between pairs of connected nodes in the graph. A request specifies a source node (or set of source nodes), a target node (or set of target nodes) and a maximum path length L. Each path length l, from 1 to L, is iteratively tested by first generating a query comprising a sequence of join operations for that path length, and secondly decomposing the join operations into a sequence of one or more tree-structured queries comprising semi-join operations. Each tree-structured query when executed as a sequence of semi-join operations will return either an empty result set, indicating that no shortest path exists at that path length, or a non-empty result set which identifies all edges at step k of each shortest path of length l, where 1≤k≤l. If all of the tree-structured queries for a path length l return non-empty result sets, the shortest paths of length l can be constructed from the result sets with each result set specifying the edges at a particular step along the shortest path.