Journal article icon

Journal article

The complexity and expressive power of limit Datalog

Abstract:

Motivated by applications in declarative data analysis, in this article, we study DatalogZ—an extension of Datalog with stratified negation and arithmetic functions over integers. This language is known to be undecidable, so we present the fragment of limit DatalogZ programs, which is powerful enough to naturally capture many important data analysis tasks. In limit DatalogZ, all intensional predicates with a numeric argument are limit predicates that keep maximal or minimal bounds on numeric ...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1145/3495009

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
Keble College
Role:
Author
Publisher:
Association for Computing Machinery
Journal:
Journal of the ACM More from this journal
Volume:
69
Issue:
1
Article number:
6
Publication date:
2021-12-22
Acceptance date:
2021-09-01
DOI:
EISSN:
1557-735X
ISSN:
0004-5411
Language:
English
Keywords:
Pubs id:
1207671
Local pid:
pubs:1207671
Deposit date:
2021-11-09

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP