Algebra-based XQuery cardinality estimation

The Authors

Sherif Sakr, NICTA, University of New South Wales, Sydney, Australia

Abstract

Purpose – Estimating the sizes of query results and intermediate results is crucial to many aspects of query processing. All database systems rely on the use of cardinality estimates to choose the cheapest execution plan. In principle, the problem of cardinality estimation is more complicated in the Extensible Markup Language (XML) domain than the relational domain. The purpose of this paper is to present a novel framework for estimating the cardinality of XQuery expressions as well as their sub-expressions. Additionally, this paper proposes a novel XQuery cardinality estimation benchmark. The main aim of this benchmark is to establish the basis of comparison between the different estimation approaches in the XQuery domain.

Design/methodology/approach – As a major innovation, the paper exploits the relational algebraic infrastructure to provide accurate estimation in the context of XML and XQuery domains. In the proposed framework, XQuery expressions are translated into an equivalent relational algebraic plans and then using a well defined set of inference rules and a set of special properties of the algebraic plan, this framework is able to provide high-accurate estimation for XQuery expressions.

Findings – This paper is believed to be the first which provides a uniform framework to estimate the cardinality of more powerful XML querying capabilities using XQuery expressions as well as their sub-expressions. It exploits the relational algebraic infrastructure to provide accurate estimation in the context of XML and XQuery domains. Moreover, the proposed framework can act as a meta-model through its ability to incorporate different summarized XML structures and different histogram techniques which allows the model designers to achieve their targets by focusing their effort on designing or selecting the adequate techniques for them. In addition, this paper proposes benchmark for XQuery cardinality estimation systems. The proposed benchmark distinguishes itself from the other existing XML benchmarks in its focus on establishing the basis for comparing the different estimation approaches in the XML domain in terms of their accuracy of the estimations and their completeness in handling different XML querying features.

Research limitations/implications – The current status of this proposed XQuery cardinality estimations framework does not support the estimation of the queries over the order information of the source XML documents and does not support non-numeric predicates.

Practical implications – The experiments of this XQuery cardinality estimation system demonstrate its effectiveness and show high-accurate estimation results. Utilizing the cardinality estimation properties during the SQL translation of XQuery expression results in an average improvement of 20 percent on the performance of their execution times.

Originality/value – This paper presents a novel framework for estimating the cardinality of XQuery expressions as well as its sub-expressions. A novel XQuery cardinality estimation benchmark is introduced to establish the basis of comparison between the different estimation approaches in the XQuery domain.

Article Type:

Research paper

Keyword(s):

Benchmarking; Algebra; Database management; Extensible Markup Language.

Journal:

International Journal of Web Information Systems

Volume:

Number:

Year:

2008

pp:

6-47

Copyright ©

Emerald Group Publishing Limited

ISSN:

1744-0084

1 Introduction

The Extensible Markup Language (XML) (Bray et al., 2006) has been introduced by the end of the 1990s in order to create a standard data-format for the world wide web which can be easily handled by computers as well as by humans. In recent years, XML has found practical application in numerous domains including data interchange, streaming data and data storage. The semi structured nature of XML allows data to be represented in a considerably more flexible nature than in the traditional relational paradigm. As XML continues to grow in popularity, large repositories of XML documents are going to emerge, and users are likely to pose increasingly more complex queries on these data sets. In 2001, XQuery is decided by the world wide web consortium as the standard XML query language (Boag et al., 2006). XQuery is based on a hierarchical and ordered document model which supports a wide variety of constructs and use cases. The language addresses a wide range of requirements, thus incorporating a rich set of features.

Estimating the sizes of query results and intermediate results is crucial to many aspects of query processing. Accurate forecasting for the selectivity of a given query has many advantages such as:

It is a crucial piece of information for an effective query-optimization process. The cost of an execution plan for a given query is determined by the size of the final result of the query plus the sum of sizes of the intermediate results used to compute this final result.
It allows the system to provide users with early feedback about the expected outcome of queries and their associated computational effort. The user may use this information to refine or enhance the queries such that they generate a smaller set of related results.
It gives a hint on the possible avenues to optimize resource allocation of the execution process. For example, main memory RDBMSs such as Monet DBMS (Boncz, 2002) can use the selectivity information to optimize the main memory allocation for the intermediate results.

In principle, the problem of cardinality estimation is more complicated in the XML domain than the relational domain. The main reason behind this is that the XML queries involve structural conditions in addition to the value-based conditions. Therefore, any complete and accurate size estimation system for the XML queries requires maintaining statistical summary information about the structure of the source XML documents as well as statistical summary information about the distribution of the values associated with the XML nodes. Currently, XML database management systems still lack a convincing means to estimate cardinalities for arbitrary XQuery (sub-) expressions. All of the existing work in this domain remains limited to a subset of XPath expressions and twig queries but none of them addresses the critical issues of XQuery language such as iterators, nested queries, arithmetic operations, comparison operations, etc. In this paper, we present a novel framework for estimating the cardinality of arbitrary XQuery expressions as well as its sub-expressions.

