dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

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
@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},
  ee        = {db/conf/vldb/AbiteboulMRVW98.html},
  crossref  = {DBLP:conf/vldb/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

ACM SIGMOD DiSC

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

ACM SIGMOD Anthology

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

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

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

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)

Last update Fri Sep 14 17:38:22 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page