I/O-efficient join dependency testing, Loomis–Whitney join, and triangle enumeration
Xiaocheng Hu, Miao Qiao, Yufei Tao · Journal of Computer and System Sciences · 2016
We revisit two fundamental problems in database theory. The join-dependency (JD) testing problem is to determine whether a given JD holds on a relation r . We prove that the problem is NP-hard even if the JD involves only relations each of which has only two attributes. The JD-existence testing problem is to determine if there exists any non-trivial JD satisfied by r . We present an I/O-efficient algorithm in the external memory model, which in fact settles the closely related Loomis–Whitney enumeration problem. As a side product, we solve the triangle enumeration problem with the optimal I/O-complexity, improving a recent result of Pagh and Silvestri in PODS'14.