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.9096688e-05
Overall Rank: 2,883 | 80.63%
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,323	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.637314e-05
2,666	FleXPath: Flexible Structure and Full-Text Querying for XML	2004	SIGMOD	8.1527901e-05
4,068	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.8189688e-05
5,361	Query Caching and View Selection for XML Databases	2005	VLDB	6.1596042e-05
6,060	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.8973683e-05
6,135	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	5.8749061e-05
7,060	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.6086666e-05
9,869	Answering Tree Pattern Queries Using Views	2006	VLDB	5.115245e-05
12,331	Minimization of Tree Pattern Queries	2016	PODS	4.9769913e-05
13,095	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	4.9769913e-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
391	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019245666
409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00018859247
680	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.0001483008
699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014680086
1,096	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012044781
1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5674072e-05
2,733	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.0780747e-05
3,871	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.9520505e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,747	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
2	1,599	Conjunctive Queries over Trees	2004	PODS
3	4,639	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
4	1,978	XPath Satisfiability in the Presence of DTDs	2005	PODS
5	12,773	XPath Whole Query Optimization	2010	VLDB
6	2,179	The Complexity of XPath Query Evaluation	2003	PODS
7	680	Efficient Algorithms for Processing XPath Queries	2002	VLDB
8	12,830	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
9	4,068	Rewriting XPath Queries Using Materialized Views	2005	VLDB
10	13,094	Taming XPath Queries by Minimizing Wildcard Steps	2004	VLDB