We consider the possibility problem of determining if a document is a possible world of a probabilistic document, in the setting of probabilistic XML. This basic question is a special case of query answering or tree automata evaluation, but it has specific practical uses, such as checking whether an userprovided probabilistic document outcome is possible or sufficiently likely. In this paper, we study the complexity of the possibility problem for probabilistic XML models of varying expressiveness. We show that the decision problem is often tractable in the absence of long-distance dependencies, but that its computation variant is intractable on unordered documents. We also introduce an explicit matches variant to generalize practical situations where node labels are unambiguous; this ensures tractability of the possibility problem, even under long-distance dependencies, provided event conjunctions are disallowed. Our results entirely classify the tractability boundary over all considered problem variants.
1 Translations between the probabilistic relational and XML models [
As a second practical example, assume that a user is editing a probabilistic XML document D. The user notices that choosing a certain valuation of the probabilistic events yields a certain deterministic document W , and asks whether the same document could have been obtained by making different choices. Indeed, maybe W is considered improbable under D following this particular valuation, but is likely overall because the same document can be obtained through different choices. What is the probability, over all valuations, of the user’s chosen outcome W according to D?
On the face of it, POSS seems related to query evaluation: we wish to evaluate on D
a query qW which is, informally, “is the input document exactly W ”? However, there are
three reasons why query evaluation cannot give good complexity bounds for POSS. First,
because qW depends on the possibly large W , we are not performing query answering
for a fixed query, so we can only use the unfavorable combined complexity bounds where
both the input document D and the query qW are part of the input. Second, because we
want to obtain exactly W , the match of qW should never map two query variables to
the same node of D, so the query language must allow inequalities on node identifiers.
Third, once again because we require an exact match, we need to assert the absence of
the nodes which are not in W , so we need negation in the language. To our knowledge,
then, the only upper bound for POSS from query answering is the combined complexity
bound for the (expressive) monadic second-order logic over trees whose evaluation on
deterministic (not even probabilistic) XML trees is already PSPACE-hard [
A second related approach is that of tree automata on probabilistic XML documents.
Indeed, we can encode the possible world W to a deterministic tree automaton AW and
compute the probability that AW accepts the probabilistic document D. The decision and
computation variants of POSS under local uncertainty models are thus special cases of
the “relevancy” and “p-acceptance” problems of [
This paper specifically focuses on the POSS problem to study the precise complexity
of its different formulations. Our probabilistic XML representation is the PrXML model
of [
We start by defining the required preliminaries in Section 2 and the different variants
of POSS in Section 3, establishing its overall NP-completeness and reviewing the results
of [
We start by formally defining XML documents and probability distributions over them:
label from a set L of labels. Ordered XML documents are defined in the same way but with ordered trees, that is, there is a total order over the children of every node.
finite set supp(P) to a rational number P(x), its probability according to P, with the condition that åD2supp(P) P(D) = 1. For any x 2= supp(P) we write P(x) = 0.
As it is unwieldy to manipulate explicit probability distributions over large sets
of documents, we use the language of probabilistic XML [
The semantics of a PrXML document D is the probability distribution over XML
documents defined by the following sampling process (see [
an outcome is the product of the probabilities at each step. Whenever an edge is removed, all of the descendant nodes and edges are removed. The probability of a document W according to D, written D(W ), is the total probability of all outcomes4 leading to W .
Of course, the expressiveness and compactness of PrXML frameworks depend
on which probabilistic nodes are allowed: we say that PrXMLC is more general than
PrXMLD if there is a polynomial time algorithm to rewrite any PrXMLD document
to a PrXMLC document representing the same probability distribution. Fig. 1 (adapted
from [
mie ind; det mux; ind mux; det
e cie ind
mux 0/
Complexity > #PPOOSSSS >> ee FNPP#P ((PPrroopp.. 11)) < 6< #POSS < mux; ind; det PTIME (Thm. 1) #POSS 6< ind or mux #P-hard (Thm. 2) ? POSS > ind or mux PTIME (Thm. 3) #POSS
POSS 6< 2 of mux; ind; det NP-hard (Thm. 4) #EPOSS > mux; ind; det PTIME (Thm. 5) POSS #EPOSS EPOSS ? cie NP-hard (Thm. 6)
POSS ? mie NP-hard (Thm. 7) EPOSS #EPOSS > mie PTIME (Thm. 8)
POSS6C< is to determine, given as input an unordered PrXMLC document D and an unordered XML document W , whether W is a possible world of D, namely, D(W ) > 0.
The possibility problem for ordered documents POSSC< is the same problem except that both D and W are ordered. For o 2 f6<; <g, the #POSSoC problem is the counting variant of POSSoC, whose output is D(W ).
For brevity, we write POSSC? and POSSC> when describing lower or upper complexity bounds that apply to both POSSC< and POSS6C<.
We start by giving straightforward bounds on the most general problem variants: Prop. 1. POSS>e is in NP and #POSS>e is in FP#P.
Prop. 2. POSSc?ie is NP-complete, even when D has height 3.
Local models on ordered documents are known to be tractable using tree automata:
Theorem 1 ([
We now complete the picture for the local model PrXMLmux;ind;det on unordered
documents. The results of [
6 6
By contrast, the decision variant is tractable for PrXMLind and PrXMLmux, using a dynamic algorithm. However, allowing both ind and mux, or allowing det nodes, leads to intractability (by reductions from set cover and Boolean satisfiability). Theorem 3. POSSi>nd and POSS>mux can be decided in PTIME.
Theorem 4. POSSi<nd;det, POSS<mux;det and POSS<mux;ind are NP-complete, even when D has height 4. 6 6 6
We now attempt to understand how the overall hardness of POSS is caused by the difficulty of finding how the possible world W can be matched to D.
of W to the regular nodes of D such that, if r is the root of W then f (r) is the root of D, and if n is a child of n0 in W then there is a descending path from f (n) to f (n0) going only through probabilistic nodes.
Intuitively, candidate matches are possible ways to generate W from D, ignoring probabilistic annotations, assuming we can keep exactly the regular nodes of D that are in the image of f . There are exponentially many candidate matches in general, so it is natural to ask whether POSS is tractable if all matches are explicitly provided as input:
explicit matches EPOSSoC is the same as the POSSoC problem except that the set of the candidate matches of W in D is provided as input (in addition to D and W ).
The explicit matches variant generalizes many practical cases where all possible matches can be computed in polynomial time; for instance, when node labels are assumed to be unique, or unambiguous in the sense that no two sibling nodes carry the same label.
We first note that explicit matches ensure tractability of all local dependency models,
by reduction to deterministic tree automata [
For long-distance dependencies, however, it is easily seen that POSS is still hard with conjunction of events, even if explicit matches are provided: Theorem 6. EPOSSc?ie is NP-complete, even when D has height 3.
This being said, it turns out that the hardness is really caused by event conjunctions. To see this, we introduce the PrXMLmie class, which allows only individual events: Definition 7. The PrXMLmie class features multivalued independent events taking their values from a finite set V (beyond t and f, with probabilities summing to 1), and probabilistic mie nodes whose child edges are annotated by a single event e and a value x 2 V .
Note that mie hierarchies are forbidden (because they can straightforwardly encode conjunctions), so that PrXMLmie does not capture ind hierarchies. However, as we introduced it with multivalued (not just Boolean) events, it captures PrXMLmux: Prop. 3. We can rewrite PrXMLmux to PrXMLmie and PrXMLmie to PrXMLcie in PTIME.
In the PrXMLmie class, the POSS problem is still NP-hard, by reduction to exact cover; however, with explicit matches, the #POSS problem is tractable, both in the ordered and unordered setting, despite the long-distance dependencies. Intuitively, the candidate matches are mutually exclusive, and each match’s probability can be computed as that of a conjunction of equalities and inequalities on the events at the frontier. Theorem 7. POSS?mie is NP-complete, even when D has height 3 and events are Boolean. Theorem 8. #EPOSS>mie can be solved in polynomial time.
We have characterized the complexity of the counting and decision variants of POSS for unordered or ordered XML documents, and various PrXML classes. With explicit matches, #POSS is tractable unless event conjunctions are allowed. Without explicit matches, POSS is hard unless dependencies are local; in this case, if the documents are ordered, #POSS is tractable, otherwise #POSS is hard and POSS is tractable only with ind or mux nodes (and hard if both types, or det nodes, are allowed). Our results are summarized in Table 1 on page 4.
Further work could study more precisely the effect of det nodes and ind hierarchies,
for instance by attempting to extend the PrXMLmie class to capture them, or try to
understand whether there is a connection between the algorithms of [
Acknowledgements. The author thanks Pierre Senellart for careful proofreading, useful suggestions, and insightful feedback, the anonymous referees for their valuable comments, and M. Lamine Ba and Tang Ruiming for helpful early discussion. This work has been partly funded by the French government under the X-Data project.