Static Analysis of Logical Languages with Deferred Update Semantics

Get BibTex-formatted data

Author

Elisa Bertino, Barbara Catania

Entry type

article

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 program evaluation. In logical update languages, an interesting problem is the detection of conflicting updates, inserting and deleting the same fact, for transactions based on set-oriented updates and active rules. In this paper, we investigate this topic in the context of the U-Datalog language, a set-oriented update language for deductive databases [12], based on a deferred semantics. We first formally define relevant properties of U-Datalog programs, mainly related to update conflicts. Then, we prove that the defined properties are decidable and we propose an algorithm to detect such conditions. Finally, we show how the proposed techniques can be applied to other logical update languages. Our results are based on the concept of labeling and query-tree, first used in [30], [31], [32].

Date

2003 – 03

URL

http://csdl2.computer.org/pers ... 10.1109/TKDE.2003.1185841

Journal

IEEE Transactions on Knowledge and Data Engineering

Key alpha

Bertino

Pages

386-404

Affiliation

Purdue University

Publication Date

2003-03-00

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Article{ Bertino,
	title = "Static Analysis of Logical Languages with Deferred Update Semantics",
	author = "Elisa Bertino, Barbara Catania",
	year = "2003",
	month = "03",
	journal = "IEEE Transactions on Knowledge and Data Engineering",
	pages = "386-404",
	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 program evaluation. In logical update languages, an interesting problem is the detection of conflicting updates, inserting and deleting the same fact, for transactions based on set-oriented updates and active rules. In this paper, we investigate this topic in the context of the U-Datalog language, a set-oriented update language for deductive databases [12], based on a deferred semantics. We first formally define relevant properties of U-Datalog programs, mainly related to update conflicts. Then, we prove that the defined properties are decidable and we propose an algorithm to detect such conditions. Finally, we show how the proposed techniques can be applied to other logical update languages. Our results are based on the concept of labeling and query-tree, first used in [30], [31], [32].",
	affiliation = "Purdue University",
	url = "http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/trans/tk/&toc=comp/trans/tk/2003/02/k2toc.xml&DOI=10.1109/TKDE.2003.1185841",
}