Recent studies have proposed structural summary techniques for pathquery evaluation on semi-structured data sources. One major line of this research has been the introduction of the DataGuide, 1-index, 2-index, and A(k) indices, and subsequent investigations and generalizations. Another recent study has considered structural characterizations of fragments of XPath, the standard path navigation language for XML documents. In this paper we provide a methodology on XPath query processing that couples these two areas of research on structural indices and query languages. To illustrate this methodology, we apply it to couple an upward-only XPath fragment with the A(k) and P (k) structural indices. With an eye towards applying this result to XPath query processing, we (1) show how upward-only XPath expressions can be evaluated directly on the corresponding indices and (2) leverage these results to develop generic techniques for making effective use of A(k) and P (k) indices for more general, frequently occurring XPath expressions.
XML (eXtensible Markup Language) [2] provides a standard data format that is flexible enough to be customized for various domains. An increasing number of applications use XML as their data model or as the format for exchanging data among heterogeneous data repositories for the purpose of collaboration, data integration, and information sharing, and querying XML document databases.
XQuery is currently the most popular XML query language [4]. The fundamental building block of XQuery is XPath [5]. XPath expressions are used to specify small node-labeled trees which match portions of the hierarchical XML data. How to support efficient access to XML data using XPath continues to be a critical research problem in this domain.
In XPath query evaluation, indices similar to those used in relational database systems – namely, value indices on tags and text values – are first used, together with structural join algorithms [3, 1, 21]. This approach turns out to be simple and efficient.
Index
Description
Labeling DataGuide [7] Every unique Can not use in- Target node set reachlabel path of a coming path for able by an XPath exsource appear node labeling. pression is the superset exactly once in of the result.
the index graph.
Strong Distinguishes Nodes that share Labeled by the Can be used to directly DataGuide [7] nodes that are the same incom- unique incoming answer linear XPath 1-index [14] reachable by ing path up to the path up to the query of any length.
different paths. root root 2-index[14] Distinguishes Pairs (vectors) of Can be used to diT-index[14] pairs (vectors) of nodes that share rectly answer queries nodes that shares the same paths that match a given temthe same set of plate.
paths.
A(k)-index Distinguishes Nodes that share Can be used to evalu[12] nodes with in- the same incom- ate linear XPath exprescoming path up ing path, up to sion directly when local to length k. length k similarity is sufficient.
D(k)- Uses local index Nodes that shares Need verification when index[17] to adapt to query the same incom- the XPath query expresM (k)- workload ing path, accord- sion is longer than k. index [9] ing to local simi
larity.
However, the structural containment relationships native to XML data are not directly captured by value indices.
To directly capture the structural information of XML data, a family of XML indices has been introduced. DataGuide [7] was the first to be proposed, followed by the 1-index [14], which is based on a notion of bisimulation among nodes in an XML document. These indices can be used to evaluate path expression accurately without accessing the original data graph. Milo and Suciu [14] also introduced the 2-index and T-index, based on similarity of pairs (vectors) of nodes. Unfortunately, these and other early structural indices tend to be too large for practical use because they typically maintain too fine-grained structural information about the document [10, 18].
To remedy this, Kaushik et al. introduced the A(k)-index [12] which uses a notion of bisimilarity on nodes relativized to paths of length k from nodes. This captures localized structural information of a document, and can support path expressions of length up to k. Focusing just on local similarity, the A(k)-index can be substantially smaller than the 1-index and others.
Several works have investigated maintenance and tuning of the A(k) indices. The D(k)-index [17] and M (k)-index [9] extend the A(k)-index to adapt to query workload. Yi et al. [20] developed update techniques for the A(k)-index and 1-index. Finally, the integrated use of structural and values indices has been explored [11], and there have also been investigations on covering indices [10, 18] and index selection [16, 19]. The characteristics of many of these structural indices are summarized in Table 1.
The introduction of structural indices for XML data has lead to significant improvements in the performance of XPath expression evaluation. Furthermore, great advances have been made on the theoretical and practical underpinnings of expression processing [13]. However, to date there lacks a general framework for investigating some of the most fundamental questions about using indices in expression evaluation. Such questions include: 1. For which classes of XPath expressions are structural indices ideally suited? 2. Then, for these classes, how are its expressions optimally evaluated with the index? 3. Can the answers to these questions be bootstrapped to provide general techniques for evaluation of arbitrary XPath expressions?
To answer question (
Recaputilating, recent studies have (
To illustrate this methodology, we apply it to couple the important concept of A(k)
and P (k) structural indices with a certain upward XPath fragment. With an eye towards
applying this result to XPath query processing, we (
In particular, we give a precise characterization of the family of A(k)-indices in
terms of a downward fragment of XPath (Section 3). With this result in hand, we
answer question (
n0 n4 Project n5 Project
Project n6 n2 2.1 The XPath-Algebra We first introduce the XML data model and algebraization of the navigational core of XPath, following the presentation of Gyssens et al. [8]. In this paper, documents are finite unordered node-labeled trees. More formally, a document D is a 4-tuple (V; Ed; r; ¸), with V the finite set of nodes, Ed µ V £ V the set of edges, r 2 V the root, and ¸ : V ! L a node-labeling function into a countably infinite set of labels L. A visualization of a fragment of a document is given in Figure 1. Useful notions of height and distance in a document are defined as follows.
Definition 1. Let D = (V; Ed; r; ¸) be a document and n; m 2 V . The distance from n to m in D, distance(n; m), is the length of the path from n to m in D. The height of D, height(D), is the length of the longest path in D starting from the root r. In other words, height(D) = maxfdistance(r; n) j n 2 V g.
We next present an algebraization of the logical navigational core of XPath. Definition 2. The XPath-algebra consists of the primitives "; ;; #; ", and ` together with the operations on expressions E1 ¦ E2; E1[E2]; E1 [ E2; E1 \ E2, and E1 ¡ E2.4 Given a document D = (V; Ed; r; ¸), the semantics of an XPath-algebra expression E on D, denoted E(D), is always a binary relation over V . The semantics for each operation is given in Table 2.
The XPath-algebra semantics reflects a “global” perspective of expressions being evaluated on an entire document. There is also a “local” semantic perspective, in which expressions are viewed as working on a particular node, as follows.
Definition 3. Let E be an XPath-algebra expression and let D = (V; Ed; r; ¸) be a document. For m 2 V , E(D)(m) = fn 2 V j (m; n) 2 E(D)g.
To illustrate the XPath-algebra, the XPath query for retrieving all departments with websites on the document of Figure 1, =Projects=Department[:=Web], can be formulated in the XPath-algebra with the expression Projects ¦ # ¦ Department[# ¦ Web] 4 Since we are concerned in this study with reasoning on a fixed document of which the height is known, it is not necessary to introduce ancestor or descendant axes.
"(D) = f(m; m) j m 2 V g ;(D) = ; # (D) = Ed " (D) = Ed¡1 `(D) = f(m; m) j m 2 V and ¸(m) = `g E1 [ E2(D) = E1(D) [ E2(D) E1 \ E2(D) = E1(D) \ E2(D) E1 ¡ E2(D) = E1(D) ¡ E2(D) E1 ¦ E2(D) = f(m; n) j 9w : (m; w) 2 E1(D)
& (w; n) 2 E2(D)g E1[E2](D) = f(m; n) 2 E1(D)
j 9w : (n; w) 2 E2(D)g: evaluated “locally” at the root node n0. As further illustrations of XPath-algebra expressions, consider: E1. “Retrieve all department names in projects.”
Projects ¦ # ¦ Department ¦ # ¦ Name
Department ¦ # ¦ Project[# ¦ Web] ¦ # ¦ Lead
Department ¦ # ¦ Project ¦ # ¦ Lead ¡ E2 E4. “Retrieve the names of all departments that have a website and a project with a website.”
Projects ¦ # ¦ Department[# ¦ Web][# ¦ Project ¦ # ¦ Web] ¦ # ¦ Name E5. “Retrieve all projects which are sub-projects of projects with a website.”
Project[" ¦ Project ¦ # ¦ Web]
Recall that in the “global” semantics of the XPath-algebra, expressions evaluate to pairs of satisfying nodes. For example, E1(D) = f(n0; n3); (n0; n7)g and E5(D) = f(n17; n17); (n18; n18)g. 2.2
A(k) Indexes Kaushik et al. have proposed the family of A(k)-indexes for graph-structured data, based on a notion of node bisimilarity [12]. An A(k)-index is built on a partitioning of the nodes of a semi-structured document. The definition of the equivalence relation ´A(k), specialized to XML documents, which induces this partition is as follows. Definition 4. Let D = (V; Ed; r; ¸) be a document, n1; n2 2 V , and k 2 N. We say n1 and n2 are A(k)-equivalent in D, denoted n1 ´A(k) n2, if 1. ¸(n1) = ¸(n2); and 2. if k ¸ 1 then (a) n1 has a parent in D if and only if n2 has a parent in D; and (b) if n1 has parent p1 and n2 has parent p2, then p1 ´A(k¡1) p2. n1 ´A(k+1) n2, then n1 ´A(k) n2.
A(k) equivalence defines partition blocks on the nodes n 2 V of a document D = (V; Ed; r; ¸),
[n]k = fn0 j n0 2 V & n ´A(k) n0g and the full A(k)-index is built directly on the collection of these partition blocks, D=A(k) = f[n]k j n 2 V g: We refer to this partition as simply the A(k)-index.
Following Kaushik et al. [12], a full A(k)-index can be visualized as a graph wherein each node represents a partition block and an edge exists from a node A to a node B if an edge existed in the original document from a data node in A to a data node in B. This construction is illustrated in Figure 2 on the Design Department subtree of the document of Figure 1.
We observe the following basic property of A(k) equivalence, which follows by a simple induction on k.
Proposition 1. Let D = (V; Ed; r; ¸) be a document, let k 2 N, and let n1, n2 2 V . If
At first sight, we have defined an infinite class of equivalence relations on D. However, there is no point to consider A(k) equivalence beyond k = height(D), as can also be seen by an inductive argument.
Proposition 2. Let D = (V; Ed; r; ¸) be a document, and let k ¸ height(D). Then A(k) equivalence coincides with A(height(D)) equivalence.
We now extend A(k) equivalence as follows to capture upward paths to the root in a document.
Definition 5. Let D = (V; Ed; r; ¸) be a document and n1; n2 2 V . We say n1 and n2
are A(
Not surprisingly, we have the following.
Proposition 3. Let D = (V; Ed; r; ¸) be a document. Then A(
Note that A(
Definition 6. Let D = (V; Ed; r; ¸) be a document, k 2 N, let m1, n1, m2, n2 2 V such that m1 is an ancestor of n1 and m2 is an ancestor of n2. Then, (n1; m1) and (n2; m2) are P (k) equivalent, denoted (n1; m1) ´P (k) (n2; m2), if 1. distance(n1; m1) = distance(n2; m2); and 2. n1 ´A(k) n2.
Note that P (k) equivalence on pairs of nodes induces a “localized” version of the 2index proposed by Milo and Suciu [14], just as A(k) equivalence on nodes induces a “localized” version of the 1-index [12].
Consider the subtree D0 in the document of Figure 1 rooted at n4. As an illustration of the P (k)-index (i.e., the partition set D=P (k) induced by P (k) equivalence on a document D) the P (0)-index of D0 is:
D0=P (0) = f[(n10; n10); (n19; n19)]; [(n10; n4); (n19; n9)]; [(n19; n4)]; [(n4; n4); (n9; n9)]; [(n9; n4)]; [(n11; n11); (n20; n20)]; [(n11; n4); (n20; n9)]; [(n20; n4)]g
Properties 1 and 2 of A(k) equivalence can easily be bootstrapped to properties of P (k) equivalence.
Proposition 4. Let D = (V; Ed; r; ¸) be a document, let k 2 N and let m1, n1, m2, n2 2 V such that m1 is an ancestor of n1 and m2 is an ancestor of n2. If (n1; m1) ´P (k+1) (n2; m2) then (n1; m1) ´P (k) (n2; m2) Proposition 5. Let D = (V; Ed; r; ¸) be a document, and let k ¸ height(D). Then P (k) equivalence coincides with P (height(D)) equivalence.
As with A(k) equivalence, we extend P (k) as follows to capture upward paths to the root in a document.
Definition 7. Let D = (V; Ed; r; ¸) be a document and let m1, n1, m2, n2 2 V such
that m1 is an ancestor of n1 and m2 is an ancestor of n2. Then, (n1; m1) and (n2; m2)
are P (
Proposition 3 for A(
Proposition 6. Let D = (V; Ed; r; ¸) be a document. Then P (
Note that P (
As a closing remark, we observe from the definitions of A(k) and P (k) indices that, given an A(k) index on a document D, it is straightforward to derive the corresponding P (k) index for D, and vice versa.
Algebraic Characterizations of the A(k) and P (k) Indices In this section, we give characterizations of the A(k) and P (k) family of indices based on notions of indistinguishability of nodes and pairs of nodes in fragments of the XPathalgebra. The notion of language indistinguishability on nodes is made precise in the following definition, following Gyssens et al. [8].
Definition 8. Let D = (V; Ed; r; ¸) be a document, m1; m2 2 V , and F a fragment of the XPath-algebra. We say m1 and m2 are indistinguishable by F , denoted m1 ´F m2, if for any expression E in F , it is the case that E(D)(m1) = ; if and only if E(D)(m2) = ;.
Language indistinguishability on pairs of nodes is defined as follows.
Definition 9. Let D = (V; Ed; r; ¸) be a document, n1; m1; n2; m2 2 V , and F a fragment of the XPath-algebra. We say (n1; m1) and (n2; m2) are indistinguishable by F , denoted (n1; m1) ´F (n2; m2), if for any expression E in F , it is the case that (n1; m1) 2 E(D) if and only if (n2; m2) 2 E(D).
Next, we introduce a family of algebras which we use to precisely characterize the A(k) and P (k) indices.
Definition 10. We recursively define the upward-k XPath algebras, U (k) for each k 2 N, as follows. 1. U (0) = the set of XPath-algebra expressions without occurrences of the “#” and “"” operators. 2. For k ¸ 1, (a) if E 2 U (k ¡ 1), then E 2 U (k); (b) " 2 U (k); (c) if E1 2 U (k) and E2 2 U (k), then
– E1 ? E2 2 U (k), for ? = [; \; ¡; (d) if E1 2 U (k1) and E2 2 U (k2), and k1 + k2 · k, then
– E1 ¦ E2 2 U (k) and E1[E2] 2 U (k); and 3. No other expressions are in U (k).
As a very simple example of U (k) expressions, note that " ¦ " ¦ " is in U (
The following useful observation about the U (k) algebras can be shown by a simple inductive argument.
Proposition 7. Let D = (V; Ed; r; ¸) be a document, k 2 N, m; n 2 V , and E 2 U (k). If (n; m) 2 E(D), then m is an ancestor of n such that distance(n; m) · k.
The U (k) algebras are extended as follows to an algebra with unrestricted use of the “"” primitive.
Definition 11. The upward XPath algebra U (
In other words, U (
Compositions in which the number of nested “"” primitives is strictly greater than height(D) must return the empty set, and are therefore not very meaningful. The following result should therefore not come as a surprise.
Proposition 8. The U (
In particular, indistinguishability by U (height(D)) and indistinguishability by
U (
Structural Characterizations of U (k) and U (
The following facts are crucial in the sequel.
Lemma 1. Let D = (V; Ed; r; ¸) be a document, k 2 N, and n1, m1, n2 2 V such that m1 is an ancestor of n1 and distance(n1; m1) · k. If n1 ´A(k) n2, then there exists m2 2 V such that m2 is an ancestor of n2 and (n1; m1) ´P (distance(n1;m1)) (n2; m2).5 Furthermore, m1 ´A(k¡distance(n1;m1)) m2.
Proof. By induction on k. For the base case, k = 0, clearly m1 = n1 and ¸(n1) = ¸(n2). The statement holds for m2 = n2.
For k ¸ 1, we can assume that the statement holds for k¡1. If n1 ´A(k) n2, then
either (
Proposition 9. Let D = (V; Ed; r; ¸) be a document, k 2 N, E 2 U (k), and n1; m1; n2; m2 2 V such that m1 is an ancestor of n1 and m2 is an ancestor of n2, and (n1; m1) ´P (k) (n2; m2). If (n1; m1) 2 E(D), then (n2; m2) 2 E(D), and vice versa.
Proof. First observe that it follows from E 2 U (k) and (n1; m1) 2 E(D) that distance(n1; m1) · k, by Proposition 7. 5 And even stronger, (n1; m1) ´P (k) (n2; m2).
The proof is by induction on k. The base case, k = 0, follows straightforwardly from the definition of P (0) equivalence and a simple structural induction on expressions in U (0). Now assume that k ¸ 1, and that the statement holds for 0; 1; 2; : : : ; k ¡ 1. The proof goes by structural induction on expressions in U (k). Thus, let E 2 U (k). – E 2 U (k ¡ 1). The statement holds by the induction hypothesis. – E =". If (n1; m1) 2" (D), then m1 is the parent of n1. Since (n1; m1) ´P (k) (n2; m2), it follows in particular that m2 is the parent of n2. We conclude that (n2; m2) 2" (D). – E = E1 [ E2, for E1 and E2 2 U (k). Suppose (n1; m1) 2 E(D). Then (n1; m1) 2 E1(D) or (n1; m1) 2 E2(D). Without loss of generality, assume (n1; m1) 2 E1(D). Then by structural induction, (n2; m2) 2 E1(D), and we conclude (n2; m2) 2 E(D). – E = E1 \ E2 or E = E1 ¡ E2, for E1 and E2 2 U (k). Similar to the previous case. – E = E1 ¦ E2, for E1 2 U (k1) and E2 2 U (k2), such that k1 + k2 · k. Suppose (n1; m1) 2 E(D). Then there exists a node w1 2 V such that (n1; w1) 2 E1(D) and (w1; m1) 2 E2(D). By Lemma 7, distance(n1; w1) · k1 and distance(w1; m1) · k2. By Lemma 1, there exists a node w2 2 V such that (n1; w1) ´P (distance(n1;w1)) (n2; w2), and w1 ´A(k¡distance(n1;w1)) w2. Since, k2 · k ¡ distance(n1; w1), by Lemma 1, a node m0 2 V exists with (w1; m1) ´P (distance(w1;m1)) (w2; m0). Since (n1; w1) ´P (distance(n1;w1)) (n2; w2), and (w1; m1) ´P (distance(w1;m1)) (w2; m0), we know, by the definition of ´P (k1) and ´P (k2), that distance(n2; w2) = distance(n1; w1) and distance(w2; m0) = distance(w1; m1). Consequently, distance(n2; m0) = distance(n1; m1), and since m0 is the unique ancestor at this distance, we conclude that m0 = m2. Thus (w1; m1) ´P (k2) (w2; m2). By the induction hypothesis, we can conclude that (n2; w2) 2 E1(D) and (w2; m) 2 E2(D) and thus (n2; m2) 2 E(D). – E = E1[E2], for E1 2 U (k1) and E2 2 U (k2), such that k1 + k2 · k. Similar to the previous case.
An important corollary of Proposition 9 is the following observation.
Proposition 10. Let E 2 U (k), k 2 N, and let D = (V; Ed; r; ¸) be a document. Then E(D) is the union of some partition blocks of the P (k)-index.
We are now prepared to establish the main results of this section.
Theorem 1. Let D = (V; Ed; r; ¸) be a document, n1; n2 2 V , and k 2 N. Then n1 ´U (k) n2 if and only if n1 ´A(k) n2.
Proof. (If) Suppose n1 ´A(k) n2 and let E 2 U (k) such that E(D)(n1) 6= ;. Hence, there exists m1 2 V such that (n1; m1) 2 E(D). Then, by Lemma 1 and Proposition 9, there exists m2 2 V such that (n2; m2) 2 E(D), and therefore E(D)(n2) 6= ;. It follows symmetrically that if E(D)(n2) 6= ;, then E(D)(n1) 6= ;. We conclude that n1 ´U (k) n2.
(Only if) For the converse, assume that n1 ´U (k) n2. We first establish two facts.
Following a similar argument, we have the following characterization of U (k) indistinguishability on node pairs.
Theorem 2. Let D = (V; Ed; r; ¸) be a document, n1; m1; n2; m2 2 V , and k 2 N. Then (n1; m1) ´U (k) (n2; m2) if and only if (n1; m1) ´P (k) (n2; m2).
We remind the reader that indistinguishability by U (
Theorem 3. Let D = (V; Ed; r; ¸) be a document and n1; n2 2 V . Then n1 ´U (
Similarly, by Proposition 6, P (
Theorem 4. Let D = (V; Ed; r; ¸) be a document and n1, m1, n1, n2 2 V . Then
(n1; m1) ´U (
XPath Query Evaluation with A(k) and P (k) Indices
In this section, we consider strategies to evaluate XPath expressions, leveraging the
results and characterizations of the A(k) and P (k) indices (Sections 3). First, we discuss
how A(k) and P (k) indices can be used in the evaluation of upward XPath
expressions, as expressed in the U (
Actually, any U (
A natural way to evaluate D (
The main idea behind turning top-down evaluation into bottom-up evaluation is to convert a downward expression, or certain of its sub-expressions, into an upward expression using a technique that we will refer to as “inverting expressions.” We first illustrate this technique on predicate-free downward expressions, and then consider general downward expressions.
Downward Expressions without Predicates In general, predicate-free expressions in the downward algebras can be “inverted” into predication-free expressions in the corresponding upward algebras using the rewrite rules shown in Table 3.
As discussed above, an upward algebraic expression in U (k) can be evaluated by
P (k)-index lookup and set unions. Therefore, a predicate-free downward algebraic
expression in D (k) can be evaluated by inversion, P (k)-index lookup, and set unions.
Downward Expressions with Predicates Now consider the evaluation of downward
algebra expressions wherein predicate operations occur. A simple example is the
expression E2 =# [#]: Applied to a document, E2 evaluates to the document’s
parentchild pairs for children that have at least one child itself. As in Section 4.2, to evaluate
E2 on a document D, we could consider the concept of inverting E2 into an
expression E2¡1 2 U (
Clearly E2 is equivalent to the XPath-algebra expression # ¦ # ¦ ". Notice that
this expression is neither a downward nor an upward expression. However its
subexpression G1 =# ¦ # is in D (
Given that the selectivity of a longer path is no larger than that of short sub-paths of the path, evaluating G1 reduces the search space to the minimum that can be obtained on such a chain expression. Starting from any given node, upward navigation in an XML data tree, unlike downward ones, has one and only one route to follow, which is to reach its parent. Therefore, it is reasonable to claim that the result of G1¡1(D) is substantially smaller than that of G2(D), and the ./ operation can be further optimized by G1¡1(D) followed by an upward navigation.
We will now consider a slightly more complicated downward expression E3 2
D (
E3 = Department ¦ # ¦ Project[# ¦ Web] ¦ # ¦ Lead: E3 can be represented as an expression pattern tree, as illustrated in Figure 3(a). The shaded node can be interpreted as the “answer” of E3.
Lead (a)
Department
First, assume there exists a P (
Using G1, G2, and G4, the expression E3 is equivalent to the expression H1 defined as follows:
H1 = ((G1 ¦ ") \ (G2 ¦ ")) ¦ G4;
and therefore, for a document D, E3(D) can be computed as follows:
All sub-expressions in this transformed expression of E3 are in U (
However, it may not always be the case that P (k)-partitions exist for k larger than
or equal to the height of the query expression. Again, for E3, consider the case when
only a P (
H2 = (((G3 ¦ G4) ¦ ") \ ((G3 ¦ G5) ¦ ")) ¦ G4:
Similar to the generalization from E2 to E3, the decomposition + inversion
techniques can be used to transform any arbitrary expression in the downward algebra
D (
Future Directions
It is clear that many aspects of the query evaluation guidelines presented in the previous
section warrant further investigation. We close by listing a few of the more interesting
directions for research. First, a more thorough study of query decomposition and
inversion algorithms is crucial. Second, it is interesting to develop approaches to (