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 (varDelta V), deletion propagation is to find a side effect free update (varDelta D) on database D such that (Q(D{setminus }varDelta D)=V{setminus }varDelta 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 ((textit{b}text {-}mathsf{dp}) for short), where number of tuples deleted ‘(|varDelta D|)’ is bounded by constant b, in which it aims to find the view side-effect free and bounded (varDelta 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. |
Year | Venue | Field |
---|---|---|
2016 | COCOA | Discrete mathematics,Combinatorics,Algebraic number,Relational database,Tuple,Computer science,Functional dependency,Monotone polygon,Computational complexity theory,Bounded function |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
9 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dongjing Miao | 1 | 18 | 9.91 |
Yingshu Li | 2 | 671 | 53.71 |
Xianmin Liu | 3 | 12 | 5.00 |
Jianzhong Li | 4 | 3196 | 304.46 |