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.00037421163
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,246	On the Content of Materialized Aggregate Views	2000	PODS	6.694623e-05
4,293	Core Schema Mappings	2009	SIGMOD	6.6660982e-05
4,392	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	6.6087376e-05
4,533	View-Based Query Containment	2003	PODS	6.540906e-05
5,249	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.1979445e-05
5,516	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.0859896e-05
5,847	Opportunistic Physical Design for Big Data Analytics	2014	SIGMOD	5.9537345e-05
6,051	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS	5.8865476e-05
6,074	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.877868e-05
6,224	Efficient Detection of Empty-Result Queries	2006	VLDB	5.828372e-05
6,239	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD	5.8234909e-05
6,417	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.7743102e-05
6,641	Representing and Querying XML with Incomplete Information	2001	PODS	5.7075003e-05
6,681	Generating Efficient Plans for Queries Using Views	2001	SIGMOD	5.6945953e-05
6,758	Information Preserving XML Schema Embedding	2005	VLDB	5.6714382e-05
6,910	Query Processing under GLAV Mappings for Relational and Graph Databases	2013	VLDB	5.6336774e-05
7,167	Optimizing Recursive Queries with Program Synthesis	2022	SIGMOD	5.5794956e-05
7,288	Query Evaluation using Overlapping Views: Completeness and Efficiency	2006	SIGMOD	5.5489538e-05
7,441	Structured Materialized Views for XML Queries	2007	VLDB	5.5118606e-05
7,628	On Scale Independence for Querying Big Data	2014	PODS	5.4649494e-05
7,734	Generating Low-cost Plans From Proofs	2014	PODS	5.4495579e-05
8,013	When Can We Answer Queries Using Result-Bounded Data Interfaces?	2018	PODS	5.3911362e-05
8,038	Foundations of Schema Mapping Management	2010	PODS	5.385844e-05
8,072	On Views and XML	1999	PODS	5.3800033e-05
8,123	Optimizing the Chase: Scalable Data Integration under Constraints	2014	VLDB	5.3739121e-05
8,724	View Selection over Knowledge Graphs in Triple Stores	2021	VLDB	5.2705676e-05
9,166	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.2031263e-05
9,620	Materializing Views with Minimal Size To Answer Queries	2003	PODS	5.1376962e-05
9,904	Answering Tree Pattern Queries Using Views	2006	VLDB	5.0983308e-05
10,887	FedAugment: Table Augmentation Search over Decentralized Data Repositories	2026	VLDB	4.9605343e-05
10,966	Benchmarking the Full Pipeline of Materialized-View-Based Query Rewriting	2026	VLDB	4.9605343e-05
11,967	High-dimensional Data Cubes	2022	VLDB	4.9605343e-05
12,107	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS	4.9605343e-05
12,185	The Selfish Models Property: Bounding the Complexity of Query Containment and Entailment Problems	2019	PODS	4.9605343e-05
12,201	An Efficient Index for RDF Query Containment	2019	SIGMOD	4.9605343e-05
12,250	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS	4.9605343e-05
12,373	Bounded Query Rewriting Using Views	2016	PODS	4.9605343e-05
12,596	Fine-Grained Disclosure Control for App Ecosystems	2013	SIGMOD	4.9605343e-05
12,831	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	4.9605343e-05
12,890	Complexity and Composition of Synthesized Web Services	2008	PODS	4.9605343e-05
12,948	Incompleteness in Information Integration	2008	VLDB	4.9605343e-05
13,235	Using LDAP Directory Caches	1999	PODS	4.9605343e-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
148	On Rules, Procedures, Caching And Views In Data Base Systems	1990	SIGMOD	0.00028920518
168	Query Transformation for PSJ-queries	1987	VLDB	0.00027117709
179	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00026563438
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021612162
553	Computing Queries from Derived Relations	1985	VLDB	0.00016493992
567	Answering Queries with Aggregation Using Views	1996	VLDB	0.00016228477
579	The GMAP: A Versatile Tool for Physical Data Independence	1994	VLDB	0.00016069665
645	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015188342
878	Queries Independent of Updates	1993	VLDB	0.0001326705
981	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012688969
1,833	Adapting Materialized Views after Redefinitions	1995	SIGMOD	9.532574e-05
1,886	Sleepers and Workaholics: Caching Strategies in Mobile Environments	1994	SIGMOD	9.4201248e-05
3,539	Data Replication for Mobile Computers	1994	SIGMOD	7.1995202e-05

Semantically Similar Papers

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