MAX: Incremental Maintenance of Schema-Based XML Statistics Maya Ramanath, Lingzhi Zhang, Juliana Freire, and Jayant R. Haritsa   View Paper (PDF)   Return to Research Session 8: XML Query Processing (I) Abstract 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. In this paper, we investigate efficient strategies for incrementally maintaining statistical summaries as and when updates are applied to the data. Specifically, we propose algorithms that handle both the addition of new documents as well as random insertions in the existing document trees. We also show, through a detailed performance evaluation, that our incremental techniques are significantly faster than the naive recomputation approach; and that estimation accuracy can be maintained even with a fixed memory budget. ©2006 Association for Computing Machinery