On the Complexity of Managing Probabilistic XML Data
Summary: Complexity analysis of probabilistic XML (unordered labeled trees with node conjunctions of probabilistic events), identifying a large tractable class where simple query/update algorithms succeed. Decision procedure for tree equivalence in co-RP; pruning low-probability worlds and DTD validation intractable. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 9 of 9 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,978 | Matching Twigs in Probabilistic XML | 2007 | VLDB | 7.7845728e-05 |
| 4,958 | Efficient Subgraph Search over Large Uncertain Graphs | 2011 | VLDB | 5.8031038e-05 |
| 5,270 | Annotated XML: Queries and Provenance | 2008 | PODS | 5.5963545e-05 |
| 5,296 | Running Tree Automata on Probabilistic XML | 2009 | PODS | 5.5802694e-05 |
| 6,681 | Query Efficiency in Probabilistic XML Models | 2008 | SIGMOD | 4.9643102e-05 |
| 8,558 | Incorporating Constraints in Probabilistic XML | 2008 | PODS | 4.4937074e-05 |
| 9,506 | ProApproX: A Lightweight Approximation Query Processor over Probabilistic Trees | 2011 | SIGMOD | 4.3341665e-05 |
| 12,129 | Answering Queries using Views over Probabilistic XML: Complexity and Tractability | 2012 | VLDB | 4.1945683e-05 |
| 12,298 | XML with Incomplete Information: Models, Properties, and Query Answering | 2009 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 74 | Efficient Query Evaluation on Probabilistic Databases | 2004 | VLDB | 0.00057857292 |
| 149 | Trio: A System for Integrated Management of Data, Accuracy, and Lineage | 2005 | CIDR | 0.00041101118 |
| 450 | The Theory Of Probabilistic Databases | 1987 | VLDB | 0.00022822073 |
| 841 | The reliability of queries (Extended Abstract) | 1995 | PODS | 0.00016050985 |
| 2,774 | ProTDB: Probabilistic Data in XML | 2002 | VLDB | 8.134432e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 12,215 | Certain Answers for XML Queries | 2010 | PODS | 4.1945683e-05 |
| 1,848 | Typing and Querying XML Documents: Some Complexity Bounds | 2003 | PODS | 0.00010330772 |
| 1,663 | Conjunctive Queries over Trees | 2004 | PODS | 0.00010977096 |
| 7,601 | Conjunctive Queries on Probabilistic Graphs: Combined Complexity | 2017 | PODS | 4.698961e-05 |
| 6,284 | Probabilistic XML via Markov Chains | 2010 | VLDB | 5.128131e-05 |
| 2,774 | ProTDB: Probabilistic Data in XML | 2002 | VLDB | 8.134432e-05 |
| 6,681 | Query Efficiency in Probabilistic XML Models | 2008 | SIGMOD | 4.9643102e-05 |
| 2,978 | Matching Twigs in Probabilistic XML | 2007 | VLDB | 7.7845728e-05 |
| 12,129 | Answering Queries using Views over Probabilistic XML: Complexity and Tractability | 2012 | VLDB | 4.1945683e-05 |
| 5,296 | Running Tree Automata on Probabilistic XML | 2009 | PODS | 5.5802694e-05 |