The work of this paper was developed within the Pathfinder project (Pathfinder, available at: http://pathfinder-xquery.org). The aim of the Pathfinder project is to implement the XQuery language to query XML data stored on relational database systems. The architecture of Pathfinder is designed in a front-end/back-end fashion. Pathfinder receives an XQuery expression, which is parsed, normalized, simplified, type checked, optimized, and translated into an equivalent relational algebraic plan. This algebraic plan thus serves as an intermediate representation for the XQuery expression which is then in our context translated into SQL code over the conventional RDBMS (Grust et al., 2007) and in other contexts translated into MIL code over MonetDB DBMS (Boncz et al., 2006; Rittinger, 2005). At the time of writing, this work, the Pathfinder XQuery compiler supported all features of XQuery langauge except user-defined recursive functions.

The intermediate algebraic plans of Pathfinder play a main role in our framework. As a major innovation, we exploit these algebraic plans as well as the relational estimation techniques to provide accurate cardinality estimations in the context of XML and XQuery domains. In particular, the main contributions of the work of this paper is a novel framework for XQuery cardinality estimation with the following main advantages:

it exploits the relational algebraic infrastructure to provide accurate selectivity estimation in the context of XML and XQuery domains;
it is able to support the cardinality estimation of a large subset (almost complete) of the powerful XML query language XQuery;
it is able to estimate not only arbitrary XQuery expressions but also each of their sub-expressions as well as the cardinality of each iteration in the context of the FLWOR expressions; and
it introduces a novel concept that of a guide node annotation which gives the framework the flexibility to integrate any XPath or predicates size estimation techniques.

Additionally, this paper introduces a novel XQuery cardinality estimation benchmark. Unlike the usual XML benchmarks, the main focus of this benchmark is to establish the basis of comparison between XQuery cardinality estimation approaches in terms of the accuracy of estimation and the completeness in handling the different features of XQuery language.

The rest of this paper is organized as follows. In Section 2, we give an overview of our proposed XQuery cardinality estimation framework. In Section 3, we give an overview of the loop-lifting compilation technique which translates XQuery expressions into their equivalent intermediate relational algebraic plans. In Section 4, we describe the main building blocks of our proposed XQuery cardinality estimation framework. In Section 5, we describe the process for estimating the cardinality of XQuery expression as well as its sub-expressions. Our proposed benchmark for XQuery cardinality estimation system is presented in Section 6 to establish the basis of the experimental analysis introduced in Section 7. Section 8 reviews the related work before we conclude in Section 9. The appendix of this paper fully describes the queries of our proposed benchmark for XQuery cardinality estimation system.

2 XQuery cardinality estimation framework

Figure 1 shows framework of our proposed XQuery cardinality estimation. In this framework, the cardinality-estimation process for XQuery expressions runs through the following steps:

The source XML documents have to be mapped (shredded) into an encoding relational scheme. During the shredding process, we build our summarized tree structure to capture summary information about the structure of the source XML document. We name this summary structure as the statistical guide.
To support the estimation of the value-based predicates, we need to build statistical histograms for capturing the distribution of the data values. As it is always a trade-off between the required estimation accuracy and the used storage space, the decision to build the histograms for capturing the distribution of the atomic values of the most frequently used guide nodes of the statistical guide is left to the system administrator.
Using the loop-lifting compilation techniques, the Pathfinder algebraic translation module translates its input XQuery expressions into their equivalent relational algebraic plans (Grust et al., 2004; Teubner, 2006).
The XQuery selectivity estimation module receives four inputs, the outputs of the previous three steps, plus inference rules for the cardinality estimation of the Pathfinder algebraic operators (Section 5.1) and returns back the estimated cardinality for each operator in the algebraic plan.
The estimated cardinality for the root operator in the Pathfinder algebraic plan represents the estimated cardinality for the whole XQuery expression, while the estimated cardinalities for the intermediated operators represent the estimated sizes of their correspondent sub-expressions.

3 XQuery algebraic compilation

Relational algebra has been a main component in relational database systems, and has played an important role in their success for gaining widespread usage. A corresponding XML algebra would have the same importance and substantial role for XML query processing. In our context, having an adequate algebraic compilation for XQuery expressions provides us with the solid infrastructure for predicting the cardinality of the main XQuery expressions and its sub-expressions in a very convenient and accurate way. Many proposals for an algebra for XML query processing have been introduced (Brantner et al., 2005; Chen et al., 2003; Sartiani and Albano, 2002; Jagadish et al., 2001; Paparizos et al., 2002; Zhang and Tompa, 2003). According to Re et al. (2006), existing algebras for XQuery fall into two classes:

Tuple-based algebra. This class of algebra tries to facilitate the use of relational optimization techniques as well as the whole relational query processing framework (theory, compilation, optimization, execution).
Tree-based algebra. This class of algebra provides more natural support for novel XML-specific optimizations and manipulates XML data modelled as forests of labelled ordered trees.

The Pathfinder project has a special module for compiling XQuery expressions into its own dialect of tuple-based algebra producing equivalent relational query plans. The Pathfinder algebra is quite primitive such that it can efficiently fit within the capabilities of SQL-based systems. Pathfinder compiles the XQuery core dialect listed in Table I into relational query plans using the set of algebraic operators listed in Table II. The Pathfinder algebraic operators are designed to receive one or more inputs and produce one or more outputs. These inputs and outputs are in the form of sets of tuples. Most of these operators are rather standard or even restricted variants of the operators found in a classical relational algebra which allow the query optimizer to employ the usual relational algebraic optimization techniques such as the pushdown of the selection operator. For example, the attachment operator (@_a:v) appends one a new attribute a to the tuples of the input relation R where the value for the new attribute is assigned via the value v. The selection operator (σ _a) filters the tuples of the input relation R to only the tuples where the Boolean selection attribute a equals to true. The Boolean selection attribute (a) are usually produced from applying the comparison operator (Fixed graphic 1). The unsorted row numbering operator (#_a) and the sorted row numbering operator (ϱ _{a:(o
₁, … ,o
_n)/p}) are two of the most important Pathfinder's algebraic operators. Together, they are responsible of preserving the order concept defined by the XQuery/XPath specifications (Fernández et al., 2006). The unsorted row numbering operator (#_a) receives an input relation R and returns the same relation extended with a new consecutive numbering attribute (a) from 1 to n where n is the cardinality of the input relation R. The sorted row numbering operator (ϱ _{a:(o
₁, … ,o
_n)/p}) receives an input relation R, an ordering attribute list (o ₁, … o _n) and an optional partitioning attribute p. It returns the same relation extended with a new consecutive numbering attribute (a). The numbering attribute (a) respects the tuple sorting of relation R defined by the order specification (o ₁, … o _n) and restarts the numbering from one for each partition defined by the optional partitioning attribute (p). The XPath location step evaluator operator (Fixed graphic 2 _{item:(α, n)}) is responsible for evaluating XPath expressions. It returns the result nodes for each iteration of the input context relation in the document order and duplicate free. Figure 2 shows examples for the behavior of some Pathfinder algebraic operators.

In this section, we give an overview of the loop-lifting technique, which is considered to be the heart of this compilation process. For a detailed and complete description of this technique and its translation rules we refer to Teubner (2006), Grust et al. (2004) and Grust (2005). In a nutshell, loop-lifting is the key technique used to compile XQuery iterations into efficient bulk style application of algebraic operators. The principal idea behind the compilation scheme is that every XQuery expression occurs in the scope of an iteration. The iterations of each scope are encoded by a column iter in the associated relational representation. In order to clarify the loop-lifting idea, we will show some examples of Pathfinder loop-lifted translations for some XQuery expressions into their associated Pathfinder algebraic relational representation.

3.1 Sequences

The XQuery language is designed to operate over ordered, finite sequences of items as its principal data type. The evaluation of any XQuery expression yields an ordered sequence of n≥0 items. These items can be either atomic values (integers, strings, … , etc.) or XML tree nodes. An XQuery item sequence (x1, … x _n) is encoded with a relational table with a schema (pos, item) where the column pos is used to preserve the order information between the items inside the target sequence. The item column is a polymorphic column. In the case of atomic items, it stores the values of the encoded atomic items (1, “A” …) and in the other case of XML tree nodes, it stores the pre-order ranks of the encoded nodes. The RDBMS supports the representation of such polymorphic columns using the variant data type. The empty sequence ( ) is encoded with an empty table with the same schema (pos, item).

3.2 FLWOR expressions

The FLWOR expression is one of the main features provided by the XQuery language. It is used for representing iterations and for the binding of variables to intermediate results. It is also used for computing joins between two or more sequences and for restructuring data. A loop of n iterations is represented by a relation loop with a single column iter of n values (1, 2, … n). The compilation of variables bound in the iterations of FLWOR expression is translated into a relational table with a schema (iter, pos, item) where each tuple of the encoding relation (i, p, x) indicates that for the i-th iteration, the item at position p stores the value x.

3.3 Path steps

The compilation of path steps is represented in the algebraic plans using the XPath evaluator operator (Fixed graphic 3). It takes a context relation (iter, item) as input, where the item column stores the node identifiers of the input context nodes. It uses the XPath encoding relation of the current live nodes (Γ) to evaluate the path step (α, n) and returns a new relation with the same schema (iter, item). In the output relation, the item column stores the node identifiers of the resulting nodes. Figure 3 shows an example for the loop-lifted compilation of the path step where Figure 3(a) shows the input context nodes, Figure 3(b) shows the sample source XML document and Figure 3(c) shows the output context nodes from applying the path step child::c over input context nodes and the sample source XML document.

3.4 Arithmetic and comparison expressions

Given the relational representation R ₁(iter1, item1) and R ₂(iter2, item2) of two XQuery expression e ₁ and e ₂, the design of the loop-lifting compilation of the arithmetic and comparison expressions requires that the schema of the relational representation (R _i) of each argument expression (e _i) must have a single node identifier column (item_i) for each iteration (iter_i) with no order preserving column (pos). The arithmetic expression e ₁ e ₂ is evaluated by joining R ₁ and R ₂ over their iterations attribute iter, for each tuple of the result we apply the arithmetic operator (∘) over the two arguments columns item1 and item2, and store the result in a new column res. The algebraic representation of the arithmetic expression (e ₁ e ₂) is defined as follows: Equation 1 where R ₁ and R ₂ are consequentially representing the relational representation of the two expressions e ₁ and e ₂.

