Incremental Validation of XML Documents Yannis Papakonstantinou and Victor Vianu   View Paper (PDF)   Return to Research Papers Abstract We investigate the incremental validation of XML documents with respect to DTDs and XML Schemas, under updates consisting of element tag renamings, insertions and deletions. DTDs are modeled as extended context-free grammars and XML Schemas are abstracted as "specialized DTDs", allowing to decouple element types from element tags. For DTDs, we exhibit an $O(m \log n)$ incremental validation algorithm using an auxiliary structure of size $O(n)$, where $n$ is the size of the document and m the number of updates. For specialized DTDs, we provide an $O(m \log^2 n)$ incremental algorithm, again using an auxiliary structure of size $O(n)$. This is a significant improvement over brute-force re-validation from scratch. ©2004 Association for Computing Machinery