Cardinality estimation of navigational XPath expressions
G. Broenink · 2008
XML is an often used format to send data over the internet. This data has to be stored in databases, so database management systems(DBMS) which can store XML data are needed. Therefore, several projects work to develop databases which are optimized to store XML data. There are two kinds of projects, some develop a new native XML database, other projects adapt an existing relational database, where XML data is transformed into tables. These databases contain XML data, and this data can be queried with XPath and XQuery (the XML variant of SQL). To optimize the execution of queries in these DBMS, cost models are needed to estimate the costs of different ways to compute the result of a query. An essential part of a cost model is the cardinality estimation, because it is impossible to calculate the total cost of the execution, without knowing the (estimated) size of the (intermediate) results. The cardinality estimation algorithms of relational databases can not be used to estimate the cardinality of XML databases, because a XML data has a tree structure, and relational data has a table structure. To perform accurate cardinality estimation, the algorithms need to be aware of this tree structure, and need to use this tree structure for their estimations. This project focused on estimating the cardinality of navigational XPath expressions. Navigational XPath expressions are XPath expressions which contain only predicates to navigate through the XML tree. So, value based predicates are left out of the scope of this project, because they are already researched as part of relational database systems. Algorithms are developed to estimate the cardinality for all navigational XPath expressions, including predicates which contain a predicate with a check or the existence of a sub path. For each axis an algorithm is developed, to transform a map with context paths and their cardinalities into a map with the resulting paths, and their estimated cardinalities. This resulting map can be used as the context map for the next axis step. To calculate the estimations, the algorithms need a summary of the structure of the tree. This summary, is called a synopsis, and is build by grouping all nodes in the tree, according to their paths, and store the path, and its cardinality in the synopsis. The relations between siblings in the tree are also stored in the synopsis. The algorithms are validated using data centric and document centric documents, and it is concluded that the accuracy of the estimations for the data centric documents is higher then the accuracy of the estimations of the document centric documents. However, the accuracy of the algorithms do not meet our demands. Therefore, three possible improvements to the algorithms are developed. - Ranges can be used to calculate whether the context nodes are at the beginning or at the end of the document. This information improves the estimations of the following and preceding step - Lineage can be used to store specific characteristics of the context nodes. For example, for the following query: //B/parent::A/B it is useful to know that the context nodes (A) of the last child step, all have at least one child B - Splitting groups of nodes. When two nodes with the same path have different sets of children, the assumption that all children are equally distributed among their parents is violated. This violation can be restored, by splitting the nodes into groups which are identified by the combination of path and set of children These three improvements, make the system more accurate. Therefore, they are all useful in their own situation, however there is a price to pay. Therefore, a DBMS has to make a choice: which improvement to use, and in which situation.