Mapping XML to Inverted Indexed Circular Linked Lists

Extensible Markup Language (XML) has become the de facto standard for data exchange on the World Wide Web and is widely used in many fields, so it is urgent to develop some efficient methods to manage, store, and query XML data. Traditional methods use relational databases to store XML data which take advantage of mature technologies of relational databases. But it needs to map XML schemas to relational schemas, then rewrite XML queries to SQL queries, and finally, transform returned SQL-style results to XML-style results again. One possible solution to this is to store XML data directly and query it directly by XML query languages. In this paper, we research the problem of how to map XML data so that storing and querying it can be efficient. We propose the following framework to gain the goal: Firstly, we map a given XML data tree to a set of inverted indexed circular list, in which the relationships between parent and child nodes (and also ancestor and descendent nodes) are preserved. Then, an XML schema tree is used to guide and improve the efficiency of querying the corresponding XML data tree, which is generated from the given XML data tree. Finally, an efficient algorithm is given to query the XML data tree by using the corresponding set of inverted indexed circular list and its schema. The algorithms analysis and experiments prove the efficiency of our method over naïve method.