Similarly, the comparison expression e ₁ Fixed graphic 4 e ₂ is evaluated by joining R ₁ and R ₂ over their iterations attribute iter, for each tuple of the result we apply the comparison operator (∘) over the two argument attributes item1 and item2, and store the result in a new attribute res. The comparison operators are normally followed by a selection operator to filter the tuples satisfying the comparison condition. The algebraic representation of the comparison expression (e ₁ Fixed graphic 5 e ₂) is defined as follows: Equation 2

4 Building blocks of XQuery cardinality estimation

The problem of cardinality estimation is more complicated in the XML domain than the relational domain. The main reason behind this is that the XML queries involve structural conditions in addition to the value-based conditions. Therefore, any complete and accurate size estimation system for the XML queries requires maintaining statistical summary information about the structure of the source XML documents as well as statistical summary information about the distribution of the values associated with the XML nodes. In this section, we describe the building blocks of our XQuery cardinality estimation system which capture the summary information about the structure and the values of the source XML documents. In addition, we describe the process of inferring some special properties for the Pathfinder algebraic plans. These special properties play a vital role in our estimation process using the relational estimation techniques as we will show next in Section 5.

4.1 Statistical guide

The first step in estimating the result size of an XQuery expression is to summarize the source XML document into a compact graph structure which we name the statistical guide. The statistical guide represents an implementation for the data guide summary tree structure presented in Goldman and Widom (1997) and is very similar to the path tree summary structure presented by Aboulnaga et al. (2001). Every node in the statistical guide represents a rooted path starting from the root node of the source XML document. The root node of the statistical guide represents the root element of the document. The statistical guide has a node for every distinct rooted path in the source XML document. Each node of the statistical guide is labeled with the tag name of the elements reachable by the path it represents and annotated with the number of occurrences for such node (rooted path). Figure 4 shows an XML document and its associated statistical guide. We construct the statistical guide of an XML document during the normal shredding process of the XML document using the XPath accelerator storage scheme presented by Grust (2002). It is thus constructed during the normal scan of the document using a SAX parser. To estimate the cardinality of an XPath expression using the statistical guide, we need to evaluate the XPath expression over the statistical guide. This will result in a set of nodes which correspond to the query path expression. Hence, the estimated cardinality of the XPath expression is defined by computing the sum of the number of occurrences of these resulting nodes. Owing to its compact size even for larger XML documents, the statistical guide can easily fit into main memory and be made available for the query processor during the compilation process.

4.2 Histograms

Histograms are the most popular summary data structures used for estimating query result sizes in relational systems. In our XQuery cardinality estimation system, it is used to estimate the number of nodes satisfying a specified value predicate. Although, we can build a histogram for each value node (text node-attribute) in the statistical guide, it is always a trade-off between the required estimation accuracy and the used storage space. In practice, we leave it to the system administrator to decide building the required histograms for the frequently used nodes in the statistical guide. A histogram H on node X is constructed by partitioning the data distribution of the node values into N mutually disjoint subsets called buckets and then counting the number of values for each bucket. The histogram's buckets can be defined according to different partitioning rules that searches for effective distribution of the values which leads to accurate estimations. The values in the range of each bucket is assumed to be uniformly distributed between the lowest and highest values in the bucket. Poosala et al. (1996) has provided a survey on several well known histograms such as equi-width, equi-depth and serial histograms (Ioannidis, 1993) where each of them is using different partitioning rules and constraints. In particular, each of these histograms has its own advantages. For example, equi-depth histogram works well for range queries only when the data distribution has low skew while serial histogram has shown to be optimal for equality joins and selection when a list of all the attribute values in each bucket is maintained.

In fact our proposed estimation framework is not dependent on or affected by the type of the used histograms and it is flexible to integrate any of them. Currently, we are using on standard the simple equi-width histograms for collecting the statistical information of the relevant nodes however it is also open for the system administrator to use any other type of histograms without affecting the estimation process.

4.3 Histograms operation

4.3.1 Histograms constant manipulation

The XQuery language provides the capability of performing arithmetic operations. One variation of the instances of the arithmetic operators ⊚_{x:(x, y)} inside the algebraic plan is the instance where one argument (x) is represented by an item sequence of atomic values and the other argument (y) is a constant value v. Assuming the data distribution for the atomic values of the item sequence representing the first argument (x) is captured by the histogram (H1). Applying the arithmetic operation yields a resulting item sequence where the data distribution is captured by the histogram (H2). The characteristics of the data distribution of (H2) is defined by manipulating the boundaries of the histogram (H1), its minimum value, its maximum value and the boundaries of its associated buckets with the defined arithmetic operation and constant value (V) while the distribution of the values inside each buckets remains as the same. Figure 5 shows a visual example of manipulating the distribution of the data values of histogram H1 with different arithmetic operations and the constant value five.

4.3.2 Histograms arithmetic

Another variation of the instances of the arithmetic operators ⊚_{z:(x, y)} is the situation where both of the arguments (x, y) are represented by an item sequence of atomic values. Assume that the data distribution for the atomic values of the item sequence representing the two arguments (x, y) are captured by the two histograms (HX, HY), respectively. In this situation we rely on the histogram discretization algorithm presented by Berleant (1993) for performing arithmetic operations over histograms and computing the resulting histogram H3 which captures the distribution of the values of the resulting attribute z. The steps of performing the arithmetic operation ∘ over the two histograms (HX, HY) using the histogram discretization algorithm are described as follows:

Compute the Cartesian product of the buckets of two histograms (HX, HY).
For each member (HX _i, HY _j) in the Cartesian product, an intermediate result bucket is computed by:
- executing the arithmetic operation ∘ on HX _i and HY _j to get the intermediate resulting bucket HZ _ij=HX _i∘HY _j; and
- associating with the intermediate bucket HZ _ij the size information equal to the size of the bucket HX _i multiplied by the size of the bucket HY _j.
The resulting intermediate buckets are combined to get a final result by:
- Deciding on a set of intervals partitioning the domain of HZ. This partition determines the placement of the boundaries of the buckets of the resulting histogram.
- Calculating the size of each bucket of the resulting histogram HZ as follows:
  1. any intermediate result bucket HZ _ij that falls completely within some member of the partition has its entire results added to that member; and
  2. any intermediate result bucket that overlaps more than one member of the partition has its size divided among them proportionally to the fraction of the intermediate result bucket it overlaps.

To illustrate let us consider the following example:

Let us assume that the histogram HX where its buckets information are described as follows (Table III). The buckets of the histogram HY are described in Table IV.

Applying the multiplication operation between the two histograms HX and HY will produce the intermediate buckets as shown in Table V.

The decision of the resulting number of buckets and partitioning values can be defined in many ways. We use the heuristic rule for deciding the number of the resulting buckets to be equal to the maximum number of the buckets of the two argument histograms. In our example, the resulting histogram HZ will consist of three buckets covering the range of values between 0 and 120 and the width of each bucket is equal to 40. Hence, the buckets of the histogram HZ are described as shown in Table VI, where the resulting bucket number 1 combines the full data of the intermediate buckets 1, 2, 3 and fractions from the buckets 4, 5. The resulting bucket number 2 combines fractions from the data of the buckets 4, 5, 6 and the resulting bucket number 3 contains a fraction of the data in the intermediate bucket number 6.

