Partition semantics for relations
type: Item
instance of: scholarly article
title: Partition semantics for relations
zbMATH Open document ID: 0625.68073
DOI: 10.1016/0022-0000(86)90019-X
author: Paris C. Kanellakis
author: Stavros S. Cosmandakis
published in: Journal of Computer and System Sciences
publication date: 1986-01-01T00:00:00Z
review text: We use set-theoretic partitions to assign semantics to relation schemes, relations, and dependencies. This approach leads to a natural extension of functional dependencies, the most common database constraints, which is based on the duality between product and sum of partitions. These more general constraints, which we call partition dependencies (PDs), have the power to express both functional determination and connectivity in undirected graphs. We show that the implication problem for PDs is the uniform word problem for lattices, and we give a polynomial time algorithm for this implication problem. Our decision procedure for the uniform word problem for lattices improves upon previous exponential decision procedures. The algebraic techniques we use are new to database theory. We investigate the expressive power of PDs, and show that partition semantics justify a number of variants of an assumption commonly used in database theory, namely the weak instance assumption. Finally, we provide a polynomial time test for consistency of a set of relations with a set of PDs.
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 06B25
zbMATH DE Number: 4016231
zbMATH Keywords: relational database
zbMATH Keywords: set-theoretic partitions
zbMATH Keywords: functional dependencies
zbMATH Keywords: partition dependencies
zbMATH Keywords: functional determination
zbMATH Keywords: connectivity
zbMATH Keywords: undirected graphs
zbMATH Keywords: implication problem
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: uniform word problem for lattices
zbMATH Keywords: partition semantics
MaRDI profile type: Publication
cites work: Q4050122
cites work: Formal Systems for Tuple and Equality Generating Dependencies
cites work: A Proof Procedure for Data Dependencies
cites work: Algebraic Structures with Hard Equivalence and Minimization Problems
cites work: Inclusion dependencies and their interaction with functional dependencies
cites work: Q3956998
cites work: Component Subsets of the Free Lattice on n Generators
cites work: Q4052071
cites work: The Word Problem for Abstract Algebras
cites work: Word problems
cites work: Horn clauses and database dependencies
cites work: Q4058132
cites work: Q4198056
cites work: Q5572358
cites work: Testing satisfaction of functional dependencies
cites work: Q5592246
cites work: On the Computational Complexity of Algebra on Lattices
cites work: Q3668890
cites work: The decision problem for some classes of sentences without quantifiers
cites work: Every finite lattice can be embedded in a finite partition lattice
cites work: Template Dependencies
cites work: Q3051422
cites work: Free lattices
cites work: Lattices, equivalence relations, and subgroups
cites work: Algebraic dependencies
full work available at URL: 0022-0000(86)90019-x
OpenAlex ID: W2051200809
description: scientific article; zbMATH DE number 4016231