This is the first and preliminary study on answering queries using views in a probabilistic XML setting. We formalize the problem and study it under the two possible semantics for XML query results: with node identifiers and in their absence. Accordingly, we consider rewrite plans that can exploit a single view, by means of compensation, and plans that can use multiple views, by means of intersection. Since in probabilistic settings queries return answers with probabilities, the problem of rewriting goes beyond the classical one of retrieving answers from views. For both semantics of XML queries, we show that, even if the XML answers can be retrieved, the computation of their probabilities might not be possible. We give restrictions that make probabilistic rewriting feasible in polynomial time, and present some initial hardness results for this problem.
Uncertainty is ubiquitous in data and many applications must cope with this [
Recent work has proposed models for probabilistic data, both in the relational [
Views over XML documents can be seen as fragments of data that may be available along with the nodes selected by the query. Over a p-document, the data fragments come dPER : together with their probability. In the general setting, we are given a document d and a set of view queries v1; : : : ; vn. Given a query q, the goal is to understand whether one can obtain q(d), the answers of q over d, by accessing view results v1(d); : : : ; vn(d) only. For XML data, the problem was studied under the two possible semantics for XML query results: with persistent node identifiers or in their absence. For the latter case, only rewrite plans that rely on a single view, by means of compensation, are possible. For the former, plans using multiple views, by means of intersection and compensation, are exploitable. We consider both settings and alternatives for rewritings.
We present a preliminary study of the problem of answering queries using views in the probabilistic XML setting. We formalize the problem in Section 3 and we give a preliminary study of it for the two possible settings: in the absence of node Ids, in Section 4, and in their presence, in Section 5. We show that, in the probabilistic setting, the problem of answering queries using views becomes more complex and it does not reduce to its deterministic version. The reason is that query results now involve not only data trees, but also their probabilities. Hence probabilities should also be retrieved from probabilistic view results, by means of a probabilistic function computing them.
Even for the simpler setting (without Ids), the existence of the probabilistic function is not guaranteed by the existence of a data-retrieving rewriting. We present examples of views and queries for which such a function does not exist. Based on a notion of probabilistic independence between queries, we also isolate a class of queries and views for which this function, when it exists, can be found and computed efficiently. For rewritings with intersection, we provide a sufficient condition (also based on probabilistic independence) that guarantees that the probabilities of query answers can be computed as a product-like formula over the probabilities of the views appearing in the intersection. We also present an NP-hardness result for deciding whether a selection of probabilistically independent views for a rewriting is possible. 2
Preliminaries
We briefly define here the data and query model. Details can be found in [
We define a finite probability space of XML documents, or px-space for short, as a
pair (D; Pr) with D a set of documents and Pr mapping every document d to a
probability Pr(d) such that PfPr(d) j d 2 Dg = 1:
Probabilistic documents. p-Documents give a general syntax for compactly
representing px-spaces. Like a document, a p-document is a tree but with two kinds of nodes:
ordinary nodes, which have labels and are the same as in documents, and distributional,
which are used to define the probabilistic process for generating random documents. We
consider three kinds of distributional nodes: ind (for independent), mux (for mutually
exclusive), and det (for deterministic). Other kinds of distributional nodes are studied
in [
A p-document Pb has as associated semantics a px-space JPbK defined by the following random process. Independently for each mux(Prv) (resp. ind(Prv)) node, we select at most one (resp. some) of its children v0 and delete all other children along with their descendants. We do not delete any of the children of det nodes. We then remove in turn each distributional node, connecting ordinary children of deleted distributional nodes with their lowest ordinary ancestors. The result of this process is a random document P. The probability of P, Pr(P), is the product of all (i) Prv(v0) for each chosen child qRBON : IT- personnel
person bonus Rick bonus laptop pda 1 vBON :
IT- personnel
person bonus Rick laptop 2 vBON : IT- personnel person Rick bonus pda v0 of a mux or ind node v, (ii) 1 Prv(v0) for each not chosen child v0 of a ind node v, (iii) 1 Pv0 Prv(v0) for all children of each mux node v for which no children were chosen. Note that for any P 2 JPbK there is a unique way to generate it.
Example 4. Looking again at Figures 1 and 2, one can obtain the document dPER from PbPER by choosing: the left child of the mux node n11, the right child of the mux node n20, and the right one of child of the mux node n52. The marginal probability of these choices (and the probability of dPER), is 0:135 = 0:75 0:6 0:3.
Tree-Pattern queries. The language of tree-pattern queries (TP) is roughly the subset of navigational XPath with child, descendant navigation, predicates, without wildcards. Definition 5. A tree-pattern q is a non-empty, unordered, unranked rooted tree, with a set of nodes nodes(q) labeled with symbols from L, a node called the output node out(q) (i.e., tree-patterns are unary queries), and two types of edges: child edges, labeled by = and descendant edges, labeled by ==. The root of q is denoted root(q).
Due to space limitations, we will often write tree-patterns q in XPath notation [
Example 6. Consider the query qRBON in Figure 3 (left) (where RBON stands for Rick’s bonuses) asking whether Rick has received a bonus from the project laptop and a bonus from the project pda. In this representation, single lines denote child edges and 1 2 double lines descendant edges. The other two queries vRBON and vRBON in Figure 3 (center and right) ask whether Rick has received a bonus on either of these projects. The output node in all the three queries is labeled with Rick.
The semantics of tree-patterns is given using embeddings. An embedding e of a TP query q into a document d is a function from nodes(q) to nodes(d) satisfying: (i) e(root(q)) = root(d); (ii) for any n 2 nodes(q), lbl(e(n)) = lbl(n); (iii) for any =-edge (n1; n2) in q, (e(n1); e(n2)) is an edge in d; (iv) for any ==-edge (n1; n2) in q, there is a path from e(n1) to e(n2) in d.
The result q(d) of applying a tree-pattern q to a document d is the set:
q(d) := fe(out(q)) j e is an embedding of q into dg Example 7. Continuing with the three queries in Figure 3, they all return fn8g over the document dPER, since Rick has got bonuses from both of the requested projects. Intersections of tree-patterns. We consider in this paper the extension TP\ of TP with respect to intersection, which denotes intersections of tree-pattern queries.
TP\ = fq1 \ \ qk j k 2 N; qi 2 TP; and lbl(root(qi)) = lbl(root(qj )); and
lbl(out(qi)) = lbl(out(qj )) for i; j 2 f1; : : : ; kgg: The result of a TP\ query q1 \
\ qk over a document d is the set of nodes Tik=1 qi(d):
Query equivalence and containment. A pattern q1 is contained in a pattern q2, denoted
q1 v q2, if q1(d) q2(d) for every d. Also q1 is equivalent to q2, q1 q2, if q1 v q2
and q2 v q1. We discuss how to check containment of TP\ queries in Section 5. For
TP queries, containment can be decided using containment mappings [
1
Querying p-documents. Up to now, we have seen queries as functions over XML
documents outputting sets of nodes. Over a p-document Pb, a query q (TP or TP\) naturally
yields a set of node-probability pairs (n; p), where n is a node of Pb, and p is the
probability that q can be embedded into a random document P of Pb with some e such that
e(out(q)) = n; this value will also be written as Pr(n 2 q(P)). Formally:
q(Pb) := f(n; p) j 9 d 2 JPbK: n 2 q(d) and p = X
d2JPbK: n2q(d) Pr(d)g:
It is known [
Example 8. Evaluation of qRBON over PbPER returns the node n8 iff the left child of the node n11 and the right child of n20 are chosen. Hence, qRBON(PbPER) = f(n8; 0:75 (0:1 + 0:6))g Further notations. We introduce now some additional terminology for TP queries, which will be used in Sections 4 and 5, and can be skipped until then.
The main branch mb(q) of q is the path from root(q) to out(q), and the main branch nodes of q, mbn(q), are the nodes of mb(q). A prefix qp of q is any tree-pattern that can be build from q by setting root(q) as root(qp), setting some node n 2 mbn(q) as out(qp), and removing from q all mbn(q) nodes below n along with their descendants. A suffix qs of q is any subtree of q rooted at a node of mbn(q). The rank of a main branch node is the distance from it to the root, i.e., the rank of root(q) is 1 and of out(q) is jmbn(q)j. The suffix of q rooted at the node of rank k is denoted qk. For any rank k, cut(q; k) denotes the prefix of q with k main branch nodes.
Problem Definition We assume an infinite set of view names V disjoint from the set of labels L. By a view v we denote a tree-pattern query (that defines the view) together with its name v 2 V. Deterministic view-based rewriting. Let d be a document and v a view. A (deterministic) view extension of v over d, denoted dv, is a document obtained by connecting to a root node labeled doc(v) all the documents from the set fd0 j d0 d and root(d0) 2 v(d)g. Such a document can be queried by TP-queries of the form doc(v)=lbl(v)= : : : . If V is a set of views defined over a document d, then DVd = fdv j v 2 V g. Let q be a query in Q 2 fTP; TP\g that may use doc(v)=lbl(v) for v 2 V , then unfoldV (q) is the query in Q obtained by replacing in q each doc(v)=lbl(v) with the definition of v. Example 9. Two views vR1BON and vR2BON are in Figure 3. Their extensions over dPER are, respectively, documents (dPER)vR1BON and (dPER)vR2BON each with two nodes: the root labeled, respectively, with doc(vR1BON) and doc(vR2BON), and with one child n8 labeled Rick in both cases. Let v be vR2BON without the node labeled Rick and with the output node person. Then (dPER)v has the root labeled doc(v) to which two subdocuments of dPER are connected: a subdocument rooted at n2 and one at n3.
Let d be a document, q a TP-query, V a set of TP-views, and Q 2 fTP; TP\g. In the deterministic setting the problem of query answering using views is to find an alternative query plan qr in Q, called a rewriting, that can be used to answer q. Formally, a Q-rewriting qr of q using V is a query qr 2 Q such that for every document d it holds that qr(DVd ) = q(d). Clearly, this implies that unfoldV (qr) q.
The two alternatives, TP-rewritings and TP\-rewritings, are respectively motivated by the two possible interpretations of XML query results. In an XML document, nodes have unique Ids used by internal operators (selections, unions, joins, etc.) to manipulate data during query evaluation. Queries can then either (i) output fresh Ids for the nodes of the result, or (ii) expose (preserve) in the result the original Ids from the document. The former case corresponds to what is called the copy semantics, under which the Ids of any document in DVd are disjoint from those of d and from those of any other document in DVd . Since one cannot know if nodes from results of different views are in fact copies of the same node in d, the only possible rewritings are those that access a single document from DVd and maybe navigate inside it. A rewriting qr 2 TP will thus be of the form doc(v)=lbl(v)[p1]=p2 or doc(v)=lbl(v)[p1]==p2, where v 2 V and the (possibly empty) TP-queries p1, p2 represent the compensation of v. In the latter case, every document in DVd preserves the original Ids, which will identify nodes across different documents in DVd . One can thus formulate and exploit more complex rewritings, as node Ids can be used to intersect (join by Id) results of different views over the same input data d. TP\-rewritings qr extend TP-rewritings in that they can access several DVd documents at once, by first navigating in individual documents and then intersecting the result. Thus the form of TP\-rewritings is Ti;j uij ; where each uij is a TP-rewriting. Probabilistic view-based rewriting. We generalize the definition of view extension to the probabilistic case: Pbv is a p-document rooted at a node labeled doc(v) whose contents is constructed as follows: (i) plug an unique ind-child below root(Pbv), (ii) for each pair ( ; ) in the set f(Pb0; p) j Pb0 Pb and (root(Pb0); p) 2 q(Pb)g, add as subtree of this ind-node with the probability . A set of p-documents DVPb for the set of views V and unfolding of a query over DVPb is defined as in the deterministic case. Example 10. Continuing with Example 9, extensions (PbPER)vR1BON (PbPER)vR2BON of the views over PbPER are p-documents with three nodes: the roots are labeled respectively doc(vR1BON) and doc(vR2BON), with one child labeled ind, that in turns has one child with the id n8 labeled Rick. The edge between the ind-node and its child is labeled 0:75 in both cases. The extension (PbPER)v has the root labeled v, with one child labeled ind, and two p-subdocuments of PbPER rooted under the ind node: one is the p-subdocument rooted at n2 and the other one rooted at n3. Probabilities on the edges to n2 and n3 are 1.
Query answering using views in the probabilistic setting is more involved than in the deterministic one, since q(Pb) is a set of node-probability pairs. Therefore, rewrite plans should deal with two sub-problems: (i) to find a query in terms of views, that retrieves the nodes N of q(Pb) (this corresponds to deterministic rewriting plans) and (ii) to compute the probabilities for the nodes in N , using probabilities from DVPb. Both sub-problems require algorithms accessing p-documents DVPb only. More formally: Definition 11. Let q be a TP query, V be a set of TP views and Q 2 fTP; TP\g. A probabilistic Q-rewriting Qr = (qr; fr) of q using V is a pair of (i) a deterministic Q-rewriting qr of q using V , and (ii) a probability function fr such that for every p-documents Pb and every node n of
Pb it holds that fr(n; DVPb) = Pr(n 2 q(P)).
When DVPb is clear from the context we will use fr(n) as short notation for fr(n; DVPb).
For given q and V , a probabilistic rewriting problem is to find Qr. The main challenge in solving this problem is to construct a probability function fr that, by definition, has access only to the p-documents in DVPb. In Sections 4 and 5 we respectively show that this is not always possible for TP and TP\-rewritings. 4
TP-rewrite Plans Here we discuss when probabilistic TP-rewrite plans do not exist and present cases for which they do exist and can be computed in polynomial time.
We first introduce some auxiliary notation. By dn we denote the subdocument of d rooted at n. We denote the p-subdocument of Pb rooted at a node n as Pbn. For TP queries q1 and q2, compensation of q1 with q2, denoted comp(q1; q2), is a TP-query obtained by deleting the first symbol from xpath(q2) and concatenating the rest to xpath(q1). For instance, the result of compensating q1 = a=b with q2 = b[c][d]=e is the concatenation of a=b and [c][d]=e, i.e., comp(q1; q2) = a=b[c][d]=e. Intuitively, view’s compensation brings further navigation over the view’s result Pbv, and a rewrite plan will be of the form qr = comp(doc(v)=lbl(v); qk) such that its unfolding comp(v; qk) is equivalent to q. Note that qr is over Pbv, its unfolding is over Pb while they yield the same result.
We remind the reader the main result for deterministic compensations [
P2 : a b mux 0.5 c Fact 12. Let q and V be TP-queries. Then there exists a deterministic TP-rewriting of q over V if and only if there is v 2 V and k 2 N such that comp(v; qk) q.
This criterion can be verified in polynomial time [
Pr(n 2 qr(Pv)) > 0: 4.1
Nonexistence of TP-rewrite Plans Is information in Pbv also sufficient to extract the probabilities Pr(n 2 q(P)) for nodes n 2 q(P)? It turns out that the answer is negative. There are q and v for which a deterministic rewriting qr exists but not the probabilistic one, i.e. the function fr such that for every Pb it holds that fr(n) = Pr(n 2 q(P)) does not exist. Thus the probabilistic rewriting problem crucially different from the deterministic one. We now present two example that will give insides on this phenomenon.
Example 14. Consider the query q = a=b[c] and the view v = a[:==c]=b. We now show that there is no probabilistic rewriting (qr; fr) for q over fvg. One can see that comp(v; q2) = a[:==c]=b[c] is equivalent to q, hence, qr = comp(doc(v)=lbl(v); q2). Consider now two p-documents Pb1 and Pb2 from Figure 4. Clearly, Pr(b 2 q(P1)) = 0:65 0:5 and Pr(b 2 q(P2)) = 0:5, and these probabilities are different. The function fr should compute the first probability 0:325 on a p-document (Pb1)v and 0:5 on (Pb2)v, hence fr should distinguish these p-documents. While one can see that these p-documents are indistinguishable by v: (Pb1)v = (Pb2)v. Hence, fr does not exist.
The problem raised in this example comes from the fact that in the unfolding of the rewriting a[:==c]==b[c] the predicate [:==c] coming from the view (i.e. located above the b-labeled node out(q)) and the predicate [c] coming from the compensation, (i.e. located below out(q)) may interact. Where the interaction is of the following kind: there is a document, e.g., d with the root a that has one child b, which in tern has one child c. that satisfies a[:==c]==b[c] but both c-nodes of the query should be mapped to the same c-node of d. In other words, the existence of a match for one predicate depends on the (non-)existence of a match of the other. We now introduce a condition of probabilistic independence that prevents such an interaction. This condition will be further used for both TP and TP\-rewritings.
TP-queries q1 and q2 are independent, denoted q1?q2, if for every Pb and n 2 Pb: Pr(n 2 (q1 \ q2)(P)) = [Pr(n 2 q1(P))
Pr(n 2 q2(P))]
Pr(n 2 P):
Clearly, the view a[:==c]==b and the compensation b[c] from Example 14 are probabilistically dependent. Deciding probabilistic dependency is tractable: Proposition 15. For TP-queries the independence q1?q2 is decidable in polynomial time.
Observe that probabilistic independence between a view and its compensation in a
deterministic rewriting does not guarantee existence of a probabilistic rewriting.
Example 16. Consider q = a==b[
Simple Queries and Restricted Compensations We now provide a class of queries and a class of compensated queries for which deciding existence of probability rewriting is based on probabilistic independence.
A query q is simple if either its main branch has =-edges only, or all the nodes in mbn(q) n out(q) reachable from (the first occurrence of) a ==-edge have no predicates. Clearly, a query is not simple if it is of the form : : : == : : : [: : : ] : : : . The compensation of a view v with c is restricted if either v is simple, or mb(c) has no ==-edges.
Let n0 be the highest ancestor-or-self node of n occurring in v(Pb) and let k = jmb(v)j. We show that under some conditions on qr and v, the probability Pr(n 2 q(P)) INPUT : TP query q and views V OUTPUT: Set of TP-rewritings R R := ;, Prefs := f(q1; vi) j vi 2 V; q1 is a lossless prefix of q; mb(q1) mb(vi); q1 v vig; for each (q1; vi) 2 Prefs do k := jmb(q1)j = jmb(vi)j if comp(vi; qk) q and restricted then vi0 := comp(mb(vi); vik)
// vi w/o predicates of nodes at rank 1; : : : ; k 1 vi00 := comp(cut(vi; k 1); mb(vi)k 1)
// vi w/o predicates of node at rank k q0 := comp(cut(mb(q); k); qk)
// q w/o predicates of nodes at rank 1; : : : ; k 1 if vi0 ? vi00 and vi00 ? q0 then R := R [ fcomp(doc(v)=lbl(v); qk)g Algorithm 1: TPrewrite for finding TP-rewritings qr for which fr are as in Eq. 1 that a node n occurs in q’s result is the probability Pr(n 2 qr(Pv)) that n can be found by qr in qr(Pbv), divided by the probability Pr(n0 2 vk(Pvn0 )) that n0 verifies the predicates of v found on its output node out(v). The following theorem is the main result of this section, where for k = jmbn(v)j the query v0 = comp(mb(v); vk) is v without all predicates of (main branch) nodes of rank in f1; : : : ; k 1g, the query v00 = comp(cut(v; k 1); mb(v)k 1) is v without all predicates of the node at rank k (i.e., the output node), and q0 = comp(cut(mb(q); k); qk) is q without all predicates of main branch nodes of rank in f1; : : : ; k 1g.
Theorem 17. Let v be a TP-view, q a TP-query, and k = jmb(v)j. Let qr be a restricted TP-rewriting of q over v. If v0 ? v00 and v00 ? q0 hold, then for every n 2 q(P) and its highest ancestor-or-self node n0 2 v(P):
Pr(n 2 q(P)) = Pr(n 2 qr(Pv))
Pr(n0 2 vk(Pvn0 )): (1)
We summarize this section with a polynomial time algorithm TPrewrite (see Algorithm 1), that takes an the input a TP query q and a set of views V and returns all possible TP-rewritings qr, for which the probability functions fr are as in Equation 1. In the algorithm we use so-called lossless prefixes: q1 is a lossless prefix of q, if q1 is a tree-pattern obtained from q by setting out(q1) as some node of mbn(q). 5
TP\-rewrite Plans
First we discuss how to decide equivalence between TP and TP\ queries and then
provide a restriction on views for which probability functions fr exist and tractable.
Since Q in TP\ is a rewriting for q in TP iff unfoldV (Q) q, deciding whether a TP
query q is equivalent to a TP\ query Q is crucial in our setting. It is known [
The equivalence problem was however shown in [
Computing Probability Function fr for Mutually Independent TP\ Views We start with the assumption that a deterministic rewriting qr has been found. Without loss of generality, let us assume that qr consists only of intersected views (no compensations of views). Let v1; : : : ; vk be the TP views of qr. Towards building the probability component of the rewrite plan, fr, we give some intuition first: for a given node n 2 q(P), since each view vi gives a probability, n 2 vi(P), and since we are interested in the probability of the intersection thereof, we might be tempted to try what is arguably the most intuitive definition for fr, the one which would simply combine by multiplication the probabilities Pr(n 2 vi(P)). But there are two issues with this straightforward fr candidate.
Regarding the first issue, a basic principle in probability theory is that the joint
probability of several events equals the product of the individual probabilities only when
these events are independent. For instance, for a given node n 2 P, are Pr(n 2 a[
Regarding the second issue, for each node n that appears in q(Pb) and, consequently, appears in each v1(Pb); : : : ; vk(Pb), we have k probability values Pr(n 2 vi(P)). Furthermore, each value Pr(n 2 vi(P)) can be seen as the product of two distinct terms: (i) the probability of n appearing in a possible world of Pb, denoted Pr(n 2 P), (ii) the probability of n being selected by vi in a possible world in which n is known to appear, denoted in the following Pr(n 2 vi(P) j n 2 nodes(P)).
Note that the first term is independent of any particular view as it only depends on the document itself We can thus write for each vi and each pair (n; pi) 2 vi(P) that pi = Pr(n 2 P)
Pr(n 2 vi(P) j n 2 nodes(P)): Given a deterministic rewriting qr of q formed by pairwise independent views v1; : : : ; vk, for a node n 2 q(P)), we would thus have as the overall product the following: Y Pr(n 2 vi(P)) = Pr(n 2 P)k i
Y Pr(n 2 vi(P) j n 2 nodes(P)): i Observe that in Equation 2 we account for the probability Pr(n 2 P) too many times, once for each view that participates in the rewrite plan. But we should instead account for it only once. Hence, by dividing Equation 2 with Pr(n 2 P)k 1, we obtain fr: fr(n) := Pr(n 2 P)
Y Pr(n 2 vi(P) j n 2 nodes(P)): i
Each independent view vi gives us Pr(n 2 vi(P) j n 2 nodes(P)), while there is now one missing ingredient in Equation 3: Pr(n 2 P). We can compute this value only if there is a view vi 2 V subsuming mb(q), i.e., mb(q) v vi. Summing up we conclude: Theorem 19. Let q be a TP-query, V a set of pairwise independent TP-views s.t. there is v 2 V satisfying mb(q) v v. Let qr be a TP\-rewriting of q over V . Then (qr; fr) with the fr as in Equation 3 is a probabilistic TP\-rewriting of q over V .
The next theorem shows that for ==-free q and V 0 it is hard to decide the existence of V V 0 of pairwise independent views (by reduction from k-dimensional perfect matching). Thus, deciding whether the result of Theorem 19 is applicable even for ==free TP queries and views is intractable. This also implies that for extended skeletons it is hard to find TP\-rewritings using the probability function as in Equation 3. Theorem 20. Let q and views V be both of TP and without ==-edges, deciding whether a TP\-rewriting of q using only pairwise independent views from V exists is NP-hard. (2) (3) 6
Conclusion
This is the first study on answering queries using views over probabilistic XML. The
main challenge of this problem is to find probability-retrieving functions that can access
only view results, while able to compute the probabilities of XML answers. So far
we studied two cases of TP and TP\-rewritings where these functions exist under the
assumption of probabilistic independence for queries and views. In the TP case, our
setting allows for polynomial time query answering in the size of both data and query.
In the TP\ case, our setting allows for polynomial time query answering in the size of
data, while it is intractable in the number of views. Recall that (direct) query answering
for probabilistic XML model considered here is also polynomial in data and intractable
in query complexity [
Acknowledgements. We are grateful to the anonymous reviewers for their comments. The second author is supported by the ERC FP7 grant Webdam (agreement n. 226513).