4.3.3 Histograms comparison

One variation of the instances of the comparison operators Fixed graphic 6 _{z:(x, y)} is the instance where both of the arguments (x, y) are represented by an item sequence of atomic values. Assuming the data distribution for the atomic values of the item sequence representing the two argument (x, y) are captured by the two histograms (HX, HY), respectively. In this situation and using the same idea of the histogram discretization algorithm, the selectivity of the resulting boolean attribute z is computed by applying bucket by bucket comparison of the Cartesian product between the two histograms (HX, HY).To illustrate let us represent the following example:

Let us consider the histogram HX where its buckets information are described as shown in Table VII. The buckets of the histogram HY are described as shown in Table VIII.

Estimating the selectivity of the comparison HX<HY will be computed as shown in Table IX.

For the intermediate buckets number 1, 2 and 4 it is guaranteed that any value which belongs to the HX _i bucket is less than any value belongs to the HY _j bucket. Hence, the estimated size of the number of pairs satisfying the conditions (HX _i<HY _j) is equal to the total size. For the intermediate bucket number 5, it is guaranteed that there is no value which belongs to the HX _i bucket can be less than any value which belongs to the HY _j bucket. Hence, the estimated size of the number of pairs satisfying the conditions (HX _i<HY _j) is equal to 0. For the intermediate buckets number 3 and 6, we use the mean value of the HX _i bucket to estimate the number of pairs satisfying the comparison condition. In the case of the buckets comparison 3, the mean value of HX _i is equal to 7.5 and the size of the pairs satisfying the condition (HX _i<HY _j) is estimated as follows: Equation 3 In the case of the buckets comparison 5, the mean value of HX _i is equal to 12.5 and the size of the pairs satisfying the condition (HX _i<HY _j) is estimated as follows: Equation 4 The selectivity of the resulting Boolean attribute z is then computed by dividing the estimated sum of all pairs satisfying the condition (HX _i<HY _j) by the total number of the pair values as follows: Equation 5

4.4 Guide node annotation

Having an accurate estimation of XPath expression is a very crucial aspect for having accurate XQuery cardinality estimation system. In our presented algebraic compilation of XQuery expression, the XPath evaluator operator (Fixed graphic 7 _{item:(α, n)}) is used for representing the XPath steps. The XPath evaluator operator (Fixed graphic 8 _{item:(α, n)}) receives an input context relation (ctx) with the schema (iter, item) where the item column stores the node identifiers of the input context nodes as well as an encoded XPath accelerator relation for the associated live nodes fragment (Γ) and returns back the set of output context nodes from the evaluation the path step (α, n) over the input context nodes. In order to estimate the cardinality of the XPath evaluator operator Fixed graphic 9 _{item:(α, n)}), we need to keep track of the node identifiers of the input context nodes. Hence, we represent a new annotation for the item columns storing the node identifiers of the context nodes, we name it as guide node annotation. An item column of the context relation (ctx) annotated with the guide node property X indicates that the list of the node identifiers stored in the item are corresponding to the node with the pre-order rank X of the statistical guide. Having an input context relation where the item column is annotated by the guide node property X. Applying the XPath evaluator operator (Fixed graphic 10 _{item:(α, n)}) over the context relation ctx annotates the item column of the resulting context relation with the guide node property equal to Y, where Y is the set of the pre-order rank(s) of the resulting node(s) from applying the path step (α, n) over the guide node X. A detailed explanation for the steps of estimating the cardinality of the XPath evaluator operator Fixed graphic 11 will be presented in Section 5.1.

4.5 Special properties for the algebraic plan

Grust (2005) has shown that further analysis on the Pathfinder algebraic plans reveals the following two important observations:

Pathfinder algebraic plans always include several occurrences of common sub-plans. Based on this observation, it is more suitable and effective to use direct acyclic graphs (DAGs) instead of operators tree for representing the resulting algebraic plans.
Owing to the design of the loop-lifting compilation rules, it is noticed that some of the algebraic operators have specific properties such as: all join operators (⋈) are equi-join, the projection operators (π) do not need to remove any duplicates and all union operators (Fixed graphic 12) are receiving disjoint argument relations.

Based on these observations, it becomes possible infer a variety of properties for the algebraic operators of the Pathfinder algebraic plans. Additionally, Sakr (2007) has added to these properties three cardinality estimation related special properties (GuideNode, Histogram, Selectivity) to keep track of the information about the context nodes paths and values to support the selectivity-estimation process.

Table X lists the properties we are able to infer and propagate during the plan analysis of the algebraic plan. These properties play a vital role in our proposed size estimation system for XQuery. Making use of these inferred properties for having accurate size estimations for the results of XQuery expressions will be described in Section 5.1. Figures 6-8 show the complete and sound set of inference rules for inferring and propagating the special properties during the loop-lifting compilation process of XQuery expressions. These inference rules are represented in the form: Equation 6 where each inference rule establishes a relationship between a set of premises and conclusions, whereby the conclusion is said to be inferable from the premises. In other words, whenever in the course of some logical derivation the given premises have been obtained, the specified conclusion can be taken for granted as well. Examples of the used notations for representing the special properties of the algebraic operators listed in Table X are given as follows:

The notation (R.cols:{a, b}) represents that the schema of the relation R consists of the attributes (a, b). While the notation (a∈R.cols) represents that the attribute (a) belongs to the schema of the relation R.
The notation (R.key:{a, b}) represents that the attributes (a, b) are the key attributes for the relation R. While the notation (a∈R.key) represents that the attribute (a) is a key attribute for the relation R.
The notation (R.domain:{a ^(α), b ^(β)}) represents that the schema of the relation R contains the attributes (a, b), the domain identifier of the attribute a is α and the domain identifier of the attribute b is β. While the notation (a ^(α)∈R.domain) represents that the attribute (a) with the domain identifier (α) belongs to the schema of the relation R.
The notation (R.const:{a ⁽¹⁰⁾, b ^(True)}) represents that the constant attributes of the relation R are the two constant attributes (a, b) where the constant value of the attribute a is 10 and the constant value of the attribute b is True. While the notation (a ⁽¹⁰⁾∈R.const) represents that the constant attribute (a) with the value 10 belongs to the schema of the relation R.
The notation (R.card:C) represents that the cardinality of the relation R is equal to C.
The notation (a ^{gn}∈R.GuideNode) represents that the attribute (a) of the relation R stores a sequence of node identifiers associated with guide node with a pre-order rank (gn) on the statistical guide.
The notation (a ^{h}∈R.Histogram) represents that the distribution of the values of the attribute (a) of the relation R is captured by the histogram definition (h).
The notation (a ^(s)∈R.Selectivity) represents that the attribute (a) of the relation R is a Boolean attribute where the percentage of its true value is equal to s.
The notation (a ⁽ⁿ⁾∈R.DomainSize) represents that the values of the attribute (a) of the relation R are ranging between 1 and n.

For a detailed description of the inference rules of the special properties of the Pathfinder algebraic plan (Figures 6-8) we refer to Sakr (2007). Remarks about the inference rules are given as follows:

