Database Paper Browser

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
1152
Venue
PODS
Year
1998
Pagerank
0.00028596715
Overall Rank
297 | 97.94%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 54 citing papers.

Rank Citing Paper Year Venue Pagerank
48 Data Integration: A Theoretical Perspective 2002 PODS 0.00069720859
494 Data Exchange: Getting to the Core 2003 PODS 0.00021805832
621 Schema Mappings, Data Exchange, and Metadata Management 2005 PODS 0.00019005115
678 ConQuer: Efficient Management of Inconsistent Databases 2005 SIGMOD 0.00018253213
698 The Chase Revisited 2008 PODS 0.00018030148
721 Data Integration with Uncertainty 2007 VLDB 0.00017570539
879 Composing Mappings Among Data Sources 2003 VLDB 0.00015674595
893 Data Integration: The Teenage Years 2006 VLDB 0.00015558352
989 Relational Transducers for Electronic Commerce 1998 PODS 0.00014814282
1,038 Weighted Hypertree Decompositions and Optimal Query Plans 2004 PODS 0.00014492414
1,078 Model Management 2.0: Manipulating Richer Mappings 2007 SIGMOD 0.00014245848
1,155 A Scalable Algorithm for Answering Queries Using Views 2000 VLDB 0.00013616518
2,034 Views and Queries: Determinacy and Rewriting 2005 PODS 9.7156155e-05
2,211 XML Data Exchange: Consistency and Query Answering 2005 PODS 9.2771941e-05
2,342 Rewriting of Regular Expressions and Regular Path Queries 1999 PODS 9.0015589e-05
2,370 Query-Based Data Pricing 2012 PODS 8.9488834e-05
2,479 Efficient Query Reformulation in Peer Data Management Systems 2004 SIGMOD 8.6909119e-05
2,715 Peer Data Exchange 2005 PODS 8.2433779e-05
3,011 Update Rewriting and Integrity Constraint Maintenance in a Schema Evolution Support System: PRISM++ 2011 VLDB 7.7183382e-05
3,168 Query Containment for Data Integration Systems 2000 PODS 7.4508875e-05
3,324 On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information 2006 PODS 7.2213002e-05
3,502 Data Exchange and Incomplete Information 2006 PODS 7.0366655e-05
3,724 Toward Large Scale Integration: Building a MetaQuerier over Databases on the Web 2005 CIDR 6.8173288e-05
3,892 QIRANA: A Framework for Scalable Query Pricing 2017 SIGMOD 6.659352e-05
3,937 On Reconciling Data Exchange, Data Integration, and Peer Data Management 2007 PODS 6.6159574e-05
4,010 A Web Odyssey: from Codd to XML 2001 PODS 6.5351699e-05
4,082 On the Content of Materialized Aggregate Views 2000 PODS 6.4639136e-05
4,466 Data Exchange and Schema Mappings in Open and Closed Worlds 2008 PODS 6.1601459e-05
4,553 View-Based Query Containment 2003 PODS 6.091702e-05
4,705 Locally Consistent Transformations and Query Answering in Data Exchange 2004 PODS 5.9830709e-05
4,977 Constraint Satisfaction and Database Theory: a Tutorial 2000 PODS 5.7881576e-05
5,459 Capturing Missing Tuples and Missing Values 2010 PODS 5.4957751e-05
5,460 Relative Information Completeness 2009 PODS 5.4957751e-05
5,471 Answering Queries Using Views with Arithmetic Comparisons 2002 PODS 5.4888202e-05
5,494 Incomplete Data: What Went Wrong, and How to Fix It 2014 PODS 5.4759469e-05
5,659 Implementation Strategies for Views over Property Graphs 2024 SIGMOD 5.3847762e-05
5,717 Query Processing under GLAV Mappings for Relational and Graph Databases 2013 VLDB 5.3553228e-05
6,509 Representing and Querying XML with Incomplete Information 2001 PODS 5.0331402e-05
6,567 Generating Efficient Plans for Queries Using Views 2001 SIGMOD 5.0069599e-05
6,652 Information Preserving XML Schema Embedding 2005 VLDB 4.9761854e-05
7,322 Interactive Source Registration in Community-oriented Information Integration 2008 VLDB 4.7628024e-05
7,393 Incomplete Information and Certain Answers in General Data Models 2011 PODS 4.7428879e-05
7,856 On Views and XML 1999 PODS 4.6347452e-05
7,962 Access Control over Uncertain Data 2008 VLDB 4.613363e-05
8,545 Optimal Security-Aware Query Processing 2014 VLDB 4.4937074e-05
8,851 Efficient Approximations of Conjunctive Queries 2012 PODS 4.4363908e-05
8,886 Provenance-based Data Skipping 2022 VLDB 4.4279829e-05
8,947 Queries with Arithmetic on Incomplete Databases 2020 PODS 4.4248197e-05
10,486 Rule-Based Graph Cleaning with GPUs on a Single Machine 2025 SIGMOD 4.1945683e-05
11,900 Recovering Exchanged Data 2015 PODS 4.1945683e-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
58 Efficient Optimization of a Class of Relational Expressions 1978 SIGMOD 0.00064826446
82 Answering Queries Using Views (Extended Abstract) 1995 PODS 0.00054402763
127 Querying Heterogeneous Information Sources Using Source Descriptions 1996 VLDB 0.00044642203
138 Query Transformation for PSJ-queries 1987 VLDB 0.00042334092
144 Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) 1982 PODS 0.00041462501
172 Decidability And Expressiveness Aspects Of Logic Queries 1987 PODS 0.00038808816
291 Answering Queries Using Templates With Binding Patterns (Extended Abstract) 1995 PODS 0.00028831632
532 Answering Recursive Queries Using Views 1997 PODS 0.00020778506
909 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015428222
976 Answering Queries Using Limited External Query Processors 1996 PODS 0.0001489085
1,952 Deciding Containment for Queries with Complex Objects (Extended Abstract) 1997 PODS 9.9677831e-05
2,536 Rewriting Queries Using Views in Description Logics 1997 PODS 8.5837937e-05
5,133 The WHIPS Prototype for Data Warehouse Creation and Maintenance 1997 SIGMOD 5.6740049e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,911 Algorithms for Materialized View Design in Data Warehousing Environment 1997 VLDB 0.00010120234
1,617 Adapting Materialized Views after Redefinitions 1995 SIGMOD 0.00011119837
3,583 A Formal Perspective on the View Selection Problem 2001 VLDB 6.9463532e-05
532 Answering Recursive Queries Using Views 1997 PODS 0.00020778506
1,112 Materialized View Selection and Maintenance Using Multi-Query Optimization 2001 SIGMOD 0.00013917776
1,059 Answering Complex SQL Queries Using Automatic Summary Tables 2000 SIGMOD 0.00014382575
82 Answering Queries Using Views (Extended Abstract) 1995 PODS 0.00054402763
584 Answering Queries with Aggregation Using Views 1996 VLDB 0.0001971526
9,259 Materializing Views with Minimal Size To Answer Queries 2003 PODS 4.3690661e-05
4,082 On the Content of Materialized Aggregate Views 2000 PODS 6.4639136e-05