Simplification Rules and Complete Axiomatization for Relational Update Transactions.

Dino Karabeg, Victor Vianu: Simplification Rules and Complete Axiomatization for Relational Update Transactions. ACM Trans. Database Syst. 16(3): 439-475(1991)
  author    = {Dino Karabeg and
               Victor Vianu},
  title     = {Simplification Rules and Complete Axiomatization for Relational
               Update Transactions},
  journal   = {ACM Trans. Database Syst.},
  volume    = {16},
  number    = {3},
  year      = {1991},
  pages     = {439-475},
  ee        = {, db/journals/tods/KarabegV91.html},
  bibsource = {DBLP,}


Relational update transactions consisting of line programs of inserts, deletes, and modifications are studied with respect to equivalence and simplification. A sound and complete set of axioms for proving transaction equivalence is exhibited. The axioms yield a set of simplification rules that can be used to optimize efficiently a large class of transactions of practical interest. The simplification rules are particularly well suited to a dynamic environment where transactions are presented in an on-line fashion, and where the time available for optimization may consist of arbitrarily short and sparse intervals.

Copyright © 1991 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 2, TODS 1991-1995, TKDE 1989-1992" 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, 2257 KB]


Serge Abiteboul, Victor Vianu: Equivalence and optimization of relational transactions. J. ACM 35(1): 70-120(1988) BibTeX
Serge Abiteboul, Victor Vianu: Transactions in Relational Databases (Preliminary Report). VLDB 1984: 46-56 BibTeX
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
Dino Karabeg, Victor Vianu: Parallel Update Transactions (Extended Abstract). ICDT 1988: 307-321 BibTeX
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980

Referenced by

  1. Michael Benedikt, Timothy Griffin, Leonid Libkin: Verifiable Properties of Database Transactions. PODS 1996: 117-127
  2. Weidong Chen: Declarative Updates of Relational Databases. ACM Trans. Database Syst. 20(1): 42-70(1995)
  3. Danilo Montesi, Riccardo Torlone: A Rewriting Technique for the Analysis and the Optimization of Active Databases. ICDT 1995: 238-251
  4. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:39:11 2008