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

Universal Finiteness and Satisfiability.

Inderpal Singh Mumick, Oded Shmueli: Universal Finiteness and Satisfiability. PODS 1994: 190-200
@inproceedings{DBLP:conf/pods/MumickS94,
  author    = {Inderpal Singh Mumick and
               Oded Shmueli},
  title     = {Universal Finiteness and Satisfiability},
  booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 24-26, 1994, Minneapolis,
               Minnesota},
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {190-200},
  ee        = {http://doi.acm.org/10.1145/182591.182612, db/conf/pods/pods94-190.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The problem of determining whether, for every extensional database, a given predicate in a given program has a finite number of derivations is called the universal finiteness problem. The problem of determining whether a given predicate in a given program has a non-empty extension for some extensional database is called the satisfiability problem. We show that the universal finiteness problem can be reduced to the satisfiability problem. Thus all decidability results for satisfiability can be applied to universal finiteness - for example, we can infer that the universal finiteness problem is decidable for Datalog extended with negation on base predicates. The satisfiability problem can be easily reduced to the universal finiteness problem, so that all undecidability results for satisfiability can be applied to universal finiteness. For example we can infer that the universal finiteness problem is undecidable for Datalog extended with stratified negation.

Many recursive programs have infinite number of derivations only when edb relations have data cycles. It is thus of particular interest to study universal finiteness in the presence of acyclicity constraints on the edb relations. We define acyclicity constraints in terms of non-satisfiability of a specific recursive program. We show that both the problems of universal finiteness and satisfiability of Datalog in the presence of acyclicity constraints (on one or more edb relations) remain decidable for a language L whenever the problems are decidable for language L in absence of such constraints. We also show that the problems are undecidable for arbitrary constraints expressed in terms of non-satisfiability of a recursive program.

Copyright © 1994 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 ...

Printed Edition

Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota. ACM Press 1994, ISBN 0-89791-642-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1111 KB]

References

[Abi89]
Serge Abiteboul: Boundedness is Undecidable for Datalog Programs with a Single Recursive Rule. Inf. Process. Lett. 32(6): 281-287(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CGKV88]
Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, Moshe Y. Vardi: Decidable Optimization Problems for Database Logic Programs (Preliminary Report). STOC 1988: 477-490 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GKM92]
Ashish Gupta, Dinesh Katiyar, Inderpal Singh Mumick: Counting solutions to the View Maintenance Problem. Workshop on Deductive Databases, JICSLP 1992: 185-194 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GMSV87]
Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GMS93]
Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gue90]
Irène Guessarian: Deciding Boundedness for Uniformly Connected Datalog Programs. ICDT 1990: 395-405 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HKMV91]
Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Tools for Datalog Boundedness. PODS 1991: 1-12 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ISO93]
...
[KKR90]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LMSS93]
Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli: Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions. PODS 1993: 109-122 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LS92]
Alon Y. Levy, Yehoshua Sagiv: Constraints and Redundancy in Datalog. PODS 1992: 67-80 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MFPR90]
Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MPR90]
Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MR89]
Michael J. Maher, Raghu Ramakrishnan: Déjà Vu in Fixpoints of Logic Programs. NACLP 1989: 963-980 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MS93]
Inderpal Singh Mumick, Oded Shmueli: Finiteness Properties of Database Queries. Australian Database Conference 1993: 274-288 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mum91]
...
[Nau86]
Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. J. Comput. Syst. Sci. 38(2): 259-289(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NS87]
Jeffrey F. Naughton, Yehoshua Sagiv: A Decidable Class of Bounded Recursions. PODS 1987: 227-236 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shm87]
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SS86]
...
[UVG88]
Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. Algorithmica 3: 5-42(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[vdM90]
...
[vdM92]
...
[Var88]
Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:19:57 2010 by Michael Ley (ley@uni-trier.de)