Static Analysis of Intensional Databases in U-Datalog.

@inproceedings{DBLP:conf/pods/BertinoC96,
  author    = {Elisa Bertino and
               Barbara Catania},
  title     = {Static Analysis of Intensional Databases in U-Datalog},
  booktitle = {Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 3-5, 1996, Montreal,
               Canada},
  publisher = {ACM Press},
  year      = {1996},
  isbn      = {0-89791-781-2},
  pages     = {202-212},
  ee        = {http://doi.acm.org/10.1145/237661.237711, db/conf/pods/BertinoC96.html},
  crossref  = {DBLP:conf/pods/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Static analysis of declarative languages deals with the detection, at compile time, of program properties that can be used to better understand the program semantics and to improve the efficiency of the program evaluation. In logical update languages, an interesting problem is the detection of situations that may lead to inconsistent updates (insertion and deletion of the same fact), generating non-deterministic behavior. The analysis of this problem for transactions based on set-oriented updates is not a simple task.

In this paper, we investigate this topic in the context of the U-Datalog language, a set-oriented update language for deductive databases [BMM92]. We first formally define relevant properties of U-Datalog programs, mainly to conflicts leading to non-deterministic results. Then, we prove that the presented properties are decidable. Our results are based on an analysis tool, the query tree, first used in [LS92].

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.

• 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/...

• 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

Online Edition: ACM Digital Library

References

[AL91]

...

[AV87]

Serge Abiteboul, Victor Vianu: A Transcation Language Complete for Database Update and Specification. PODS 1987: 260-268 BibTeX

[BC95]

...

[BCGM94]

Elisa Bertino, Barbara Catania, Giovanna Guerrini, Danilo Montesi: Transaction Optimization in Rule Databases. RIDE-ADS 1994: 137-145 BibTeX

[BGL91]

Annalisa Bossi, Maurizio Gabbrielli, Giorgio Levi, Maria Chiara Meo: Contributions to the Semantics of Open Logic Programs. FGCS 1992: 570-580 BibTeX

[BK94]

Anthony J. Bonner, Michael Kifer: An Overview of Transaction Logic. Theor. Comput. Sci. 133(2): 205-265(1994) BibTeX

[BMM92]

Elisa Bertino, Maurizio Martelli, Danilo Montesi: Modelling Database Updates with Constraint Logic Programming. FMLDO 1992: 121-132 BibTeX

[DMP93]

Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: Design and Implementation of the Glue-Nail Database System. SIGMOD Conference 1993: 147-156 BibTeX

[JL87]

Joxan Jaffar, Jean-Louis Lassez: Constraint Logic Programming. POPL 1987: 111-119 BibTeX

[KNZ89]

Ravi Krishnamurthy, Shamim A. Naqvi, Carlo Zaniolo: Database Transactions in LDL. NACLP 1989: 795-815 BibTeX

[Levy93]

...

[LMSS93]

Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli: Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions. PODS 1993: 109-122 BibTeX

[LS92]

Alon Y. Levy, Yehoshua Sagiv: Constraints and Redundancy in Datalog. PODS 1992: 67-80 BibTeX

[LS93]

Christian Laasch, Marc H. Scholl: Deterministic Semantics of Set-Oriented Update Sequences. ICDE 1993: 4-13 BibTeX

[Shmu87]

Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX

[Shmu93]

Oded Shmueli: Equivalence of DATALOG Queries is Undecidable. J. Log. Program. 15(3): 231-241(1993) BibTeX

[St90]

Oded Shmueli, Shalom Tsur: Logical Diagnosis of LDL Programs. ICLP 1990: 112-129 BibTeX

[Ull89]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[ZN94]

Du Zhang, Doan Nguyen: PREPARE: A Toll for Knowledge Base Verification. IEEE Trans. Knowl. Data Eng. 6(6): 983-989(1994) BibTeX

Referenced by

1. Danilo Montesi, Elisa Bertino, Maurizio Martelli: Transactions and Updates in Deductive Databases. IEEE Trans. Knowl. Data Eng. 9(5): 784-797(1997)