ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Decidability and Undecidability Results for the Termination Problem of Active Database Rules.

James Bailey, Guozhu Dong, Kotagiri Ramamohanarao: Decidability and Undecidability Results for the Termination Problem of Active Database Rules. PODS 1998: 264-273
@inproceedings{DBLP:conf/pods/BaileyDR98,
  author    = {James Bailey and
               Guozhu Dong and
               Kotagiri Ramamohanarao},
  title     = {Decidability and Undecidability Results for the Termination Problem
               of Active Database Rules},
  booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-996-3},
  pages     = {264-273},
  ee        = {http://doi.acm.org/10.1145/275487.275517, db/conf/pods/BaileyDR98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Active database systems enhance the functionality of traditional databases through the use of active rules or `triggers'. One of the principal questions for such systems is that of termination - is it possible for the rules to recursively activate one another indefinitely, given an initial triggering event. In this paper, we study the decidability of the termination problem, our aim being to delimit the boundary between the decidable and the undecidable. We present two families of rule languages, the one literal languages where each update is permitted to have just one atom in its body, and the unary languages where only unary relations may be updated, but higher arity relations may be accessed through views. Within each of these, we identify members close to the boundary of (un)decidability. Our context is similar to the while query language and the dynamics gives an interesting contrast to Datalog with negation; our results shed insights on the power of triggers as well as comparison of the termination problem to boundedness and query containment.

Copyright © 1998 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 ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington. ACM Press 1998, ISBN 0-89791-996-3
Contents BibTeX

Online Edition: ACM Digital Library

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

References

[1]
Serge Abiteboul: Boundedness is Undecidable for Datalog Programs with a Single Recursive Rule. Inf. Process. Lett. 32(6): 281-287(1989) BibTeX
[2]
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX
[3]
Serge Abiteboul, Victor Vianu: Procedural Languages for Database Queries and Updates. J. Comput. Syst. Sci. 41(2): 181-229(1990) BibTeX
[4]
Serge Abiteboul, Victor Vianu: Computing with First-Order Logic. J. Comput. Syst. Sci. 50(2): 309-335(1995) BibTeX
[5]
Alexander Aiken, Jennifer Widom, Joseph M. Hellerstein: Behavior of Database Production Rules: Termination, Confluence, and Observable Determinism. SIGMOD Conference 1992: 59-68 BibTeX
[6]
...
[7]
James Bailey, Guozhu Dong, Kotagiri Ramamohanarao: Structural Issues in Active Rule Systems. ICDT 1997: 203-214 BibTeX
[8]
Elena Baralis, Jennifer Widom: An Algebraic Approach to Rule Analysis in Expert Database Systems. VLDB 1994: 475-486 BibTeX
[9]
Sara Comai, Letizia Tanca: Using the Properties of Datalog to Prove Termination and Confluence in Active Databases. Rules in Database Systems 1997: 100-117 BibTeX
[10]
Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115 BibTeX
[11]
Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. J. ACM 40(3): 683-713(1993) BibTeX
[12]
Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Undecidable Boundedness Problems for Datalog Programs. J. Log. Program. 25(2): 163-190(1995) BibTeX
[13]
Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli: Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions. PODS 1993: 109-122 BibTeX
[14]
Bertram Ludäscher, Ulrich Hamann, Georg Lausen: A Logical Framework for Active Rules. COMAD 1995: 0- BibTeX
[15]
Philippe Picouet, Victor Vianu: Semantics and Expressiveness Issues in Active Databases. PODS 1995: 126-138 BibTeX
[16]
...
[17]
Leonie van der Voort, Arno Siebes: Termination and Confluence of Rule Execution. CIKM 1993: 245-255 BibTeX
[18]
Jennifer Widom, Stefano Ceri (Eds.): Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996, ISBN 1-55860-304-2
Contents BibTeX
[19]
Yuli Zhou, Meichun Hsu: A Theory for Rule Triggering Systems. EDBT 1990: 407-421 BibTeX

Referenced by

  1. James Bailey, Guozhu Dong: Decidability of First-Order Logic Queries over Views. ICDT 1999: 83-99
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:21 2009