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

作者：

Highlights：

• 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.

摘要

•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.

论文关键词：Join dependency,Loomis–Whitney join,Triangle enumeration,External memory

论文评审过程：Received 17 August 2015, Revised 21 April 2016, Accepted 17 May 2016, Available online 11 June 2016, Version of Record 15 July 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.05.005