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.00023591683
Overall Rank: 238 | 98.41%
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 4 of 54 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,392	Recovering Exchanged Data	2015	PODS	4.9793485e-05
12,783	XML with Incomplete Information: Models, Properties, and Query Answering	2009	PODS	4.9793485e-05
12,900	Incompleteness in Information Integration	2008	VLDB	4.9793485e-05
13,015	Determining Source Contribution in Integration Systems	2005	PODS	4.9793485e-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.00037549176
102	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00033914384
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00031630695
136	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00029740459
167	Query Transformation for PSJ-queries	1987	VLDB	0.00027190004
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.000266613
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021682744
532	Answering Recursive Queries Using Views	1997	PODS	0.0001682881
979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012729663
1,052	Answering Queries Using Limited External Query Processors	1996	PODS	0.00012275281
1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5718481e-05
2,574	Rewriting Queries Using Views in Description Logics	1997	PODS	8.278796e-05
5,565	The WHIPS Prototype for Data Warehouse Creation and Maintenance	1997	SIGMOD	6.0823233e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,706	Algorithms for Materialized View Design in Data Warehousing Environment	1997	VLDB
2	1,822	Adapting Materialized Views after Redefinitions	1995	SIGMOD
3	3,392	A Formal Perspective on the View Selection Problem	2001	VLDB
4	532	Answering Recursive Queries Using Views	1997	PODS
5	923	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD
6	1,054	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,585	Materializing Views with Minimal Size To Answer Queries	2003	PODS
10	4,232	On the Content of Materialized Aggregate Views	2000	PODS