On the complexity of view update analysis and its application to annotation propagation

This paper investigates three problems identified in [1] 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 t...

Full description

Saved in:
Bibliographic Details
Main Authors: Cong, Gao, Fan, Wenfei, Geerts, Floris, Li, Jianzhong, Luo, Jizhou
Other Authors: School of Computer Engineering
Format: Article
Language:English
Published: 2013
Subjects:
Online Access:https://hdl.handle.net/10356/98880
http://hdl.handle.net/10220/13488
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-98880
record_format dspace
spelling sg-ntu-dr.10356-988802020-05-28T07:18:22Z On the complexity of view update analysis and its application to annotation propagation Cong, Gao Fan, Wenfei Geerts, Floris Li, Jianzhong Luo, Jizhou School of Computer Engineering DRNTU::Engineering::Computer science and engineering This paper investigates three problems identified in [1] 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 in [1], 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 [1]. We revisit these problems by considering several dichotomies: (1) views defined in various subclasses of SPJU, versus SPJU views under a practical key preserving condition; (2) annotations attached to existing tuples in a view versus annotations on tuples to be inserted into the view; and (3) 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. Indeed, some problems become tractable for certain key preserving views, as opposed to the intractability of their counterparts that are not key preserving. However, group annotations often make the analysis harder. In addition, the problems have quite diverse complexity when annotations are attached to existing tuples in a view and when they are entered for tuples to be inserted into the view. 2013-09-16T07:22:58Z 2019-12-06T20:00:46Z 2013-09-16T07:22:58Z 2019-12-06T20:00:46Z 2012 2012 Journal Article Cong, G., Fan, W., Geerts, F., Li, J., & Luo, J. (2012). On the Complexity of View Update Analysis and Its Application to Annotation Propagation. IEEE Transactions on Knowledge and Data Engineering, 24(3), 506-519. 1041-4347 https://hdl.handle.net/10356/98880 http://hdl.handle.net/10220/13488 10.1109/TKDE.2011.27 en IEEE transactions on knowledge and data engineering © 2012 IEEE
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic DRNTU::Engineering::Computer science and engineering
spellingShingle DRNTU::Engineering::Computer science and engineering
Cong, Gao
Fan, Wenfei
Geerts, Floris
Li, Jianzhong
Luo, Jizhou
On the complexity of view update analysis and its application to annotation propagation
description This paper investigates three problems identified in [1] 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 in [1], 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 [1]. We revisit these problems by considering several dichotomies: (1) views defined in various subclasses of SPJU, versus SPJU views under a practical key preserving condition; (2) annotations attached to existing tuples in a view versus annotations on tuples to be inserted into the view; and (3) 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. Indeed, some problems become tractable for certain key preserving views, as opposed to the intractability of their counterparts that are not key preserving. However, group annotations often make the analysis harder. In addition, the problems have quite diverse complexity when annotations are attached to existing tuples in a view and when they are entered for tuples to be inserted into the view.
author2 School of Computer Engineering
author_facet School of Computer Engineering
Cong, Gao
Fan, Wenfei
Geerts, Floris
Li, Jianzhong
Luo, Jizhou
format Article
author Cong, Gao
Fan, Wenfei
Geerts, Floris
Li, Jianzhong
Luo, Jizhou
author_sort Cong, Gao
title On the complexity of view update analysis and its application to annotation propagation
title_short On the complexity of view update analysis and its application to annotation propagation
title_full On the complexity of view update analysis and its application to annotation propagation
title_fullStr On the complexity of view update analysis and its application to annotation propagation
title_full_unstemmed On the complexity of view update analysis and its application to annotation propagation
title_sort on the complexity of view update analysis and its application to annotation propagation
publishDate 2013
url https://hdl.handle.net/10356/98880
http://hdl.handle.net/10220/13488
_version_ 1681056869078007808