From relation algebra to semi-join algebra
Jelle Hellings, Catherine Pilachowski, Dirk Van Gucht, Marc Gyssens, Yuqing Wu · 2017
Many graph query languages rely on the composition operator to navigate graphs and select nodes of interests, even though evaluating compositions of relations can be costly. Often, this need for composition can be reduced by rewriting towards queries that use semi-joins instead. In this way, the cost of evaluating queries can be significantly reduced.