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: 3183
Venue: SIGMOD
Year: 1999
Pagerank: 9.1481121e-05
Overall Rank: 2,114 | 85.50%
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
407	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00019021441
913	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB	0.00013253821
917	Data Integration: The Teenage Years	2006	VLDB	0.00013224381
1,290	DTD Inference for Views of XML Data	2000	PODS	0.00011312135
2,285	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.8052998e-05
2,757	Secure XML Querying with Security Views	2004	SIGMOD	8.1601016e-05
5,146	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.3470184e-05
5,264	Implementation Strategies for Views over Property Graphs	2024	SIGMOD	6.2947526e-05
5,360	Lazy Query Evaluation for Active XML	2004	SIGMOD	6.2487273e-05
5,842	Optimizing the Secure Evaluation of Twig Queries	2002	VLDB	6.0690726e-05
5,936	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	6.0353909e-05
6,293	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB	5.9247942e-05
7,267	Structured Materialized Views for XML Queries	2007	VLDB	5.6597556e-05
8,130	Maintaining XPath Views in Loosely Coupled Systems	2006	VLDB	5.4819552e-05
9,352	Querying Virtual Hierarchies using Virtual Prefix-Based Numbers	2014	SIGMOD	5.2831061e-05
10,082	Wred: Workload Reduction for Scalable Index Tuning	2024	SIGMOD	5.1587525e-05
10,837	G-View: View Management for Graph Databases	2025	VLDB	5.093636e-05
12,136	Virtual eXist-db: Liberating Hierarchical Queries from the Shackles of Access Path Dependence	2015	VLDB	5.093636e-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
48	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00044033592
69	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00038090878
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00032192665
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
166	Query Transformation for PSJ-queries	1987	VLDB	0.00027676268
171	Optimizing Queries across Diverse Data Sources	1997	VLDB	0.00027363924
391	View Maintenance in a Warehousing Environment	1995	SIGMOD	0.00019370653
515	Answering Recursive Queries Using Views	1997	PODS	0.00017177428
686	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014948634
1,031	Answering Queries Using Limited External Query Processors	1996	PODS	0.0001253927
1,777	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.7849758e-05
2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.2348082e-05
2,296	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.7908999e-05
4,542	Capability Based Mediation in TSIMMIS	1998	SIGMOD	6.6395511e-05
4,555	On the Equivalence of Database Restructurings Involving Object Identifiers	1991	PODS	6.6344715e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,479	Optimizing Query Answering under Ontological Constraints	2011	VLDB
2	1,829	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB
3	2,261	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS
4	879	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD
5	12,029	Bounded Query Rewriting Using Views	2016	PODS
6	2,527	Rewriting Queries Using Views in Description Logics	1997	PODS
7	686	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS
8	2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS
9	5,146	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
10	4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS