On Testing Satisfiability of Tree Pattern Queries

Summary: Systematically characterizes satisfiability of tree-pattern XPath queries under integrity constraints and schemas, giving polynomial-time algorithms and NP-completeness results. Experiments show near-negligible checking cost with substantial query-processing savings. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9400
Venue: VLDB
Year: 2004
Pagerank: 6.6417534e-05
Overall Rank: 4,537 | 68.88%
DOI: 10.1016/B978-012088469-8.50014-0

Incoming Non-self Citations Over Time

Authors

1. Laks V.S. Lakshmanan (University of British Columbia)
2. Ganesh Ramesh (University of British Columbia)
3. Hui (Wendy) Wang (University of British Columbia)
4. Zheng (Jessica) Zhao (University of British Columbia)

BibTeX Citation

@article{lakshmanan_vldb04,
        title = {{On Testing Satisfiability of Tree Pattern Queries}},
        author = {Lakshmanan, Laks V.S. and Ramesh, Ganesh and Wang, Hui (Wendy) and Zhao, Zheng (Jessica)},
        journal = {PVLDB},
        series = {{VLDB} '04},
        pages = {120},
        doi = {10.1016/B978-012088469-8.50014-0},
        url = {https://doi.org/10.1016/B978-012088469-8.50014-0},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.4878711e-05
2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS	9.255274e-05
3,976	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.9785468e-05
9,678	Deciding Well-Definedness of XQuery Fragments	2005	PODS	5.2373357e-05
9,811	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.214913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
137	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029877792
362	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00020125068
395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00019298983
1,068	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012326498
1,290	DTD Inference for Views of XML Data	2000	PODS	0.00011312135
2,132	The Complexity of XPath Query Evaluation	2003	PODS	9.119436e-05
2,662	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.2831426e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,622	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB
2	3,976	Rewriting XPath Queries Using Materialized Views	2005	VLDB
3	9,249	Decidable XPath Fragments in the Real World	2019	PODS
4	9,687	Answering Tree Pattern Queries Using Views	2006	VLDB
5	2,817	On the minimization of XPath queries	2003	VLDB
6	1,564	Conjunctive Queries over Trees	2004	PODS
7	12,534	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
8	8,440	On XPath with Transitive Axes and Data Tests	2013	PODS
9	1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS
10	3,167	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB