XML data exchange: Consistency and query answering

Simple item page
dc.contributor.authorArenas, Marcelo
dc.contributor.authorLibkin, Leonid
dc.date.accessioned2024-01-10T13:09:58Z
dc.date.available2024-01-10T13:09:58Z
dc.date.issued2008
dc.description.abstractData exchange is the problem of finding an instance of a target schema, given an instance of a source schema and a specification of the relationship between the source and the target. Theoretical foundations of data exchange have recently been investigated for relational data.
dc.description.abstractIn this article, we start looking into the basic properties of XML data exchange, that is, restructuring of XML documents that conform to a source DTD under a target DTD, and answering queries written over the target schema. We define XML data exchange settings in which source-to-target dependencies refer to the hierarchical structure of the data. Combining DTDs and dependencies makes some XML data exchange settings inconsistent. We investigate the consistency problem and determine its exact complexity.
dc.description.abstractWe then move to query answering, and prove a dichotomy theorem that classifies data exchange settings into those over which query answering is tractable, and those over which it is coNP-complete, depending on classes of regular expressions used in DTDs. Furthermore, for all tractable cases we give polynomial-time algorithms that compute target XML documents over which queries can be answered.
dc.description.funderEngineering and Physical Sciences Research Council
dc.fechaingreso.objetodigital2024-05-14
dc.format.extent72 páginas
dc.fuente.origenWOS
dc.identifier.doi10.1145/1346330.1346332
dc.identifier.eissn1557-735X
dc.identifier.issn0004-5411
dc.identifier.urihttps://doi.org/10.1145/1346330.1346332
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/77732
dc.identifier.wosidWOS:000256117000002
dc.information.autorucIngeniería;Arenas M;S/I;81488
dc.issue.numero2
dc.language.isoen
dc.nota.accesocontenido parcial
dc.publisherASSOC COMPUTING MACHINERY
dc.revistaJOURNAL OF THE ACM
dc.rightsacceso restringido
dc.subjectmanagement
dc.subjecttheory
dc.subjectdata exchange
dc.subjectconsistency
dc.subjectcomputing certain answers
dc.subjectXML
dc.titleXML data exchange: Consistency and query answering
dc.typeartículo
dc.volumen55
sipa.codpersvinculados81488
sipa.indexWOS
sipa.indexScopus
sipa.trazabilidadCarga SIPA;09-01-2024
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
XML data exchange - Consistency and query answering.pdf
Size:
2.67 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas