 |
|
|
Complexity of Answering Queries Using Materialized Views |
Full Paper (PDF)
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. |
References, where available, link to the DBLP on the World Wide Web.
[1]Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents[2]Serge Abiteboul, Paris C. Kanellakis, Gösta Grahne:
On the Representation and Querying of Sets of Possible Worlds.
TCS 78(1): 158-187(1991)[3]Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman:
Efficient Optimization of a Class of Relational Expressions.
TODS 4(4): 435-454(1979)[4]Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman:
Equivalences Among Relational Expressions.
SIAM J. Comput. 8(2): 218-246(1979)[5]Catriel Beeri, Alon Y. Levy, Marie-Christine Rousset:
Rewriting Queries Using Views in Description Logics.
PODS 1997: 99-108[6]Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim:
Optimizing Queries with Materialized Views.
ICDE 1995: 190-200[7]Ashok K. Chandra, Philip M. Merlin:
Optimal Implementation of Conjunctive Queries in Relational Data Bases.
STOC 1977: 77-90[8]Stephen A. Cook:
The Complexity of Theorem-Proving Procedures.
STOC 1971: 151-158[9]Surajit Chaudhuri, Moshe Y. Vardi:
On the Equivalence of Recursive and Nonrecursive Datalog Programs.
PODS 1992: 55-66[10]Oliver M. Duschka, Michael R. Genesereth:
Answering Recursive Queries Using Views.
PODS 1997: 109-116[11]...
[12]...
[13]Guozhu Dong, Jianwen Su:
Conjunctive Query Containment with Respect to Views and Constraints.
IPL 57(2): 95-102(1996)[14]Oliver M. Duschka:
Query Optimization Using Local Completeness.
AAAI/IAAI 1997: 249-255[15]...
[16]...
[17]...
[18]...
[19]...
[20]Tomasz Imielinski, Witold Lipski Jr.:
Incomplete Information in Relational Databases.
JACM 31(4): 761-791(1984)[21]David S. Johnson, Anthony C. Klug:
Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies.
JCSS 28(1): 167-189(1984)[22]...
[23]Anthony C. Klug:
On Conjunctive Queries Containing Inequalities.
JACM 35(1): 146-160(1988)[24]Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava:
Answering Queries Using Views.
PODS 1995: 95-104[25]Alon Y. Levy, Anand Rajaraman, Joann J. Ordille:
Querying Heterogeneous Information Sources Using Source Descriptions.
VLDB 1996: 251-262[26]Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman:
Answering Queries Using Limited External Processors.
PODS 1996: 227-237[27]Alon Y. Levy, Dan Suciu:
Deciding Containment for Queries with Complex Objects.
PODS 1997: 20-31[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[29]...
[30]Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman:
Answering Queries Using Templates with Binding Patterns.
PODS 1995: 105-112[31]Oded Shmueli:
Decidability and Expressiveness of Logic Queries.
PODS 1987: 237-249[32]Oded Shmueli:
Equivalence of DATALOG Queries is Undecidable.
JLP 15(3): 231-241(1993)[33]Yehoshua Sagiv, Mihalis Yannakakis:
Equivalences Among Relational Expressions with the Union and Difference Operators.
JACM 27(4): 633-655(1980)[34]Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume I.
Computer Science Press 1988, ISBN 0-7167-8158-1
[35]Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
[36]Jeffrey D. Ullman:
Information Integration Using Logical Views.
ICDT 1997: 19-40[37]Moshe Y. Vardi:
The Complexity of Relational Query Languages (Extended Abstract).
STOC 1982: 137-146[38]Moshe Y. Vardi:
Querying Logical Databases.
JCSS 33(2): 142-160(1986)[39]...
[40]...
[41]Ron van der Meyden:
Recursively Indefinite Databases.
TCS 116(1&2): 151-194(1993)[42]Ron van der Meyden:
The Complexity of Querying Indefinite Data about Linearly Ordered Domains.
JCSS 54(1): 113-135(1997)[43]H. Z. Yang, Per-Åke Larson:
Query Transformation for PSJ-Queries.
VLDB 1987: 245-254
|
@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-966-3},
pages = {254-263},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
