Answering Recursive Queries Using Views

Summary: Extends view-based rewriting from conjunctive queries to general recursive datalog: ask whether a datalog program P can be rewritten to use only materialized views as EDBs. Proves undecidability, but provides an effective construction of a maximal contained datalog rewriting using views that is guaranteed to be equivalent if any view-only equivalent exists. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h147dea64ade625d6
Venue: PODS
Year: 1997
Pagerank: 0.00016821057
Overall Rank: 532 | 96.43%
DOI: 10.1145/263661.263674

Incoming Non-self Citations Over Time

Authors

1. Oliver M. Duschka (Stanford University)
2. Michael R. Genesereth (Stanford University)

BibTeX Citation

@inproceedings{duschka_pods97,
        address = {New York, NY, USA},
        series = {{PODS} '97},
        title = {{Answering Recursive Queries Using Views}},
        url = {https://dl.acm.org/doi/10.1145/263661.263674},
        doi = {10.1145/263661.263674},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Duschka, Oliver M. and Genesereth, Michael R.},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 32 of 32 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055018384
162	Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity	1998	SIGMOD	0.00027524669
238	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023580688
326	Storing Semistructured Data with STORED	1999	SIGMOD	0.00020953829
418	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00018609134
814	Composing Mappings Among Data Sources	2003	VLDB	0.000137163
824	Data Integration: The Teenage Years	2006	VLDB	0.00013641217
906	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD	0.00013164767
936	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB	0.00012983552
1,330	Catching the Boat with Strudel: Experiences with a Web-Site Management System	1998	SIGMOD	0.00010994625
1,358	Design Considerations for High Fan-in Systems: The HiFi Approach	2005	CIDR	0.00010917457
1,554	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010265583
2,043	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1379399e-05
2,046	Views and Queries: Determinacy and Rewriting	2005	PODS	9.1331561e-05
2,128	Query Rewriting for Semistructured Data	1999	SIGMOD	8.9984814e-05
2,574	Rewriting Queries Using Views in Description Logics	1997	PODS	8.2749164e-05
3,097	Query Containment for Data Integration Systems	2000	PODS	7.649698e-05
3,765	Dynamically Distributed Query Evaluation	2001	PODS	7.0386131e-05
4,232	On the Content of Materialized Aggregate Views	2000	PODS	6.7114333e-05
5,430	Active Knowledge: Dynamically Enriching RDF Knowledge Bases by Web Services	2010	SIGMOD	6.1313e-05
5,496	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.1058078e-05
5,763	Providing Database-like Access to the Web Using Queries Based on Textual Similarity	1998	SIGMOD	6.0008113e-05
6,227	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD	5.8428038e-05
6,265	Inverting Schema Mappings: Bridging the Gap between Theory and Practice	2009	VLDB	5.8299552e-05
6,406	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.7934139e-05
6,668	Generating Efficient Plans for Queries Using Views	2001	SIGMOD	5.7134654e-05
8,022	Foundations of Schema Mapping Management	2010	PODS	5.4037117e-05
8,296	User-Optimizer Communication using Abstract Plans in Sybase ASE	2001	VLDB	5.3589207e-05
8,457	Access Control over Uncertain Data	2008	VLDB	5.3324907e-05
12,788	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	4.9769913e-05
12,847	Complexity and Composition of Synthesized Web Services	2008	PODS	4.9769913e-05
12,906	Incompleteness in Information Integration	2008	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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.0003753293
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00031616101
167	Query Transformation for PSJ-queries	1987	VLDB	0.00027190577
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00026648806
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021673683
1,052	Answering Queries Using Limited External Query Processors	1996	PODS	0.00012269616
2,026	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.1626332e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,496	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS
2	3,802	Lossless Regular Views	2002	PODS
3	4,232	On the Content of Materialized Aggregate Views	2000	PODS
4	12,330	Bounded Query Rewriting Using Views	2016	PODS
5	567	Answering Queries with Aggregation Using Views	1996	VLDB
6	72	Answering Queries Using Views (Extended Abstract)	1995	PODS
7	12,063	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS
8	1,052	Answering Queries Using Limited External Query Processors	1996	PODS
9	238	Complexity of Answering Queries Using Materialized Views	1998	PODS
10	2,574	Rewriting Queries Using Views in Description Logics	1997	PODS