Efficient incremental validation of XML documents

D. Barbosa, A. O. Mendelzon, L. Libkin, L. Mignet, M. Arenas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We discuss incremental validation of XML documents with respect to DTDs and XML schema definitions. We consider insertions and deletions of subtrees, as opposed to leaf nodes only, and we also consider the validation of ID and IDREF attributes. For arbitrary schemas, we give a worst-case n log n time and linear space algorithm, and show that it often is far superior to revalidation from scratch. We present two classes of schemas, which capture most real-life DTDs, and show that they admit a logarithmic time incremental validation algorithm that, in many cases, requires only constant auxiliary space. We then discuss an implementation of these algorithms that is independent of, and can be customized for different storage mechanisms for XML. Finally, we present extensive experimental results showing that our approach is highly efficient and scalable.
Original languageEnglish
Title of host publicationData Engineering, 2004. Proceedings. 20th International Conference on
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages671-682
Number of pages12
ISBN (Print)0-7695-2065-0
DOIs
Publication statusPublished - Mar 2004

Fingerprint Dive into the research topics of 'Efficient incremental validation of XML documents'. Together they form a unique fingerprint.

Cite this