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.8835751e-05
Overall Rank: 2,897 | 80.59%
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,333	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.6088875e-05
2,677	FleXPath: Flexible Structure and Full-Text Querying for XML	2004	SIGMOD	8.1266688e-05
4,090	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.7964465e-05
5,378	Query Caching and View Selection for XML Databases	2005	VLDB	6.1392368e-05
6,074	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.877868e-05
6,150	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	5.8555004e-05
7,080	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.5901209e-05
9,904	Answering Tree Pattern Queries Using Views	2006	VLDB	5.0983308e-05
12,374	Minimization of Tree Pattern Queries	2016	PODS	4.9605343e-05
13,136	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	4.9605343e-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.0001918714
409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00018797031
683	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00014781223
703	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014638214
1,100	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012005004
1,827	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5417632e-05
2,743	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.0513978e-05
3,883	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.9293185e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,755	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
2	1,606	Conjunctive Queries over Trees	2004	PODS
3	4,659	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
4	1,983	XPath Satisfiability in the Presence of DTDs	2005	PODS
5	12,816	XPath Whole Query Optimization	2010	VLDB
6	2,195	The Complexity of XPath Query Evaluation	2003	PODS
7	683	Efficient Algorithms for Processing XPath Queries	2002	VLDB
8	12,873	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
9	4,090	Rewriting XPath Queries Using Materialized Views	2005	VLDB
10	13,135	Taming XPath Queries by Minimizing Wildcard Steps	2004	VLDB