Temporal Slicing in the Evaluation of XML Queries Dengfeng Gao and Richard T. Snodgrass   View Paper (PDF)   Return to Access Methods & Temporal Data (Session B7) Abstract As with relational data, XML data changes over time with the creation, modification, and deletion of XML documents. Expressing queries on time- varying (relational or XML) data is more diffi- cult than writing queries on nontemporal data. In this paper, we present a temporal XML query lan- guage, a2 XQuery, in which we add valid time sup- port to XQuery by minimally extending the syn- tax and semantics of XQuery. We adopt a stra- tum approach which maps a a2 XQuery query to a conventional XQuery. The paper focuses on how to perform this mapping, in particular, on mapping sequenced queries, which are by far the most challenging. The critical issue of support- ing sequenced queries (in any query language) is time-slicing the input data while retaining pe- riod timestamping. Timestamps are distributed throughout an XML document, rather than uni- formly in tuples, complicating the temporal slic- ing while also providing opportunities for op- timization. We propose four optimizations of our initial maximally-fragmented time-slicing ap- proach: selected node slicing, copy-based per- expression slicing, in-place per-expression slic- ing, and idiomatic slicing, each of which reduces the number of constant periods over which the query is evaluated. While performance tradeoffs clearly depend on the underlying XQuery engine, we argue that there are queries that favor each of the five approaches. ©2004 Association for Computing Machinery