ACM SIGMOD Anthology TODS dblp.uni-trier.de

Heraclitus: Elevating Deltas to be First-Class Citizens in a Database Programming Language.

Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs: Heraclitus: Elevating Deltas to be First-Class Citizens in a Database Programming Language. ACM Trans. Database Syst. 21(3): 370-426(1996)
@article{DBLP:journals/tods/GhandeharizadehHJ96,
  author    = {Shahram Ghandeharizadeh and
               Richard Hull and
               Dean Jacobs},
  title     = {Heraclitus: Elevating Deltas to be First-Class Citizens in a
               Database Programming Language},
  journal   = {ACM Trans. Database Syst.},
  volume    = {21},
  number    = {3},
  year      = {1996},
  pages     = {370-426},
  ee        = {http://doi.acm.org/10.1145/232753.232801, db/journals/tods/GhandeharizadehHJ96.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Traditional database systems provide a user with the ability to query and manipulate one database state, namely the current database state. However, in several emerging applications, the ability to analyze "what-if" scenarios in order to reason about the impact of an update (before committing that update) is of paramount importance. Example applications include hypothetical database access, active database management systems, and version management, to name a few. The central thesis of the Heraclitus paradigm is to provide flexible support for applications such as these by elevating deltas, which represent updates proposed against the current database state, to be first-class citizens. Heraclitus[Alg,C] is a database programming language that extends C to incorporate the relational algebra and deltas. Operators are provided that enable the programmer to explicitly construct, combine, and access deltas. Most interesting is the when operator, that supports hypothetical access to a delta: the expression E when [sigma] yields the value that side effect free expression E would have if the value of delta expression [sigma] were applied to the current database state. This article presents a broad overview of the philosophy underlying the Heraclitus paradigm, and describes the design and prototype implementation of Heraclitus[Alg, C]. A model-independent formalism for the Heraclitus paradigm is also presented. To illustrate the utility of Heraclitus, the article presents an in-depth discussion of how Heraclitus[Alg, C] can be used to specify, and thereby implement, a wide range of execution models for rule application in active databases; this includes both prominent execution models presented in the literature, and more recent "customized" execution models with novel features.

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 3673 KB]

References

[Abiteboul 1988]
Serge Abiteboul: Updates, A New Frontier. ICDT 1988: 1-18 BibTeX
[Abiteboul et al. 1994]
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX
[Atkinson and Buneman 1987]
Malcolm P. Atkinson, Peter Buneman: Types and Persistence in Database Programming Languages. ACM Comput. Surv. 19(2): 105-190(1987) BibTeX
[Beeri and Milo 1991]
Catriel Beeri, Tova Milo: A Model for Active Object Oriented Databases. VLDB 1991: 337-349 BibTeX
[Bonner 1995]
...
[Bonner 1990]
Anthony J. Bonner: Hypothetical Datalog: Complexity and Expressibility. Theor. Comput. Sci. 76(1): 3-51(1990) BibTeX
[Boucelma et al. 1995]
...
[Bratbergsengen 1984]
Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 BibTeX
[Cacace et al. 1990]
Filippo Cacace, Stefano Ceri, Stefano Crespi-Reghizzi, Letizia Tanca, Roberto Zicari: Integrating Object-Oriented Data Modeling with a Rule-Based Programming Paradigm. SIGMOD Conference 1990: 225-236 BibTeX
[Carey et al. 1986]
Michael J. Carey, David J. DeWitt, Joel E. Richardson, Eugene J. Shekita: Object and File Management in the EXODUS Extensible Database System. VLDB 1986: 91-100 BibTeX
[Ceri and Widom 1991]
Stefano Ceri, Jennifer Widom: Deriving Production Rules for Incremental View Maintenance. VLDB 1991: 577-589 BibTeX
[Chen et al. 1995]
I-Min A. Chen, Richard Hull, Dennis McLeod: An Execution Model for Limited Ambiguity Rules and Its Application to Derived Data Update. ACM Trans. Database Syst. 20(4): 365-413(1995) BibTeX
[Chen et al. 1994]
I-Min A. Chen, Richard Hull, Dennis McLeod: Local Ambiguity and Derived Data Update. RIDE-ADS 1994: 77-86 BibTeX
[Chou et al. 1985]
Hong-Tai Chou, David J. DeWitt, Randy H. Katz, Anthony C. Klug: Design and Implementation of the Wisconsin Storage System. Softw., Pract. Exper. 15(10): 943-962(1985) BibTeX
[Cohen 1989]
Donald Cohen: Compiling Complex Database Transition Triggers. SIGMOD Conference 1989: 225-234 BibTeX
[Cohen 1986]
...
[Collet et al. 1994]
...
[Dalrymple 1995]
...
[Dayal et al. 1988]
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
[de Maindreville and Simon 1988]
Christophe de Maindreville, Eric Simon: Modelling Non Deterministic Queries and Updates in Deductive Databases. VLDB 1988: 395-406 BibTeX
[Derr et al. 1993]
Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: Design and Implementation of the Glue-Nail Database System. SIGMOD Conference 1993: 147-156 BibTeX
[DeWitt and Gerber 1985]
David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164 BibTeX
[DeWitt et al. 1990]
David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, Rick Rasmussen: The Gamma Database Machine Project. IEEE Trans. Knowl. Data Eng. 2(1): 44-62(1990) BibTeX
[DeWitt et al. 1984]
David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 BibTeX
[Doherty and Hull 1995]
Michael Doherty, Richard Hull: Towards a Framework for Efficient Management of Potentially Conflicting Database Updates. DS-6 1995: 317-344 BibTeX
[Doherty et al. 1995a]
Michael Doherty, Richard Hull, Marcia A. Derr, Jacques Durand: On Detecting Conflict Between Proposed Updates. DBPL 1995: 7 BibTeX
[Doherty et al. 1995b]
...
[Escobar-Molano et al. 1996]
Martha Escobar-Molano, Shahram Ghandeharizadeh, Doug Ierardi: An Optimal Resource Scheduler for Continuous Display of Structured Video Objects. IEEE Trans. Knowl. Data Eng. 8(3): 508-511(1996) BibTeX
[Eswaran et al. 1976]
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
[Gabbay 1985]
Dov M. Gabbay: N-Prolog: An Extension of Prolog with Hypothetical Implication II - Logical Foundations, and Negation as Failure. J. Log. Program. 2(4): 251-283(1985) BibTeX
[Gatziu and Dittrich 1994]
Stella Gatziu, Klaus R. Dittrich: Detecting Composite Events in Active Database Systems Using Petri Nets. RIDE-ADS 1994: 2-9 BibTeX
[Gehani and Jagadish 1991]
Narain H. Gehani, H. V. Jagadish: Ode as an Active Database: Constraints and Triggers. VLDB 1991: 327-336 BibTeX
[Ghandeharizadeh 1995]
...
[Ghandeharizadeh et al. 1993]
Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs, Jaime Castillo, Martha Escobar-Molano, Shih-Hui Lu, Junhui Luo, Chiu Tsang, Gang Zhou: On Implementing a Language for Specifying Active Database Execution Models. VLDB 1993: 441-454 BibTeX
[Ghandeharizadeh et al. 1992]
Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs: Implementation of Delayed Updates in Heraclitus. EDBT 1992: 261-276 BibTeX
[Gray and Reuter 1993]
Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX
[Hanson 1989]
Eric N. Hanson: An Initial Report on The Design of Ariel: A DBMS With an Integrated Production Rule System. SIGMOD Record 18(3): 12-19(1989) BibTeX
[Hanson and Widom 1992]
...
[Heineman et al. 1992]
...
[Hsu et al. 1988]
Meichun Hsu, Rivka Ladin, Dennis R. McCarthy: An Execution Model for Active Data Base Management Systems. JCDKB 1988: 171-179 BibTeX
[Hull and Jacobs 1991]
Richard Hull, Dean Jacobs: Language Constructs for Programming Active Databases. VLDB 1991: 455-467 BibTeX
[Hull and King 1987]
Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987) BibTeX
[Hull and Zhou 1995]
Richard Hull, Gang Zhou: A Framework for Supporting Data Integration Using the Materialized and Virtual Approaches. SIGMOD Conference 1996: 481-492 BibTeX
[Imielinski and Naqvi 1988]
Tomasz Imielinski, Shamim A. Naqvi: Explicit Control of Logic Programs Through Rule Algebra. PODS 1988: 103-116 BibTeX
[Jacobs and Hull 1991]
Dean Jacobs, Richard Hull: Database Programming with Delayed Updates. DBPL 1991: 416-428 BibTeX
[Kitsuregawa et al. 1983]
Masaru Kitsuregawa, Hidehiko Tanaka, Tohru Moto-Oka: Application of Hash to Data Base Machine and Its Architecture. New Generation Comput. 1(1): 63-74(1983) BibTeX
[Lloyd 1987]
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX
[McCarthy and Dayal 1989]
Dennis R. McCarthy, Umeshwar Dayal: The Architecture Of An Active Data Base Management System. SIGMOD Conference 1989: 215-224 BibTeX
[Morgenstern 1983]
Matthew Morgenstern: Active Databases as a Paradigm for Enhanced Computing Environments. VLDB 1983: 34-42 BibTeX
[Ramakrishnan et al. 1992]
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: CORAL - Control, Relations and Logic. VLDB 1992: 238-250 BibTeX
[Ramakrishnan et al. 1993]
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri: Implementation of the CORAL Deductive Database System. SIGMOD Conference 1993: 167-176 BibTeX
[Schmidt 1977]
Joachim W. Schmidt: Some High Level Language Constructs for Data of Type Relation. ACM Trans. Database Syst. 2(3): 247-261(1977) BibTeX
[Schneider and DeWitt 1989]
Donovan A. Schneider, David J. DeWitt: A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment. SIGMOD Conference 1989: 110-121 BibTeX
[Severance and Lohman 1976]
Dennis G. Severance, Guy M. Lohman: Differential Files: Their Application to the Maintenance of Large Databases. ACM Trans. Database Syst. 1(3): 256-267(1976) BibTeX
[Shapiro 1986]
Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) BibTeX
[Simon and de Maindreville 1988]
Eric Simon, Christophe de Maindreville: Deciding Whether a Production Rule is Relational Computable. ICDT 1988: 205-222 BibTeX
[Simon and Kiernan 1995]
...
[Stonebraker 1992]
Michael Stonebraker: The Integration of Rule Systems and Database Systems. IEEE Trans. Knowl. Data Eng. 4(5): 415-423(1992) BibTeX
[Stonebraker et al. 1990]
Michael Stonebraker, Anant Jhingran, Jeffrey Goh, Spyros Potamianos: On Rules, Procedures, Caching and Views in Data Base Systems. SIGMOD Conference 1990: 281-290 BibTeX
[Stoy 1977]
...
[Widom 1993]
Jennifer Widom: The Starburst Active Database Rule System. IEEE Trans. Knowl. Data Eng. 8(4): 583-595(1996) BibTeX
[Widom and Ceri 1995]
Jennifer Widom, Stefano Ceri (Eds.): Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996, ISBN 1-55860-304-2
Contents BibTeX
[Widom and Finkelstein 1990]
Jennifer Widom, Sheldon J. Finkelstein: Set-Oriented Production Rules in Relational Database Systems. SIGMOD Conference 1990: 259-270 BibTeX
[Woodfill and Stonebraker 1983]
John Woodfill, Michael Stonebraker: An Implementation of Hypothetical Relations. VLDB 1983: 157-166 BibTeX
[Zhou and Hsu 1990]
Yuli Zhou, Meichun Hsu: A Theory for Rule Triggering Systems. EDBT 1990: 407-421 BibTeX
[Zhou et al. 1994]
...
[Zhou et al. 1995]
Gang Zhou, Richard Hull, Roger King, Jean-Claude Franchitti: Using Object Matching and Materialization to Integrate Heterogeneous Databases. CoopIS 1995: 4-18 BibTeX

