Koshkin, Sergiy (2023) Logical reduction of relations: from relational databases to Peirce's reduction thesis. Logic Journal of the IGPL. ISSN 1367-0751
|
Text
Reduction of Relations.pdf Download (459kB) | Preview |
Abstract
We study logical reduction (factorization) of relations into relations of lower arity by Boolean or relative products that come from applying conjunctions and existential quantifiers to predicates, i.e. by primitive positive formulas of predicate calculus. Our algebraic framework unifies natural joins and data dependencies of database theory and relational algebra of clone theory with the bond algebra of C.S. Peirce. We also offer new constructions of reductions, systematically study irreducible relations and reductions to them, and introduce a new characteristic of relations, ternarity, that measures their `complexity of relating' and allows to refine reduction results. In particular, we refine Peirce's controversial reduction thesis, and show that reducibility behavior is dramatically different on finite and infinite domains.
| Export/Citation: | EndNote | BibTeX | Dublin Core | ASCII/Text Citation (Chicago) | HTML Citation | OpenURL |
| Social Networking: |
| Item Type: | Published Article or Volume | ||||||
|---|---|---|---|---|---|---|---|
| Creators: |
|
||||||
| Keywords: | relational algebra, relation scheme, attribute, Cartesian product, Boolean product, natural join, primitive positive formula, constraint satisfaction problem, co-clone, project-join expression, relative product, irreducible relation, teridentity, bonding algebra, Peirce's reduction thesis, subcubic graph | ||||||
| Subjects: | Specific Sciences > Computation/Information > Classical Specific Sciences > Mathematics > History of Philosophy Specific Sciences > Mathematics > Logic |
||||||
| Depositing User: | Dr. Sergiy Koshkin | ||||||
| Date Deposited: | 11 Jun 2024 17:18 | ||||||
| Last Modified: | 11 Jun 2024 17:18 | ||||||
| Item ID: | 23544 | ||||||
| Journal or Publication Title: | Logic Journal of the IGPL | ||||||
| Publisher: | Oxford University Press | ||||||
| Official URL: | https://academic.oup.com/jigpal/advance-article-ab... | ||||||
| DOI or Unique Handle: | https://doi.org/10.1093/jigpal/jzad010 | ||||||
| Subjects: | Specific Sciences > Computation/Information > Classical Specific Sciences > Mathematics > History of Philosophy Specific Sciences > Mathematics > Logic |
||||||
| Date: | 7 June 2023 | ||||||
| ISSN: | 1367-0751 | ||||||
| URI: | https://philsci-archive.pitt.edu/id/eprint/23544 |
Monthly Views for the past 3 years
Monthly Downloads for the past 3 years
Plum Analytics
Altmetric.com
Actions (login required)
 |
View Item |
![[feed]](http://philsci-archive.pitt.edu/style/images/feed-icon-32x32.png){kind=icon}