Completeness of Relational Algebra via Cylindric Algebra
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915866649559040 |
|---|---|
| author | Laštovička, Jan |
| author_facet | Laštovička, Jan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_15099 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Completeness of Relational Algebra via Cylindric Algebra Laštovička, Jan Logic in Computer Science Databases Logic 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. |
| title | Completeness of Relational Algebra via Cylindric Algebra |
| topic | Logic in Computer Science Databases Logic |
| url | https://arxiv.org/abs/2603.15099 |