Research On F&B Index Structure Supporting XML Query

XML(eXtensible Markup Language), as the tool of describing data and exchanging information online, has been a new language of Internet, because of its advantages of self-description, independence of platform, and so on. Since XML has been applied wildly, the research of indexes of XML and the related technology become very important.To solve the practical problem of F&B index, which is the most important structural index of XML, this paper studies several key problems, such as construction of F&B index, storage of F&B index and query processing. Main contributions of this paper include:First, to save the memory, new algorithms for building F&B Index of XML tree model and DAG model, SAJ and SAM, have been proposed. Theoretical analysis shows that SAJ saves more space cost than previous algorithm and SAM is better than previous one over time and space cost. Experiment results show that these algorithms are correct, efficient and well scaled.Second, considering the space problem caused loading F&B index into memory, EDF&B index, a new structure of F&B Index stored on disk by clustering, has been proposed, which saves much space cost. Experiment results show it's feasible in practice.Finally, current algorithms of query processing on F&B index are extended to EDF&B index, and new algorithm based EDF&B index is proposed. Experiment results show the efficiency of new algorithm and EDF&B index.