Name
Title | ||
|---|---|---|
I/O-efficient join dependency testing, Loomis-Whitney join, and triangle enumeration. |
Abstract | ||
|---|---|---|
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. 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.jcss.2016.05.005 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
Join dependency,Loomis–Whitney join,Triangle enumeration,External memory | Discrete mathematics,Combinatorics,Existential quantification,Join dependency,Enumeration,Input/output,Database theory,Mathematics,Auxiliary memory | Journal |
Volume | Issue | ISSN |
82 | 8 | 0022-0000 |
Citations | PageRank | References |
1 | 0.36 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiaocheng Hu | 1 | 218 | 11.94 |
| Miao Qiao | 2 | 90 | 5.04 |
| Yufei Tao | 3 | 7231 | 316.71 |