Title :
Datalog vs. first-order logic
Author :
Ajtai, Miklos ; Gurevich, Yuri
Author_Institution :
IBM Almaden Res. Center, San Jose, CA, USA
fDate :
30 Oct-1 Nov 1989
Abstract :
The relation between the expressive power of datalog and that of first-order languages, is clarified. It is then proved that every first-order expressible datalog query is bounded. A form of compactness theorem for finite structure implied by this result is examined, and counterexamples to natural generalizations of the above result are given
Keywords :
database theory; formal languages; formal logic; query languages; relational databases; bounded; compactness theorem; finite structure; first-order expressible datalog query; first-order languages; first-order logic; Database languages; Logic; Relational databases;
Conference_Titel :
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location :
Research Triangle Park, NC
Print_ISBN :
0-8186-1982-1
DOI :
10.1109/SFCS.1989.63469
