@inproceedings{d815d29ed87c4cb18f0c7e03470905b5,
title = "On the complexity of bounded deletion propagation",
abstract = "Deletion propagation problem is a class of view update problem in relational databases [1]. Given a source database D, a monotone relational algebraic query Q, the view V generated by the query Q(D) and an update on view ΔV , deletion propagation is to find a side effect free update ΔD on database D such that Q(D\textbackslash{}ΔD) = V \textbackslash{}ΔV . In general, the database updated may be very distant from the original database. In this paper, we propose a new approach, bounded version deletion propagation problem (b-dp for short), where number of tuples deleted {\textquoteleft}|ΔD|{\textquoteright} is bounded by constant b, in which it aims to find the view side-effect free and bounded ΔD, then analyze its computational complexity. Our results show that in many cases both the data and combined complexity drop, even for functional dependency restricted version deletion propagation.",
keywords = "Bounded deletion propagation, Complexity, Database, View update",
author = "Dongjing Miao and Yingshu Li and Xianmin Liu and Jianzhong Li",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016 ; Conference date: 16-12-2016 Through 18-12-2016",
year = "2016",
doi = "10.1007/978-3-319-48749-6\_33",
language = "英语",
isbn = "9783319487489",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "453--462",
editor = "Minming Li and Lusheng Wang and Chan, \{T-H. Hubert\}",
booktitle = "Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings",
address = "德国",
}