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: 1321
Venue: PODS
Year: 2004
Pagerank: 0.00010977096
Overall Rank: 1,663 | 88.44%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,095	The Lixto Data Extraction Project - Back and Forth between Theory and Practice	2004	PODS	0.00014126427
2,211	XML Data Exchange: Consistency and Query Answering	2005	PODS	9.2771941e-05
2,781	JSON: Data model, Query languages and Schema specification	2017	PODS	8.1305074e-05
3,117	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	7.5407318e-05
3,851	The Expressivity of XPath with Transitive Closure*	2006	PODS	6.7057867e-05
4,366	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.2538592e-05
4,568	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.0784118e-05
4,946	Querying Graph Patterns	2011	PODS	5.8149362e-05
5,716	XML Transformation by Tree-Walking Transducers with Invisible Pebbles	2007	PODS	5.3561157e-05
7,393	Incomplete Information and Certain Answers in General Data Models	2011	PODS	4.7428879e-05
7,601	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.698961e-05
8,190	XML Schema Mappings	2009	PODS	4.5641911e-05
9,890	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS	4.2617199e-05
11,827	Minimization of Tree Pattern Queries	2016	PODS	4.1945683e-05
12,215	Certain Answers for XML Queries	2010	PODS	4.1945683e-05
12,298	XML with Incomplete Information: Models, Properties, and Query Answering	2009	PODS	4.1945683e-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
713	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00017731096
766	MARS: A System for Publishing XML from Mixed and Redundant Storage	2003	VLDB	0.00017014604
1,370	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	0.00012338027
2,698	Visual Web Information Extraction with Lixto*	2001	VLDB	8.2753317e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,610	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB	6.9196208e-05
1,848	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010330772
8,200	On XPath with Transitive Axes and Data Tests	2013	PODS	4.5602267e-05
13,753	On the Power of Walking for Querying Tree-Structured Data	2002	PODS	-
2,855	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	8.0059865e-05
6,150	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.1846373e-05
3,084	On the minimization of Xpath queries	2003	VLDB	7.6011919e-05
4,625	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.0406081e-05
12,340	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.1945683e-05
3,117	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	7.5407318e-05