Abstract | dc.description.abstract | In this paper we address the problem of modeling
and implementing temporal data in XML. We propose
a data model for tracking historical information in
an XML document and for recovering the state of the
document as of any given time. We study the temporal
constraints imposed by the data model, and present algorithms
for validating a temporal XML document against
these constraints, along with methods for fixing inconsistent
documents. In addition, we discuss different ways
of mapping the abstract representation into a temporal
XML document, and introduce TXPath, a temporal
XML query language that extends XPath 2.0.
In the second part of the paper, we present our approach
for summarizing and indexing temporal XML
documents. In particular we show that by indexing continuous
paths, i.e., paths that are valid continuously during
a certain interval in a temporal XML graph, we
can dramatically increase query performance. To achieve
this, we introduce a new class of summaries, denoted
TSummary, that adds the time dimension to the wellknown
path summarization schemes. Within this framework,
we present two new summaries: LCP and Interval
summaries. The indexing scheme, denoted TempIndex,
integrates these summaries with additional data
structures. We give a query processing strategy based on
TempIndex and a type of ancestor-descendant encoding,
denoted temporal interval encoding. We present a persistent
implementation of TempIndex, and a comparison
against a system based on a non-temporal path index, and one based on DOM. Finally, we sketch a language
for updates, and show that the cost of updating the index
is compatible with real-world requirements. | en_US |