The relational model of data and cylindric algebras

Tomasz Imieliński, Witold Lipski

Research output: Contribution to journalArticlepeer-review

49 Scopus citations

Abstract

It is shown how the theory of cylindric algebras (a notion introduced by Tarski and others as a tool in the algebraization of the first order predicate calculus) can give a new insight into Codd's relational model of data. The relational algebra of Codd can be embedded in a natural way into a cylindric algebra where the join operation becomes the usual set-theoretical intersection. It is shown, by using known facts from the theory of cylindric algebras, that a version of the relational algebra is not finitely axiomatizable and that the equivalence problem for certain relational expressions is undecidable. A duality between the project-join and selectunion operator pairs is also briefly discussed.

Original languageEnglish (US)
Pages (from-to)80-102
Number of pages23
JournalJournal of Computer and System Sciences
Volume28
Issue number1
DOIs
StatePublished - Feb 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Applied Mathematics
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'The relational model of data and cylindric algebras'. Together they form a unique fingerprint.

Cite this