Loading…

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
Published in:IEEE transactions on knowledge and data engineering 2012-03, Vol.24 (3), p.506-519
Main Authors: Gao Cong, Wenfei Fan, Geerts, F., Jianzhong Li, Jizhou Luo
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c293t-c1bfb09b4909a36a491010a53f7fb8f4644f185a79db1bca5f8d80e9bf773a873
cites cdi_FETCH-LOGICAL-c293t-c1bfb09b4909a36a491010a53f7fb8f4644f185a79db1bca5f8d80e9bf773a873
container_end_page 519
container_issue 3
container_start_page 506
container_title IEEE transactions on knowledge and data engineering
container_volume 24
creator Gao Cong
Wenfei Fan
Geerts, F.
Jianzhong Li
Jizhou Luo
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.
doi_str_mv 10.1109/TKDE.2011.27
format article
fullrecord <record><control><sourceid>crossref_ieee_</sourceid><recordid>TN_cdi_crossref_primary_10_1109_TKDE_2011_27</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>5708147</ieee_id><sourcerecordid>10_1109_TKDE_2011_27</sourcerecordid><originalsourceid>FETCH-LOGICAL-c293t-c1bfb09b4909a36a491010a53f7fb8f4644f185a79db1bca5f8d80e9bf773a873</originalsourceid><addsrcrecordid>eNo9kLFOwzAQhi0EEqWwsbH4AUi5i53aHqtSoKJSGVoYIzuxwSiNo9gS9O1pKGK6__R_d8NHyDXCBBHU3eb5fjHJAXGSixMywqKQWY4KTw8ZOGaccXFOLmL8BAApJI7I27ql6cPSedh1jf32aU-Do6_eftFtV-tk6azVzT76SHVb02WKdNZ1ja908uFwGg59G9Jxe-lDp99_8yU5c7qJ9upvjsn2YbGZP2Wr9eNyPltlVa5Yyio0zoAyXIHSbKq5QkDQBXPCGen4lHOHstBC1QZNpQsnawlWGScE01KwMbk9_q36EGNvXdn1fqf7fYlQDlLKQUo5SCnzAb854t5a-48WAiRywX4ApFReDA</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>On the Complexity of View Update Analysis and Its Application to Annotation Propagation</title><source>IEEE Xplore (Online service)</source><creator>Gao Cong ; Wenfei Fan ; Geerts, F. ; Jianzhong Li ; Jizhou Luo</creator><creatorcontrib>Gao Cong ; Wenfei Fan ; Geerts, F. ; Jianzhong Li ; Jizhou Luo</creatorcontrib><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.</description><identifier>ISSN: 1041-4347</identifier><identifier>EISSN: 1558-2191</identifier><identifier>DOI: 10.1109/TKDE.2011.27</identifier><identifier>CODEN: ITKEEH</identifier><language>eng</language><publisher>IEEE</publisher><subject>Algebra ; Algorithm design and analysis ; Annotation ; Complexity theory ; Database systems ; Polynomials ; SPJU queries ; view maintenance ; view updates ; XML</subject><ispartof>IEEE transactions on knowledge and data engineering, 2012-03, Vol.24 (3), p.506-519</ispartof><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c293t-c1bfb09b4909a36a491010a53f7fb8f4644f185a79db1bca5f8d80e9bf773a873</citedby><cites>FETCH-LOGICAL-c293t-c1bfb09b4909a36a491010a53f7fb8f4644f185a79db1bca5f8d80e9bf773a873</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/5708147$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>314,780,784,27924,27925,54796</link.rule.ids></links><search><creatorcontrib>Gao Cong</creatorcontrib><creatorcontrib>Wenfei Fan</creatorcontrib><creatorcontrib>Geerts, F.</creatorcontrib><creatorcontrib>Jianzhong Li</creatorcontrib><creatorcontrib>Jizhou Luo</creatorcontrib><title>On the Complexity of View Update Analysis and Its Application to Annotation Propagation</title><title>IEEE transactions on knowledge and data engineering</title><addtitle>TKDE</addtitle><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.</description><subject>Algebra</subject><subject>Algorithm design and analysis</subject><subject>Annotation</subject><subject>Complexity theory</subject><subject>Database systems</subject><subject>Polynomials</subject><subject>SPJU queries</subject><subject>view maintenance</subject><subject>view updates</subject><subject>XML</subject><issn>1041-4347</issn><issn>1558-2191</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2012</creationdate><recordtype>article</recordtype><recordid>eNo9kLFOwzAQhi0EEqWwsbH4AUi5i53aHqtSoKJSGVoYIzuxwSiNo9gS9O1pKGK6__R_d8NHyDXCBBHU3eb5fjHJAXGSixMywqKQWY4KTw8ZOGaccXFOLmL8BAApJI7I27ql6cPSedh1jf32aU-Do6_eftFtV-tk6azVzT76SHVb02WKdNZ1ja908uFwGg59G9Jxe-lDp99_8yU5c7qJ9upvjsn2YbGZP2Wr9eNyPltlVa5Yyio0zoAyXIHSbKq5QkDQBXPCGen4lHOHstBC1QZNpQsnawlWGScE01KwMbk9_q36EGNvXdn1fqf7fYlQDlLKQUo5SCnzAb854t5a-48WAiRywX4ApFReDA</recordid><startdate>20120301</startdate><enddate>20120301</enddate><creator>Gao Cong</creator><creator>Wenfei Fan</creator><creator>Geerts, F.</creator><creator>Jianzhong Li</creator><creator>Jizhou Luo</creator><general>IEEE</general><scope>97E</scope><scope>RIA</scope><scope>RIE</scope><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20120301</creationdate><title>On the Complexity of View Update Analysis and Its Application to Annotation Propagation</title><author>Gao Cong ; Wenfei Fan ; Geerts, F. ; Jianzhong Li ; Jizhou Luo</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c293t-c1bfb09b4909a36a491010a53f7fb8f4644f185a79db1bca5f8d80e9bf773a873</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2012</creationdate><topic>Algebra</topic><topic>Algorithm design and analysis</topic><topic>Annotation</topic><topic>Complexity theory</topic><topic>Database systems</topic><topic>Polynomials</topic><topic>SPJU queries</topic><topic>view maintenance</topic><topic>view updates</topic><topic>XML</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Gao Cong</creatorcontrib><creatorcontrib>Wenfei Fan</creatorcontrib><creatorcontrib>Geerts, F.</creatorcontrib><creatorcontrib>Jianzhong Li</creatorcontrib><creatorcontrib>Jizhou Luo</creatorcontrib><collection>IEEE All-Society Periodicals Package (ASPP) 2005–Present</collection><collection>IEEE All-Society Periodicals Package (ASPP) 1998-Present</collection><collection>IEEE Xplore</collection><collection>CrossRef</collection><jtitle>IEEE transactions on knowledge and data engineering</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Gao Cong</au><au>Wenfei Fan</au><au>Geerts, F.</au><au>Jianzhong Li</au><au>Jizhou Luo</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>On the Complexity of View Update Analysis and Its Application to Annotation Propagation</atitle><jtitle>IEEE transactions on knowledge and data engineering</jtitle><stitle>TKDE</stitle><date>2012-03-01</date><risdate>2012</risdate><volume>24</volume><issue>3</issue><spage>506</spage><epage>519</epage><pages>506-519</pages><issn>1041-4347</issn><eissn>1558-2191</eissn><coden>ITKEEH</coden><abstract>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.</abstract><pub>IEEE</pub><doi>10.1109/TKDE.2011.27</doi><tpages>14</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1041-4347
ispartof IEEE transactions on knowledge and data engineering, 2012-03, Vol.24 (3), p.506-519
issn 1041-4347
1558-2191
language eng
recordid cdi_crossref_primary_10_1109_TKDE_2011_27
source IEEE Xplore (Online service)
subjects Algebra
Algorithm design and analysis
Annotation
Complexity theory
Database systems
Polynomials
SPJU queries
view maintenance
view updates
XML
title On the Complexity of View Update Analysis and Its Application to Annotation Propagation
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-25T07%3A27%3A57IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-crossref_ieee_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=On%20the%20Complexity%20of%20View%20Update%20Analysis%20and%20Its%20Application%20to%20Annotation%20Propagation&rft.jtitle=IEEE%20transactions%20on%20knowledge%20and%20data%20engineering&rft.au=Gao%20Cong&rft.date=2012-03-01&rft.volume=24&rft.issue=3&rft.spage=506&rft.epage=519&rft.pages=506-519&rft.issn=1041-4347&rft.eissn=1558-2191&rft.coden=ITKEEH&rft_id=info:doi/10.1109/TKDE.2011.27&rft_dat=%3Ccrossref_ieee_%3E10_1109_TKDE_2011_27%3C/crossref_ieee_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c293t-c1bfb09b4909a36a491010a53f7fb8f4644f185a79db1bca5f8d80e9bf773a873%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=5708147&rfr_iscdi=true