Codd’s Theorem for Databases over Semirings

ABSTRACT

Codd’s Theorem, a fundamental result of database theory, asserts that relational algebra and relational calculus have the same expressive power on relational databases. We explore Codd’s Theorem for databases over semirings and establish two different versions of this result for such databases: the first version involves the five basic operations of relational algebra, while in the second version the division operation is added to the five basic operations of relational algebra. In both versions, the difference operation of relations is given semantics using semirings with monus, while on the side of relational calculus a limited form of negation is used. The reason for considering these two different versions of Codd’s theorem is that, unlike the case of ordinary relational databases, the division operation need not be expressible in terms of the five basic operations of relational algebra for databases over an arbitrary positive semiring; in fact, we show that this inexpressibility result holds even for bag databases.

SHORT BIO:

Guillermo Badia is a Lecturer in Logic (continuing position) in the School of Historical and Philosophical Inquiry at the University of Queensland, Australia. From 2022-2025, his research is supported by an Australian Research Council Discovery Early Career Researcher Award (DE220100544). He serves as an editor of Archive for Mathematical  Logic and Journal of Multiple-Valued Logic and Soft Computing. According to the Mathematics Genealogy Project, he is one of the many academic descendants of G. H. Hardy through the path  G. H. Hardy – R. Rado – K. Gravett – John N. Crossley – John L. Bell – G. Priest – Z. Weber – G. Badia. His research interests include: Mathematical Fuzzy Logic and particularly model theory of many-valued predicate logics. Intuitionistic and bi-intuitionistic logic. Equality-free first-order logic. Second-order logic. Relevant and paraconsistent logic. Modal logic.