Logic in Computer Science (LICS 1996)

Paper: DATALOG SIRUPs uniform boundedness is undecidable (at LICS 1996)

Authors: Jerzy Marcinkowski

Abstract

DATALOG is the paradigmatic database query language. If it is possible to eliminate recursion from a DATALOG program then it is uniformly bounded. Since uniformly bounded programs can be executed in parallel constant time, the possibility of automated boundedness detection is an important issue, and has been studied in many papers. In this paper we solve one of the most famous open problems in the theory of deductive databases (see e.g. P.C. Kanellakis, Elements of Relational Database Theory in Handbook of Theoretical Computer Science) showing that uniform boundedness is undecidable for single rule programs (called also sirups).

BibTeX

  @InProceedings{Marcinkowski-DATALOGSIRUPsunifor,
    author = 	 {Jerzy Marcinkowski},
    title = 	 {DATALOG SIRUPs uniform boundedness is undecidable},
    booktitle =  {Proceedings of the Eleventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1996},
    year =	 1996,
    editor =	 {Edmund M. Clarke},
    month =	 {July}, 
    pages =      {13-24},
    location =   {New Brunswick, NJ, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }