Abstract:

The art of indexing and querying XML document is not yet mature.

While previous results in the field propose index and algorithms which
permits to query XML documents with a complexity at best linear in the
size of the document, we propose a finer analysis, an index and an
algorithm permitting to solve twig pattern queries in a logarithmic
number of comparisons in the size of the document. Those methods and
results are a direct application of similar ones in relational databases
problems, namely the intersection problems.