In the inference rules of the domain property, we use the annotation a ^(D+) to represent the assignment of a new domain identifier (D+) for the attribute (a). For example, some of the algebraic operators commonly propagate all domain information of the attributes from their input relations to their output relation without any changes and additionally the operators create a new domain identifiers (D+) for their resulting (extending) attributes (r) (Rule Dom-1). These operators are: the attachment operator (@), the unsorted row numbering operator (#), the sorted row numbering operator (ϱ), the arithmetic operator (⊚), the comparison operator (Fixed graphic 13), the negation operator (¬) and the document access operator (Δ).
If the attribute item in the input context relation R is annotated with the guide node property (Ign) (the set of input guide nodes), then applying the XPath location step evaluator operator (Fixed graphic 14 _{item:(α, n)}) over the input context relation R changes the annotation of the attribute item in the resulting relation by the set of the guide nodes (Ogn) resulting from applying the step (α, n) over the set of guide nodes (Ign) in the statistical guide (Rule Guide-6).
The document access operator (Δ_value:item) uses the guide node(s) information annotated to the item column of the context relation to retrieve their associated histogram(s) from the statistical repository. The retrieved histogram(s) are annotated to the histogram property of the resulting value attribute (Rule Hist-3). If the item column of the context relation is annotated with more than one guide node information, then each of the retrieved histograms is assigned a weight of a participation (H _i.weight) which is equal to the computed percentage by dividing the size of its associated guide node (StatisticalGuide.getSize(gns_i)) by the total size of all annotated guide nodes StatisticalGuide.getSize(gns). Another alternative in this situation is to merge the retrieved histograms for the set of the guide nodes into one histogram. However, we prefer to use and maintain the weight of each histogram for gaining more accurate estimation of the selectivity values by applying the comparison operators. If the item column is annotated with only one guide node, then the weight percentage of the retrieved histogram is naturally equal to 100 percent. In fact, the document access operator is responsible for retrieving the atomic values of the context nodes. Consequently, the document access operator is the algebraic operator which is responsible for introducing the histogram property into the algebraic plans.
If the attribute a in relation R is annotated with the histogram property X and the attribute a in relation S is annotated with the histogram property Y (each of X and Y represents a set of histograms which may contain one or more histogram), then the resulting attribute a in (R Fixed graphic 15 S) combines all the histogram information of both input attributes where the weight of each element histogram in the resulting set of histograms Z (Z.Histogram(X _i).weight and Z.Histogram(Y _j).weight) is computed by dividing the computed values of associated tuples in the source relation (X.Histogram(X _i).weight*C1 and Y.Histogram(Y _j).weight*C2) by the total number of the tuples of the resulting relation (C1 + C2) where C1 is the cardinality of the relation R and C2 is the cardinality of the relations S (Rule Hist-4).
The instances of the arithmetic operators (⊚_{z:(x, y)}) in the Pathfinder algebraic plans come in one of the following three situations:
- The argument attribute x is a constant attribute with the value v1 and the argument attribute y is a constant attribute with the value v2. In this case, the resulting attribute z is a constant attribute with the value (v1∘v2) (Rule Hist-7).
- The argument attribute x is a constant attribute with the value v and the argument attribute y is annotated with the histogram property equal to H1 where H1 represents a set of histograms. In this case, the resulting attribute z is annotated with the histogram property equal to H2. The set of histograms H2 is a result of manipulating each element of the set of histograms H1 with the arithmetic operation ∘ and the constant value v (Rule Hist-9). In Rule Hist-9, the function ArithHistConst represents the process of histogram manipulation using a constant value discussed in Section 4.3.
- The argument attribute x is annotated with the histogram property equal to the set of histograms H1 and the argument attribute y is annotated with the histogram property equal to the set of histograms H2. In this case, the resulting attribute z is annotated with the histogram property equal to the set of histograms H3. The set of histograms H3 is a result of manipulating the histogram(s) of H1 with the arithmetic operation ∘ and the histogram(s) of H2 (Rule Hist-8). In Rule Hist-8, the function ArithHistHist represents the process of applying arithmetic operations on histograms discussed in Section 4.3.
If the attribute a in relation R is annotated with the selectivity property s1 and the attribute a in relation S is annotated with the selectivity property s2, then the selectivity property of the resulting attribute a in (R Fixed graphic 16 S) is computed by dividing the sum of the tuples with the True value in R and S by the total sum of all tuples in R and S (Rule Sel-3).
The instances of the comparison operators (Fixed graphic 17 _{z:(x, y)}) in the Pathfinder algebraic plans come in one of the following three situations:
- The argument attribute x is a constant attribute with the value v1 and the argument attribute y is a constant attribute with the value v2. In this case, the resulting Boolean attribute z is either annotated with the selectivity property equal to 1, if (v1∘v2) is equal to true, or with the selectivity property equal to 0, if (v1∘v2) is equal to false (Rule Sel-7). In Rule Sel-7, the function CompareConstConst evaluates the comparison operator (v1∘v2) and returns the equivalent selectivity value.
- The argument attribute x is annotated with the histogram property equal to the set of histograms H and the argument attribute y is a constant attribute with the value v. In this case, the resulting Boolean attribute z is annotated with the selectivity property equal to (s) where the values of (s) is computed using the following two steps (Rule Sel-8):
  1. Computing the intermediate selectivity values s _i by comparing each element histogram H _i with the constant value v.
  2. The final resulting selectivity values s is equal to the weighted average of the intermediate selectivity values s _i. It is computed by summing the values resulting from multiplying each intermediate selectivity values s _i with the weight of each associated histogram H _i.weight.
- The argument attribute x is annotated with the histogram property that is equal to the set of histograms H1 and the argument attribute y is annotated with the histogram property that is equal to the set of histograms H2. In this case, the resulting Boolean attribute z is annotated with the selectivity property equal to (s) where (s) is computed using the following three steps (Rule Sel-9):
  1. Computing the intermediate selectivity values s _i results from applying the comparison operator ∘ over the values of each pair of histograms (H1_i and H2_j).
  2. Each intermediate selectivity value s _i is assigned a weight value equals to the resulting value from multiplying the weights of its associated pair of histograms (H1_i and H2 _j).
  3. The final resulting selectivity values s is equal to the weighted average of the intermediate selectivity values s _ij. It is computed by summing the values resulting from multiplying each intermediate selectivity values s _ij with its computed weight s _ij. weight.In Rule Sel-9, the function CompareHistHist represents the process of histograms comparison discussed in Section 4.3.
If the relational R is annotated with the cardinality property equal to C, then applying the unsorted row numbering operator (#_a) or the sorted row numbering operator with no partitioning argument (ϱ _{a:(o
₁, … ,o
_n)}) over the input relation R annotates the resulting numbering attribute a with DomainSize property equal to C (Rules DomSize-6, DomSize-7).

5 XQuery cardinality estimation

5.1 Estimation rules

This section presents the main part of the estimation process which integrates the different building blocks of the XQuery cardinality estimation framework. In this section, we present the inference rules for estimating the cardinality of XQuery expression and its sub-expressions using the previously mentioned building blocks. As previously mentioned, Pathfinder compiles the input XQuery expression into its equivalent algebraic plans. The XQuery expressions are compositional in nature as sub-expressions are combined with each other to form the final query. Our approach is able to estimate the cardinality of the final XQuery expression as well as its sub-expressions. It uses the Pathfinder intermediate algebraic plans and the relational well-known estimation techniques to estimating the cardinality of each algebraic operators in the query plan. Our current set of rules is supporting the most typical and frequent constellations of Pathfinder algebraic plans. Currently, we are working on defining further sophisticated rules to increase the forecast quality and to complete the set of possible arbitrary Pathfinder algebraic constellations. Figure 9 shows the inference rules for estimating the cardinalities of Pathfinder algebraic operators. In Section 5.2, we will provide an example to describe the use of these inference rules in the estimation process.

