Querying Optimization Research Based On XML Database

XML has become the de-facto standard for data representation and exchange on the World-Wide Web. Due to the nature of information on the Web and the inherent flexibility of XML, we expect that much of the data encoded in XML will be semi-structured. Data on the Internet is increasingly presented in XML format which enables researches on various kinds of XML storage model. Meanwhile, XML query optimization has become a hot research topic in database field.The query of XML database is similar to that of relational database, trying hard to conduct effective and accurate data query by the means of succinct query sentences. XQuery has become the standard query language for XML. XQuery processing strategies can be classified into two categories: core syntax based strategy and algebra based strategy.Due to XML datas has self-description characteristic; type and number of data node value are very flexible. So we can't process them by the fixed form. It is difficult to query to XML data on account of characteristic that built-in structure and the information is not integrated. In fact, computation of the XML query expression is seeks mapping process for the tree pattern to the documents tree. In other word it is the query match base on the tree pattern. Generally speaking, matching efficiency the tree pattern query is correlation with the tree pattern query scale directly. Tree query model is bigger, the match efficiency is lower. It must simplify query as possible.Structural join operations are central in XML query processing. Structural join order selection is at the heart of query optimization in an XML database. This paper researches XML algebra, minimization of tree pattern queries and structural join order selection to get the purpose of query optimization. The main researches are as follows:1. This thesis is based on the theory of RTA algebra. The algebra uses simple operations on types and structural recursion for lists. The author presents a method to translate XQuery into RTA algebra through the operations. The author uses the rules of equivalent transformation to get the purpose of query rewriting through the RTA algebra. Some optimized principles are proposed in this thesis, which can reduce the cost of combination.2. This thesis provides an algorithm for TPQ (tree pattern queries) minimization without XML constraints involved. This algorithm uses a dynamic programming to search the relation of coverage which can find the redundant node and then remove it. Then we present another algorithm which contains the integrity constrains as required-child, required-descendant, required-sibling and subtype. We show the result that the algorithm obtained by first augmenting the input tree pattern using the constraints, and then applying minimization, always finds the unique minimal equivalent to the original query.3. This thesis analyzes the basic structural join algorithms and introduces a new algorithm; this algorithm can effectively reduce index spaces.