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.2534908e-05
Overall Rank: 8,931 | 39.98%
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,478	Running Tree Automata on Probabilistic XML	2009	PODS	6.1147103e-05
7,060	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.6086666e-05
12,789	XML with Incomplete Information: Models, Properties, and Query Answering	2009	PODS	4.9769913e-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.00042926566
179	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026617591
1,066	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012194105
2,565	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.2870757e-05
2,619	ProTDB: Probabilistic Data in XML	2002	VLDB	8.2180287e-05
3,133	Matching Twigs in Probabilistic XML	2007	VLDB	7.6103114e-05
3,379	On the Complexity of Managing Probabilistic XML Data	2007	PODS	7.3535108e-05
4,262	Maximally Joining Probabilistic Data	2007	PODS	6.6954238e-05
7,060	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.6086666e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,215	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
2	571	The Theory of Probabilistic Databases	1987	VLDB
3	3,133	Matching Twigs in Probabilistic XML	2007	VLDB
4	12,622	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB
5	5,478	Running Tree Automata on Probabilistic XML	2009	PODS
6	6,843	Probabilistic Databases for All	2020	PODS
7	6,641	Probabilistic XML via Markov Chains	2010	VLDB
8	7,060	Query Efficiency in Probabilistic XML Models	2008	SIGMOD
9	3,379	On the Complexity of Managing Probabilistic XML Data	2007	PODS
10	2,619	ProTDB: Probabilistic Data in XML	2002	VLDB