Applying an Update Method to a Set of Receivers.

Marc Andries, Luca Cabibbo, Jan Paredaens, Jan Van den Bussche: Applying an Update Method to a Set of Receivers. PODS 1995: 208-218

@inproceedings{DBLP:conf/pods/AndriesCPB95,
  author    = {Marc Andries and
               Luca Cabibbo and
               Jan Paredaens and
               Jan Van den Bussche},
  title     = {Applying an Update Method to a Set of Receivers},
  booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 22-25, 1995, San Jose,
               California},
  publisher = {ACM Press},
  year      = {1995},
  isbn      = {0-89791-730-8},
  pages     = {208-218},
  ee        = {http://doi.acm.org/10.1145/212433.220216, db/conf/pods/AndriesCPB95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In the context of object databases, we study the application of an update method to a collection of receivers rather than to a single one. The obvious strategy of applying the update to the receivers one after the other, in some arbitrary order, brings up the problem of order independence. On a very general level, we investigate how update behavior can be analyzed in terms of certain schema annotations called colorings. We are able to characterize those colorings which always describe order-independent updates. We also consider a more specific model of update methods implemented in the relational algebra. Order independence of such algebraic methods is undecidable in general, but decidable if the expressions used are positive. Finally, we consider an alternative parallel strategy for set-oriented application of algebraic methods and compare and relate it to the sequential strategy.

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

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 22-25, 1995, San Jose, California. ACM Press 1995, ISBN 0-89791-730-8
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1110 KB]

References

[1]: Serge Abiteboul, Victor Vianu: Procedural Languages for Database Queries and Updates. J. Comput. Syst. Sci. 41(2): 181-229(1990)
[2]: Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979)
[3]: Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120
[4]: Val Tannen, Peter Buneman, Shamim A. Naqvi: Structural Recursion as a Query Language. DBPL 1991: 9-19
[5]: Val Tannen, Ramesh Subrahmanyam: Logical and Computational Aspects of Programming with Sets/Bags/Lists. ICALP 1991: 60-75
[6]: ...
[7]: Edward P. F. Chan: Containment and Minimization of Positive Conjunctive Queries in OODB's. PODS 1992: 202-211
[8]: Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62
[9]: Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90
[10]: Richard Hull, Jianwen Su: On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions (Extended Abstract). SIGMOD Conference 1989: 147-158
[11]: Richard Hull, Masatoshi Yoshikawa: ILOG: Declarative Creation and Manipulation of Object Identifiers. VLDB 1990: 455-468
[12]: David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. J. Comput. Syst. Sci. 28(1): 167-189(1984)
[13]: Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988)
[14]: Christian Laasch, Marc H. Scholl: Deterministic Semantics of Set-Oriented Update Sequences. ICDE 1993: 4-13
[15]: Peter Lyngbæk, Victor Vianu: Mapping a Semantic Database Model to the Relational Model. SIGMOD Conference 1987: 132-142
[16]: David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979)
[17]: Xiaolei Qian: The Expressive Power of the Bounded-Iteration Construct. Acta Inf. 28(7): 631-656(1991)
[18]: Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980)
[19]: ...
[20]: Eric Simon, Christophe de Maindreville: Deciding Whether a Production Rule is Relational Computable. ICDT 1988: 205-222

Referenced by

Gisela Fischer, Karl Aberer: Admissible Record-Oriented Evaluation Plans for Declarative Updates. ADBIS 1997: 133-140