Evolving Schemes for Streaming XML

In this paper, the authors model schema evolution for XML by defining formal language operators on Visibly Pushdown Languages (VPLs). Their goal is to provide a framework for efficient validation of streaming XML in the realistic setting where the schemas of the exchanging parties evolve and thus diverge from one another. They show that Visibly Pushdown Languages are closed under the defined language operators and this enables one to expand the schemas (for XML) in order to account for flexible or constrained evolution.