Research into XML query transformation has become important with the increased use of XML. Currently the research into XML query transformation concentrates on transformation based on structure of the XML document. In this paper, we will introduce our research which transforms queries using the classification of elements of XML documents. The experiments have shown that our method improves query execution dramatically.
Query transformation [
In this paper, we introduce our research into
transforming XML queries based on the data in XML documents.
The aim of our research is to improve query execution
by transforming the queries based on the elements’
classification. Elements in the queried XML document will
be analyzed and their value distribution characteristics
will be abstracted. Then classifications will be generated
based on the elements’ value distribution charactestics.
With the information of the elements’ classification, the
input XML queries will be evaluated and transformed to
a query, which will return the same results as the
original query but can be executed faster. A series of
experiments have been carried out and the results show that
query execution can be improved dramatically with our
method. Our early contributions are: First, we introduce
a method to transform XML queries based on the content
of the XML document [
The remainder of this paper is structured as follows. Background information is introduced in section 2. Our query transformation method is introduced in section 3. Section 4 introduces the query transformations in our method. In section 5, we introduce the experiments and analyze the experimental results. In section 6, we discuss related work. Section 7 draws conclusions and discusses the problems that we are working on. 2
In this section, we discuss the existing semantic query optimization methods in XML and the challenges that arise in XML analysis.
XML semantic query optimization can be classified into
two main groups: optimization based on the structure of
the document, and optimization based on the content of
the document. Optimization based on the structure of
the document uses information that is found in the
document’s schema to optimize XML query processing. In
[
Optimizations based on the content use the
characteristics of values of elements to improve XML query
execution. Currently most of this kind of research
concentrates on statistical information. An example of this kind
of optimization is implemented in Lore [
The relationship can be siblings, parent-child or ancestor-descendant. 3. same name elements may appear within different parent nodes and be distributed at different levels in an XML document. 3
Our method for transforming XML queries is to classify elements based on distribution characteristics of the values of elements and transform the queries based on the classifications. As we discussed in the previous section, the biggest obstacle is the flexibility of XML documents. However if we concentrate only on specific elements instead of the whole document, it is possible to abstract their value distribution characteristics, and related elements may be classified based on the distribution characteristics. Then query transformation may be carried out based on the classification.
Consider the XML file shown in Fig. 1. It may be difficult to classify the product elements based on the values of all their subelements. This problem can be overcome by choosing the most important elements for the classification. For example we may analyze two elements ID and material, and find that all products that are made of cotton have IDs smaller than 200000 and the IDs of products that are made of leather are greater than 200000. So we can classify the elements product to two groups: product of cotton, which have IDs smaller than 200000, and product of leather, which have IDs bigger than 200000. With this classification, a query “document( store.xml )//product[ID > 200000 and material = ‘leather ]” can be transformed to “document( store.xml )//product[material = ‘leather ]” and the transformed query will return same results as the original when executed against the data in Fig. 1.
The element classification results and the related information of elements, including both element value characteristics and the number of the elements of each group, are all useful in query transformation. With the classification information, queries will be evaluated and possible query transformations may be generated. If there are multiple transformations, the number of elements in each group may be used to choose the most efficient transformation.
XML query with element 4
Element classification based XML query transformations can be classified into three categories: Elimination, which removes mutually exclusive query conditions; Reduction, which removes the semantically redundant query conditions; and Introduction, which introduces extra conditions to the original query conditions. Below, we will discuss these transformations in detail. In order to explain the transformations clearly, we will use “ConditionM (e)” to represent the result of evaluating query condition “M” on element “e” and σCon(M)(E) to represent all the elements that satisfy query condition “M” when applied to the elements in E. 4.1
Elimination is the operation that eliminates queries with mutually exclusive query conditions. Consider an XML document in which “all the managers are paid more than $5000”, then the condition of query “document(’record.xml’)//person [position = ’manager’ and getP aid < 4500] ”1 can be transformed to F alse. Theorem 3.1 If two conditions in a query are mutually exclusive and the operator between them is “∧”, the two conditions can be transformed to F alse, which can be illustrated as
ConditionM∧N (e) = False if ConditionM (e) ∧ ConditionN (e) = False2 1We represent all queries in this paper in XPath.
2For more discussion and a proof about each transformation please
refer to [
Reduction is the operation that eliminates redundant query conditions so this kind of transformation can only be applied to multiple-condition queries. An example of this transformation is that the original query “document(’record.xml’) // person [position = manager and salary > 5000]” can be simplified to “document( record.xml )// person[position = manager ]” if we know that all the managers are paid more than 5000.
Theorem 3.2 If all elements “e” that satisfy query condition “M” always satisfy condition “N” and the operator between the two query conditions is “∧”, then the two query conditions can be simplified to condition “M”. This is written below:
if ∀e(e ∈ σCon(M)(E) ⇒ e ∈ σCon(N)(E)) Theorem 3.3 If all elements “e” that satisfy query condition “M” always satisfy condition “N” and the operator between the two query conditions is “∨”, then the two query conditions can be simplified to condition “N”. This can be represented as:
if ∀e(e ∈ σCon(M)(E) ⇒ e ∈ σCon(N)(E)) Because the redundant query conditions are removed by the reduction transformation, both the amount of work of “computation” and “join” will be reduced and the performance of the query execution will be improved.
Introduction is the transformation that adds a new condition, with the aim of reducing the query search space, compared with the original query condition. Consider the scenario where only people, whose rank is lower that 4, get paid less than 3000, the query “ document(’record.xml’)// person [salary < 3000] ” can be transformed to “ document(’record.xml’ )// person[rank < 4 and salary < 3000] ”. The necessary conditions for this kind of transformation are : • the domain of the original query condition must be a subset of the domain of the additional condition. • an index is built on the additional condition-related element. • the selectivity of the additional condition-related element is higher than that of the original conditionrelated element.
Theorem 3.4 If all elements “e” that satisfy query condition “M” always satisfy condition “N”, then the query condition “M” can be transformed to condition “M ∧N ”. The transformation can be illustrated as
if ∀e(e ∈ σCon(M)(E) ⇒ e ∈ σCon(N)(E)) 5
In this section, we present the experiments designed
for our research. All the experiments are run on an HP
workstation XW4200, which is equipped with an Intel
Pentium 4 CPU 3.40GHZ and 2 GB memory.
The experimental data sets are built using an XML
generator [
Three groups of queries are designed for the experiments and the formats are shown in Fig. 3. Because the condition of the original query will be transformed to F alse using the Elimination Transformation, there is no query generated. For “reduction” and “introduction”, we can get a series of queries with different selectivity by changing the values of V al1 and V al2. The introduced condition for “introduction” will be generated automatically according the descriptions of element classifications and for different situations the generated conditions are different.
A transforming engine was designed for the experiments, which includes the following modules: 1. Information management module, which is designed to manage the elements’ classification descriptions used in query transformation;
to extract information for each kind of element from the XML document;
with the Elimination transformation;
Reduction transformation;
the Introduction transformation.
The structure of the engine is shown in Fig. 4 3.
We use the eXist XML database [
The results of these experiments are shown in Fig. 5. It
3For more discussion about the transforming engine please refer to
[
Results of “reduction” are shown in Fig. 6. From the Fig. it can be seen that because the workload on both computation and join are reduced, the performance of query execution can be improved by about 30% when the query is executed with the automatically built index. When the queries are executed with a manually built index, the performance can be improved around 20%. This phenomena becomes more obvious when the selectivity or the size of the XML document is increased.
From Fig. 7, it can be seen that the results of “introduction” are different from our prediction and the query execution time has increased instead of reduced. In fact, the bigger the selectivity or the size of the document, the more the execution time increases. After analyzing the query execution, we assume transformation “introduction” may only work on some query engines which execute queries by choosing a sub-query execution strategy. And for query engines, which execute multiplecondition queries by choosing the intersection of the results of each sub-query, the transformation “introduction” will increase the workload and make the query execution worse.
From the results of our experiments we can draw the conclusion that element classification based query transformation can improve the query execution in some situations. 6
Currently XML query optimization based on the content
of the data mainly concentrates on element statistics. In
the optimization mechanism in “Lore” [
In [
Authors of [
The research reported above improves the performance of XML query execution. However, none of this work is based on the distribution of the values of elements. 7
In this paper, We discuss the possibility of transforming XML queries based on the content of data. We also discuss the possible transformations, which are carried out based on the content of data. A series of experiments are presented and the results are discussed. The experimental results show that transforming queries based on data can improve query execution time in some situations. Currently the element classifications are edited manually. Now we are working on an algorithm, which analyzes the values of elements and abstracts distribution characteristics. As we discussed previously, XML documents are very flexible making analysis difficult. We have identified the following issues:
ument is analyzed, it is very difficult for a user
or database administrator to specify an accurate
or suitable number of classifications based on the
data distribution. Because of this, we chose the
XMeans [
Our contributions to date have been a data generator to build data sets with specific characteristics to carry out accurate and targeted experiments, the classification of possible transformations and experiments that prove how well the transformations work. From here, we plan to build a tool that classifies the data. In order to do so, we will have to address the issues described above.