Title :
DATALOG SIRUPs uniform boundedness is undecidable
Author :
Marcinkowski, Jerzy
Author_Institution :
Theor. of Comput. Sci. Group, Wroclaw Univ., Poland
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)
Keywords :
DATALOG; computational complexity; database theory; decidability; deductive databases; DATALOG; automated boundedness detection; database query language; parallel constant time; recursion; single rule programs; theory of deductive databases; undecidable; uniform boundedness; Computer science; Logic; Relational databases; Upper bound;
Conference_Titel :
Logic in Computer Science, 1996. LICS '96. Proceedings., Eleventh Annual IEEE Symposium on
Conference_Location :
New Brunswick, NJ
Print_ISBN :
0-8186-7463-6
DOI :
10.1109/LICS.1996.561299
