Right-Adjoints for Datalog Programs, and Homomorphism Dualities over Restricted Classes Article Swipe

PDF

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

YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2302.06366

A Datalog program can be viewed as a syntactic specification of a functor from database instances over some schema to database instances over another schema. The same holds more generally for $\exists$Datalog. We establish large classes of Datalog and $\exists$Datalog programs for which the corresponding functor 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. We also derive new results regarding the existence of uniquely characterizing data examples for database queries.

Related Topics

Concepts

Datalog Homomorphism Schema (genetic algorithms) Computer science Functor Programming language Deductive database Mathematics Discrete mathematics Information retrieval

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2302.06366
PDF: https://arxiv.org/pdf/2302.06366
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4320908126

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4320908126

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2302.06366

Digital Object Identifier
Title: Right-Adjoints for Datalog Programs, and Homomorphism Dualities over Restricted Classes

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2023

Year of publication
Publication date: 2023-02-13

Full publication date if available
Authors: Balder ten Cate, Víctor Dalmau, Jakub Opršal

List of authors in order
Landing page: https://arxiv.org/abs/2302.06366

Publisher landing page
PDF URL: https://arxiv.org/pdf/2302.06366

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2302.06366

Direct OA link when available
Concepts: Datalog, Homomorphism, Schema (genetic algorithms), Computer science, Functor, Programming language, Deductive database, Mathematics, Discrete mathematics, Information retrieval

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4320908126
doi	https://doi.org/10.48550/arxiv.2302.06366
ids.doi	https://doi.org/10.48550/arxiv.2302.06366
ids.openalex	https://openalex.org/W4320908126
fwci
type	preprint
title	Right-Adjoints for Datalog Programs, and Homomorphism Dualities over Restricted Classes
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11010
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9926999807357788
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Logic, Reasoning, and Knowledge
topics[1].id	https://openalex.org/T10126
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9883000254631042
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1702
topics[1].subfield.display_name	Artificial Intelligence
topics[1].display_name	Logic, programming, and type systems
topics[2].id	https://openalex.org/T10317
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9715999960899353
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1705
topics[2].subfield.display_name	Computer Networks and Communications
topics[2].display_name	Advanced Database Systems and Queries
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C148230440
concepts[0].level	2
concepts[0].score	0.9928957223892212
concepts[0].wikidata	https://www.wikidata.org/wiki/Q1172264
concepts[0].display_name	Datalog
concepts[1].id	https://openalex.org/C4042151
concepts[1].level	2
concepts[1].score	0.6849001049995422
concepts[1].wikidata	https://www.wikidata.org/wiki/Q215111
concepts[1].display_name	Homomorphism
concepts[2].id	https://openalex.org/C52146309
concepts[2].level	2
concepts[2].score	0.6373035311698914
concepts[2].wikidata	https://www.wikidata.org/wiki/Q7431116
concepts[2].display_name	Schema (genetic algorithms)
concepts[3].id	https://openalex.org/C41008148
concepts[3].level	0
concepts[3].score	0.5729283690452576
concepts[3].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[3].display_name	Computer science
concepts[4].id	https://openalex.org/C156772000
concepts[4].level	2
concepts[4].score	0.5549571514129639
concepts[4].wikidata	https://www.wikidata.org/wiki/Q864475
concepts[4].display_name	Functor
concepts[5].id	https://openalex.org/C199360897
concepts[5].level	1
concepts[5].score	0.43795377016067505
concepts[5].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[5].display_name	Programming language
concepts[6].id	https://openalex.org/C2777502361
concepts[6].level	2
concepts[6].score	0.42900460958480835
concepts[6].wikidata	https://www.wikidata.org/wiki/Q1182254
concepts[6].display_name	Deductive database
concepts[7].id	https://openalex.org/C33923547
concepts[7].level	0
concepts[7].score	0.35966652631759644
concepts[7].wikidata	https://www.wikidata.org/wiki/Q395
concepts[7].display_name	Mathematics
concepts[8].id	https://openalex.org/C118615104
concepts[8].level	1
concepts[8].score	0.2999824285507202
concepts[8].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[8].display_name	Discrete mathematics
concepts[9].id	https://openalex.org/C23123220
concepts[9].level	1
concepts[9].score	0.07399442791938782
concepts[9].wikidata	https://www.wikidata.org/wiki/Q816826
concepts[9].display_name	Information retrieval
keywords[0].id	https://openalex.org/keywords/datalog
keywords[0].score	0.9928957223892212
keywords[0].display_name	Datalog
keywords[1].id	https://openalex.org/keywords/homomorphism
keywords[1].score	0.6849001049995422
keywords[1].display_name	Homomorphism
keywords[2].id	https://openalex.org/keywords/schema
keywords[2].score	0.6373035311698914
keywords[2].display_name	Schema (genetic algorithms)
keywords[3].id	https://openalex.org/keywords/computer-science
keywords[3].score	0.5729283690452576
keywords[3].display_name	Computer science
keywords[4].id	https://openalex.org/keywords/functor
keywords[4].score	0.5549571514129639
keywords[4].display_name	Functor
keywords[5].id	https://openalex.org/keywords/programming-language
keywords[5].score	0.43795377016067505
keywords[5].display_name	Programming language
keywords[6].id	https://openalex.org/keywords/deductive-database
keywords[6].score	0.42900460958480835
keywords[6].display_name	Deductive database
keywords[7].id	https://openalex.org/keywords/mathematics
keywords[7].score	0.35966652631759644
keywords[7].display_name	Mathematics
keywords[8].id	https://openalex.org/keywords/discrete-mathematics
keywords[8].score	0.2999824285507202
keywords[8].display_name	Discrete mathematics
keywords[9].id	https://openalex.org/keywords/information-retrieval
keywords[9].score	0.07399442791938782
keywords[9].display_name	Information retrieval
language	en
locations[0].id	pmh:oai:arXiv.org:2302.06366
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2302.06366
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2302.06366
locations[1].id	doi:10.48550/arxiv.2302.06366
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2302.06366
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5080220262
authorships[0].author.orcid	https://orcid.org/0000-0002-2538-5846
authorships[0].author.display_name	Balder ten Cate
authorships[0].author_position	first
authorships[0].raw_author_name	Cate, Balder ten
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5057975755
authorships[1].author.orcid	https://orcid.org/0000-0002-9365-7372
authorships[1].author.display_name	Víctor Dalmau
authorships[1].author_position	middle
authorships[1].raw_author_name	Dalmau, Víctor
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5056419307
authorships[2].author.orcid	https://orcid.org/0000-0003-1245-3456
authorships[2].author.display_name	Jakub Opršal
authorships[2].author_position	last
authorships[2].raw_author_name	Opršal, Jakub
authorships[2].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2302.06366
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Right-Adjoints for Datalog Programs, and Homomorphism Dualities over Restricted Classes
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11010
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9926999807357788
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Logic, Reasoning, and Knowledge
related_works	https://openalex.org/W1565767456, https://openalex.org/W4242285398, https://openalex.org/W79246384, https://openalex.org/W2593015871, https://openalex.org/W1552372479, https://openalex.org/W2583213513, https://openalex.org/W1582387176, https://openalex.org/W2058395701, https://openalex.org/W2079714382, https://openalex.org/W4246091227
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2302.06366
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2302.06366
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2302.06366
primary_location.id	pmh:oai:arXiv.org:2302.06366
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2302.06366
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2302.06366
publication_date	2023-02-13
publication_year	2023
referenced_works_count	0
abstract_inverted_index.A	0
abstract_inverted_index.a	7, 11, 47
abstract_inverted_index.We	32, 50, 73
abstract_inverted_index.as	6
abstract_inverted_index.be	4
abstract_inverted_index.of	10, 36, 71, 81
abstract_inverted_index.to	19, 54
abstract_inverted_index.The	25
abstract_inverted_index.and	38, 62
abstract_inverted_index.can	3
abstract_inverted_index.for	30, 41, 64, 86
abstract_inverted_index.new	56, 76
abstract_inverted_index.of,	61
abstract_inverted_index.the	43, 59, 79
abstract_inverted_index.also	74
abstract_inverted_index.data	84
abstract_inverted_index.from	13
abstract_inverted_index.into	58
abstract_inverted_index.more	28
abstract_inverted_index.over	16, 22
abstract_inverted_index.same	26
abstract_inverted_index.some	17
abstract_inverted_index.holds	27
abstract_inverted_index.large	34
abstract_inverted_index.these	52
abstract_inverted_index.which	42
abstract_inverted_index.admits	46
abstract_inverted_index.derive	75
abstract_inverted_index.employ	51
abstract_inverted_index.obtain	55
abstract_inverted_index.schema	18
abstract_inverted_index.viewed	5
abstract_inverted_index.within	68
abstract_inverted_index.Datalog	1, 37
abstract_inverted_index.another	23
abstract_inverted_index.classes	35, 70
abstract_inverted_index.functor	12, 45
abstract_inverted_index.methods	63
abstract_inverted_index.program	2
abstract_inverted_index.results	53, 77
abstract_inverted_index.schema.	24
abstract_inverted_index.database	14, 20, 87
abstract_inverted_index.examples	85
abstract_inverted_index.insights	57
abstract_inverted_index.programs	40
abstract_inverted_index.queries.	88
abstract_inverted_index.uniquely	82
abstract_inverted_index.dualities	67
abstract_inverted_index.establish	33
abstract_inverted_index.existence	60, 80
abstract_inverted_index.generally	29
abstract_inverted_index.instances	15, 21
abstract_inverted_index.regarding	78
abstract_inverted_index.syntactic	8
abstract_inverted_index.instances.	72
abstract_inverted_index.restricted	69
abstract_inverted_index.generalized	48
abstract_inverted_index.homomorphism	66
abstract_inverted_index.constructing,	65
abstract_inverted_index.corresponding	44
abstract_inverted_index.specification	9
abstract_inverted_index.characterizing	83
abstract_inverted_index.right-adjoint.	49
abstract_inverted_index.$\exists$Datalog	39
abstract_inverted_index.$\exists$Datalog.	31
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile