Complexity of Answering Queries Using Materialized Views

Summary: Studies complexity of answering queries using materialized views when view/query languages extend beyond conjunctive (CQ+inequality, positive, Datalog, FO). Proves complexity depends critically on whether materialized views are assumed complete or may be partial, with consequences for view consistency and self‑maintainability. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h02126fd7e9646954
Venue: PODS
Year: 1998
Pagerank: 0.00023510465
Overall Rank: 239 | 98.40%
DOI: 10.1145/275487.275516

Incoming Non-self Citations Over Time

Authors

1. Serge Abiteboul (INRIA)
2. Oliver M. Duschka (Socratix Systems, Inc.)

BibTeX Citation

@inproceedings{abiteboul_pods98,
        address = {New York, NY, USA},
        series = {{PODS} '98},
        title = {{Complexity of Answering Queries Using Materialized Views}},
        url = {https://dl.acm.org/doi/10.1145/275487.275516},
        doi = {10.1145/275487.275516},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Abiteboul, Serge and Duschka, Oliver M.},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 54 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055201845
393	Data Exchange: Getting to the Core	2003	PODS	0.00019157229
524	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00016888746
540	The Chase Revisited	2008	PODS	0.00016674946
597	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00015742369
718	Data Integration with Uncertainty	2007	VLDB	0.00014507333
795	Model Management 2.0: Manipulating Richer Mappings	2007	SIGMOD	0.00013895182
817	Composing Mappings Among Data Sources	2003	VLDB	0.00013671477
826	Data Integration: The Teenage Years	2006	VLDB	0.00013599086
940	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB	0.00012941424
1,181	Relational Transducers for Electronic Commerce	1998	PODS	0.00011599434
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,113	XML Data Exchange: Consistency and Query Answering	2005	PODS	9.0162242e-05
2,333	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.6088875e-05
2,399	Query-Based Data Pricing	2012	PODS	8.5059294e-05
2,560	Peer Data Exchange	2005	PODS	8.2744665e-05
2,739	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	8.0598805e-05
2,996	Materialized Views in Probabilistic Databases: For Information Exchange and Query Optimization	2007	VLDB	7.7548593e-05
3,004	Data Exchange and Incomplete Information	2006	PODS	7.7463337e-05
3,103	Query Containment for Data Integration Systems	2000	PODS	7.6298414e-05
3,515	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS	7.2247195e-05
3,624	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	7.1341025e-05
3,767	Toward Large Scale Integration: Building a MetaQuerier over Databases on the Web	2005	CIDR	7.0171417e-05
4,246	On the Content of Materialized Aggregate Views	2000	PODS	6.694623e-05
4,281	A Web Odyssey: from Codd to XML	2001	PODS	6.6721591e-05
4,392	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	6.6087376e-05
4,493	Data Exchange and Schema Mappings in Open and Closed Worlds	2008	PODS	6.5609585e-05
4,533	View-Based Query Containment	2003	PODS	6.540906e-05
4,675	Update Rewriting and Integrity Constraint Maintenance in a Schema Evolution Support System: PRISM++	2011	VLDB	6.4584174e-05
5,259	Implementation Strategies for Views over Property Graphs	2024	SIGMOD	6.194191e-05
5,338	QIRANA: A Framework for Scalable Query Pricing	2017	SIGMOD	6.1613525e-05
5,415	Incomplete Data: What Went Wrong, and How to Fix It	2014	PODS	6.1270091e-05
5,516	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.0859896e-05
5,753	Capturing Missing Tuples and Missing Values	2010	PODS	5.9887721e-05
5,754	Relative Information Completeness	2009	PODS	5.9887721e-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,627	Incomplete Information and Certain Answers in General Data Models	2011	PODS	5.4649537e-05
7,871	Interactive Source Registration in Community-oriented Information Integration	2008	VLDB	5.4199943e-05
8,072	On Views and XML	1999	PODS	5.3800033e-05
8,472	Access Control over Uncertain Data	2008	VLDB	5.3148581e-05
8,505	Provenance-based Data Skipping	2022	VLDB	5.3126038e-05
8,940	Optimal Security-Aware Query Processing	2014	VLDB	5.2361195e-05
9,205	Efficient Approximations of Conjunctive Queries	2012	PODS	5.1945931e-05
9,435	Queries with Arithmetic on Incomplete Databases	2020	PODS	5.1649519e-05
11,254	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	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
104	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00033799916
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00031526277
136	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00029636761
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
534	Answering Recursive Queries Using Views	1997	PODS	0.0001677412
981	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012688969
1,057	Answering Queries Using Limited External Query Processors	1996	PODS	0.00012235875
1,827	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5417632e-05
2,579	Rewriting Queries Using Views in Description Logics	1997	PODS	8.253743e-05
5,582	The WHIPS Prototype for Data Warehouse Creation and Maintenance	1997	SIGMOD	6.0596256e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,711	Algorithms for Materialized View Design in Data Warehousing Environment	1997	VLDB
2	1,833	Adapting Materialized Views after Redefinitions	1995	SIGMOD
3	3,393	A Formal Perspective on the View Selection Problem	2001	VLDB
4	534	Answering Recursive Queries Using Views	1997	PODS
5	927	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD
6	1,059	Answering Complex SQL Queries Using Automatic Summary Tables	2000	SIGMOD
7	72	Answering Queries Using Views (Extended Abstract)	1995	PODS
8	567	Answering Queries with Aggregation Using Views	1996	VLDB
9	9,620	Materializing Views with Minimal Size To Answer Queries	2003	PODS
10	4,246	On the Content of Materialized Aggregate Views	2000	PODS