On the data complexity of relative information completeness

作者：

Highlights：

• This work is among the first efforts to study the data complexity of relative information completeness.

• Three problems fundamental to relative information completeness are identified and studied.

• We provide the upper and lower bounds of these problems, all matching, for data complexity.

摘要

Highlights•This work is among the first efforts to study the data complexity of relative information completeness.•Three problems fundamental to relative information completeness are identified and studied.•We provide the upper and lower bounds of these problems, all matching, for data complexity.

论文关键词：Incomplete information,Relative completeness,Master data management,Partially closed databases,Data complexity

论文评审过程：Received 19 July 2013, Revised 20 February 2014, Accepted 15 April 2014, Available online 24 April 2014.

论文官网地址：https://doi.org/10.1016/j.is.2014.04.001