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: 1057
Venue: PODS
Year: 1995
Pagerank: 0.00038090878
Overall Rank: 69 | 99.53%
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 40 of 90 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,155	On the Content of Materialized Aggregate Views	2000	PODS	6.866935e-05
4,193	Core Schema Mappings	2009	SIGMOD	6.842657e-05
4,281	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	6.7848108e-05
4,445	View-Based Query Containment	2003	PODS	6.699172e-05
5,146	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.3470184e-05
5,361	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.2484907e-05
5,720	Opportunistic Physical Design for Big Data Analytics	2014	SIGMOD	6.1092082e-05
5,936	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	6.0353909e-05
5,982	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS	6.0207284e-05
6,084	Efficient Detection of Empty-Result Queries	2006	VLDB	5.9830699e-05
6,090	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD	5.9796288e-05
6,278	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.9287393e-05
6,501	Representing and Querying XML with Incomplete Information	2001	PODS	5.8604724e-05
6,540	Generating Efficient Plans for Queries Using Views	2001	SIGMOD	5.8471897e-05
6,611	Information Preserving XML Schema Embedding	2005	VLDB	5.8228205e-05
6,747	Query Processing under GLAV Mappings for Relational and Graph Databases	2013	VLDB	5.784841e-05
7,035	Optimizing Recursive Queries with Program Synthesis	2022	SIGMOD	5.7216112e-05
7,121	Query Evaluation using Overlapping Views: Completeness and Efficiency	2006	SIGMOD	5.6969248e-05
7,267	Structured Materialized Views for XML Queries	2007	VLDB	5.6597556e-05
7,484	On Scale Independence for Querying Big Data	2014	PODS	5.6074278e-05
7,565	Generating Low-cost Plans From Proofs	2014	PODS	5.5957787e-05
7,830	When Can We Answer Queries Using Result-Bounded Data Interfaces?	2018	PODS	5.5357919e-05
7,859	Foundations of Schema Mapping Management	2010	PODS	5.5303517e-05
7,881	On Views and XML	1999	PODS	5.5242839e-05
7,930	Optimizing the Chase: Scalable Data Integration under Constraints	2014	VLDB	5.5181056e-05
8,527	View Selection over Knowledge Graphs in Triple Stores	2021	VLDB	5.4119882e-05
8,971	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.3420194e-05
9,403	Materializing Views with Minimal Size To Answer Queries	2003	PODS	5.2755515e-05
9,687	Answering Tree Pattern Queries Using Views	2006	VLDB	5.2351299e-05
11,609	High-dimensional Data Cubes	2022	VLDB	5.093636e-05
11,754	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS	5.093636e-05
11,834	The Selfish Models Property: Bounding the Complexity of Query Containment and Entailment Problems	2019	PODS	5.093636e-05
11,852	An Efficient Index for RDF Query Containment	2019	SIGMOD	5.093636e-05
11,901	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS	5.093636e-05
12,029	Bounded Query Rewriting Using Views	2016	PODS	5.093636e-05
12,256	Fine-Grained Disclosure Control for App Ecosystems	2013	SIGMOD	5.093636e-05
12,492	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	5.093636e-05
12,551	Complexity and Composition of Synthesized Web Services	2008	PODS	5.093636e-05
12,610	Incompleteness in Information Integration	2008	VLDB	5.093636e-05
12,898	Using LDAP Directory Caches	1999	PODS	5.093636e-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
146	On Rules, Procedures, Caching And Views In Data Base Systems	1990	SIGMOD	0.00029540467
166	Query Transformation for PSJ-queries	1987	VLDB	0.00027676268
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
298	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00022138018
539	Computing Queries from Derived Relations	1985	VLDB	0.00016872223
554	Answering Queries with Aggregation Using Views	1996	VLDB	0.00016580778
570	The GMAP: A Versatile Tool for Physical Data Independence	1994	VLDB	0.00016328445
633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015560958
853	Queries Independent of Updates	1993	VLDB	0.00013587101
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
1,787	Adapting Materialized Views after Redefinitions	1995	SIGMOD	9.7681572e-05
1,835	Sleepers and Workaholics: Caching Strategies in Mobile Environments	1994	SIGMOD	9.6526423e-05
3,479	Data Replication for Mobile Computers	1994	SIGMOD	7.377382e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,029	Bounded Query Rewriting Using Views	2016	PODS
2	6,540	Generating Efficient Plans for Queries Using Views	2001	SIGMOD
3	913	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB
4	4,155	On the Content of Materialized Aggregate Views	2000	PODS
5	6,090	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD
6	4,445	View-Based Query Containment	2003	PODS
7	7,121	Query Evaluation using Overlapping Views: Completeness and Efficiency	2006	SIGMOD
8	554	Answering Queries with Aggregation Using Views	1996	VLDB
9	225	Complexity of Answering Queries Using Materialized Views	1998	PODS
10	9,403	Materializing Views with Minimal Size To Answer Queries	2003	PODS