Answering Queries using Views over Probabilistic XML: Complexity and Tractability

Summary: Probabilistic XML view-based rewriting; PTIME for large XPath fragments under two result semantics. Single-view compensation and multi-view compensation+intersection yield tractable rewritings, though probabilities may be non‑computable; PTIME under permissive conditions with deterministic rewritings. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10354
Venue: VLDB
Year: 2012
Pagerank: 4.1905499e-05
Overall Rank: 12,137 | 15.65%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Bogdan Cautis
2. Evgeny Kharlamov

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,662	An Efficient Index for RDF Query Containment	2019	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
149	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00041085859
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00021654356
718	Data Integration with Uncertainty	2007	VLDB	0.00017558942
761	MARS: A System for Publishing XML from Mixed and Redundant Storage	2003	VLDB	0.00016998994
1,269	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012911894
2,783	ProTDB: Probabilistic Data in XML	2002	VLDB	8.1268718e-05
2,980	A Framework for Using Materialized XPath Views in XML Query Processing	2004	VLDB	7.7800968e-05
3,592	On the Complexity of Managing Probabilistic XML Data	2007	PODS	6.9362111e-05
4,568	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.0725918e-05
5,621	Query Caching and View Selection for XML Databases	2005	VLDB	5.4061733e-05
6,221	Efficient Mining of XML Query Patterns for Caching	2003	VLDB	5.1446262e-05
6,300	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.1174095e-05
7,295	Structured Materialized Views for XML Queries	2007	VLDB	4.7658356e-05
7,625	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB	4.6888879e-05
9,507	ProApproX: A Lightweight Approximation Query Processor over Probabilistic Trees	2011	SIGMOD	4.3300131e-05
12,348	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,624	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.034764e-05
5,301	Running Tree Automata on Probabilistic XML	2009	PODS	5.5749031e-05
1,662	Conjunctive Queries over Trees	2004	PODS	0.00010966423
12,223	Certain Answers for XML Queries	2010	PODS	4.1905499e-05
2,981	Matching Twigs in Probabilistic XML	2007	VLDB	7.7783189e-05
12,348	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.1905499e-05
9,535	Answering Tree Pattern Queries Using Views	2006	VLDB	4.3226836e-05
6,682	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	4.9596732e-05
4,568	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.0725918e-05
3,592	On the Complexity of Managing Probabilistic XML Data	2007	PODS	6.9362111e-05