Incremental Maintenance for Materialized Views over Semistructured Data.

Serge Abiteboul, Jason McHugh, Michael Rys, Vasilis Vassalos, Janet L. Wiener: Incremental Maintenance for Materialized Views over Semistructured Data. VLDB 1998: 38-49
  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
  booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
               Large Data Bases, August 24-27, 1998, New York City, New York,
  publisher = {Morgan Kaufmann},
  year      = {1998},
  isbn      = {1-55860-566-5},
  pages     = {38-49},
  ee        = {db/conf/vldb/AbiteboulMRVW98.html},
  crossref  = {DBLP:conf/vldb/98},
  bibsource = {DBLP,}


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.

Copyright © 1998 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper


CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Ashish Gupta, Oded Shmueli, Jennifer Widom (Eds.): VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. Morgan Kaufmann 1998, ISBN 1-55860-566-5
Contents BibTeX


Serge Abiteboul: Querying Semi-Structured Data. ICDT 1997: 1-18 BibTeX
Serge Abiteboul, Anthony J. Bonner: Objects and Views. SIGMOD Conference 1991: 238-247 BibTeX
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) BibTeX
Catriel Beeri, Yoram Kornatzky: A Logical Query Language for Hypertext Systems. ECHT 1990: 67-80 BibTeX
Elisa Bertino: A View Mechanism for Object-Oriented Databases. EDBT 1992: 136-151 BibTeX
Elisa Bertino, Paola Foscoli: On Modeling Cost Functions for Object-Oriented Databases. IEEE Trans. Knowl. Data Eng. 9(3): 500-508(1997) BibTeX
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
Peter Buneman: Semistructured Data. PODS 1997: 117-121 BibTeX
Peter Buneman, Susan B. Davidson, Mary F. Fernandez, Dan Suciu: Adding Structure to Unstructured Data. ICDT 1997: 336-350 BibTeX
Peter Buneman, Susan B. Davidson, Dan Suciu: Programming Constructs for Unstructured Data. DBPL 1995: 12 BibTeX
R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.1). Morgan Kaufmann 1994
Vassilis Christophides, Serge Abiteboul, Sophie Cluet, Michel Scholl: From Structured Documents to Novel Query Facilities. SIGMOD Conference 1994: 313-324 BibTeX
Vassilis Christophides, Sophie Cluet, Guido Moerkotte: Evaluating Queries with Generalized Path Expressions. SIGMOD Conference 1996: 413-422 BibTeX
Latha S. Colby, Timothy Griffin, Leonid Libkin, Inderpal Singh Mumick, Howard Trickey: Algorithms for Deferred View Maintenance. SIGMOD Conference 1996: 469-480 BibTeX
Mary F. Fernandez, Dan Suciu: Optimizing Regular Path Expressions Using Graph Schemas. ICDE 1998: 14-23 BibTeX
Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang: A Cost Model for Clustered Object-Oriented Databases. VLDB 1995: 323-334 BibTeX
Dieter Gluche, Torsten Grust, Christof Mainberger, Marc H. Scholl: Incremental Updates for Materialized OQL Views. DOOD 1997: 52-66 BibTeX
Roy Goldman, Jennifer Widom: DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. VLDB 1997: 436-445 BibTeX
Timothy Griffin, Leonid Libkin: Incremental Maintenance of Views with Duplicates. SIGMOD Conference 1995: 328-339 BibTeX
Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995) BibTeX
Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166 BibTeX
Eric N. Hanson: A Performance Analysis of View Materialization Strategies. SIGMOD Conference 1987: 440-453 BibTeX
Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Kenneth A. Ross: Implementing Incremental View Maintenance in Nested Data Models. DBPL 1997: 202-221 BibTeX
David Konopnicki, Oded Shmueli: W3QS: A Query System for the World-Wide Web. VLDB 1995: 54-65 BibTeX
Bruce G. Lindsay, Laura M. Haas, C. Mohan, Hamid Pirahesh, Paul F. Wilms: A Snapshot Differential Refresh Algorithm. SIGMOD Conference 1986: 53-60 BibTeX
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) BibTeX
Alberto O. Mendelzon, George A. Mihaila, Tova Milo: Querying the World Wide Web. PDIS 1996: 80-91 BibTeX
Svetlozar Nestorov, Jeffrey D. Ullman, Janet L. Wiener, Sudarshan S. Chawathe: Representative Objects: Concise Representations of Semistructured, Hierarchial Data. ICDE 1997: 79-90 BibTeX
Yannis Papakonstantinou, Hector Garcia-Molina, Jeffrey D. Ullman: MedMaker: A Mediation System Based on Declarative Specifications. ICDE 1996: 132-141 BibTeX
Yannis Papakonstantinou, Hector Garcia-Molina, Jennifer Widom: Object Exchange Across Heterogeneous Information Sources. ICDE 1995: 251-260 BibTeX
Nick Roussopoulos, Chung-Min Chen, Stephen Kelley, Alex Delis, Yannis Papakonstantinou: The ADMS Project: View R Us. IEEE Data Eng. Bull. 18(2): 19-28(1995) BibTeX
Elke A. Rundensteiner: Multiview: A Methodology for Supporting Multiple Views in Object-Oriented Databases. VLDB 1992: 187-198 BibTeX
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 BibTeX
Marc H. Scholl, Christian Laasch, Markus Tresch: Updatable Views in Object-Oriented Databases. DOOD 1991: 189-207 BibTeX
Cassio Souza dos Santos, Serge Abiteboul, Claude Delobel: Virtual Schemas and Bases. EDBT 1994: 81-94 BibTeX
Dan Suciu: Query Decomposition and View Maintenance for Query Languages for Unstructured Data. VLDB 1996: 227-238 BibTeX
Jeffrey D. Ullman, Jennifer Widom: A First Course in Database Systems. Prentice-Hall 1997, ISBN 0-13-861337-0
Yue Zhuge, Hector Garcia-Molina: Graph Structured Views and Their Incremental Maintenance. ICDE 1998: 116-125 BibTeX

Referenced by

  1. Alexandros Labrinidis, Nick Roussopoulos: WebView Materialization. SIGMOD Conference 2000: 367-378
  2. Serge Abiteboul: On Views and XML. SIGMOD Record 28(4): 30-38(1999)
  3. Serge Abiteboul, Bernd Amann, Sophie Cluet, Anat Eyal, Laurent Mignet, Tova Milo: Active Views for Electronic Commerce. VLDB 1999: 138-149
  4. Serge Abiteboul: On Views and XML. PODS 1999: 1-9
  5. Daniela Florescu, Alon Y. Levy, Alberto O. Mendelzon: Database Techniques for the World-Wide Web: A Survey. SIGMOD Record 27(3): 59-74(1998)
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:46:20 2009