Query Rewriting for Semistructured Data

Summary: Introduces a TSL-based rewriting framework for semistructured data, deriving rewrites from views by generalized containment mappings and chase. Shows soundness and completeness for TSL, adds a view-equivalence checker and constraints-based rewritings. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h87df95e46d51ec3b
Venue: SIGMOD
Year: 1999
Pagerank: 8.9984814e-05
Overall Rank: 2,128 | 85.70%
DOI: 10.1145/304182.304222

Incoming Non-self Citations Over Time

Authors

1. Yannis Papakonstantinou (University of California San Diego)
2. Vasilis Vassalos (Stanford University)

BibTeX Citation

@inproceedings{papakonstantinou_sigmod99,
        title = {{Query Rewriting for Semistructured Data}},
        author = {Papakonstantinou, Yannis and Vassalos, Vasilis},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304222},
        url = {https://dl.acm.org/doi/10.1145/304182.304222},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
418	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00018609134
824	Data Integration: The Teenage Years	2006	VLDB	0.00013641217
936	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB	0.00012983552
1,315	DTD Inference for Views of XML Data	2000	PODS	0.00011053178
2,238	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.7738068e-05
2,817	Secure XML Querying with Security Views	2004	SIGMOD	7.9732421e-05
4,327	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB	6.6600895e-05
5,230	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.2178069e-05
5,238	Implementation Strategies for Views over Property Graphs	2024	SIGMOD	6.2147408e-05
5,494	Lazy Query Evaluation for Active XML	2004	SIGMOD	6.1065309e-05
5,966	Optimizing the Secure Evaluation of Twig Queries	2002	VLDB	5.9300908e-05
6,060	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.8973683e-05
7,421	Structured Materialized Views for XML Queries	2007	VLDB	5.5301467e-05
8,311	Maintaining XPath Views in Loosely Coupled Systems	2006	VLDB	5.356418e-05
9,540	Querying Virtual Hierarchies using Virtual Prefix-Based Numbers	2014	SIGMOD	5.1622507e-05
9,950	Wred: Workload Reduction for Scalable Index Tuning	2024	SIGMOD	5.102891e-05
10,277	G-View: View Management for Graph Databases	2025	VLDB	5.0461162e-05
12,435	Virtual eXist-db: Liberating Hierarchical Queries from the Shackles of Access Path Dependence	2015	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
50	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.0004311045
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.0003753293
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00031616101
130	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030306096
167	Query Transformation for PSJ-queries	1987	VLDB	0.00027190577
173	Optimizing Queries across Diverse Data Sources	1997	VLDB	0.00026814969
398	View Maintenance in a Warehousing Environment	1995	SIGMOD	0.00019143434
532	Answering Recursive Queries Using Views	1997	PODS	0.00016821057
699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014680086
1,052	Answering Queries Using Limited External Query Processors	1996	PODS	0.00012269616
1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5674072e-05
2,043	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1379399e-05
2,350	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.5959895e-05
4,641	Capability Based Mediation in TSIMMIS	1998	SIGMOD	6.4889857e-05
4,648	On the Equivalence of Database Restructurings Involving Object Identifiers	1991	PODS	6.4847033e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,653	Optimizing Query Answering under Ontological Constraints	2011	VLDB
2	1,680	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB
3	2,319	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS
4	906	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD
5	12,330	Bounded Query Rewriting Using Views	2016	PODS
6	2,574	Rewriting Queries Using Views in Description Logics	1997	PODS
7	699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS
8	2,043	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS
9	5,230	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
10	4,594	Queries with Incomplete Answers over Semistructured Data	1999	PODS