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: 1450
Venue: PODS
Year: 2008
Pagerank: 5.3766157e-05
Overall Rank: 8,761 | 39.90%
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,346	Running Tree Automata on Probabilistic XML	2009	PODS	6.257995e-05
6,917	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.7400564e-05
12,493	XML with Incomplete Information: Models, Properties, and Query Answering	2009	PODS	5.093636e-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
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
1,041	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012453494
2,515	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.4811795e-05
2,569	ProTDB: Probabilistic Data in XML	2002	VLDB	8.4090027e-05
3,075	Matching Twigs in Probabilistic XML	2007	VLDB	7.7839831e-05
3,318	On the Complexity of Managing Probabilistic XML Data	2007	PODS	7.5247776e-05
4,187	Maximally Joining Probabilistic Data	2007	PODS	6.8456588e-05
6,917	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.7400564e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
2	557	The Theory of Probabilistic Databases	1987	VLDB
3	3,075	Matching Twigs in Probabilistic XML	2007	VLDB
4	12,325	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB
5	5,346	Running Tree Automata on Probabilistic XML	2009	PODS
6	6,741	Probabilistic Databases for All	2020	PODS
7	6,508	Probabilistic XML via Markov Chains	2010	VLDB
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	2,569	ProTDB: Probabilistic Data in XML	2002	VLDB