PhilSci Archive

Logical reduction of relations: from relational databases to Peirce's reduction thesis

Koshkin, Sergiy (2023) Logical reduction of relations: from relational databases to Peirce's reduction thesis. Logic Journal of the IGPL. ISSN 1367-0751

[img]
Preview
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:
Share |

Item Type: Published Article or Volume
Creators:
CreatorsEmailORCID
Koshkin, Sergiy0000-0001-8264-3701
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 View Item