DocumentCode
2101249
Title
Datalog vs. first-order logic
Author
Ajtai, Miklos ; Gurevich, Yuri
Author_Institution
IBM Almaden Res. Center, San Jose, CA, USA
fYear
1989
fDate
30 Oct-1 Nov 1989
Firstpage
142
Lastpage
147
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location
Research Triangle Park, NC
Print_ISBN
0-8186-1982-1
Type
conf
DOI
10.1109/SFCS.1989.63469
Filename
63469
Link To Document