Static Analysis of Intensional Databases in U-Datalog.

@inproceedings{DBLP:conf/pods/BertinoC96,
  author    = {Elisa Bertino and
               Barbara Catania},
  editor    = {Richard Hull},
  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

[BC95]

...

[BCGM94]

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

[BGL91]

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

[BK94]

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

[BMM92]

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

[DMP93]

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

[JL87]

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

[KNZ89]

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

[Levy93]

...

[LMSS93]

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

[LS92]

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

[LS93]

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

[Shmu87]

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

[Shmu93]

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

[St90]

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

[Ull89]

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

[ZN94]

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

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)

Last update Fri May 25 08:32:50 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page