article

Datalog vs first-order logic

Authors:

Miklos Ajtai,

Yuri GurevichAuthors Info & Claims

Journal of Computer and System Sciences, Volume 49, Issue 3

Pages 562 - 588

https://doi.org/10.1016/S0022-0000(05)80071-6

Published: 01 December 1994 Publication History

Abstract

Our main result is that every datalog query expressible in first-order logic is bounded; in terms of classical model theory it is a kind of compactness theorem for finite structures. In addition, we give some counter-examples delimiting the main result.

References

[1]

Ajtai, M. and Gurevich, Y., Datalog vs. first-order logic. In: 30th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Amsterdam. pp. 142-147.

Digital Library

Google Scholar

[2]

Cosmadakis, S.S., On the first-order expressibility of recursive queries. In: Principles of Database Systems, ACM. pp. 311-323.

Crossref

Google Scholar

[3]

B. Courcelle, Private communication.

Google Scholar

[4]

Gaifman, H., On local and non-local properties. In: Stern, J. (Ed.), Proceedings of the Herbrand Symposium, Logic Colloquium '81, North-Holland.

Google Scholar

[5]

Y. Gurevich, Toward logic tailored for computational complexity, in -Computation and Proof Theory- (M. Richter et al., Ed.), Lecture Notes in Mathematics, Vol. 1104, pp. 175-216.

Crossref

Google Scholar

[6]

P. Kolaitis and M. Y. Vardi, Private communication.

Google Scholar

[7]

Robertson, N. and Seymour, P.D., Graph minors. III. Planar tree-width. J. Combin. Theory Ser. B. v36. 49-64.

Google Scholar

Cited By

View all

Ciatto GSabbatini FAgiollo AMagnini MOmicini A(2024)Symbolic Knowledge Extraction and Injection with Sub-symbolic Predictors: A Systematic Literature ReviewACM Computing Surveys10.1145/364510356:6(1-35)Online publication date: 8-Feb-2024
https://dl.acm.org/doi/10.1145/3645103
Fan ZKoutris POuyang XWijsen J(2023)LinCQA: Faster Consistent Query Answering with Linear Time GuaranteesProceedings of the ACM on Management of Data10.1145/35887181:1(1-25)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588718
Feng S(2023)The Expressive Power of Revised Datalog on Problems with Closure PropertiesLogic, Rationality, and Interaction10.1007/978-3-031-45558-2_9(109-125)Online publication date: 26-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-45558-2_9
Show More Cited By

Index Terms

Datalog vs first-order logic
1. Information systems
  1. Data management systems
    1. Query languages
2. Theory of computation
  1. Logic
  2. Theory and algorithms for application domains
    1. Database theory
      1. Database query languages (principles)

Recommendations

Datalog vs. first-order logic
SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer Science

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 ...
Proving Isomorphism of First-Order Logic Proof Systems in HOL
First-Order Modal Logic: Frame Definability and a Lindström Theorem

We generalize two well-known model-theoretic characterization theorems from propositional modal logic to first-order modal logic (FML, for short). We first study FML-definable frames and give a version of the Goldblatt---Thomason theorem for this logic. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 49, Issue 3

Dec. 1994

356 pages

ISSN:0022-0000

Editors:
Zvi Galil,
E. K. Blum
Univ. of Southern California, Los Angeles

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 December 1994

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ciatto GSabbatini FAgiollo AMagnini MOmicini A(2024)Symbolic Knowledge Extraction and Injection with Sub-symbolic Predictors: A Systematic Literature ReviewACM Computing Surveys10.1145/364510356:6(1-35)Online publication date: 8-Feb-2024
https://dl.acm.org/doi/10.1145/3645103
Fan ZKoutris POuyang XWijsen J(2023)LinCQA: Faster Consistent Query Answering with Linear Time GuaranteesProceedings of the ACM on Management of Data10.1145/35887181:1(1-25)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588718
Feng S(2023)The Expressive Power of Revised Datalog on Problems with Closure PropertiesLogic, Rationality, and Interaction10.1007/978-3-031-45558-2_9(109-125)Online publication date: 26-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-45558-2_9
Garg PSengamedu S(2022)Synthesizing code quality rules from examplesProceedings of the ACM on Programming Languages10.1145/35633506:OOPSLA2(1757-1787)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563350
Magnini MCiatto GOmicini A(2022)On the Design of PSyKI: A Platform for Symbolic Knowledge Injection into Sub-symbolic PredictorsExplainable and Transparent AI and Multi-Agent Systems10.1007/978-3-031-15565-9_6(90-108)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-15565-9_6
Bourhis PLeclère MMugnier MTison SUlliana FGalois L(2019)Oblivious and semi-oblivious boundedness for existential rulesProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367243.3367258(1581-1587)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367243.3367258
Barceló PBerger GLutz CPieris A(2018)First-order rewritability of frontier-guarded ontology-mediated queriesProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304889.3304896(1707-1713)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304889.3304896
Zhang HZhang Y(2017)Expressiveness of Logic Programs under the General Stable Model SemanticsACM Transactions on Computational Logic10.1145/303924418:2(1-28)Online publication date: 5-May-2017
https://dl.acm.org/doi/10.1145/3039244
Zhou YZhang Y(2017)A progression semantics for first-order logic programsArtificial Intelligence10.1016/j.artint.2017.06.001250:C(58-79)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1016/j.artint.2017.06.001
Bienvenu MHansen PLutz CWolter F(2016)First order-rewritability and containment of conjunctive queries in horn description logicsProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060755(965-971)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3060621.3060755
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations