Answering Queries Using Limited External Query Processors

Summary: Partitions infinite (finitely encoded) view-sets into finitely many equivalence classes so one representative per class suffices to test conjunctive-query rewritability. Provides algorithms for datalog-encoded views, handles built-ins (<,<=,=,!=) on dense domains and integers, and gives an integer query-minimization procedure. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hc738a6551425497a
Venue: PODS
Year: 1996
Pagerank: 0.00012235875
Overall Rank: 1,057 | 92.92%
DOI: 10.1145/237661.237716

Incoming Non-self Citations Over Time

Authors

1. Alon Y. Levy (AT&T)
2. Anand Rajaraman (Stanford University)
3. Jeffrey D. Ullman (Stanford University)

BibTeX Citation

@inproceedings{levy_pods96,
        address = {New York, NY, USA},
        series = {{PODS} '96},
        title = {{Answering Queries Using Limited External Query Processors}},
        url = {https://dl.acm.org/doi/10.1145/237661.237716},
        doi = {10.1145/237661.237716},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Levy, Alon Y. and Rajaraman, Anand and Ullman, Jeffrey D.},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 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
174	Optimizing Queries across Diverse Data Sources	1997	VLDB	0.00026736308
239	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023510465
534	Answering Recursive Queries Using Views	1997	PODS	0.0001677412
817	Composing Mappings Among Data Sources	2003	VLDB	0.00013671477
826	Data Integration: The Teenage Years	2006	VLDB	0.00013599086
1,528	Managing Semantic Heterogeneity in Databases : A Theoretical Perspective	1997	PODS	0.00010322417
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,579	Rewriting Queries Using Views in Description Logics	1997	PODS	8.253743e-05
2,961	Mind Your Vocabulary: Query Mapping Across Heterogeneous Information Sources	1999	SIGMOD	7.7957135e-05
3,574	QURSED: Querying and Reporting Semistructured Data	2002	SIGMOD	7.1772903e-05
3,630	Describing and Using Query Capabilities of Heterogeneous Sources	1997	VLDB	7.1283222e-05
5,857	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.9512616e-05
6,660	Interactive Query Formulation over Web Service-Accessed Sources	2006	SIGMOD	5.7016119e-05
7,829	Positive Higher-Order Queries	2010	PODS	5.4296075e-05
12,730	HOMES: A Higher-Order Mapping Evaluation System	2011	VLDB	4.9605343e-05
13,225	Approximate Query Translation Across Heterogeneous Information Sources	2000	VLDB	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
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037421163
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00031526277
168	Query Transformation for PSJ-queries	1987	VLDB	0.00027117709
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021612162
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
1,425	SIMS: Retrieving and Integrating Information From Multiple Sources	1993	SIGMOD	0.00010694075
1,522	Constraint Checking with Partial Information	1994	PODS	0.00010341308
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
3,898	Constraints and Redundancy in Datalog	1992	PODS	6.9199453e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,681	Generating Efficient Plans for Queries Using Views	2001	SIGMOD
2	12,373	Bounded Query Rewriting Using Views	2016	PODS
3	567	Answering Queries with Aggregation Using Views	1996	VLDB
4	239	Complexity of Answering Queries Using Materialized Views	1998	PODS
5	2,579	Rewriting Queries Using Views in Description Logics	1997	PODS
6	5,516	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS
7	940	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB
8	9,620	Materializing Views with Minimal Size To Answer Queries	2003	PODS
9	534	Answering Recursive Queries Using Views	1997	PODS
10	72	Answering Queries Using Views (Extended Abstract)	1995	PODS