Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractIn this paper, we revisit two fundamental problems in database theory. The first one is called join dependency (JD) testing, where we are given a relation r and a JD, and need to determine whether the JD holds on r. The second problem is called JD existence testing, where we need to determine if there exists any non-trivial JD that holds on r. We prove that JD testing is NP-hard even if the JD is defined only on binary relations (i.e., each with only two attributes). Unless P = NP, this result puts a negative answer to the question whether it is possible to efficiently test JDs defined exclusively on small (in terms of attribute number) relations. The question has been open since the classic NP-hard proof of Maier, Sagiv, and Yannakakis in JACM-81 which requires the JD to involve a relation of (d) attributes, where d is the number of attributes in r. For JD existence testing, the challenge is to minimize the computation cost because the problem is known to be solvable in polynomial time. We present a new algorithm for solving the problem I/O-efficiently in the external memory model. Our algorithm in fact settles the closely related Loomis-Whitney (LW) enumeration problem, and as a side product, achieves the optimal I/O complexity for the triangle enumeration problem, improving a recent result of Pagh and Silvestri in PODS-14.
All Author(s) ListHu X., Qiao M., Tao Y.
Name of Conference34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2015
Start Date of Conference21/05/2015
End Date of Conference04/06/2015
Place of ConferenceMelbourne
Country/Region of ConferenceAustralia
Volume Number31
Pages291 - 301
LanguagesEnglish-United Kingdom
KeywordsJoin Dependency, Loomis-Whitney Join, Triangle Enumeration

Last updated on 2020-09-08 at 04:14