Processing Queries on Tree-Structured Data Efficiently

Summary: Survey of algorithms, complexity results, and techniques for efficient evaluation of node/tuple queries on trees (conjunctive queries, FO, Datalog, XPath). Organizes results by the core ideas yielding tractability and exposes previously unnoticed connections among approaches. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h3258382c74432942
Venue: PODS
Year: 2006
Pagerank: 6.7214366e-05
Overall Rank: 4,208 | 71.80%
DOI: 10.1145/1142351.1142382

Incoming Non-self Citations Over Time

Authors

1. Christoph Koch (Saarland University)

BibTeX Citation

@inproceedings{koch_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{Processing Queries on Tree-Structured Data Efficiently}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142382},
        doi = {10.1145/1142351.1142382},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Koch, Christoph},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,488	Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability	2014	PODS	8.3790632e-05
2,930	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	7.8287763e-05
12,314	The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries	2017	PODS	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
180	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026534482
248	Efficient Filtering of XML Documents for Selective Dissemination of Information	2000	VLDB	0.00023113032
391	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.0001918714
683	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00014781223
715	Archiving Scientific Data	2002	SIGMOD	0.00014558752
735	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00014329959
765	Stream Processing of XPath Queries with Predicates	2003	SIGMOD	0.00014108028
962	XPath Queries on Streaming Data	2003	SIGMOD	0.00012811834
1,339	Catching the Boat with Strudel: Experiences with a Web-Site Management System	1998	SIGMOD	0.0001096441
1,361	MARS: A System for Publishing XML from Mixed and Redundant Storage	2003	VLDB	0.00010889401
1,606	Conjunctive Queries over Trees	2004	PODS	0.00010079487
1,817	Validating Streaming XML Documents	2002	PODS	9.560097e-05
1,912	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.3690697e-05
2,113	XML Data Exchange: Consistency and Query Answering	2005	PODS	9.0162242e-05
2,238	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	8.7761804e-05
2,624	Visual Web Information Extraction with Lixto	2001	VLDB	8.1951041e-05
2,691	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	8.1124785e-05
2,756	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	8.0322898e-05
2,786	XQuery on SQL Hosts	2004	VLDB	7.9991918e-05
3,595	Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams	2004	VLDB	7.1627397e-05
3,755	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS	7.0291407e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,873	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
2	5,443	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD
3	7,793	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB
4	683	Efficient Algorithms for Processing XPath Queries	2002	VLDB
5	2,533	Path Queries on Compressed XML	2003	VLDB
6	3,252	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB
7	8,218	On Tree-Based Techniques for Query Evaluation	1992	PODS
8	4,659	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
9	2,691	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
10	1,606	Conjunctive Queries over Trees	2004	PODS