IMAX: Incremental Maintenance of Schema-Based XML Statistics

Current approaches for estimating the cardinality of XML queries are applicable to a static scenario wherein the underlying XML data does not change subsequent to the collection of statistics on the repository. However, in practice, many XML-based applications are dynamic and involve frequent updates to the data. This paper investigates efficient strategies for incrementally maintaining statistical summaries as and when updates are applied to the data. Specifically, the paper proposes algorithms that handle both the addition of new documents as well as random insertions in the existing document trees.