Symmetric Linear Arc Monadic Datalog and Gadget Reductions

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Contributors

Abstract

A Datalog program solves a constraint satisfaction problem (CSP) if and only if it derives the goal predicate precisely on the unsatisfiable instances of the CSP. There are three Datalog fragments that are particularly important for finite-domain constraint satisfaction: arc monadic Datalog, linear Datalog, and symmetric linear Datalog, each having good computational properties. We consider the fragment of Datalog where we impose all of these restrictions simultaneously, i.e., we study symmetric linear arc monadic (slam) Datalog. We characterise the CSPs that can be solved by a slam Datalog program as those that have a gadget reduction to a particular Boolean constraint satisfaction problem. We also present exact characterisations in terms of a homomorphism duality (which we call unfolded caterpillar duality), and in universal-algebraic terms (using known minor conditions, namely the existence of quasi Maltsev operations and k-absorptive operations of arity nk, for all n, k ≥ 1). Our characterisations also imply that the question whether a given finite-domain CSP can be expressed by a slam Datalog program is decidable.

Details

Original languageEnglish
Title of host publication28th International Conference on Database Theory, ICDT 2025
EditorsSudeepa Roy, Ahmet Kara
PublisherSchloss Dagstuhl- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
Pages13:1-13:20
ISBN (electronic)9783959773645
Publication statusPublished - 21 Mar 2025
Peer-reviewedYes

Publication series

SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume328
ISSN1868-8969

Conference

TitleJoint Conference of the 28th International Conference on Extending Database Technology & the 28th International Conference on Database Theory
Abbreviated titleEDBT/ICDT 2025
Conference number28
Duration25 - 28 March 2025
Website
LocationUniversitat Politècnica de Catalunya (UPC)
CityBarcelona
CountrySpain

External IDs

ORCID /0000-0001-8228-3611/work/208071912

Keywords

ASJC Scopus subject areas

Keywords

  • Datalog, Gadget Reductions, Homomorphism Dualities, Minor Conditions