Complexity of Answering Queries Using Materialized Views.

@inproceedings{DBLP:conf/pods/AbiteboulD98,
  author    = {Serge Abiteboul and
               Oliver M. Duschka},
  title     = {Complexity of Answering Queries Using Materialized Views},
  booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-996-3},
  pages     = {254-263},
  ee        = {http://doi.acm.org/10.1145/275487.275516, db/conf/pods/AbiteboulD98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We study the complexity of the problem of answering queries using materialized views. This problem has attracted a lot of attention recently because of its relevance in data integration. Previous work considered only conjunctive view definitions. We examine the consequences of allowing more expressive view definition languages. The languages we consider for view definitions and user queries are: conjunctive queries with inequality, positive queries, datalog, and first-order logic.

We show that the complexity of the problem depends on whether views are assumed to store all the tuples that satisfy the view definition, or only a subset of it. Finally, we apply the results to the view consistency and view self-maintainability problems which arise in data warehousing.

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX

[2]

Serge Abiteboul, Paris C. Kanellakis, Gösta Grahne: On the Representation and Querying of Sets of Possible Worlds. Theor. Comput. Sci. 78(1): 158-187(1991) BibTeX

[3]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979) BibTeX

[4]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX

[5]

Catriel Beeri, Alon Y. Levy, Marie-Christine Rousset: Rewriting Queries Using Views in Description Logics. PODS 1997: 99-108 BibTeX

[6]

Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200 BibTeX

[7]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[8]

Stephen A. Cook: The Complexity of Theorem-Proving Procedures. STOC 1971: 151-158 BibTeX

[9]

Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66 BibTeX

[10]

Oliver M. Duschka, Michael R. Genesereth: Answering Recursive Queries Using Views. PODS 1997: 109-116 BibTeX

[11]

...

[12]

...

[13]

Guozhu Dong, Jianwen Su: Conjunctive Query Containment with Respect to Views and Constraints. Inf. Process. Lett. 57(2): 95-102(1996) BibTeX

[14]

Oliver M. Duschka: Query Optimization Using Local Completeness. AAAI/IAAI 1997: 249-255 BibTeX

[15]

...

[16]

...

[17]

...

[18]

...

[19]

...

[20]

Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. J. ACM 31(4): 761-791(1984) BibTeX

[21]

David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. J. Comput. Syst. Sci. 28(1): 167-189(1984) BibTeX

[22]

...

[23]

Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) BibTeX

[24]

Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 BibTeX

[25]

Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996: 251-262 BibTeX

[26]

Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Processors. PODS 1996: 227-237 BibTeX

[27]

Alon Y. Levy, Dan Suciu: Deciding Containment for Queries with Complex Objects. PODS 1997: 20-31 BibTeX

[28]

Wilburt Labio, Yue Zhuge, Janet L. Wiener, Himanshu Gupta, Hector Garcia-Molina, Jennifer Widom: The WHIPS Prototype for Data Warehouse Creation and Maintenance. SIGMOD Conference 1997: 557-559 BibTeX

[29]

...

[30]

Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman: Answering Queries Using Templates with Binding Patterns. PODS 1995: 105-112 BibTeX

[31]

Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX

[32]

Oded Shmueli: Equivalence of DATALOG Queries is Undecidable. J. Log. Program. 15(3): 231-241(1993) BibTeX

[33]

Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX

[34]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[35]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[36]

Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40 BibTeX

[37]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

[38]

Moshe Y. Vardi: Querying Logical Databases. J. Comput. Syst. Sci. 33(2): 142-160(1986) BibTeX

[39]

...

[40]

...

[41]

Ron van der Meyden: Recursively Indefinite Databases. Theor. Comput. Sci. 116(1&2): 151-194(1993) BibTeX

[42]

Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. J. Comput. Syst. Sci. 54(1): 113-135(1997) BibTeX

[43]

H. Z. Yang, Per-Åke Larson: Query Transformation for PSJ-Queries. VLDB 1987: 245-254 BibTeX

Referenced by

1. Chen Li, Mayank Bawa, Jeffrey D. Ullman: Minimizing View Sets without Losing Query-Answering Power. ICDT 2001: 99-113
2. Gösta Grahne, Alex Thomo: Algebraic Rewritings for Optimizing Regular Path Queries. ICDT 2001: 301-315
3. Moshe Y. Vardi: Constraint Satisfaction and Database Theory: a Tutorial. PODS 2000: 76-85
4. Todd D. Millstein, Alon Y. Levy, Marc Friedman: Query Containment for Data Integration Systems. PODS 2000: 67-75
5. Stéphane Grumbach, Leonardo Tininini: On the Content of Materialized Aggregate Views. PODS 2000: 47-57
6. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi: View-Based Query Processing for Regular Path Queries with Inverse. PODS 2000: 58-66
7. Serge Abiteboul: On Views and XML. SIGMOD Record 28(4): 30-38(1999)
8. Alon Y. Levy: Review - Complexity of Answering Queries Using Materialized Views. ACM SIGMOD Digital Review 1: (1999)
9. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi: Rewriting of Regular Expressions and Regular Path Queries. PODS 1999: 194-204
10. Serge Abiteboul: On Views and XML. PODS 1999: 1-9
11. Gösta Grahne, Alberto O. Mendelzon: Tableau Techniques for Querying Information Sources through Global Schemas. ICDT 1999: 332-347
12. James Bailey, Guozhu Dong: Decidability of First-Order Logic Queries over Views. ICDT 1999: 83-99
13. Foto N. Afrati, Manolis Gergatsoulis, Theodoros G. Kavalieros: Answering Queries Using Materialized Views with Disjunctions. ICDT 1999: 435-452
14. Daniela Florescu, Alon Y. Levy, Alberto O. Mendelzon: Database Techniques for the World-Wide Web: A Survey. SIGMOD Record 27(3): 59-74(1998)