Mapping XML to Inverted Indexed Circular Linked Lists
Teng Lv1, Ping Yan2,
and Weimin He3
1School
of Information Engineering, Anhui
Xinhua University, China
2School of
Science, Anhui Agricultural University, China
3Department
of Computing and New Media Technologies, University
of Wisconsin-Stevens Point, USA
Abstract: 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.
Keywords: XML, mapping, query, schema.
Received August 12, 2014; accepted December 23, 2014