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.
- A Proof Procedure for Data Dependencies
- Algebraic dependencies
- Algebraic Structures with Hard Equivalence and Minimization Problems
- Component Subsets of the Free Lattice on n Generators
- Every finite lattice can be embedded in a finite partition lattice
- Formal Systems for Tuple and Equality Generating Dependencies
- Free lattices
- Horn clauses and database dependencies
- scientific article; zbMATH DE number 3646330 (Why is no real title available?)
- scientific article; zbMATH DE number 3823168 (Why is no real title available?)
- scientific article; zbMATH DE number 3777562 (Why is no real title available?)
- scientific article; zbMATH DE number 3464827 (Why is no real title available?)
- scientific article; zbMATH DE number 3467028 (Why is no real title available?)
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3290336 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- Inclusion dependencies and their interaction with functional dependencies
- Lattices, equivalence relations, and subgroups
- On the Computational Complexity of Algebra on Lattices
- Template Dependencies
- Testing satisfaction of functional dependencies
- The decision problem for some classes of sentences without quantifiers
- The Word Problem for Abstract Algebras
- Word problems
- Constrained dependencies
- On the orthographic dimension of definable sets
- Containment and disjointedness in partitioned normal form relations
- Reducing one class of machine learning algorithms to logical operations of plausible reasoning
- Partitioned binary relations
- A NEW RELATIONAL (DOMAIN-CALCULUS TYPE) QUERY LANGUAGE BASED ON THE PARTITION MODEL
- scientific article; zbMATH DE number 3922023 (Why is no real title available?)
- Logic and linguistics meeting, Stanford, 1987
- Functional and approximate dependency mining: database and FCA points of view
- scientific article; zbMATH DE number 817193 (Why is no real title available?)
- Partition Relations and Transitivity Domains of Binary Relations
- Dependencies and generalized relations
- Consistent query answering in multi-relation databases
- A chase-based approach to consistent answers of analytic queries in star schemas
- Partition relations on a plain product order type
- A new interpretation for null values in the weak instance model
This page was built for publication: Partition semantics for relations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q579957)
