Abstract
This paper considers schemaless XML data stored in a column-oriented storage, particularly in C-store. A two-level model of C-store based on XML-enabled relational databases is supposed.
The axes of XPath language in this environment have been studied in [3]. A low level memory system enables the estimation of the number of two abstract operations providing an interface to an external memory.
The algorithms developed are mostly of logarithmic complexity in n, where n is the number of nodes of XML tree associated with an XML document. Here we extend the approach to the XPath fragment using only child and descendant axes and estimate the complexity of evaluating its queries.