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 50 of 92 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055201845
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00031526277
204	Aggregate-Query Processing in Data Warehousing Environments	1995	VLDB	0.0002516936
239	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023510465
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021612162
329	Storing Semistructured Data with STORED	1999	SIGMOD	0.00020888032
391	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.0001918714
410	Semantic Data Caching and Replacement	1996	VLDB	0.00018751654
419	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00018558415
534	Answering Recursive Queries Using Views	1997	PODS	0.0001677412
556	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.00016470022
567	Answering Queries with Aggregation Using Views	1996	VLDB	0.00016228477
654	Materialized Views In Oracle	1998	VLDB	0.00015096471
703	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014638214
746	Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time	1996	SIGMOD	0.0001426147
882	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013239752
909	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD	0.00013122165
940	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB	0.00012941424
1,057	Answering Queries Using Limited External Query Processors	1996	PODS	0.00012235875
1,059	Answering Complex SQL Queries Using Automatic Summary Tables	2000	SIGMOD	0.00012224962
1,528	Managing Semantic Heterogeneity in Databases : A Theoretical Perspective	1997	PODS	0.00010322417
1,550	Data Warehouse Configuration	1997	VLDB	0.00010257652
1,736	Using Schematically Heterogeneous Structures	1998	SIGMOD	9.7450722e-05
1,827	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5417632e-05
1,833	Adapting Materialized Views after Redefinitions	1995	SIGMOD	9.532574e-05
1,864	Hypothetical Queries in an OLAP Environment	2000	VLDB	9.4653035e-05
2,043	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1266211e-05
2,055	Views and Queries: Determinacy and Rewriting	2005	PODS	9.1029941e-05
2,140	Query Rewriting for Semistructured Data	1999	SIGMOD	8.9688891e-05
2,159	Query Decomposition and View Maintenance for Query Languages for Unstructured Data	1996	VLDB	8.9259899e-05
2,166	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9171951e-05
2,241	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.7710222e-05
2,301	Querying Aggregate Data	1999	PODS	8.6620636e-05
2,302	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR	8.6605971e-05
2,579	Rewriting Queries Using Views in Description Logics	1997	PODS	8.253743e-05
2,604	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS	8.2136514e-05
2,626	Cost-Based Optimization of Decision Support Queries using Transient-Views	1998	SIGMOD	8.1919956e-05
2,726	A Framework for Using Materialized XPath Views in XML Query Processing	2004	VLDB	8.0711806e-05
3,052	Incremental and Approximate Inference for Faster Occlusion-based Deep CNN Explanations	2019	SIGMOD	7.6924471e-05
3,103	Query Containment for Data Integration Systems	2000	PODS	7.6298414e-05
3,142	Statistics on Views	2003	VLDB	7.5858292e-05
3,171	Form-Based Proxy Caching for Database-Backed Web Sites	2001	VLDB	7.5571577e-05
3,413	Quality-driven Integration of Heterogeneous Information Systems	1999	VLDB	7.3058316e-05
3,444	Complete Yet Practical Search for Minimal Query Reformulations Under Constraints	2014	SIGMOD	7.277762e-05
3,584	Attacking Diophantus: Solving a Special Case of Bag Containment	2019	PODS	7.1705819e-05
3,630	Describing and Using Query Capabilities of Heterogeneous Sources	1997	VLDB	7.1283222e-05
3,859	QC-Trees: An Efficient Summary Structure for Semantic OLAP	2003	SIGMOD	6.9540456e-05
3,883	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.9293185e-05
3,979	On Efficiently Implementing SchemaSQL on a SQL Database System	1999	VLDB	6.8700205e-05
4,090	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.7964465e-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