On the minimization of XPath queries

Summary: Extends XPath minimization to include wildcards, proving the problem NP-hard. Provides an algorithm for minimum equivalent queries and identifies a tractable fragment admitting polynomial-time minimization. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9162
Venue: VLDB
Year: 2003
Pagerank: 8.0945626e-05
Overall Rank: 2,817 | 80.68%
DOI: 10.1016/B978-012722442-8/50022-7

Incoming Non-self Citations Over Time

Authors

1. S. Flesca (University of Calabria)
2. F. Furfaro (University of Calabria)
3. E. Masciari (National Research Council of Italy)

BibTeX Citation

@article{flesca_vldb03,
        title = {{On the minimization of XPath queries}},
        author = {Flesca, S. and Furfaro, F. and Masciari, E.},
        journal = {PVLDB},
        series = {{VLDB} '03},
        doi = {10.1016/B978-012722442-8/50022-7},
        url = {https://doi.org/10.1016/B978-012722442-8/50022-7},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,268	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.8370676e-05
2,616	FleXPath: Flexible Structure and Full-Text Querying for XML	2004	SIGMOD	8.339188e-05
3,976	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.9785468e-05
5,237	Query Caching and View Selection for XML Databases	2005	VLDB	6.3037813e-05
5,936	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	6.0353909e-05
6,005	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	6.0119945e-05
6,917	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.7400564e-05
9,687	Answering Tree Pattern Queries Using Views	2006	VLDB	5.2351299e-05
12,030	Minimization of Tree Pattern Queries	2016	PODS	5.093636e-05
12,799	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019546431
395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00019298983
666	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00015166582
686	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014948634
1,068	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012326498
1,777	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.7849758e-05
2,680	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.267202e-05
3,801	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	7.1130194e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,659	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
2	1,564	Conjunctive Queries over Trees	2004	PODS
3	4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
4	1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS
5	12,476	XPath Whole Query Optimization	2010	VLDB
6	2,132	The Complexity of XPath Query Evaluation	2003	PODS
7	666	Efficient Algorithms for Processing XPath Queries	2002	VLDB
8	12,534	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
9	3,976	Rewriting XPath Queries Using Materialized Views	2005	VLDB
10	12,798	Taming XPath Queries by Minimizing Wildcard Steps	2004	VLDB