I/O-efficient join dependency testing, Loomis–Whitney join, and triangle enumeration

• It is NP-hard to check whether a relation satisfies a specific join dependency J, even if all the relation schemas in J have only 2 attributes.
• An I/O-efficient algorithm is given for checking whether a relation satisfies any non-trivial join dependency at all.
• An I/O-efficient algorithm is given for processing Loomis–Whitney (LW) Joins.
• An I/O-efficient algorithm is given for solving the triangle enumeration problem optimally and deterministically.

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.