DBScholar

Back to papers

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

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.00055043581
392 Data Exchange: Getting to the Core 2003 PODS 0.0001922472
517 Schema Mappings, Data Exchange, and Metadata Management 2005 PODS 0.00016948466
539 The Chase Revisited 2008 PODS 0.00016735847
595 ConQuer: Efficient Management of Inconsistent Databases 2005 SIGMOD 0.00015798582
715 Data Integration with Uncertainty 2007 VLDB 0.00014559092
793 Model Management 2.0: Manipulating Richer Mappings 2007 SIGMOD 0.00013942384
813 Composing Mappings Among Data Sources 2003 VLDB 0.00013722762
824 Data Integration: The Teenage Years 2006 VLDB 0.00013646923
935 A Scalable Algorithm for Answering Queries Using Views 2000 VLDB 0.00012989395
1,176 Relational Transducers for Electronic Commerce 1998 PODS 0.00011643011
2,041 Rewriting of Regular Expressions and Regular Path Queries 1999 PODS 9.1421879e-05
2,044 Views and Queries: Determinacy and Rewriting 2005 PODS 9.137464e-05
2,100 XML Data Exchange: Consistency and Query Answering 2005 PODS 9.050183e-05
2,321 Efficient Query Reformulation in Peer Data Management Systems 2004 SIGMOD 8.6413639e-05
2,387 Query-Based Data Pricing 2012 PODS 8.5381364e-05
2,554 Peer Data Exchange 2005 PODS 8.3056046e-05
2,728 Weighted Hypertree Decompositions and Optimal Query Plans 2004 PODS 8.0895728e-05
2,984 Materialized Views in Probabilistic Databases: For Information Exchange and Query Optimization 2007 VLDB 7.7830089e-05
2,989 Data Exchange and Incomplete Information 2006 PODS 7.7755739e-05
3,095 Query Containment for Data Integration Systems 2000 PODS 7.6532922e-05
3,503 On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information 2006 PODS 7.2520222e-05
3,614 On Reconciling Data Exchange, Data Integration, and Peer Data Management 2007 PODS 7.1605909e-05
3,759 Toward Large Scale Integration: Building a MetaQuerier over Databases on the Web 2005 CIDR 7.0430209e-05
4,232 On the Content of Materialized Aggregate Views 2000 PODS 6.7145949e-05
4,266 A Web Odyssey: from Codd to XML 2001 PODS 6.6972871e-05
4,367 Locally Consistent Transformations and Query Answering in Data Exchange 2004 PODS 6.633173e-05
4,471 Data Exchange and Schema Mappings in Open and Closed Worlds 2008 PODS 6.5848385e-05
4,514 View-Based Query Containment 2003 PODS 6.5650143e-05
4,656 Update Rewriting and Integrity Constraint Maintenance in a Schema Evolution Support System: PRISM++ 2011 VLDB 6.4827966e-05
5,233 Implementation Strategies for Views over Property Graphs 2024 SIGMOD 6.2176841e-05
5,312 QIRANA: A Framework for Scalable Query Pricing 2017 SIGMOD 6.1847211e-05
5,392 Incomplete Data: What Went Wrong, and How to Fix It 2014 PODS 6.1502284e-05
5,492 Answering Queries Using Views with Arithmetic Comparisons 2002 PODS 6.1086968e-05
5,739 Capturing Missing Tuples and Missing Values 2010 PODS 6.011429e-05
5,740 Relative Information Completeness 2009 PODS 6.011429e-05
6,404 Constraint Satisfaction and Database Theory: a Tutorial 2000 PODS 5.796156e-05
6,626 Representing and Querying XML with Incomplete Information 2001 PODS 5.7291244e-05
6,664 Generating Efficient Plans for Queries Using Views 2001 SIGMOD 5.7161652e-05
6,736 Information Preserving XML Schema Embedding 2005 VLDB 5.6928321e-05
6,887 Query Processing under GLAV Mappings for Relational and Graph Databases 2013 VLDB 5.6550447e-05
7,605 Incomplete Information and Certain Answers in General Data Models 2011 PODS 5.485681e-05
7,851 Interactive Source Registration in Community-oriented Information Integration 2008 VLDB 5.4404838e-05
8,049 On Views and XML 1999 PODS 5.4003954e-05
8,448 Access Control over Uncertain Data 2008 VLDB 5.3350162e-05
8,495 Provenance-based Data Skipping 2022 VLDB 5.3304338e-05
8,912 Optimal Security-Aware Query Processing 2014 VLDB 5.2559789e-05
9,169 Efficient Approximations of Conjunctive Queries 2012 PODS 5.2141412e-05
9,401 Queries with Arithmetic on Incomplete Databases 2020 PODS 5.1845414e-05
11,186 Rule-Based Graph Cleaning with GPUs on a Single Machine 2025 SIGMOD 4.9793485e-05
Previous Page 1 / 2 Next

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
Previous Page 1 / 1 Next

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