DBScholar

Back to papers

Answering Queries using Views over Probabilistic XML: Complexity and Tractability

Summary: Characterizes when XPath queries over probabilistic XML can be answered from views, distinguishing persistent identifiers and identifier-free semantics. Gives PTime criteria and algorithms for compensation/intersection rewritings, exposing cases where answers are retrievable but probabilities are not computable. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h13ef3fbfa854f690
Venue
VLDB
Year
2012
Pagerank
4.9793485e-05
Overall Rank
12,616 | 15.18%
DOI
10.14778/2350229.2350241

Incoming Non-self Citations Over Time

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

Authors

BibTeX Citation

@article{cautis_vldb12,
        title = {{Answering Queries using Views over Probabilistic XML: Complexity and Tractability}},
        author = {Cautis, Bogdan and Kharlamov, Evgeny},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {11},
        pages = {1148--1159},
        doi = {10.14778/2350229.2350241},
        url = {https://doi.org/10.14778/2350229.2350241},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank Citing Paper Year Venue Pagerank
12,152 An Efficient Index for RDF Query Containment 2019 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

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
126 Trio: A System for Integrated Management of Data, Accuracy, and Lineage 2005 CIDR 0.00030439683
409 Containment and Equivalence for an XPath Fragment [Extended Abstract] 2002 PODS 0.00018868173
715 Data Integration with Uncertainty 2007 VLDB 0.00014559092
1,065 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.0001219981
1,353 MARS: A System for Publishing XML from Mixed and Redundant Storage 2003 VLDB 0.00010930523
2,617 ProTDB: Probabilistic Data in XML 2002 VLDB 8.2219007e-05
2,715 A Framework for Using Materialized XPath Views in XML Query Processing 2004 VLDB 8.1017908e-05
3,378 On the Complexity of Managing Probabilistic XML Data 2007 PODS 7.3569859e-05
4,066 Rewriting XPath Queries Using Materialized Views 2005 VLDB 6.8221983e-05
5,355 Query Caching and View Selection for XML Databases 2005 VLDB 6.1625215e-05
5,971 Efficient Mining of XML Query Patterns for Caching 2003 VLDB 5.9316289e-05
6,059 Rewriting Nested XML Queries Using Nested Views 2006 SIGMOD 5.9001613e-05
7,418 Structured Materialized Views for XML Queries 2007 VLDB 5.5327659e-05
7,863 Optimizing Probabilistic Query Processing on Continuous Uncertain Data 2011 VLDB 5.4367962e-05
9,817 ProApproX: A Lightweight Approximation Query Processor over Probabilistic Trees 2011 SIGMOD 5.1257999e-05
12,824 Efficient Rewriting of XPath Queries Using Query Set Specifications 2009 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,636 On Testing Satisfiability of Tree Pattern Queries 2004 VLDB
2 5,474 Running Tree Automata on Probabilistic XML 2009 PODS
3 1,599 Conjunctive Queries over Trees 2004 PODS
4 12,701 Certain Answers for XML Queries 2010 PODS
5 3,132 Matching Twigs in Probabilistic XML 2007 VLDB
6 12,824 Efficient Rewriting of XPath Queries Using Query Set Specifications 2009 VLDB
7 9,862 Answering Tree Pattern Queries Using Views 2006 VLDB
8 7,057 Query Efficiency in Probabilistic XML Models 2008 SIGMOD
9 4,066 Rewriting XPath Queries Using Materialized Views 2005 VLDB
10 3,378 On the Complexity of Managing Probabilistic XML Data 2007 PODS