Incorporating Constraints in Probabilistic XML

Summary: Introduce PXDB: the probability subspace of p-document instances satisfying constraints, with tractable query evaluation, sampling, and well-definedness. Supports aggregates (count,max,min,ratio) and probabilistic constraints, yielding expressive yet tractable probabilistic XML. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h00f97a5b7720b61c
Venue: PODS
Year: 2008
Pagerank: 5.2559789e-05
Overall Rank: 8,923 | 40.01%
DOI: 10.1145/1376916.1376933

Incoming Non-self Citations Over Time

Authors

1. Sara Cohen (Hebrew University)
2. Benny Kimelfeld (Hebrew University)
3. Yehoshua Sagiv (Hebrew University)

BibTeX Citation

@inproceedings{cohen_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{Incorporating Constraints in Probabilistic XML}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376933},
        doi = {10.1145/1376916.1376933},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cohen, Sara and Kimelfeld, Benny and Sagiv, Yehoshua},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,474	Running Tree Automata on Probabilistic XML	2009	PODS	6.1176063e-05
7,057	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.6113229e-05
12,783	XML with Incomplete Information: Models, Properties, and Query Answering	2009	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
178	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026628894
1,065	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.0001219981
2,565	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.2910005e-05
2,617	ProTDB: Probabilistic Data in XML	2002	VLDB	8.2219007e-05
3,132	Matching Twigs in Probabilistic XML	2007	VLDB	7.6137556e-05
3,378	On the Complexity of Managing Probabilistic XML Data	2007	PODS	7.3569859e-05
4,262	Maximally Joining Probabilistic Data	2007	PODS	6.6984258e-05
7,057	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.6113229e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,213	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
2	571	The Theory of Probabilistic Databases	1987	VLDB
3	3,132	Matching Twigs in Probabilistic XML	2007	VLDB
4	12,616	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB
5	5,474	Running Tree Automata on Probabilistic XML	2009	PODS
6	6,839	Probabilistic Databases for All	2020	PODS
7	6,637	Probabilistic XML via Markov Chains	2010	VLDB
8	7,057	Query Efficiency in Probabilistic XML Models	2008	SIGMOD
9	3,378	On the Complexity of Managing Probabilistic XML Data	2007	PODS
10	2,617	ProTDB: Probabilistic Data in XML	2002	VLDB