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: 10353
Venue: VLDB
Year: 2012
Pagerank: 4.1945683e-05
Overall Rank: 12,129 | 15.63%
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,657	An Efficient Index for RDF Query Containment	2019	SIGMOD	4.1945683e-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.00041101118
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.000216753
721	Data Integration with Uncertainty	2007	VLDB	0.00017570539
766	MARS: A System for Publishing XML from Mixed and Redundant Storage	2003	VLDB	0.00017014604
1,268	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012931993
2,774	ProTDB: Probabilistic Data in XML	2002	VLDB	8.134432e-05
2,977	A Framework for Using Materialized XPath Views in XML Query Processing	2004	VLDB	7.7876083e-05
3,589	On the Complexity of Managing Probabilistic XML Data	2007	PODS	6.9427709e-05
4,568	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.0784118e-05
5,611	Query Caching and View Selection for XML Databases	2005	VLDB	5.4113701e-05
6,224	Efficient Mining of XML Query Patterns for Caching	2003	VLDB	5.1495715e-05
6,300	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.1223169e-05
7,298	Structured Materialized Views for XML Queries	2007	VLDB	4.770411e-05
7,623	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB	4.6933659e-05
9,506	ProApproX: A Lightweight Approximation Query Processor over Probabilistic Trees	2011	SIGMOD	4.3341665e-05
12,340	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,625	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.0406081e-05
5,296	Running Tree Automata on Probabilistic XML	2009	PODS	5.5802694e-05
1,663	Conjunctive Queries over Trees	2004	PODS	0.00010977096
12,215	Certain Answers for XML Queries	2010	PODS	4.1945683e-05
2,978	Matching Twigs in Probabilistic XML	2007	VLDB	7.7845728e-05
12,340	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.1945683e-05
9,534	Answering Tree Pattern Queries Using Views	2006	VLDB	4.3268303e-05
6,681	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	4.9643102e-05
4,568	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.0784118e-05
3,589	On the Complexity of Managing Probabilistic XML Data	2007	PODS	6.9427709e-05