Probabilistic XML via Markov Chains

Summary: Recursive Markov Chains define probabilistic XML distributions, unifying and extending prior probabilistic models. RMCs offer exponential succinctness, unbounded probability domains, and tractable fragments that subsume probabilistic DTDs and map expressiveness between formalisms. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10315
Venue: VLDB
Year: 2010
Pagerank: 5.8576101e-05
Overall Rank: 6,508 | 55.36%
DOI: 10.14778/1920841.1920939

Incoming Non-self Citations Over Time

Authors

1. Michael Benedikt (University of Oxford)
2. Evgeny Kharlamov (Free University of Bolzano; INRIA)
3. Dan Olteanu (University of Oxford)
4. Pierre Senellart (Institut Mines-Telecom; National Centre for Scientific Research; Télécom Paris)

BibTeX Citation

@article{benedikt_vldb10,
        title = {{Probabilistic XML via Markov Chains}},
        author = {Benedikt, Michael and Kharlamov, Evgeny and Olteanu, Dan and Senellart, Pierre},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {770--783},
        doi = {10.14778/1920841.1920939},
        url = {https://doi.org/10.14778/1920841.1920939},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,511	A Quest for Beauty and Wealth (or, Business Processes for Database Researchers)	2011	PODS	6.1915384e-05
6,170	Probabilistic Databases with an Infinite Open-World Assumption	2019	PODS	5.9514805e-05
8,259	Tuple-Independent Representations of Infinite Probabilistic Databases	2021	PODS	5.4574671e-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
644	The Complexity of Query Reliability	1998	PODS	0.00015367965
2,180	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	9.0110009e-05
3,050	Event Queries on Correlated Probabilistic Streams	2008	SIGMOD	7.8140428e-05
3,075	Matching Twigs in Probabilistic XML	2007	VLDB	7.7839831e-05
5,346	Running Tree Automata on Probabilistic XML	2009	PODS	6.257995e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,274	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS
2	12,625	The Complexity of Reasoning about Pattern-based XML Schemas	2007	PODS
3	3,590	On Probabilistic Fixpoint and Markov Chain Query Languages	2010	PODS
4	2,569	ProTDB: Probabilistic Data in XML	2002	VLDB
5	12,325	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB
6	3,075	Matching Twigs in Probabilistic XML	2007	VLDB
7	8,761	Incorporating Constraints in Probabilistic XML	2008	PODS
8	6,917	Query Efficiency in Probabilistic XML Models	2008	SIGMOD
9	3,318	On the Complexity of Managing Probabilistic XML Data	2007	PODS
10	5,346	Running Tree Automata on Probabilistic XML	2009	PODS