Data Sharing Analysis for a Database Programming Lanaguage via Abstract Interpretation.

Giuseppe Amato, Fosca Giannotti, Gianni Mainetto: Data Sharing Analysis for a Database Programming Lanaguage via Abstract Interpretation. VLDB 1993: 405-415

@inproceedings{DBLP:conf/vldb/AmatoGM93,
  author    = {Giuseppe Amato and
               Fosca Giannotti and
               Gianni Mainetto},
  editor    = {Rakesh Agrawal and
               Se{\'a}n Baker and
               David A. Bell},
  title     = {Data Sharing Analysis for a Database Programming Lanaguage via
               Abstract Interpretation},
  booktitle = {19th International Conference on Very Large Data Bases, August
               24-27, 1993, Dublin, Ireland, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1993},
  isbn      = {1-55860-152-X},
  pages     = {405-415},
  ee        = {db/conf/vldb/AmatoGM93.html},
  crossref  = {DBLP:conf/vldb/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper presents an experiment in using a formal techniqne for static program analysis, based on abstract interpretation, in the context of persistent programming languages. The aim of the analysis is to detect opportunities for safe parallelism for transaction operation scheduling. Transaction operations can he safely interleaved when there is no overlapping among their readsets and writesets. A non-standard interpreter performs the analysis. This interpreter, given the text of a transaction and a representation of the data stored in the database automatically derives in a finite time an approximation of the readset and writeset of the analysed transaction. Information obtained from the non-standard interpretation is provided to the scheduler before beginning the execution of transaction operations. In this way, we obtain a scheduler that realises a conservative two-phase locking protocol for persistent programming language transactions. We apply the analysis to a language that is a significant subset of Galileo. The goal of the analysis is to detect the accesses solely to shareable and modifiable persistent data.

Copyright © 1993 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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" 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
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" 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
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Rakesh Agrawal, Seán Baker, David A. Bell (Eds.): 19th International Conference on Very Large Data Bases, August 24-27, 1993, Dublin, Ireland, Proceedings. Morgan Kaufmann 1993, ISBN 1-55860-152-X
Contents

References

[1]: ...
[2]: Samson Abramsky: Abstract Interpretation, Logical Relations and Kan Extensions. J. Log. Comput. 1(1): 5-40(1990)
[3]: Antonio Albano, Luca Cardelli, Renzo Orsini: Galileo: A Strongly-Typed, Interactive Conceptual Language. ACM Trans. Database Syst. 10(2): 230-260(1985)
[4]: Giuseppe Amato, Fosca Giannotti, Gianni Mainetto: Analysis of Concurrent Transactions in a Functional Database Programming Language. WSA 1992: 174-184
[5]: ...
[6]: Malcolm P. Atkinson, Peter Buneman: Types and Persistence in Database Programming Languages. ACM Comput. Surv. 19(2): 105-190(1987)
[7]: Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents
[8]: Patrick Cousot, Radhia Cousot: Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. POPL 1977: 238-252
[9]: ...
[10]: Patrick Cousot, Radhia Cousot: Abstract Interpretation Frameworks. J. Log. Comput. 2(4): 511-547(1992)
[11]: Alain Deutsch: On Determining Lifetime and Aliasing of Dynamically Allocated Data in Higher-Order Functional Specifications. POPL 1990: 157-168
[12]: David J. DeWitt, Philippe Futtersack, David Maier, Fernando Vélez: A Study of Three Alternative Workstation-Server Architectures for Object Oriented Database Systems. VLDB 1990: 107-121
[13]: ...
[14]: ...
[15]: ...