On the complexity of verifying consistency of XML specifications

Arenas, M; Fan, WF; Libkin, L

Abstract

XML 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 verification 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. © 2008 Society for Industrial and Applied Mathematics.

Más información

Título según WOS: On the complexity of verifying consistency of XML specifications
Título según SCOPUS: On the complexity of verifying consistency of XML specifications
Título de la Revista: SIAM JOURNAL ON COMPUTING
Volumen: 38
Número: 3
Editorial: SIAM PUBLICATIONS
Fecha de publicación: 2008
Página de inicio: 841
Página final: 880
Idioma: English
URL: http://epubs.siam.org/doi/abs/10.1137/050646895
DOI:

10.1137/050646895

Notas: ISI, SCOPUS