|
|
|
|
|
by namibj
1423 days ago
|
|
Funnily enough, this hypergraph view is used to describe symptomatic query complexity for cyclical joins, the simplest if which is "count triangles in adjacency list" (naive RDBMS yields O(n²) on pathological data, despite the wrist case optimal tactic being something like O(n + #Triangles), with #Triangles limited inherently to O(n^(1.5))). See https://arxiv.org/abs/1404.0703 for some reading material and one particular way at beyond worst case (i.e., sharing worst case asympotics with the best constant time algorithm, but better performance on non-pathological data (a more precise notion is complicated; there are at least 3 different useful definitions)) runtime performance. AFAIK the worst cyclical query on a 2-column table is "k-clique counting", from a POV of performance between WCOJ and what Postgres can do (asympotics). |
|