Right-Adjoints for Datalog Programs

Balder ten Cate; Víctor Dalmau; Jakub Opršal

doi:10.4230/LIPIcs.ICDT.2024.10

Right-Adjoints for Datalog Programs

Balder ten Cate, Víctor Dalmau^*, Jakub Opršal^*

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

10 Downloads (Pure)

Abstract

A Datalog program can be viewed as a syntactic specification of a mapping from database instances over some schema to database instances over another schema. We establish a large class of Datalog programs for which this mapping admits a (generalized) right-adjoint. We employ these results to obtain new insights into the existence of, and methods for constructing, homomorphism dualities within restricted classes of instances. From this, we derive new results regarding the existence of uniquely characterizing data examples for database queries in the presence of integrity constraints.

Original language	English
Title of host publication	27th International Conference on Database Theory (ICDT 2024)
Editors	Graham Cormode, Michael Shekelyan
Publisher	Schloss Dagstuhl
ISBN (Electronic)	9783959773126
DOIs	https://doi.org/10.4230/LIPIcs.ICDT.2024.10
Publication status	Published - 14 Mar 2024
Event	27th International Conference on Database Theory, ICDT 2024 - Paestum, Italy Duration: 25 Mar 2024 → 28 Mar 2024

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	290
ISSN (Print)	1868-8969

Conference

Conference	27th International Conference on Database Theory, ICDT 2024
Country/Territory	Italy
City	Paestum
Period	25/03/24 → 28/03/24

Bibliographical note

Funding:
Balder ten Cate: Supported by the European Union’s Horizon 2020 research and innovation programme (MSCA-101031081). Víctor Dalmau: Supported by the MiCin under grants PID2019-109137GB-C22 and PID2022-138506NB-C22, and the Maria de Maeztu program (CEX2021-001195-M). Jakub Opršal: Supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413.

Publisher Copyright:
© Balder ten Cate, Víctor Dalmau, and Jakub Opršal.

Keywords

Adjoints
Conjunctive Queries
Data Examples
Database Constraints
Datalog
Homomorphism Dualities

ASJC Scopus subject areas

Software

Access to Document

10.4230/LIPIcs.ICDT.2024.10Licence: Creative Commons: Attribution (CC BY)

tenCateB2024RightFinal published version, 863 KBLicence: Creative Commons: Attribution (CC BY)

Cite this

@inproceedings{7483060efdc94b5f828531750cbf83ba,

title = "Right-Adjoints for Datalog Programs",

abstract = "A Datalog program can be viewed as a syntactic specification of a mapping from database instances over some schema to database instances over another schema. We establish a large class of Datalog programs for which this mapping admits a (generalized) right-adjoint. We employ these results to obtain new insights into the existence of, and methods for constructing, homomorphism dualities within restricted classes of instances. From this, we derive new results regarding the existence of uniquely characterizing data examples for database queries in the presence of integrity constraints.",

keywords = "Adjoints, Conjunctive Queries, Data Examples, Database Constraints, Datalog, Homomorphism Dualities",

author = "{ten Cate}, Balder and V{\'i}ctor Dalmau and Jakub Opr{\v s}al",

note = "Funding: Balder ten Cate: Supported by the European Union{\textquoteright}s Horizon 2020 research and innovation programme (MSCA-101031081). V{\'i}ctor Dalmau: Supported by the MiCin under grants PID2019-109137GB-C22 and PID2022-138506NB-C22, and the Maria de Maeztu program (CEX2021-001195-M). Jakub Opr{\v s}al: Supported by the European Union{\textquoteright}s Horizon 2020 research and innovation programme under the Marie Sk{\l}odowska-Curie Grant Agreement No 101034413. Publisher Copyright: {\textcopyright} Balder ten Cate, V{\'i}ctor Dalmau, and Jakub Opr{\v s}al.; 27th International Conference on Database Theory, ICDT 2024 ; Conference date: 25-03-2024 Through 28-03-2024",

year = "2024",

month = mar,

day = "14",

doi = "10.4230/LIPIcs.ICDT.2024.10",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl",

editor = "Graham Cormode and Michael Shekelyan",

booktitle = "27th International Conference on Database Theory (ICDT 2024)",

address = "Germany",

}

ten Cate, B, Dalmau, V & Opršal, J 2024, Right-Adjoints for Datalog Programs. in G Cormode & M Shekelyan (eds), 27th International Conference on Database Theory (ICDT 2024)., 10, Leibniz International Proceedings in Informatics, LIPIcs, vol. 290, Schloss Dagstuhl, 27th International Conference on Database Theory, ICDT 2024, Paestum, Italy, 25/03/24. https://doi.org/10.4230/LIPIcs.ICDT.2024.10

Right-Adjoints for Datalog Programs. / ten Cate, Balder; Dalmau, Víctor; Opršal, Jakub.
27th International Conference on Database Theory (ICDT 2024). ed. / Graham Cormode; Michael Shekelyan. Schloss Dagstuhl, 2024. 10 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 290).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Right-Adjoints for Datalog Programs

AU - ten Cate, Balder

AU - Dalmau, Víctor

AU - Opršal, Jakub

N1 - Funding: Balder ten Cate: Supported by the European Union’s Horizon 2020 research and innovation programme (MSCA-101031081). Víctor Dalmau: Supported by the MiCin under grants PID2019-109137GB-C22 and PID2022-138506NB-C22, and the Maria de Maeztu program (CEX2021-001195-M). Jakub Opršal: Supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Publisher Copyright: © Balder ten Cate, Víctor Dalmau, and Jakub Opršal.

PY - 2024/3/14

Y1 - 2024/3/14

N2 - A Datalog program can be viewed as a syntactic specification of a mapping from database instances over some schema to database instances over another schema. We establish a large class of Datalog programs for which this mapping admits a (generalized) right-adjoint. We employ these results to obtain new insights into the existence of, and methods for constructing, homomorphism dualities within restricted classes of instances. From this, we derive new results regarding the existence of uniquely characterizing data examples for database queries in the presence of integrity constraints.

AB - A Datalog program can be viewed as a syntactic specification of a mapping from database instances over some schema to database instances over another schema. We establish a large class of Datalog programs for which this mapping admits a (generalized) right-adjoint. We employ these results to obtain new insights into the existence of, and methods for constructing, homomorphism dualities within restricted classes of instances. From this, we derive new results regarding the existence of uniquely characterizing data examples for database queries in the presence of integrity constraints.

KW - Adjoints

KW - Conjunctive Queries

KW - Data Examples

KW - Database Constraints

KW - Datalog

KW - Homomorphism Dualities

UR - http://www.scopus.com/inward/record.url?scp=85188611324&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICDT.2024.10

DO - 10.4230/LIPIcs.ICDT.2024.10

M3 - Conference contribution

AN - SCOPUS:85188611324

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 27th International Conference on Database Theory (ICDT 2024)

A2 - Cormode, Graham

A2 - Shekelyan, Michael

PB - Schloss Dagstuhl

T2 - 27th International Conference on Database Theory, ICDT 2024

Y2 - 25 March 2024 through 28 March 2024

ER -

Right-Adjoints for Datalog Programs

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this