Referenced by

  1. Sudarshan S. Chawathe, Serge Abiteboul, Jennifer Widom: Representing and Querying Changes in Semistructured Data. ICDE 1998: 4-13
  2. Timothy Griffin, Richard Hull: A Framework for Implementing Hypothetical Queries. SIGMOD Conference 1997: 231-242
  3. Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh, Tolga Yurek: Efficient View Maintenance at Data Warehouses. SIGMOD Conference 1997: 417-427
  4. Richard Hull: Managing Semantic Heterogeneity in Databases: A Theoretical Perspective. PODS 1997: 51-61
  5. Richard Hull, Gang Zhou: A Framework for Supporting Data Integration Using the Materialized and Virtual Approaches. SIGMOD Conference 1996: 481-492
  6. Michael Doherty, Richard Hull, Mohammed Rupawalla: Structures for Manipulating Proposed Updates in Object-Oriented Databases. SIGMOD Conference 1996: 306-317
  7. Latha S. Colby, Timothy Griffin, Leonid Libkin, Inderpal Singh Mumick, Howard Trickey: Algorithms for Deferred View Maintenance. SIGMOD Conference 1996: 469-480
  8. I-Min A. Chen, Richard Hull, Dennis McLeod: An Execution Model for Limited Ambiguity Rules and Its Application to Derived Data Update. ACM Trans. Database Syst. 20(4): 365-413(1995)
  9. Gang Zhou, Richard Hull, Roger King, Jean-Claude Franchitti: Data Integration and Warehousing Using H2O. IEEE Data Eng. Bull. 18(2): 29-40(1995)
  10. Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995)
  11. Michael Doherty, Richard Hull, Marcia A. Derr, Jacques Durand: On Detecting Conflict Between Proposed Updates. DBPL 1995: 7
  12. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
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:20 2008