Remarks about the estimation inference rules are given as follows:

Since the two input relations R, S of the union operator (Fixed graphic 18) are guaranteed to be always disjoint (Grust, 2005), the estimated cardinality of (R Fixed graphic 19 S) is equal to the sum of the cardinality of R (C1) plus the cardinality of S (C2) (Rule Card-2).
An accurate estimation of XPath location steps is crucial for an accurate estimation of the whole XQuery expression. Assuming that the cardinality of the input relation R is equal to C1 and the item column storing the node identifier of the input context nodes is annotated with the set of guide node(s) (Igns), the estimated cardinality of the operator Fixed graphic 20 _{(α, n)}(R) is achieved through the following steps represented in Rule Card-15:
- Using our summarized tree structure, the statistical guide, we can get the sum of cardinalities of the input guide node(s) (Igns) represented as (C2).
- We apply the location step (α, n) over the statistical guide with the input context guide nodes (Igns) and the resulting guide nodes (Ogns) are annotated to the resulting item column.
- Once again, the statistical guide is used to get the sum of cardinalities of the output guide node(s) (Ogns) represented as (C3).
- Using the cardinality of the input relation (C1), the cardinality of the input guide nodes (C2) and the cardinality of the output guide nodes (C3), the estimated cardinality of the operator Fixed graphic 21 _{(α, n)}(R) is calculated as follows: Equation 7
The estimated cardinality of the resulting relation from applying the join operator (⋈_a=b) is very dependent on the key and domain properties of the join attributes of the input relations. Many different situations can occur in this context hence, four different inference rules have been defined to deal with the different possible instances of the join operators (Rules Card-16, Card-17, Card-18, Card-19 and Card-20). Since some instances of the join operators may fit with the preconditions of more than one size estimation inference rule, the instances of the join operations are checked against the preconditions of the specified inference rules in a deterministic order as shown in Figure 9. Rule Card-20 represents the else case of these set of the inference rules which is used when we do not have sufficient information about the domain and key properties of the join attributes. In this case, we use the System R rule which estimates the cardinality of the resulting relation to be equal to 1/10 of the Cartesian product of the input relations (Selinger et al., 1979).
Generally, the cardinality estimation of the duplicate elimination operator (δ) is very difficult and not as straightforward in the general case because it is very dependant on the values of the attributes of the tuples of the input relation. However, we have provided different estimation rules for handling the most common cases for instances of this operator. These cases are listed as follows:
- The estimated cardinality of the resulting relation from applying the duplicate elimination operator (δ(R)) is equal to the cardinality of the input relation R if any of the attributes of the input relation is a key attribute (Rule Card-21).
- If the schema of the input relation R consists of only one attribute a and this attribute is a constant attribute then the cardinality of the resulting relation is equal to 1 (Rule Card-22).
- If the schema of the input relation R consists of only one attribute a and this attribute is annotated with the histogram property that is equal to H, the cardinality of the resulting relation is equal to the cardinality of the input relation R multiplied by the percentage of the unique values of the data represented by the histogram H1 (Rule Card-23).
- If the schema of the input relation R consists of only one attribute a and this attribute is annotated with a DomainSize property that is equal to n, assuming that the cardinality of the input relation R is equal to C1, the cardinality of the resulting relation would then equal to the minimum value between C and n (Rule Card-24).
- For cases where the schema of the input relation R consists of more than one attribute where all attributes are constant attributes with the exception of an attribute a, if the attribute a is annotated with the histogram property that is equal to H then the estimation is done in the same way as in the third case (Rule Card-25), if the attribute a is annotated with the DomainSize property equal to n then the estimation is done in the same way as described in the fourth case (Rule Card-26).

In the case where the status of the duplicate elimination operator does not fit with the preconditions of any of the mentioned cases, then we estimate the cardinality of the resulting relation to be equal to the cardinality of the input relation.

5.2 Estimation process

Having the algebraic compilation of the XQuery expressions, the special properties of the algebraic plans, the statistical guide, the histogram repository and the estimation inference rules of the algebraic operators, the XQuery cardinality estimation in our framework becomes a very straightforward process. The estimation process is mainly achieved through two main steps. Firstly, the input XQuery expression is compiled into its equivalent algebraic plan. Secondly, the cardinality estimation of the input XQuery expression and its sub-expression is done by traversing the DAG of the algebraic operators in a post-order approach and then estimating the cardinality of each algebraic operator using its defined estimation rules (Section 5.1). Each sub-expression is associated with an algebraic operator in the DAG plan and the estimated cardinality of each intermediate algebraic operator is used as an input for the immediate following operator(s) in the algebraic DAG plan. To illustrate, we present an example of the estimation process of an XQuery expressions using its associated compiled algebraic plan and the estimation rules. In this example, we use the XMark sample document “auction.xml” as a source XML document where Figure 10 shows its associated statistical guide. In the statistical guide figure, we used the following notations:

the notation […] is used to replace the sub-trees which are not relevant for our sample queries;
all nodes of the statistical guide are annotated on their left sides with their associated pre-order ranks; and
the interesting nodes for our examples are annotated on their right-hand side with their associated number of occurrences.

Example 1

Find all price nodes with value less than 50

for $x in doc(“auction.xml”)//closed_auctions//price/text( )

where $x<50

return $x

Figure 11(a) shows the Pathfinder algebraic plan for the XQuery query Q1. Figure 11(b) shows the distribution of the price values (H1 – GuideNode51). Figure 12 shows the operators of the algebraic plans and the annotations of the special properties related to the estimation process. The columns with the title GNode represents the annotation of the guide node property while the column with the title Hist represents the annotation of the histogram property. Remarks about the inferred properties and cardinalities of the algebraic operators are given as follows:

The (Doc) operator 17 retrieves the document node from the XPath accelerator encoding relation of the “auction.xml” document. Hence, the resulting item column is annotated with the guide node property equal to 0 referring to the root node of the statistical guide of the “auction.xml” document.
The operators 16, 15 are instances of the XPath evaluator operator (Fixed graphic 22). Operator 16 represents the evaluation of the path step (descendant::closed_auctions) while the operator 15 represents the evaluation of the path step (descendent::price). The notation desc is used as an abbreviation for the descendant axis.
The estimated cardinalities of the XPath evaluator operators (Fixed graphic 23) 16, 15 are done on the basis of the inference Rule Card-15. For operator number 16, applying the path step (descendant::closed_auctions) over the statistical guide with the input context document guide node (GuideNode 0) yields to the guide node with the pre-order rank equal to 47 (GuideNode 47) and the number of occurrences is equal to 1. Hence, the estimated cardinality for this operator is equal to 1 and the resulting item attribute is annotated with the guide node property equal to 47. Similarly, for operator 15 applying the path step (descendent::price) over the statistical guide with the input context guide node (GuideNode 47) yields to the guide node with the pre-order rank equal to 51 (GuideNode 51) where the number of occurrences is equal to 100. The estimated cardinality for this operator is equal to 100 and the resulting item attribute is annotated with the guide node property equal to 51.
The document access operator (Δ_item1:item) 10 uses the guide node property of the input item attribute to annotate the resulting attribute item1 with its associated histogram H1 capturing the distribution of the values of the price values (GuideNode 51). Simultaneously the estimated cardinality of the resulting relation is equal to the cardinality of the input relation.
The comparison operator 7 (<_{item: item1, item2}) applies a comparison operation (<) between the item1 attribute annotated with the histogram property equal to H1 and the item2 attribute annotated with the constant value 50 resulting from the attachment operator 8 (@_item2:50). Using the following information of the histogram H1:
- the histogram size is equal to 100; and
- the constant value 50 lies within the range of the third bucket [40, 60] where the size of the bucket is equal to 20 and the accumulative size of the values that are less than 40 is equal to 80.the selectivity of the resulting Boolean attribute (item) is computed as follows: Equation 8 The estimated cardinality of the resulting relation from applying the document access operators is equal to the estimated cardinality of the input relation.
The estimated cardinality of the resulting relation from applying the selection operator 5 (σ _item) is computed by multiplying the value of the annotated selectivity property of the selection attribute item (0.9) by the estimated cardinality of the input relation (100).
The operator 3 (⋈_{iter = iter}) applies a join operation between the resulting relations from applying the operators 4 and 12. The estimated cardinality of the resulting relation from applying the join operator 3 is derived using the Rule Card-17 where the join attribute of each input relation is a key attribute and the domain of one join attribute is a subset of the domain other join attribute.
Additionally, the cardinality estimation of the sub-expressions could be inferred by detecting the corresponding relationship between each sub-expression and its associated algebraic operator. For example, the operator 15 with estimated cardinality equal to 100 corresponds to the evaluation of the sub-expression doc(“auction.xml”)//closed_auctions//price while the operator 4 with estimated cardinality equal to 90 corresponds to the evaluation of the sub-expression $x<50.
Using the loop-lifted compilation of the FLWOR expression and the loop scope relations described in Section 3, we are able to estimate the cardinality of each iteration in the scope of the FLWOR expression. A description of the estimation of the cardinality of each iteration in the FLWOR expression will be presented in the experiments of Section 7.2.

