Answering Queries Using Views (Extended Abstract)

Summary: Reduces query rewriting to containment mappings from views to the query for conjunctive/union queries with built-in comparisons. Shows NP-completeness, separates complexity into mapping enumeration vs. literal deletion, and gives a poly-time redundancy test that often yields minimal rewritings. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h4e64d222c0876c8f
Venue: PODS
Year: 1995
Pagerank: 0.00037549176
Overall Rank: 72 | 99.52%
DOI: 10.1145/212433.220198

Incoming Non-self Citations Over Time

Authors

1. Alon Y. Levy (AT&T)
2. Alberto O. Mendelzon (University of Toronto)
3. Yehoshua Sagiv (Hebrew University)
4. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{levy_pods95,
        address = {New York, NY, USA},
        series = {{PODS} '95},
        title = {{Answering Queries Using Views (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/212433.220198},
        doi = {10.1145/212433.220198},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Levy, Alon Y. and Mendelzon, Alberto O. and Sagiv, Yehoshua and Srivastava, Divesh},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 42 of 92 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,232	On the Content of Materialized Aggregate Views	2000	PODS	6.7145949e-05
4,280	Core Schema Mappings	2009	SIGMOD	6.6898592e-05
4,367	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	6.633173e-05
4,514	View-Based Query Containment	2003	PODS	6.5650143e-05
5,226	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.2207517e-05
5,492	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.1086968e-05
5,834	Opportunistic Physical Design for Big Data Analytics	2014	SIGMOD	5.9759267e-05
6,043	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS	5.9060629e-05
6,059	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.9001613e-05
6,208	Efficient Detection of Empty-Result Queries	2006	VLDB	5.8497045e-05
6,224	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD	5.8455673e-05
6,404	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.796156e-05
6,626	Representing and Querying XML with Incomplete Information	2001	PODS	5.7291244e-05
6,664	Generating Efficient Plans for Queries Using Views	2001	SIGMOD	5.7161652e-05
6,736	Information Preserving XML Schema Embedding	2005	VLDB	5.6928321e-05
6,887	Query Processing under GLAV Mappings for Relational and Graph Databases	2013	VLDB	5.6550447e-05
7,139	Optimizing Recursive Queries with Program Synthesis	2022	SIGMOD	5.6006128e-05
7,266	Query Evaluation using Overlapping Views: Completeness and Efficiency	2006	SIGMOD	5.5699944e-05
7,418	Structured Materialized Views for XML Queries	2007	VLDB	5.5327659e-05
7,610	On Scale Independence for Querying Big Data	2014	PODS	5.4844912e-05
7,714	Generating Low-cost Plans From Proofs	2014	PODS	5.4702268e-05
7,991	When Can We Answer Queries Using Result-Bounded Data Interfaces?	2018	PODS	5.4115836e-05
8,017	Foundations of Schema Mapping Management	2010	PODS	5.4062707e-05
8,049	On Views and XML	1999	PODS	5.4003954e-05
8,098	Optimizing the Chase: Scalable Data Integration under Constraints	2014	VLDB	5.3942942e-05
8,696	View Selection over Knowledge Graphs in Triple Stores	2021	VLDB	5.2905577e-05
9,135	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.2224867e-05
9,585	Materializing Views with Minimal Size To Answer Queries	2003	PODS	5.1571823e-05
9,862	Answering Tree Pattern Queries Using Views	2006	VLDB	5.1176676e-05
10,816	FedAugment: Table Augmentation Search over Decentralized Data Repositories	2026	VLDB	4.9793485e-05
10,896	Benchmarking the Full Pipeline of Materialized-View-Based Query Rewriting	2026	VLDB	4.9793485e-05
11,917	High-dimensional Data Cubes	2022	VLDB	4.9793485e-05
12,057	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS	4.9793485e-05
12,135	The Selfish Models Property: Bounding the Complexity of Query Containment and Entailment Problems	2019	PODS	4.9793485e-05
12,152	An Efficient Index for RDF Query Containment	2019	SIGMOD	4.9793485e-05
12,201	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS	4.9793485e-05
12,324	Bounded Query Rewriting Using Views	2016	PODS	4.9793485e-05
12,547	Fine-Grained Disclosure Control for App Ecosystems	2013	SIGMOD	4.9793485e-05
12,782	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	4.9793485e-05
12,841	Complexity and Composition of Synthesized Web Services	2008	PODS	4.9793485e-05
12,900	Incompleteness in Information Integration	2008	VLDB	4.9793485e-05
13,188	Using LDAP Directory Caches	1999	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
147	On Rules, Procedures, Caching And Views In Data Base Systems	1990	SIGMOD	0.00029019485
167	Query Transformation for PSJ-queries	1987	VLDB	0.00027190004
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.000266613
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021682744
551	Computing Queries from Derived Relations	1985	VLDB	0.000165527
567	Answering Queries with Aggregation Using Views	1996	VLDB	0.00016272161
577	The GMAP: A Versatile Tool for Physical Data Independence	1994	VLDB	0.00016118789
642	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015243164
875	Queries Independent of Updates	1993	VLDB	0.00013316445
979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012729663
1,822	Adapting Materialized Views after Redefinitions	1995	SIGMOD	9.5664616e-05
1,876	Sleepers and Workaholics: Caching Strategies in Mobile Environments	1994	SIGMOD	9.4539144e-05
3,533	Data Replication for Mobile Computers	1994	SIGMOD	7.2258575e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,324	Bounded Query Rewriting Using Views	2016	PODS
2	6,664	Generating Efficient Plans for Queries Using Views	2001	SIGMOD
3	935	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB
4	4,232	On the Content of Materialized Aggregate Views	2000	PODS
5	6,224	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD
6	4,514	View-Based Query Containment	2003	PODS
7	7,266	Query Evaluation using Overlapping Views: Completeness and Efficiency	2006	SIGMOD
8	567	Answering Queries with Aggregation Using Views	1996	VLDB
9	238	Complexity of Answering Queries Using Materialized Views	1998	PODS
10	9,585	Materializing Views with Minimal Size To Answer Queries	2003	PODS