Functional dependency restricted insertion propagation (Q1986557)

Views in database systems provide an excerpt of underlying information, and they can be used to restrict the amount of information that specific target users need to know or are allowed to access. While processing of queries over views is simple, propagating updates expressed over views to the underlying base data is known to be hard (and impossible in a side-effect-free manner for large classes of views). This paper presents complexity results to decide whether there is a side-effect-free propagation of given insertions into subclasses of monotonic views expressed in the relational algebra over relations with functional dependencies. The problem is abbreviated with the acronym FD-vsef-IP (Functional Dependency, view side-effect-free, Insertion Propagation) and considered for insertions of single tuples as well as groups of tuples. In their theorems, the authors establish the following results: FD-vsef-IP is NP-complete for union views under group insertions on data complexity (Theorem 1). FD-vsef-IP is coNP-complete for select-join queries under group insertions on combined complexity (Theorem 2). FD-vsef-IP is NP-complete for select-project-join queries under group insertions with finite domain on data complexity; it is in PTime for select-project-join queries without self-joins under single insertions on data complexity (Theorem 3). FD-vsef-IP is \(\Sigma_2^{\mathrm{P}}\)-complete for select-project-join queries under group insertions with finite domain on combined complexity (Theorem 4). FD-vsef-IP is \(\Sigma_2^{\mathrm{P}}\)-complete for select-join-union queries under group insertions with finite domain on combined complexity (Theorem 5). This paper is restricted to the above complexity results. Practical aspects (such as (a) what to do if an insertion cannot be propagated in a side-effect-free manner or (b) whether to allow view updates if such cases can arise) are not considered.