FIX to The Ring: Worst-Case Optimal Joins in Graph Databases using (Almost) No Extra Space
Level: Medium
Theorem 7.9 holds only for cycles, not for general order graphs (i.e., "hairy"
cycles). Although the reasoning with δ is right (i.e., branching does
not yield more distinct l-paths than edges), the fact that we need as
many distinct l-paths for each attribute A as said in the theorem no
longer holds when there is branching: a single position of A may cover several
l-paths.
We noticed this after Ruben Becker, Adrián Gómez-Brandón,
and Nicola Prezza found an order graph for dimension 6 with just 40 edges. The
lower bound according to the theorem is 42. This also shows, for the first
time, that order graphs can be smaller than the smallest set of cycles.