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: hce9a8b187d8e9e61
Venue: VLDB
Year: 2004
Pagerank: 6.4931113e-05
Overall Rank: 4,636 | 68.84%
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,976	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.2797174e-05
2,100	XML Data Exchange: Consistency and Query Answering	2005	PODS	9.050183e-05
4,066	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.8221983e-05
9,851	Deciding Well-Definedness of XQuery Fragments	2005	PODS	5.1198285e-05
9,980	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.1013913e-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
141	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029294114
374	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00019707844
409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00018868173
1,096	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012050482
1,315	DTD Inference for Views of XML Data	2000	PODS	0.00011058412
2,177	The Complexity of XPath Query Evaluation	2003	PODS	8.9153711e-05
2,716	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.1006747e-05

Semantically Similar Papers

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