6 Proposed benchmark for XQuery cardinality estimation systems

The XML research community has proposed several benchmarks such as Böhme and Rahm (2001), Schmidt et al. (2002), Yao et al. (2003) and Nicola et al. (2007) which are very useful for their targets and perspectives. However, none of these benchmarks fits in our context. As such, in our context we need a benchmark which is designed with a main focus to measure the accuracy of our XQuery cardinality estimation systems with their different aspects. In this section, we present our proposed benchmark for XML query size estimation. Unlike the usual XML database benchmarks, the aim of our proposed benchmark is to establish the basis of different estimation approaches in the XML domain in terms of the accuracy of the estimations and its completeness in handling different XML querying features. A good XQuery selectivity estimation system must be able to support as much as possible from the different estimation aspects mentioned in this benchmark, and must scale reasonably well for combinations of these aspects. To the best of our knowledge, the work of this paper is the first which provides a uniform framework to estimate the cardinality of XQuery expressions. Hence, we have the situation that we have no other systems to compare with them in terms of the accuracy or any other aspects. The benchmark consists of six groups of queries where each group is intended to address the challenges posed by the different aspects of XML query result size estimation. The individual queries in each covers the major possibilities of XML querying capabilities.

The queries of our proposed benchmark are based on the well-known sample XML document of the XMark benchmark “auction.xml”. The structure of this XML document is described in details in Schmidt et al. (2002). We also reuse some of the XMark queries but from other perspectives serving our cardinality estimation targets. Table XI lists the descriptions of the queries of our proposed benchmark and the specific XQuery cardinality estimation aspect handled by each query. The appendix of this paper will give a complete description for the queries of our proposed benchmark.

7 Experiments

This sections presents as an assessment for the quality of the estimates produced by our proposed XQuery estimation framework. The experiments of this section have the following goals:

To demonstrate that our system supports a wide range of different XQuery selectivity estimations aspects. No pervious system supports all of these different aspects together.
To demonstrate that our proposed XQuery cardinality estimation system has a high-accuracy rate.
To demonstrate the ability of our estimation system to provide accurate cardinality estimations not only for the main XQuery expression but also for its sub-expressions as well as the estimated cardinality per each iteration in the scope of the FLWOR expression.

7.1 Estimation accuracy

This sub-section presents an assessment for the accuracy for our XQuery estimation system described in this paper. In these experiments, we use the queries of our proposed XQuery estimation benchmark and an XMark document instance with a size of 10 MB. As previously mentioned, unlike usual XML database benchmarks, our proposed queries are designed with close eyes for the different aspects of testing the accuracy of XQuery cardinality estimation system.

To assess the accuracy of our system, we compare our estimated cardinalities for the proposed queries with their actual resulting cardinalities. We use the following error metric for evaluating the accuracy of our estimation system: Equation 9 where RE(Q) represents the relative error in the estimated cardinality of the query Q, EST(Q) represents the estimated cardinality of the query Q and ACT(Q) represents the actual resulting cardinality of applying the query Q.

Figure 13 shows the computed relative errors for our experiment. Remarks about the results of this figure are given as follows:

Using our introduced notion of guide node annotations and our summary structure, statistical guide, our XQuery estimation system is able to produce exact estimates with no errors for different types of order-insensitive path expressions as well as twig expressions (Q1, Q2, Q3, Q5, Q6, Q7 and Q8). Similarly, the cardinality of nested XQuery expression (Q21) is very dependent on the cardinality of the referenced XPath expression in the scope of the outer for loop. Since we are able to produce exact estimates for the cardinality of XPath expression, we are also able to produce exact estimates for similar nested expressions. Q4 does not appear on the results of Figure 13 because our estimation system does not support the estimation of XPath expressions with order-based axes due to a limitation in our summary structure as it does not capture the order information of the source XML documents.
The resulting relative errors of predicates-based XQuery expressions and join-based XQuery expressions (Q9-Q20) are very dependent on the used statistical histogram techniques for capturing the distribution of the data values as well as the used algorithms for performing comparison and arithmetic operations over histograms. The more sophisticated histogram techniques and algorithms used, the higher the accuracy that could be achieved. Q14 does not appear on the results of Figure 13 because our estimation system does not currently support string-based histograms.
The queries (Q22-Q25) do not appear in the results of Figure 13 because our estimation system does not support them for the following reasons:
- Q22, Q24 are using a form of predicates which is dependent on individual values of the source data values. We cannot track or estimate these values in our algebraic plans.
- Q23 is similar to Q14 uses string-based predicates. Our estimation system does not currently support string-based histograms.
- Q25 is similar to Q4 uses order-based operation. Our currently used summary structure does not capture the order information of the source XML documents.

7.2 Estimating the cardinality of XQuery sub-expression and context of FLWOR iterations

In Section 3, we described the loop-lifting compilation of FLWOR expression. In this compilation, a loop of n iterations is represented by a base loop relation with a single column iter of n values (1, 2, … n). This base loop relation preserves the scope of the context nodes in the FLWOR expression. In this section, we present an example of estimating the cardinality of each sub-expression of the main XQuery expression as well as the cardinality of the context nodes for each iteration in the scope of the FLWOR expressions. In this example, we use the XMark query Q8 and an XMark document instance with a size of 10 MB.

let $auction≔doc(“auction.xml”) return

for $p in $auction/site/people/person

let $a≔

for $t in auction/site/closed_auctions/closed_auction

where $t/buyer/@person=$p/@id

return $t

return<item person=“{$p/name/text( )}”>{count($a)}</item>

To illustrate the correspondence relationship between the sub-expressions and their associated algebraic operator we need to represent the algebraic plan of Q8. The algebraic plan of Q8 consists of a total of 245 operators. Owing to space limitation, we are not able to present this algebraic plan. Figure 14 shows the estimated cardinalities of the of XQuery sub-expressions and iterations contexts for Q8. Remarks about this figure are given as follows:

