Path Expressions' Optimization And Its Evaluation Techniques For XML Query And Filtering

XML (eXtensible Markup Language) is a self-described and flexible data format and is fast emerging as the dominant standard for representing and exchanging information over the Internet. To fulfill its potential to build effective distributed computing platform and web applications, we need effective and efficiently query and filtering techniques to extract, synthesize and analyze their contents. Path expression is the core of XML query and filtering language, so how to effective and efficiently evaluate path expressions play a key role. This thesis analyzed the data model underlying the path expression and the complexity of evaluation of path expressions and then gave an evaluation method of path query and filtering, at large, it mainly contains:1. The investigation of XML data model, path expression definition and its semantic, these are foundations of path expression evaluation.2. Finite automata representations of XML, XML Schema and path expression and the correlation relationship between XML NFA and Schema DFA.3. The optimization of regular path expression given XML Schema using finite automata and the equivalence and containment among regular linear path expressions. Only after the optimization of regular path expressions, can we answer the regular path expressions using SQLs. Clustering multiple regular linear path expressions into an equivalent class can help to decrease the cost of their evaluation.4. The storage and query of XML using relational DBMS (RDBMS). RDBMS is good at reliability, scalability and query processing performance. It is a feasible method to store and query XML data using RDBMS. A general transformation principle was provided and an experimental system-china digital library project showed the good result of this method.5. XML is often used for data exchange and data sharing. Given XML Schemas and RDBMS Schemas, a method was given to build mappings between them and show how to construct XML data from relational tuples.6. XML filtering is another important side of XML data processing. Multiple filter path expressions are transformed a novel finite automaton, which can handle...