-
In recent years, many approaches to indexing XML data have appeared. These
approaches attempt to process XML queries efficiently and sufficient query plans
are built for this purpose. Some effort has been expended in the optimization of
XML query processing [
20
].
There are not many works that take cost-based query optimizations into
account. In work [
20
], we nfid some cost-based considerations, however, they
work only with one type of structural join and one type of underlying index.
There are works depicted two types of query processing as well [
10, 17
]. The rfist
type applies an element-based index, the second type applies a navigation in a
persistent DOM-like structure. In our work, we propose usage of two path-based
indices that provide significant potential for a query optimization based on a
cost-based join selection.
We can identify some classes of approaches for efficient processing of XML
queries. The first class includes approaches based on shredding [
18
] (storing an
XML document in many relations, where each element name has its own
relation). These approaches work well only on specicfi documents with a defined
XML schema. The second class of approaches [
15, 21, 1
] provides an
elementbased decomposition of an XML document. These methods usually work with a
labeling scheme and they differ mainly in various join algorithms.
We identify two main types of join algorithms. The rfist join type works with
sorted node sets merged by a type of holistic join [
3, 4
]. This kind of structural
join is optimal when a small number of nodes is rejected during the structural
join. In this case, nodes are retrieved in a very efficient way with a small number
of I/O. In our article, this kind of join operation is called a merge join. Another
type of join algorithm is based on context nodes [
9
], where each location step is
processed using context nodes from the previous step. We say that this approach
utilizes a previously processed location step and uses the nodes for an efficient
search of nodes in the next step. If there is a large number of rejected nodes in
the join operation, this kind of join is efficient. In our article, this kind of join
operation is called a progressive join.
There are approaches that decompose XML documents according to the node
path, as opposed to the node name. Handling the paths during a query processing
Michal Kr´atky´ and Radim Baˇca
provides some advantages. If the a/b/c//e/f/g simple-path query is considered,
then the query is evaluated by vfie structural joins. The evaluation may be very
inefficient compared to path-based approaches [
16, 19, 6, 14, 13, 11
] and
summarizing approaches [
8, 7
], even when an additional optimization of structural joins
is used [
4, 3, 12
]. The path-based approaches perform these queries by finding
matched labelled paths – a relatively simple task – and then finding relevant
nodes with a single index search [
16
]. Since there is a significantly lower number
of labelled paths than nodes in an XML document, the search can be performed
very quickly. Supposing there is a set of matched labelled paths, we nfiish the
simple-path query process by nfiding nodes corresponding to those labelled paths
in an inverted list. In work [
5
], we find a comparison of different decomposition
approaches and a labelled-path approach (Prexfi-Path streaming in this case)
has good experimental results.
In the case of path-based approaches, we can observe the same issue as in
the case of element-based approaches. When we join two path results, we can
perform it with two different types of joins. One join is based on an inverted
index and the second one utilizes the previous query path result.
Chen et al. in [
6
] compares two path-based approaches to processing twig
queries. Whereas the rfist index, ROOTPATHS index, is able to process twig
queries only with the merge join, the second index, DATAPATHS index, is able
to process a query path by utilizing previous query path results. Consequently,
DATAPATHS index applies a progressive join algorithm. These indices can
outperform each other depending on the query. However, there is no general
proposal that can help to decide that the index should be used to achieve the best
query evaluation performance. In works [
13, 14
], we have introduced an index to
provide these join operations.
In work [
2
], we introduce a simple, cost-based, optimization technique for a
join selection during a query evaluation. This technique joins the advantages of
a simple path query processing based on inverted lists and usage of previous
results for a twig query processing. We show that the knowledge of the result
size can help to choose a good query evaluation strategy. We utilize advantages
of existing, state-of-the-art, path-based approaches, such as [
16, 19, 6
], to achieve
an optimal query performance.