In the loop-lifting compilation of Q8, we have four different scopes described as follows:
- S0: represents the scope of the outermost let expression;
- S1: represents the scope of the outer for expression;
- S2: represents the scope of the inner for expression; and
- S3: represents the scope of the then part of the conditional where expression.Figure 14(a) shows the four base loop relations, their actual cardinalities and their estimated cardinalities.
Figure 14(b) shows the scope of each sub-expression of the XMark query Q8, its actual cardinality, its estimated cardinality and the estimated cardinality for each iteration in the associated scope. The estimated cardinality of each sub-expression is derived from the estimated cardinality of its correspondent algebraic operator. The estimated cardinality for each iteration in the associated scope is computed by dividing the estimated cardinality of each sub-expression by the cardinality of the base loop relation of its associated scope.

8 Related work

Several research efforts have been presented in the literature to propose different estimation models for XML queries. However, all of the existing work in this domain remains limited to a subset of XPath expressions and twig queries but none of them addresses the critical issues of XQuery language such as iterators, nested queries, arithmetic operations, comparison operations, etc.

Aboulnaga et al. (2001) have presented two different techniques for capturing the structure of the XML documents and for providing accurate cardinality estimations for the path expressions. The first technique is a summarizing tree structure called a path tree. A path tree is a tree containing each distinct rooted path in the database where the nodes are labelled by the tag name of the nodes. The second technique is a statistical structure called Markov table. This table, implemented as an ordinary hash table, contains any distinct path of length up to m and its selectivity. The presented techniques only support the cardinality estimations of simple path expressions that are without predicates, inline conditions, recursive axes and order-based axes. Moreover, the models cannot be applied to twigs. Lim et al. (2002) presented XPathLearner as a cardinality estimation system for XPath expressions which employs the same summarization and estimation techniques presented in Aboulnaga et al. (2001) in a different way. Instead of scanning the XML data, XPathLearner gathers and refines the required statistical information in an online manner from query feedbacks.

Zhang et al. (2006) have addressed the problem of deriving cardinality estimation of XPath expressions. In this work, the authors are mainly focusing on the handling of XPath expressions which involve only structural conditions. The main idea behind the paper is to provide an efficient treatment of recursive XML documents and the accurate estimation of recursive queries.

Li et al. (2006) have described a framework for estimating the selectivity of XPath expressions with a main focus on the order-based axes (following, preceding, following-sibling, preceding-sibling). They used a path encoding scheme to aggregate the path and order information of XML data. They used a path encoding scheme to aggregate the path and order information of XML data.

Freire et al. (2002) have presented an XML schema-based statistics collection technique called StatiX. StatiX leverages the available information in the XML schema to capture both structural and value statistics about the source XML documents. These structural and value statistics are collected in the form of histograms.

The authors of Wang et al. (2004) proposed a framework for XML path selectivity estimation in a dynamic context using a special histogram structure named as bloom histogram. The bloom histogram keeps a count of the statistics for paths in XML data.

The work of Sartiani (2003) is the one closest related to our framework, because it deals with selectivity estimation for XQuery. However, he considers only very restricted kinds of (non-nested) FLWOR expressions. Comparing to our work, we have the following main advantages:

Sartiani approach is very limited to FLWOR expressions while we are supporting a much larger subset (almost complete) of the XQuery language.
Our approach is able to estimate not only the whole XQuery expression but also each of its sub-expressions as well as the cardinality of each iteration in the context of the FLWOR expressions.
Based on our introduced guide node annotation concept, our framework is more flexible as it is able to integrate any XPath or predicates size estimation techniques.
The ability of our framework to estimate the cardinality of the sub-expression and its associated intermediate relational results as well the inferred guide node property of each algebraic operator provides the XQuery engine with the power to generate enhanced execution plans.

9 Conclusion and outlook

In this paper, we described the design and implementation of our proposed framework for estimating the cardinality of XQuery expressions. Several research literature have presented different estimation models for XML queries. However, some of these models are limited only to cardinality estimation of path expression, while others also deal with twig queries, but all of them do not address the critical issues of XML queries such as iterators, nested queries, element construction, etc. To the best of our knowledge, our work is the first which provides a uniform framework to estimate the cardinality of more powerful XML querying capabilities using XQuery expressions as well as its sub-expressions. It exploits the relational algebraic infrastructure to provide accurate estimation in the context of XML and XQuery domains. Moreover, the proposed framework can act as a meta-model through its ability to incorporate different summarized XML structures and different histogram techniques which allows the model designers to achieve their targets by focusing their effort on designing or selecting the adequate techniques for them. Currently, the current status of the our proposed XQuery cardinality estimations framework suffers from two main limitations:

It does not support the estimation of the queries over the order information of the source XML documents using either ordered-based XPath axes or node ordering operators. That is because the used summary structure, statistical guide, does not keep this order information of the source XML document. However, currently we are working on integrating the SLT ordered-based summary structure presented by Fisher and Maneth (2007). Integrating such XML summary structure will solve this problem and enhance our framework with the ability to support ordered-based XQuery expressions.
It does not support the estimation of the data dependent queries described in our proposed benchmark.

In addition, our contributions in this paper include our proposed benchmark for XQuery cardinality estimation systems. Our proposed benchmark distinguishes itself from the other existing XML benchmarks in its focus on establishing the basis for comparing the different estimation approaches in the XML domain in terms of their accuracy of the estimations and their completeness in handling different XML querying features.

Equation 1

Equation 2

Equation 3

Equation 4

Equation 5

Equation 6

Equation 7

Equation 8

Equation 9

Fixed graphic 1

Fixed graphic 2

Fixed graphic 3

Fixed graphic 4

Fixed graphic 5

Fixed graphic 6

Fixed graphic 7

Fixed graphic 8

Fixed graphic 9

Fixed graphic 10

Fixed graphic 11

Fixed graphic 12

Fixed graphic 13

Fixed graphic 14

Fixed graphic 15

Fixed graphic 16

Fixed graphic 17

Fixed graphic 18

Fixed graphic 19

Fixed graphic 20

Fixed graphic 21

Fixed graphic 22

Fixed graphic 23

Figure 1XQuery cardinality estimation framework

Figure 2Illustrating examples for the behavior of some Pathfinder algebraic operators

Figure 3An illustrating example for the loop-lifted compilation of the path steps

Figure 4An example of an XML document and its associated statistical guide

Figure 5Histogram constant manipulation

Figure 6Inference rules of the key, domain and const properties of the Pathfinder algebraic plans

Figure 7Inference rules of the GuideNode, Histogram and Selectivity properties of the Pathfinder algebraic plans

Figure 8Inference rules of DomainSize property of the Pathfinder algebraic plans

Figure 9The inference rules for estimating the cardinalities of Pathfinder algebraic operator

Figure 10The statistical guide for the XMark document

Figure 11Estimation components of the XQuery Q1

Figure 12Annotated properties of operators of algebraic plan of Q1

Figure 13Estimation accuracy

Figure 14The estimated cardinalities of the XQuery sub-expressions and iterations contexts

Table IPathfinder supported XQuery dialect

Table IIPathfinder algebraic operators

Table III

Table IV

Table V

Table VI

Table VII

Table VIII

Table IX

Table XSpecial properties of Pathfinder algebraic operators (relations)

Table XIBenchmark queries list

References

Aboulnaga, A., Alameldeen, A.R., Naughton, J.F. (2001), "Estimating the selectivity of XML path expressions for internet scale applications", Proceedings of the 27th International Conference on Very Large Data Bases (VLDB), Roma, Italy, pp.591-600.