Conjunctive Queries over Trees

Summary: Charts the tractability frontier for conjunctive queries on unranked labeled trees with XPath-like axes, providing a framework and listing all maximal axis-sets that admit polynomial-time evaluation. Shows every CQ is equivalent to a union of acyclic CQs, but conversion can incur superpolynomial blowup. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1320
Venue: PODS
Year: 2004
Pagerank: 0.00010349456
Overall Rank: 1,564 | 89.28%
DOI: 10.1145/1055558.1055585

Incoming Non-self Citations Over Time

Authors

1. Georg Gottlob (Vienna University of Technology)
2. Christoph Koch (Vienna University of Technology)
3. Klaus U. Schulz (Ludwig Maximilian University of Munich)

BibTeX Citation

@inproceedings{gottlob_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Conjunctive Queries over Trees}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055585},
        doi = {10.1145/1055558.1055585},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gottlob, Georg and Koch, Christoph and Schulz, Klaus U.},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,131	The Lixto Data Extraction Project - Back and Forth between Theory and Practice	2004	PODS	0.00012044716
2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS	9.255274e-05
3,287	JSON: Data model, Query languages and Schema specification	2017	PODS	7.5587639e-05
3,711	The Expressivity of XPath with Transitive Closure*	2006	PODS	7.1778094e-05
3,976	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.9785468e-05
4,107	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	6.8973582e-05
4,504	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.6592957e-05
4,986	Querying Graph Patterns	2011	PODS	6.4120976e-05
6,137	XML Transformation by Tree-Walking Transducers with Invisible Pebbles	2007	PODS	5.9643797e-05
7,462	Incomplete Information and Certain Answers in General Data Models	2011	PODS	5.61159e-05
7,706	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	5.5638493e-05
8,417	XML Schema Mappings	2009	PODS	5.4288691e-05
10,044	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS	5.1703259e-05
12,030	Minimization of Tree Pattern Queries	2016	PODS	5.093636e-05
12,410	Certain Answers for XML Queries	2010	PODS	5.093636e-05
12,493	XML with Incomplete Information: Models, Properties, and Query Answering	2009	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
666	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00015166582
1,317	MARS: A System for Publishing XML from Mixed and Redundant Storage	2003	VLDB	0.00011179293
2,180	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	9.0110009e-05
2,564	Visual Web Information Extraction with Lixto	2001	VLDB	8.4118854e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
2	3,167	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB
3	8,440	On XPath with Transitive Axes and Data Tests	2013	PODS
4	13,954	On the Power of Walking for Querying Tree-Structured Data	2002	PODS
5	2,625	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
6	6,442	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS
7	2,817	On the minimization of XPath queries	2003	VLDB
8	4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
9	12,534	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
10	4,107	Processing Queries on Tree-Structured Data Efficiently	2006	PODS