 |
|
|
Incremental Maintenance for Materialized Views over Semistructured Data |
Full Paper (PDF)
|
Semistructured data is not strictly typed like relational or object-oriented data and may be irregular or incomplete.
It often arises in practice, e.g., when heterogeneous data sources are integrated or data is taken from the World Wide Web.
Views over semistructured data can be used to filter the data and to restructure (or provide structure to) it.
To achieve fast query response time, these views are often materialized.
This paper proposes an incremental maintenance algorithm for materialized views over semistructured data.
We use the graph-based data model OEM and the query language Lorel, developed at Stanford, as the framework for our work.
Our algorithm produces a set of queries that compute the updates to the view based upon an update of the source.
We develop an analytic cost model and compare the cost of executing our incremental maintenance algorithm to that of recomputing the view.
We show that for nearly all types of database updates, it is more efficient to apply our incremental maintenance algorithm to the view than to recompute the view from the database, even when there are thousands of updates.
|
References, where available, link to the DBLP on the World Wide Web.
[1]Serge Abiteboul:
Querying Semi-Structured Data.
ICDT 1997: 1-18[2]Serge Abiteboul, Anthony J. Bonner:
Objects and Views.
SIGMOD Conference 1991: 238-247[3]...
[4]...
[5]Serge Abiteboul, Dallan Quass, Jason McHugh, Jennifer Widom, Janet L. Wiener:
The Lorel Query Language for Semistructured Data.
Int. J. on Digital Libraries 1(1): 68-88(1997)[6]Catriel Beeri, Yoram Kornatzky:
A Logical Query Language for Hypertext Systems.
ECHT 1990: 67-80[7]Elisa Bertino:
A View Mechanism for Object-Oriented Databases.
EDBT 1992: 136-151[8]Elisa Bertino:
On Modeling Cost Functions for Object-Oriented Databases.
TKDE 9(3): 500-508(1997)[9]José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa:
Efficiently Updating Materialized Views.
SIGMOD Conference 1986: 61-71[10]Peter Buneman:
Semistructured Data.
PODS 1997: 117-121[11]Peter Buneman, Susan B. Davidson, Mary F. Fernandez, Dan Suciu:
Adding Structure to Unstructured Data.
ICDT 1997: 336-350[12]Peter Buneman, Susan B. Davidson, Dan Suciu:
Programming Constructs for Unstructured Data.
DBPL 1995: 12[13]...
[14]R. G. G. Cattell:
The Object Database Standard: ODMG-93 (Release 1.1).
Morgan Kaufmann 1994
[15]Vassilis Christophides, Serge Abiteboul, Sophie Cluet, Michel Scholl:
From Structured Documents to Novel Query Facilities.
SIGMOD Conference 1994: 313-324[16]Vassilis Christophides, Sophie Cluet, Guido Moerkotte:
Evaluating Queries with Generalized Path Expressions.
SIGMOD Conf. 1996: 413-422[17]Latha S. Colby, Timothy Griffin, Leonid Libkin, Inderpal Singh Mumick, Howard Trickey:
Algorithms for Deferred View Maintenance.
SIGMOD Conf. 1996: 469-480[18]Mary F. Fernandez, Dan Suciu:
Optimizing Regular Path Expressions Using Graph Schemas.
ICDE 1998: 14-23[19]Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang:
A Cost Model for Clustered Object-Oriented Databases.
VLDB 1995: 323-334[20]Dieter Gluche, Torsten Grust, Christof Mainberger, Marc H. Scholl:
Incremental Updates for Materialized OQL Views.
DOOD 1997: 52-66[21]Roy Goldman, Jennifer Widom:
DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases.
VLDB 1997: 436-445[22]Timothy Griffin, Leonid Libkin:
Incremental Maintenance of Views with Duplicates.
SIGMOD Conference 1995: 328-339[23]Ashish Gupta, Inderpal Singh Mumick:
Maintenance of Materialized Views: Problems, Techniques, and Applications.
Data Engineering Bulletin 18(2): 3-18(1995)[24]Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian:
Maintaining Views Incrementally.
SIGMOD Conference 1993: 157-166[25]Eric N. Hanson:
A Performance Analysis of View Materialization Strategies.
SIGMOD Conference 1987: 440-453[26]Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Kenneth A. Ross:
Implementing Incremental View Maintenance in Nested Data Models.
DBPL 1997: 202-221[27]David Konopnicki, Oded Shmueli:
W3QS: A Query System for the World-Wide Web.
VLDB 1995: 54-65[28]Bruce G. Lindsay, Laura M. Haas, C. Mohan, Hamid Pirahesh, Paul F. Wilms:
A Snapshot Differential Refresh Algorithm.
SIGMOD Conference 1986: 53-60[29]Jason McHugh, Serge Abiteboul, Roy Goldman, Dallan Quass, Jennifer Widom:
Lore: A Database Management System for Semistructured Data.
SIGMOD Record 26(3): 54-66(1997)[30]...
[31]Alberto O. Mendelzon, George A. Mihaila, Tova Milo:
Querying the World Wide Web.
PDIS 1996: 80-91[32]...
[33]Svetlozar Nestorov, Jeffrey D. Ullman, Janet L. Wiener, Sudarshan S. Chawathe:
Representative Objects: Concise Representations of Semistructured, Hierarchial Data.
ICDE 1997: 79-90[34]Yannis Papakonstantinou, Hector Garcia-Molina, Jeffrey D. Ullman:
MedMaker: A Mediation System Based on Declarative Specifications.
ICDE 1996: 132-141[35]Yannis Papakonstantinou, Hector Garcia-Molina, Jennifer Widom:
Object Exchange Across Heterogeneous Information Sources.
ICDE 1995: 251-260[36]...
[37]...
[38]Nick Roussopoulos, Chungmin Melvin Chen, Stephen Kelley, Alex Delis, Yannis Papakonstantinou:
The ADMS Project: View R Us.
Data Engineering Bulletin 18(2): 19-28(1995)[39]Elke A. Rundensteiner:
Multiview: A Methodology for Supporting Multiple Views in Object-Oriented Databases.
VLDB 1992: 187-198[40]Michael Rys, Moira C. Norrie, Hans-Jörg Schek:
Intra-Transaction Parallelism in the Mapping of an Object Model to a Relational Multi-Processor System.
VLDB 1996: 460-471[41]Marc H. Scholl, Christian Laasch, Markus Tresch:
Updatable Views in Object-Oriented Databases.
DOOD 1991: 189-207[42]Cassio Souza dos Santos, Serge Abiteboul, Claude Delobel:
Virtual Schemas and Bases.
EDBT 1994: 81-94[43]Dan Suciu:
Query Decomposition and View Maintenance for Query Languages for Unstructured Data.
VLDB 1996: 227-238[44]Jeffrey D. Ullman, Jennifer Widom:
A First Course in Database Systems.
Prentice-Hall 1997, ISBN 1-13-861337-0
[45]Yue Zhuge, Hector Garcia-Molina:
Graph Structured Views and Their Incremental Maintenance.
ICDE 1998: 116-125
|
@inproceedings{DBLP:conf/vldb/AbiteboulMRVW98,
author = {Serge Abiteboul and
Jason McHugh and
Michael Rys and
Vasilis Vassalos and
Janet L. Wiener},
editor = {Ashish Gupta and
Oded Shmueli and
Jennifer Widom},
title = {Incremental Maintenance for Materialized Views over Semistructured
Data},
booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
Large Data Bases, August 24-27, 1998, New York City, New York,
USA},
publisher = {Morgan Kaufmann},
year = {1998},
isbn = {1-55860-566-5},
pages = {38-49},
crossref = {DBLP:conf/vldb/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
