Partition semantics for relations

DOI10.1016/0022-0000(86)90019-XzbMath0625.68073OpenAlexW2051200809MaRDI QIDQ579957

Paris C. Kanellakis, Stavros S. Cosmandakis

Publication date: 1986

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(86)90019-x

zbMATH Keywords

polynomial time algorithmconnectivityrelational databasefunctional dependenciesundirected graphspartition semanticsfunctional determinationimplication problempartition dependenciesset-theoretic partitionsuniform word problem for lattices

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Free lattices, projective lattices, word problems (06B25)

Related Items

Dependencies and generalized relations, A new interpretation for null values in the weak instance model, Logic and linguistics meeting, Stanford, 1987, Reducing one class of machine learning algorithms to logical operations of plausible reasoning, Functional and approximate dependency mining: database and FCA points of view

Cites Work

• Inclusion dependencies and their interaction with functional dependencies
• Every finite lattice can be embedded in a finite partition lattice
• Algebraic dependencies
• Free lattices
• Component Subsets of the Free Lattice on n Generators
• Formal Systems for Tuple and Equality Generating Dependencies
• Algebraic Structures with Hard Equivalence and Minimization Problems
• A Proof Procedure for Data Dependencies
• On the Computational Complexity of Algebra on Lattices
• Template Dependencies
• Testing satisfaction of functional dependencies
• Horn clauses and database dependencies
• Word problems
• The Word Problem for Abstract Algebras
• Lattices, equivalence relations, and subgroups
• The decision problem for some classes of sentences without quantifiers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item