Partition semantics for relations

摘要

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.