<div class="csl-bib-body">
<div class="csl-entry">Khamis, M. A., Ngo, H. Q., Pichler, R., Suciu, D., & Wang, Y. R. (2022). Convergence of Datalog over (Pre-) Semirings. In <i>PODS ’22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems</i> (p. 105). Association for Computing Machinery. https://doi.org/10.1145/3517804.3524140</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/144347
-
dc.description.abstract
Recursive queries have been traditionally studied in the framework of datalog, a language that restricts recursion to monotone queries over sets, which is guaranteed to converge in polynomial time in the size of the input. But modern big data systems require recursive computations beyond the Boolean space. In this paper we study the convergence of datalog when it is interpreted over an arbitrary semiring. We consider an ordered semiring, define the semantics of a datalog program as a least fixpoint in this semiring, and study the number of steps required to reach that fixpoint, if ever. We identify algebraic properties of the semiring that correspond to certain convergence properties of datalog programs. Finally, we describe a class of ordered semirings on which one can use the semi-naive evaluation algorithm on any datalog program.
en
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.subject
Convergence
en
dc.subject
Datalog
en
dc.subject
Semirings
en
dc.subject
Fixpoint
en
dc.subject
semantics
en
dc.subject
algebraic properties
en
dc.subject
semi-naive evaluation
en
dc.subject
algorithm
en
dc.title
Convergence of Datalog over (Pre-) Semirings
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
RelationalAI
-
dc.contributor.affiliation
RelationalAI
-
dc.contributor.affiliation
University of Washington, United States of America (the)
-
dc.contributor.affiliation
University of Washington, United States of America (the)
-
dc.relation.isbn
9781450392600
-
dc.relation.doi
10.1145/3517804
-
dc.description.endpage
105
-
dc.relation.grantno
P30930-N35
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
PODS '22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Association for Computing Machinery
-
tuw.relation.publisherplace
New York, NY, United States
-
tuw.project.title
HyperTrac: hypergraph Decompositions and Tractability
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
tuw.publisher.doi
10.1145/3517804.3524140
-
dc.description.numberOfPages
117
-
tuw.author.orcid
0000-0002-1760-122X
-
tuw.event.name
2022 ACM SIGMOND/PODS International Conference on Management of Data
en
tuw.event.startdate
12-06-2022
-
tuw.event.enddate
17-06-2022
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Philadelphia, PA
-
tuw.event.country
US
-
tuw.event.presenter
Pichler, Reinhard
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.grantfulltext
restricted
-
item.openairetype
conference paper
-
item.languageiso639-1
en
-
crisitem.author.dept
RelationalAI
-
crisitem.author.dept
RelationalAI
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence
