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 AD on database D such that Q(DΔD) = VΔ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 '|ΔD|' 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.
展开▼
机译：删除传播问题是关系数据库中的一类视图更新问题[1]。给定源数据库D，单调关系代数查询Q，由查询Q（d）生成的视图v和Δv的更新，删除传播是在数据库d上找到副作用，使得q（d ΔD）= v ΔV。通常，更新的数据库可能非常远离原始数据库。在本文中，我们提出了一种新的方法，有界版本删除传播问题（简称B-DP），其中删除的元组数为“|ΔD|”被常数B界限，其中它旨在找到无副作用和有界ΔD，然后分析其计算复杂度。我们的结果表明，在许多情况下，数据和组合复杂性下降，即使是功能依赖性限制版本删除传播。
展开▼
