User manual

Report bugs

Useful links


The central idea in the Timber project is to construct an XML database that has an architecture as close as possible to that of a relational database. In this way, we attempt to reuse, where appropriate, the technologies developed for relational databases over the past several decades. See (Timber overview) for an overview of the project.

Relational Algebra plays a central role in relational database implementation. An equivalent algebra for XML is developed in TAX. This algebra manipulates sets of ordered labeled trees, rather than sets of tuples. The primary difficulties addressed include the complex and variable structure of trees in a set, and issues of ordering.

Once a query has been parsed into an algebraic representation, this algebraic expression is manipulated in a query optimizer, which then chooses an appropriate query plan to evaluate the query. The (Query optimization for XML) points out some key differences for XML query otimization vis-a-vis relational optimization.

Cost-based query optimization requires good size estimates for query results and intermediate results. Due to the complex structure of XML data, obtaining these estimates is not necessarily straightforward. Techniques for obtaining such estimates effectively are discussed in (Estimating answer sizes for XML queries and Counting Twig Matches in a Tree).

XML query evaluation often involves the computation of a structural join. One has to determine the satisfaction of predicates at multiple structurally related elements in the database. New access methods for the computation of such joins are introduced in (Structural Joins and Combining Operators in XML Query Processing).

Page last modified on 09/May/06