On the Complexity of View Update Analysis and its Application to Annotation Propagation

This paper investigates three problems identified by Buneman et al. for annotation propagation, namely, the view side-effect, source side-effect and annotation placement problems. Given annotations entered for a tuple or an attribute in a view, these problems ask what tuples or attributes in the source have to be annotated to produce the view annotations. As observed by Buneman et al., these problems are fundamental not only for data provenance but also for the management of view updates. For an annotation attached to a single existing tuple in a view, it has been shown that these problems are often intractable even for views defined in terms of simple SPJU queries. We revisit these problems by considering several dichotomies: (a) views defined in various subclasses of SPJU, versus SPJU views under a practical key preserving condition; (b) annotations attached to existing tuples in a view versus annotations on tuples to be inserted into the view; and (c) a single-tuple annotation versus a group of annotations. We provide a complete picture of intractability and tractability for the three problems in all these settings. We show that key preserving views often simplify the propagation analysis. However, group annotations often make the analysis harder.