Running Tree Automata on Probabilistic XML

Summary: Identify a tractable case for evaluating deterministic bottom-up unranked tree automata on probabilistic XML (distributional-node model): an efficient algorithm when transitions are given by deterministic string automata, enabling sampling and MSO query evaluation under schema conformance. Also analyze complexity of attributes, keys/foreign-keys and extend the model to repeated-sampling nodes that further blow up the possible-world space. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1494
Venue: PODS
Year: 2009
Pagerank: 6.257995e-05
Overall Rank: 5,346 | 63.33%
DOI: 10.1145/1559795.1559831

Incoming Non-self Citations Over Time

Authors

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

BibTeX Citation

@inproceedings{cohen_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Running Tree Automata on Probabilistic XML}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559831},
        doi = {10.1145/1559795.1559831},
        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 = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,508	Probabilistic XML via Markov Chains	2010	VLDB	5.8576101e-05
7,640	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS	5.5766474e-05
7,706	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	5.5638493e-05
12,408	Transducing Markov Sequences	2010	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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
644	The Complexity of Query Reliability	1998	PODS	0.00015367965
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
2,969	Expressive and efficient pattern languages for tree-structured data (extended abstract)	2000	PODS	7.9147299e-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,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.8810237e-05
6,917	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.7400564e-05
8,761	Incorporating Constraints in Probabilistic XML	2008	PODS	5.3766157e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,075	Matching Twigs in Probabilistic XML	2007	VLDB
2	4,071	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS
3	13,875	Trees, Automata and XML (Invited Tutorial)	2004	PODS
4	12,410	Certain Answers for XML Queries	2010	PODS
5	12,325	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB
6	6,917	Query Efficiency in Probabilistic XML Models	2008	SIGMOD
7	2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
8	2,625	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
9	6,508	Probabilistic XML via Markov Chains	2010	VLDB
10	3,318	On the Complexity of Managing Probabilistic XML Data	2007	PODS