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: 1151
Venue: PODS
Year: 1998
Pagerank: 0.00024101949
Overall Rank: 225 | 98.46%
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,099	Recovering Exchanged Data	2015	PODS	5.093636e-05
12,493	XML with Incomplete Information: Models, Properties, and Query Answering	2009	PODS	5.093636e-05
12,610	Incompleteness in Information Integration	2008	VLDB	5.093636e-05
12,725	Determining Source Contribution in Integration Systems	2005	PODS	5.093636e-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
69	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00038090878
97	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00034574497
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00032192665
134	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00030343737
166	Query Transformation for PSJ-queries	1987	VLDB	0.00027676268
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
298	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00022138018
515	Answering Recursive Queries Using Views	1997	PODS	0.00017177428
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
1,031	Answering Queries Using Limited External Query Processors	1996	PODS	0.0001253927
1,777	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.7849758e-05
2,527	Rewriting Queries Using Views in Description Logics	1997	PODS	8.4625195e-05
5,434	The WHIPS Prototype for Data Warehouse Creation and Maintenance	1997	SIGMOD	6.220805e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,743	Algorithms for Materialized View Design in Data Warehousing Environment	1997	VLDB
2	1,787	Adapting Materialized Views after Redefinitions	1995	SIGMOD
3	3,330	A Formal Perspective on the View Selection Problem	2001	VLDB
4	515	Answering Recursive Queries Using Views	1997	PODS
5	929	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD
6	1,034	Answering Complex SQL Queries Using Automatic Summary Tables	2000	SIGMOD
7	69	Answering Queries Using Views (Extended Abstract)	1995	PODS
8	554	Answering Queries with Aggregation Using Views	1996	VLDB
9	9,403	Materializing Views with Minimal Size To Answer Queries	2003	PODS
10	4,155	On the Content of Materialized Aggregate Views	2000	PODS