TY - GEN
T1 - New Results on the Complexity of Deletion Propagation
AU - Miao, Dongjing
AU - Li, Jianzhong
AU - Cai, Zhipeng
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - The problem of deletion propagation in relational database has been studied in database community for decades, where tuples are deleted from the source database in order to realize a desired removal of tuples from the result of a certain query. The deletion may result in unexpected view and source side effects. To minimize the side effects, we study two problems: MaxDP which is to seek a deletion of source tuples that maximizes query result remaining after deleting some view tuples, and MinSD which is to seek a minimum set of source tuples that should be deleted. Two problems have been proved that they are polynomially tractable for conjunctive queries without existential variables ((Formula Presented)-CQs). However, for (Formula Presented)-CQs, the complexity of MaxDP is still unknown for deletion forbidden restriction, and so does MinSD in the presence of inclusion dependencies. In this paper, new complexity results are obtained on both problems for (Formula Presented)-CQs. MaxDP is turned out to be not only NP-complete, but also NP-hard to approximate within (Formula Presented) for any constant (Formula Presented) when the deletion of some tuples is forbidden. We then show that even for linear queries, MinSD is no longer polynomially tractable in the presence of inclusion dependencies. The results shows that the complexity of deletion propagation is very sensitive to the presence of some simple constraints.
AB - The problem of deletion propagation in relational database has been studied in database community for decades, where tuples are deleted from the source database in order to realize a desired removal of tuples from the result of a certain query. The deletion may result in unexpected view and source side effects. To minimize the side effects, we study two problems: MaxDP which is to seek a deletion of source tuples that maximizes query result remaining after deleting some view tuples, and MinSD which is to seek a minimum set of source tuples that should be deleted. Two problems have been proved that they are polynomially tractable for conjunctive queries without existential variables ((Formula Presented)-CQs). However, for (Formula Presented)-CQs, the complexity of MaxDP is still unknown for deletion forbidden restriction, and so does MinSD in the presence of inclusion dependencies. In this paper, new complexity results are obtained on both problems for (Formula Presented)-CQs. MaxDP is turned out to be not only NP-complete, but also NP-hard to approximate within (Formula Presented) for any constant (Formula Presented) when the deletion of some tuples is forbidden. We then show that even for linear queries, MinSD is no longer polynomially tractable in the presence of inclusion dependencies. The results shows that the complexity of deletion propagation is very sensitive to the presence of some simple constraints.
KW - Complexity
KW - Database
KW - Deletion propagation
UR - https://www.scopus.com/pages/publications/85089715403
U2 - 10.1007/978-3-030-57602-8_30
DO - 10.1007/978-3-030-57602-8_30
M3 - 会议稿件
AN - SCOPUS:85089715403
SN - 9783030576011
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 336
EP - 345
BT - Algorithmic Aspects in Information and Management - 14th International Conference, AAIM 2020, Proceedings
A2 - Zhang, Zhao
A2 - Li, Wei
A2 - Du, Ding-Zhu
PB - Springer
T2 - 14th International Conference on Algorithmic Aspects in Information and Management, AAIM 2020
Y2 - 10 August 2020 through 12 August 2020
ER -