Deciding Boundedness for Uniformly Connected Datalog Programs.

@inproceedings{DBLP:conf/icdt/Guessarian90,
  author    = {Ir{\`e}ne Guessarian},
  editor    = {Serge Abiteboul and
               Paris C. Kanellakis},
  title     = {Deciding Boundedness for Uniformly Connected Datalog Programs},
  booktitle = {ICDT'90, Third International Conference on Database Theory, Paris,
               France, December 12-14, 1990, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {470},
  year      = {1990},
  isbn      = {3-540-53507-1},
  pages     = {395-405},
  ee        = {db/conf/icdt/Guessarian90.html},
  crossref  = {DBLP:conf/icdt/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

ACM SIGMOD Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-2 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

References

[AB89]

Serge Abiteboul: Boundedness is Undecidable for Datalog Programs with a Single Recursive Rule. Inf. Process. Lett. 32(6): 281-287(1989) BibTeX

[AG89]

Miklós Ajtai, Yuri Gurevich: Datalog vs. First-Order Logic. FOCS 1989: 142-147 BibTeX

[BKBR87]

Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226 BibTeX

[BR88]

François Bancilhon, Raghu Ramakrishnan: Performance Evaluation of Data Intensive Logic Programs. Foundations of Deductive Databases and Logic Programming. 1988: 439-517 BibTeX

[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 BibTeX

[GMSV87]

Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115 BibTeX

[Io85]

Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226 BibTeX

[K88]

Paris C. Kanellakis: Logic Programming and Parallel Complexity. Foundations of Deductive Databases and Logic Programming. 1988: 547-585 BibTeX

[K89]

...

[KAb89]

Paris C. Kanellakis, Serge Abiteboul: Database Theory Column: Deciding Bounded Recursion in Database Logic Programs. SIGACT News 20(4): 17-23(1989) BibTeX

[NS86]

Jeffrey F. Naughton, Yehoshua Sagiv: A Decidable Class of Bounded Recursions. PODS 1987: 227-236 BibTeX

[Na89]

Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. J. Comput. Syst. Sci. 38(2): 259-289(1989) BibTeX

[Sa85]

Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180 BibTeX

[TW89]

...

[Ul89-1]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[Ul89-2]

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

[Va88]

Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351 BibTeX

Referenced by

1. Irène Guessarian, Jean-Eric Pin: Linearizing Some Recursive Logic Programs. IEEE Trans. Knowl. Data Eng. 7(1): 137-149(1995)
2. Ke Wang: Some Positive Results for Boundedness of Multiple Recursive Rules. ICDT 1995: 383-396
3. Ke Wang, Li-Yan Yuan: First-Order Logic Characterization of Program Properties. IEEE Trans. Knowl. Data Eng. 6(4): 518-533(1994)
4. Inderpal Singh Mumick, Oded Shmueli: Universal Finiteness and Satisfiability. PODS 1994: 190-200
5. Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Tools for Datalog Boundedness. PODS 1991: 1-12