Incremental Validation of XML Databases

We discuss algorithmic and systems issues on the incremental schema
validation of XML databases with respect to DTDs, XML Schemas and
XQuery's type system under updates consisting of element tag
renamings, insertions and deletions. For DTDs we provide a worst-case
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 is
the number of updates. Note that a brute force solution requires O(n)
steps: following an update, we run the updated lists of elements
through automatons that correspond to regular expressions in the
DTD. For XML Schemas and XQuery types, the problem is harder, since an
update to a single node may have global repercussions for the typing
of the tree. We provide a worst-case O(m log^2 n) algorithm that is
based on the use of tree automata and an O(n) auxiliary data
structure.  Next we provide experimental results showing that for real
DTDs the worst case is relatively rare. Furthermore, we provide an
alternative auxiliary structure consisting of only a schema-dependent
set of counters for each list of elements in the database. This
auxiliary structure enables O(1) incremental validation in most cases,
using an algorithm that exploits a form of "locality".