Abstract
This paper considers schemaless XML data stored in a column-oriented storage, particularly in C-store. Axes of the XPath language are studied and a design and analysis of algorithms for processing the XPath fragment XP{*, //, /} are described in detail.
A two-level model of C-store based on XML-enabled relational databases is supposed. The associated algorithms have been used for implementation of the XPath fragment XP{*, //, /}.
The main advantage of this approach is algorithms implementing axes evaluations that are mostly of logarithmic complexity in n, where n is the number of nodes of XML tree associated with an XML document. A low level memory system enables the estimation of the number of two abstract operations providing an interface to an external memory.