On the complexity of verifying consistency of XML specifications

Simple item page
dc.contributor.authorArenas, Marcelo
dc.contributor.authorFan, Wenfei
dc.contributor.authorLibkin, Leonid
dc.date.accessioned2024-01-10T13:15:51Z
dc.date.available2024-01-10T13:15:51Z
dc.date.issued2008
dc.description.abstractXML specifications often consist of a type definition (typically, a document type definition (DTD)) and a set of integrity constraints. It has been shown previously that such specifications can be inconsistent, and thus it is often desirable to check consistency at compile time. It is known [W. Fan and L. Libkin, J. ACM, 49 (2002), pp. 368 - 406] that for general keys, foreign keys, and DTDs the consistency problem is undecidable; however, it becomes NP-complete when all keys are one-attribute (unary) and tractable, if no foreign keys are used. In this paper, we consider a variety of previously studied constraints for XML data and investigate the complexity of the consistency problem. Our main conclusion is that, in the presence of foreign key constraints, compile-time veri. cation of consistency is infeasible. We look at absolute constraints that hold in the entire document and relative constraints that hold only in a part of the document. For absolute constraints, we prove decidability and establish complexity bounds for primary multiattribute keys and unary foreign keys and study unary constraints that involve regular expressions. For relative constraints, we prove that even for unary constraints the consistency problem is undecidable. We also show that results continue to hold for extended DTDs, a more expressive typing mechanism for XML.
dc.description.funderNSF Career Award
dc.description.funderEPSRC
dc.description.funderNSFC
dc.description.funderNSERC
dc.description.funderCITO
dc.description.funderPREA
dc.description.funderEuropean Commission Marie Curie Excellence
dc.description.funderEngineering and Physical Sciences Research Council
dc.fechaingreso.objetodigital2024-05-14
dc.format.extent40 páginas
dc.fuente.origenWOS
dc.identifier.doi10.1137/050646895
dc.identifier.eissn1095-7111
dc.identifier.issn0097-5397
dc.identifier.urihttps://doi.org/10.1137/050646895
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/78536
dc.identifier.wosidWOS:000258895100005
dc.information.autorucIngeniería;Arenas M;S/I;81488
dc.issue.numero3
dc.language.isoen
dc.nota.accesocontenido parcial
dc.pagina.final880
dc.pagina.inicio841
dc.publisherSIAM PUBLICATIONS
dc.revistaSIAM JOURNAL ON COMPUTING
dc.rightsacceso restringido
dc.subjectXML
dc.subjectkeys and foreign keys
dc.subjectdocument type definition
dc.subjectconsistency
dc.subjectcomplexity
dc.subjectCONSTRAINTS
dc.subjectQUERIES
dc.titleOn the complexity of verifying consistency of XML specifications
dc.typeartículo
dc.volumen38
sipa.codpersvinculados81488
sipa.indexWOS
sipa.indexScopus
sipa.trazabilidadCarga SIPA;09-01-2024
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
On the complexity of verifying consistency of XML specifications.pdf
Size:
2.81 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas