ACM SIGMOD Anthology TODS dblp.uni-trier.de

Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates.

José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. ACM Trans. Database Syst. 14(3): 369-400(1989)
@article{DBLP:journals/tods/BlakeleyCL89,
  author    = {Jos{\'e} A. Blakeley and
               Neil Coburn and
               Per-{\AA}ke Larson},
  title     = {Updating Derived Relations: Detecting Irrelevant and Autonomously
               Computable Updates},
  journal   = {ACM Trans. Database Syst.},
  volume    = {14},
  number    = {3},
  year      = {1989},
  pages     = {369-400},
  ee        = {http://doi.acm.org/10.1145/68012.68015, db/journals/tods/BlakeleyCL89.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Consider a database containing not only base relations but also stored derived relations (also called materialized or concrete views). When a base relation is updated, it may also be necessary to update some of the derived relations. This paper gives sufficient and necessary conditions for detecting when an update of a base relation cannot affect a derived relation (an irrelevant update), and for detecting when a derived relation can be correctly updated using no data other than the derived relation itself and the given update operation (an autonomously computable update). The class of derived relations considered is restricted to those defined by PSJ-expressions, that is, any relational algebra expressions constructed from an arbitrary number of project, select and join operations (but containing no self-joins). The class of update operations consists of insertions, deletions, and modifications, where the set of tuples to be deleted or modified is specified by a selection condition on attributes of the relation being updated.

Copyright © 1989 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.


Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Conference Version

José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. VLDB 1986: 457-466 BibTeX

References

[1]
Michel E. Adiba, Bruce G. Lindsay: Database Snapshots. VLDB 1980: 86-91 BibTeX
[2]
Don S. Batory: Modeling the Storage Architectures of Commercial Database Systems. ACM Trans. Database Syst. 10(4): 463-528(1985) BibTeX
[3]
...
[4]
...
[5]
José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. VLDB 1986: 457-466 BibTeX
[6]
...
[7]
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
[8]
Peter Buneman, Eric K. Clemons: Efficient Monitoring Relational Databases. ACM Trans. Database Syst. 4(3): 368-382(1979) BibTeX
[9]
...
[10]
Umeshwar Dayal, Barbara T. Blaustein, Alejandro P. Buchmann, Upen S. Chakravarthy, Meichun Hsu, R. Ledin, Dennis R. McCarthy, Arnon Rosenthal, Sunil K. Sarin, Michael J. Carey, Miron Livny, Rajiv Jauhari: The HiPAC Project: Combining Active Databases and Timing Constraints. SIGMOD Record 17(1): 51-70(1988) BibTeX
[11]
...
[12]
...
[13]
Michael Hammer, Sunil K. Sarin: Efficient Monitoring of Database Assertions (Abstract). SIGMOD Conference 1978: 159 BibTeX
[14]
Per-Åke Larson, H. Z. Yang: Computing Queries from Derived Relations. VLDB 1985: 259-269 BibTeX
[15]
Bruce G. Lindsay, Laura M. Haas, C. Mohan, Hamid Pirahesh, Paul F. Wilms: A Snapshot Differential Refresh Algorithm. SIGMOD Conference 1986: 53-60 BibTeX
[16]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[17]
David Maier, Jeffrey D. Ullman: Fragments of Relations. SIGMOD Conference 1983: 15-22 BibTeX
[18]
Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72 BibTeX
[19]
Michael Stonebraker, Jeff Anton, Eric N. Hanson: Extending a Database System with Procedures. ACM Trans. Database Syst. 12(3): 350-376(1987) BibTeX
[20]
...
[21]
H. Z. Yang, Per-Åke Larson: Query Transformation for PSJ-Queries. VLDB 1987: 245-254 BibTeX

Referenced by

  1. Jun Yang, Jennifer Widom: Temporal View Self-Maintenance. EDBT 2000: 395-412
  2. Theo Härder, Günter Sauter, Joachim Thomas: The Intrinsic Problems of Structural Heterogeneity and an Approach to Their Solution. VLDB J. 8(1): 25-43(1999)
  3. Dominique Laurent, Jens Lechtenbörger, Nicolas Spyratos, Gottfried Vossen: Complements for Data Warehouses. ICDE 1999: 490-499
  4. Kristian Torp, Leo Mark, Christian S. Jensen: Efficient Differential Timeslice Computation. IEEE Trans. Knowl. Data Eng. 10(4): 599-611(1998)
  5. Harumi A. Kuno, Elke A. Rundensteiner: Incremental Maintenance of Materialized Object-Oriented Views in MultiView: Strategies and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 10(5): 768-792(1998)
  6. Avigdor Gal, Opher Etzion: A Multiagent Update Process in a Database with Temporal Data Dependencies and Schema Versioning. IEEE Trans. Knowl. Data Eng. 10(1): 21-37(1998)
  7. Hector Garcia-Molina, Wilburt Labio, Jun Yang: Expiring Data in a Warehouse. VLDB 1998: 500-511
  8. Tetsuya Furukawa, Fei Sha II: Reducing Algorithms for Materialized View Updates. ER 1998: 377-392
  9. Jun Yang, Jennifer Widom: Maintaining Temporal Views over Non-Temporal Information Sources for Data Warehousing. EDBT 1998: 389-403
  10. Michael O. Akinde, Ole Guttorm Jensen, Michael H. Böhlen: Minimizing Detail Data in Data Warehouses. EDBT 1998: 293-307
  11. Laks V. S. Lakshmanan, Nicola Leone, Robert B. Ross, V. S. Subrahmanian: ProbView: A Flexible Probabilistic Database System. ACM Trans. Database Syst. 22(3): 419-469(1997)
  12. Dimitri Theodoratos, Timos K. Sellis: Data Warehouse Configuration. VLDB 1997: 126-135
  13. François Llirbat, Françoise Fabret, Eric Simon: Eliminating Costly Redundant Computations from SQL Trigger Executions. SIGMOD Conference 1997: 428-439
  14. Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB J. 5(2): 101-118(1996)
  15. Arthur M. Keller, Julie Basu: A Predicate-based Caching Scheme for Client-Server Database Architectures. VLDB J. 5(1): 35-47(1996)
  16. David Botzer, Opher Etzion: Optimization of Materialization Strategies for Derived Data Elements. IEEE Trans. Knowl. Data Eng. 8(2): 260-272(1996)
  17. Alon Y. Levy: Obtaining Complete Answers from Incomplete Databases. VLDB 1996: 402-412
  18. Sibel Adali, K. Selçuk Candan, Yannis Papakonstantinou, V. S. Subrahmanian: Query Caching and Optimization in Distributed Mediator Systems. SIGMOD Conference 1996: 137-148
  19. Harumi A. Kuno, Elke A. Rundensteiner: Using Object-Oriented Principles to Optimize Update Propagation to Materialized Views. ICDE 1996: 310-317
  20. Ashish Gupta, H. V. Jagadish, Inderpal Singh Mumick: Data Integration using Self-Maintainable Views. EDBT 1996: 140-144
  21. A. Prasad Sistla, Ouri Wolfson: Temporal Triggers in Active Databases. IEEE Trans. Knowl. Data Eng. 7(3): 471-486(1995)
  22. Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995)
  23. James J. Lu, Guido Moerkotte, Joachim Schü, V. S. Subrahmanian: Efficient Maintenance of Materialized Mediated Views. SIGMOD Conference 1995: 340-351
  24. Jennifer Widom: Research Problems in Data Warehousing. CIKM 1995: 25-30
  25. Stefano Ceri, Piero Fraternali, Stefano Paraboschi, Letizia Tanca: Automatic Generation of Production Rules for Integrity Maintenance. ACM Trans. Database Syst. 19(3): 367-422(1994)
  26. Alfons Kemper, Christoph Kilger, Guido Moerkotte: Function Materialization in Object Bases: Design, Realization, and Evaluation. IEEE Trans. Knowl. Data Eng. 6(4): 587-608(1994)
  27. Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB 1994: 367-378
  28. Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Constraint Checking with Partial Information. PODS 1994: 45-55
  29. Christian S. Jensen, Leo Mark, Nick Roussopoulos, Timos K. Sellis: Using Differential Techniques to Efficiently Support Transaction Time. VLDB J. 2(1): 75-111(1993)
  30. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  31. Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181
  32. Françoise Fabret, Mireille Régnier, Eric Simon: An Adaptive Algorithm for Incremental Evaluation of Production Rules in Databases. VLDB 1993: 455-466
  33. Ashish Gupta, Jennifer Widom: Local Verification of Global Integrity Constraints in Distributed Databases. SIGMOD Conference 1993: 49-58
  34. Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166
  35. Michael Siegel, Edward Sciore, Sharon C. Salveter: A Method for Automatic Rule Derivation to Support Semantic Query Optimization. ACM Trans. Database Syst. 17(4): 563-600(1992)
  36. Keh-Chang Guh, Clement T. Yu: Efficient Management of Materialized Generalized Transitive Closure in Centralized and Parallel Environments. IEEE Trans. Knowl. Data Eng. 4(4): 371-381(1992)
  37. Toni Urpí, Antoni Olivé: A Method for Change Computation in Deductive Databases. VLDB 1992: 225-237
  38. Françoise Fabret, Mireille Régnier, Eric Simon: Optimizing Incremental Computation of Datalog Programs with Non-deterministic Semantics. ICDT 1992: 155-170
  39. Christian S. Jensen, Leo Mark, Nick Roussopoulos: Incremental Implementation Model for Relational Databases with Transaction Time. IEEE Trans. Knowl. Data Eng. 3(4): 461-473(1991)
  40. Alfons Kemper, Christoph Kilger, Guido Moerkotte: Function Materialization in Object Bases. SIGMOD Conference 1991: 258-267
  41. Keh-Chang Guh, Chengyu Sun, Clement T. Yu: Real Time Retrieval and Update of Materialized Transitive Closure. ICDE 1991: 690-697
  42. Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160
  43. José A. Blakeley, Nancy L. Martin: Join Index, Materialized View, and Hybrid-Hash Join: A Performance Analysis. ICDE 1990: 256-263
  44. Heikki Mannila, Kari-Jouko Räihä: Practical Algorithms for Finding Prime Attributes and Testing Normal Forms. PODS 1989: 128-133
  45. Charles Elkan: A Decision Procedure for Conjunctive Query Disjointness. PODS 1989: 134-139
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:07 2008