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: h9b4fc56505104ca4
Venue: VLDB
Year: 2003
Pagerank: 7.9134117e-05
Overall Rank: 2,881 | 80.64%
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,321	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.6413639e-05
2,666	FleXPath: Flexible Structure and Full-Text Querying for XML	2004	SIGMOD	8.1566309e-05
4,066	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.8221983e-05
5,355	Query Caching and View Selection for XML Databases	2005	VLDB	6.1625215e-05
6,059	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.9001613e-05
6,133	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	5.8776885e-05
7,057	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.6113229e-05
9,862	Answering Tree Pattern Queries Using Views	2006	VLDB	5.1176676e-05
12,325	Minimization of Tree Pattern Queries	2016	PODS	4.9793485e-05
13,089	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	4.9793485e-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
390	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019248147
409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00018868173
679	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00014837097
699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014686953
1,096	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012050482
1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5718481e-05
2,733	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.0819e-05
3,870	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.9551842e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,746	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
2	1,599	Conjunctive Queries over Trees	2004	PODS
3	4,636	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
4	1,976	XPath Satisfiability in the Presence of DTDs	2005	PODS
5	12,767	XPath Whole Query Optimization	2010	VLDB
6	2,177	The Complexity of XPath Query Evaluation	2003	PODS
7	679	Efficient Algorithms for Processing XPath Queries	2002	VLDB
8	12,824	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
9	4,066	Rewriting XPath Queries Using Materialized Views	2005	VLDB
10	13,088	Taming XPath Queries by Minimizing Wildcard Steps	2004	VLDB