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)

Paper ID: h531583b84715d4a5
Venue: PODS
Year: 2007
Pagerank: 7.3569859e-05
Overall Rank: 3,378 | 77.29%
DOI: 10.1145/1265530.1265570

Incoming Non-self Citations Over Time

Authors

1. Pierre Senellart (INRIA; Paris-Sud University)
2. Serge Abiteboul (INRIA; Paris-Sud University)

BibTeX Citation

@inproceedings{senellart_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{On the Complexity of Managing Probabilistic XML Data}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265570},
        doi = {10.1145/1265530.1265570},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Senellart, Pierre and Abiteboul, Serge},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,132	Matching Twigs in Probabilistic XML	2007	VLDB	7.6137556e-05
4,969	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	6.3332415e-05
5,474	Running Tree Automata on Probabilistic XML	2009	PODS	6.1176063e-05
5,611	Annotated XML: Queries and Provenance	2008	PODS	6.0684862e-05
7,057	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.6113229e-05
8,923	Incorporating Constraints in Probabilistic XML	2008	PODS	5.2559789e-05
9,817	ProApproX: A Lightweight Approximation Query Processor over Probabilistic Trees	2011	SIGMOD	5.1257999e-05
12,616	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB	4.9793485e-05
12,783	XML with Incomplete Information: Models, Properties, and Query Answering	2009	PODS	4.9793485e-05

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
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042936299
126	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00030439683
571	The Theory of Probabilistic Databases	1987	VLDB	0.00016210743
2,130	The reliability of queries (Extended Abstract)	1995	PODS	8.9957534e-05
2,617	ProTDB: Probabilistic Data in XML	2002	VLDB	8.2219007e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,701	Certain Answers for XML Queries	2010	PODS
2	2,934	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
3	1,599	Conjunctive Queries over Trees	2004	PODS
4	6,637	Probabilistic XML via Markov Chains	2010	VLDB
5	7,858	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS
6	2,617	ProTDB: Probabilistic Data in XML	2002	VLDB
7	7,057	Query Efficiency in Probabilistic XML Models	2008	SIGMOD
8	3,132	Matching Twigs in Probabilistic XML	2007	VLDB
9	12,616	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB
10	5,474	Running Tree Automata on Probabilistic XML	2009	PODS