Covering Indexes for XML Queries: Bisimulation - Simulation = Negation

Summary: Shows simulation quotients are the smallest covering indexes for BPQ+ and TPQ, while bisimulation is required for unrestricted BPQ. Hence “bisimulation − simulation = negation”: excluding negation can yield exponentially smaller XML indexes. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9163
Venue: VLDB
Year: 2003
Pagerank: 5.5353696e-05
Overall Rank: 7,836 | 46.24%
DOI: 10.1016/B978-012722442-8/50023-9

Incoming Non-self Citations Over Time

Authors

1. Prakash Ramanan (Wichita State University)

BibTeX Citation

@article{ramanan_vldb03,
        title = {{Covering Indexes for XML Queries: Bisimulation - Simulation = Negation}},
        author = {Ramanan, Prakash},
        journal = {PVLDB},
        series = {{VLDB} '03},
        doi = {10.1016/B978-012722442-8/50023-9},
        url = {https://doi.org/10.1016/B978-012722442-8/50023-9},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,202	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.6755422e-05
12,684	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
666	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00015166582
718	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00014642961
1,068	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012326498
2,680	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.267202e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,534	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
2	9,687	Answering Tree Pattern Queries Using Views	2006	VLDB
3	12,476	XPath Whole Query Optimization	2010	VLDB
4	6,005	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD
5	1,564	Conjunctive Queries over Trees	2004	PODS
6	3,976	Rewriting XPath Queries Using Materialized Views	2005	VLDB
7	4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
8	2,472	Path Queries on Compressed XML	2003	VLDB
9	2,817	On the minimization of XPath queries	2003	VLDB
10	718	Covering Indexes for Branching Path Queries	2002	SIGMOD