Research On Temporal XML Index Based On Suffix Tree

XML (Extensible Markup Language) is becoming a platform-independent standard and transmission format for data exchange, because of its simplicity, scalability, interoperability and openness. The supporting technologies of web application in current are mostly limited to static and snapshot-type. But for XML document itself, the structure and content may changes as time goes by. In order to record the modification of the XML document, express time-related data, track historical information and restore the document state at any historical state, we propose Temporal XML with "Temporal Information" in its document. The emergence of Temporal XML is inevitable with the development of web application and database technology. In such situation, it is more and more significant to research the topics about the expressions of time-related data, historical information track and the document state restore at any time. However, most of the current temporal XML index are inefficient for large temporal XML documents and have a high space cost.In order to resolve the current common problems of high space cost, inefficient queries in XML index models, we present a new Temporal XML index model-TXSIM, which consists of suffix indexing tree, node coding tables and aggregated-node chain. The main idea is:firstly we encode the temporal XML document stored the nodes into a node coding table, at the same time convert the temporal XML document into its equivalent OEM tree. Then we generate its suffix indexing tree, which can be used for temporal path querying, according to the OEM tree, and aggregated-nodes chain, which could be used for temporal value querying. Our result of experiments shows that TXSIM has a lower space cost, higher efficiency of querying the complex structure temporal query XML documents and lower maintenance costs.The thesis firstly introduces XML and TXML model, temporal database, suffix tree and semi-structured data model (OEM), and then analysises of the current index models and compares their advantages and disadvantages. After analysising the popular encoding programs a coding method based on prime numbers and the sequence is proposed, which occupys less space and maintain efficiently. Then the thesis proposes TXSIM (Temporal XML indexing model based on suffix tree), finally, it gives TXSIM inserting, modifying, deleting algorithm, and designs experiments to prove TXSIM's effectiveness and feasibility.