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: 9.0005009e-05
Overall Rank: 2,127 | 85.71%
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.00018617842
824	Data Integration: The Teenage Years	2006	VLDB	0.00013646923
935	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB	0.00012989395
1,315	DTD Inference for Views of XML Data	2000	PODS	0.00011058412
2,235	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.7779518e-05
2,816	Secure XML Querying with Security Views	2004	SIGMOD	7.9770184e-05
4,327	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB	6.6632438e-05
5,226	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.2207517e-05
5,233	Implementation Strategies for Views over Property Graphs	2024	SIGMOD	6.2176841e-05
5,490	Lazy Query Evaluation for Active XML	2004	SIGMOD	6.1094192e-05
5,964	Optimizing the Secure Evaluation of Twig Queries	2002	VLDB	5.9328994e-05
6,059	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.9001613e-05
7,418	Structured Materialized Views for XML Queries	2007	VLDB	5.5327659e-05
8,304	Maintaining XPath Views in Loosely Coupled Systems	2006	VLDB	5.3589548e-05
9,531	Querying Virtual Hierarchies using Virtual Prefix-Based Numbers	2014	SIGMOD	5.1646956e-05
10,271	G-View: View Management for Graph Databases	2025	VLDB	5.0485061e-05
10,297	Wred: Workload Reduction for Scalable Index Tuning	2024	SIGMOD	5.0430432e-05
12,429	Virtual eXist-db: Liberating Hierarchical Queries from the Shackles of Access Path Dependence	2015	VLDB	4.9793485e-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.00043130126
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037549176
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00031630695
130	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030320165
167	Query Transformation for PSJ-queries	1987	VLDB	0.00027190004
173	Optimizing Queries across Diverse Data Sources	1997	VLDB	0.00026826959
398	View Maintenance in a Warehousing Environment	1995	SIGMOD	0.00019152162
532	Answering Recursive Queries Using Views	1997	PODS	0.0001682881
699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014686953
1,052	Answering Queries Using Limited External Query Processors	1996	PODS	0.00012275281
1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5718481e-05
2,041	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1421879e-05
2,349	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.5999717e-05
4,638	Capability Based Mediation in TSIMMIS	1998	SIGMOD	6.4920463e-05
4,646	On the Equivalence of Database Restructurings Involving Object Identifiers	1991	PODS	6.4877004e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,646	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,317	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS
4	905	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD
5	12,324	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,041	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS
9	5,226	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
10	4,592	Queries with Incomplete Answers over Semistructured Data	1999	PODS