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.9688891e-05
Overall Rank: 2,140 | 85.66%
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
419	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00018558415
826	Data Integration: The Teenage Years	2006	VLDB	0.00013599086
940	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB	0.00012941424
1,326	DTD Inference for Views of XML Data	2000	PODS	0.0001101664
2,251	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.7460227e-05
2,830	Secure XML Querying with Security Views	2004	SIGMOD	7.9468777e-05
4,347	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB	6.6380671e-05
5,249	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.1979445e-05
5,259	Implementation Strategies for Views over Property Graphs	2024	SIGMOD	6.194191e-05
5,513	Lazy Query Evaluation for Active XML	2004	SIGMOD	6.0866688e-05
5,978	Optimizing the Secure Evaluation of Twig Queries	2002	VLDB	5.9104822e-05
6,074	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.877868e-05
7,441	Structured Materialized Views for XML Queries	2007	VLDB	5.5118606e-05
8,325	Maintaining XPath Views in Loosely Coupled Systems	2006	VLDB	5.3387063e-05
9,566	Querying Virtual Hierarchies using Virtual Prefix-Based Numbers	2014	SIGMOD	5.1451811e-05
9,983	Wred: Workload Reduction for Scalable Index Tuning	2024	SIGMOD	5.0860177e-05
10,304	G-View: View Management for Graph Databases	2025	VLDB	5.0294306e-05
12,478	Virtual eXist-db: Liberating Hierarchical Queries from the Shackles of Access Path Dependence	2015	VLDB	4.9605343e-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.00042977538
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037421163
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00031526277
131	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.000302173
168	Query Transformation for PSJ-queries	1987	VLDB	0.00027117709
174	Optimizing Queries across Diverse Data Sources	1997	VLDB	0.00026736308
400	View Maintenance in a Warehousing Environment	1995	SIGMOD	0.00019089369
534	Answering Recursive Queries Using Views	1997	PODS	0.0001677412
703	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014638214
1,057	Answering Queries Using Limited External Query Processors	1996	PODS	0.00012235875
1,827	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5417632e-05
2,043	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1266211e-05
2,354	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.5732755e-05
4,645	Capability Based Mediation in TSIMMIS	1998	SIGMOD	6.4729024e-05
4,664	On the Equivalence of Database Restructurings Involving Object Identifiers	1991	PODS	6.4635254e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,671	Optimizing Query Answering under Ontological Constraints	2011	VLDB
2	1,678	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB
3	2,331	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS
4	909	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD
5	12,373	Bounded Query Rewriting Using Views	2016	PODS
6	2,579	Rewriting Queries Using Views in Description Logics	1997	PODS
7	703	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,249	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
10	4,609	Queries with Incomplete Answers over Semistructured Data	1999	PODS