Reasoning about XML update constraints

We introduce in this paper a class of constraints for describing how an XML document can evolve, namely XML update constraints. For these constraints, we study the implication problem, giving algorithms and complexity results for constraints of varying expressive power. Besides classical constraint...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2009-09, Vol.75 (6), p.336-358
Main Authors: Cautis, Bogdan, Abiteboul, Serge, Milo, Tova
Format: Article
Language:English
Subjects:
Computer Science
Data integrity
Implication
Semi-structured data
Update constraints
XML
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-c380t-8aa74280e548b53aef8e9c22b050b3401ad6c7eaf67763f3d4852c98509bbab33
cites cdi_FETCH-LOGICAL-c380t-8aa74280e548b53aef8e9c22b050b3401ad6c7eaf67763f3d4852c98509bbab33
container_end_page 358
container_issue 6
container_start_page 336
container_title Journal of computer and system sciences
container_volume 75
creator Cautis, Bogdan
Abiteboul, Serge
Milo, Tova
description We introduce in this paper a class of constraints for describing how an XML document can evolve, namely XML update constraints. For these constraints, we study the implication problem, giving algorithms and complexity results for constraints of varying expressive power. Besides classical constraint implication, we also consider an instance-based approach in which we take into account data. More precisely, we study implication with respect to a current tree instance, resulting from a series of unknown updates. The main motivation of our work is reasoning about data integrity under update restrictions in contexts where owners may lose control over their data, such as in publishing or exchange.
doi_str_mv 10.1016/j.jcss.2009.02.001
format article
fullrecord <record><control><sourceid>hal_cross</sourceid><recordid>TN_cdi_hal_primary_oai_HAL_inria_00430735v1</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0022000009000154</els_id><sourcerecordid>oai_HAL_inria_00430735v1</sourcerecordid><originalsourceid>FETCH-LOGICAL-c380t-8aa74280e548b53aef8e9c22b050b3401ad6c7eaf67763f3d4852c98509bbab33</originalsourceid><addsrcrecordid>eNp9kMFKxDAQQIMouK7-gKeevEjrJGnaFLwsi7pCRRAFb2GSppqytkuSXfDvbal4dC5zeW9gHiGXFDIKtLjpss6EkDGAKgOWAdAjsqBQQcpKlh-TBQBjKYxzSs5C6EaAioIvyNWLxTD0rv9IUA_7mLw_1cl-12C0iRn6ED26PoZzctLiNtiL370kb_d3r-tNWj8_PK5XdWq4hJhKxDJnEqzIpRYcbSttZRjTIEDzHCg2hSkttkVZFrzlTS4FM5UUUGmNmvMluZ7vfuJW7bz7Qv-tBnRqs6qV671DBZBzKLk40JFmM238EIK37Z9CQU1dVKemLmrqooCN7iTdzpId_zg461UwzvbGNs5bE1UzuP_0H1dqago</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Reasoning about XML update constraints</title><source>ScienceDirect Journals</source><creator>Cautis, Bogdan ; Abiteboul, Serge ; Milo, Tova</creator><creatorcontrib>Cautis, Bogdan ; Abiteboul, Serge ; Milo, Tova</creatorcontrib><description>We introduce in this paper a class of constraints for describing how an XML document can evolve, namely XML update constraints. For these constraints, we study the implication problem, giving algorithms and complexity results for constraints of varying expressive power. Besides classical constraint implication, we also consider an instance-based approach in which we take into account data. More precisely, we study implication with respect to a current tree instance, resulting from a series of unknown updates. The main motivation of our work is reasoning about data integrity under update restrictions in contexts where owners may lose control over their data, such as in publishing or exchange.</description><identifier>ISSN: 0022-0000</identifier><identifier>EISSN: 1090-2724</identifier><identifier>DOI: 10.1016/j.jcss.2009.02.001</identifier><language>eng</language><publisher>Elsevier Inc</publisher><subject>Computer Science ; Data integrity ; Implication ; Semi-structured data ; Update constraints ; XML</subject><ispartof>Journal of computer and system sciences, 2009-09, Vol.75 (6), p.336-358</ispartof><rights>2009 Elsevier Inc.</rights><rights>Distributed under a Creative Commons Attribution 4.0 International License</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c380t-8aa74280e548b53aef8e9c22b050b3401ad6c7eaf67763f3d4852c98509bbab33</citedby><cites>FETCH-LOGICAL-c380t-8aa74280e548b53aef8e9c22b050b3401ad6c7eaf67763f3d4852c98509bbab33</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>230,314,780,784,885,27924,27925</link.rule.ids><backlink>$$Uhttps://inria.hal.science/inria-00430735$$DView record in HAL$$Hfree_for_read</backlink></links><search><creatorcontrib>Cautis, Bogdan</creatorcontrib><creatorcontrib>Abiteboul, Serge</creatorcontrib><creatorcontrib>Milo, Tova</creatorcontrib><title>Reasoning about XML update constraints</title><title>Journal of computer and system sciences</title><description>We introduce in this paper a class of constraints for describing how an XML document can evolve, namely XML update constraints. For these constraints, we study the implication problem, giving algorithms and complexity results for constraints of varying expressive power. Besides classical constraint implication, we also consider an instance-based approach in which we take into account data. More precisely, we study implication with respect to a current tree instance, resulting from a series of unknown updates. The main motivation of our work is reasoning about data integrity under update restrictions in contexts where owners may lose control over their data, such as in publishing or exchange.</description><subject>Computer Science</subject><subject>Data integrity</subject><subject>Implication</subject><subject>Semi-structured data</subject><subject>Update constraints</subject><subject>XML</subject><issn>0022-0000</issn><issn>1090-2724</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2009</creationdate><recordtype>article</recordtype><recordid>eNp9kMFKxDAQQIMouK7-gKeevEjrJGnaFLwsi7pCRRAFb2GSppqytkuSXfDvbal4dC5zeW9gHiGXFDIKtLjpss6EkDGAKgOWAdAjsqBQQcpKlh-TBQBjKYxzSs5C6EaAioIvyNWLxTD0rv9IUA_7mLw_1cl-12C0iRn6ED26PoZzctLiNtiL370kb_d3r-tNWj8_PK5XdWq4hJhKxDJnEqzIpRYcbSttZRjTIEDzHCg2hSkttkVZFrzlTS4FM5UUUGmNmvMluZ7vfuJW7bz7Qv-tBnRqs6qV671DBZBzKLk40JFmM238EIK37Z9CQU1dVKemLmrqooCN7iTdzpId_zg461UwzvbGNs5bE1UzuP_0H1dqago</recordid><startdate>20090901</startdate><enddate>20090901</enddate><creator>Cautis, Bogdan</creator><creator>Abiteboul, Serge</creator><creator>Milo, Tova</creator><general>Elsevier Inc</general><general>Elsevier</general><scope>6I.</scope><scope>AAFTH</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>1XC</scope></search><sort><creationdate>20090901</creationdate><title>Reasoning about XML update constraints</title><author>Cautis, Bogdan ; Abiteboul, Serge ; Milo, Tova</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c380t-8aa74280e548b53aef8e9c22b050b3401ad6c7eaf67763f3d4852c98509bbab33</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2009</creationdate><topic>Computer Science</topic><topic>Data integrity</topic><topic>Implication</topic><topic>Semi-structured data</topic><topic>Update constraints</topic><topic>XML</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Cautis, Bogdan</creatorcontrib><creatorcontrib>Abiteboul, Serge</creatorcontrib><creatorcontrib>Milo, Tova</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><collection>CrossRef</collection><collection>Hyper Article en Ligne (HAL)</collection><jtitle>Journal of computer and system sciences</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Cautis, Bogdan</au><au>Abiteboul, Serge</au><au>Milo, Tova</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Reasoning about XML update constraints</atitle><jtitle>Journal of computer and system sciences</jtitle><date>2009-09-01</date><risdate>2009</risdate><volume>75</volume><issue>6</issue><spage>336</spage><epage>358</epage><pages>336-358</pages><issn>0022-0000</issn><eissn>1090-2724</eissn><abstract>We introduce in this paper a class of constraints for describing how an XML document can evolve, namely XML update constraints. For these constraints, we study the implication problem, giving algorithms and complexity results for constraints of varying expressive power. Besides classical constraint implication, we also consider an instance-based approach in which we take into account data. More precisely, we study implication with respect to a current tree instance, resulting from a series of unknown updates. The main motivation of our work is reasoning about data integrity under update restrictions in contexts where owners may lose control over their data, such as in publishing or exchange.</abstract><pub>Elsevier Inc</pub><doi>10.1016/j.jcss.2009.02.001</doi><tpages>23</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0022-0000
ispartof Journal of computer and system sciences, 2009-09, Vol.75 (6), p.336-358
issn 0022-0000
1090-2724
language eng
recordid cdi_hal_primary_oai_HAL_inria_00430735v1
source ScienceDirect Journals
subjects Computer Science
Data integrity
Implication
Semi-structured data
Update constraints
XML
title Reasoning about XML update constraints
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-26T01%3A41%3A05IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-hal_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Reasoning%20about%20XML%20update%20constraints&rft.jtitle=Journal%20of%20computer%20and%20system%20sciences&rft.au=Cautis,%20Bogdan&rft.date=2009-09-01&rft.volume=75&rft.issue=6&rft.spage=336&rft.epage=358&rft.pages=336-358&rft.issn=0022-0000&rft.eissn=1090-2724&rft_id=info:doi/10.1016/j.jcss.2009.02.001&rft_dat=%3Chal_cross%3Eoai_HAL_inria_00430735v1%3C/hal_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c380t-8aa74280e548b53aef8e9c22b050b3401ad6c7eaf67763f3d4852c98509bbab33%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true