Completeness of Relational Algebra via Cylindric Algebra
This work is incremental, aiming to provide a foundation for generalizing completeness proofs to relational models with incomplete or vague information.
The paper presents an alternative proof of the completeness of relational algebra with respect to allowed formulas of first-order logic, using an embedding into cylindric algebra, and introduces an alternative algorithm for generating equivalent relational expressions.
An alternative proof of the completeness of relational algebra with respect to allowed formulas of first-order logic is presented. The proof relies on the well-known embedding of relational algebra into cylindric algebra, which makes it possible to establish completeness in a more algebraic way. Building on this proof, we present an alternative algorithm that produces a relational expression equivalent to a given allowed formula. The main motivation for the present work is to establish a proof of completeness suitable for generalisation to relational models handling incomplete or vague information.