An algebraic theory of functional and multivalued dependencies in relational databases
type: Item
instance of: scholarly article
title: An algebraic theory of functional and multivalued dependencies in relational databases
zbMATH Open document ID: 0633.68007
DOI: 10.1016/0304-3975(87)90021-1
author: V. S. Lakshmanan
author: C. E. Veni Madhavan
published in: Theoretical Computer Science
publication date: 1987-01-01T00:00:00Z
review text: Computation of the dependency basis is the fundamental step in solving the membership problem for functional dependencies (FDs) and multivalued dependencies (MVDs) in relational database theory. We examine this problem from an algebraic perspective. We introduce the notion of the inference basis of a set M of MVDs and show that it contains the maximum information about the logical consequences of M. We propose the notion of a dependency-lattice and develop an algebraic characterization of inference basis using simple notions from lattice theory. We also establish several interesting properties of dependency-lattices related to the implication problem. Founded on our characterization, we synthesize efficient algorithms for (a): computing the inference basis of a given set M of MVDs; (b): computing the dependency basis of a given attribute set with respect to M; and (c): solving the membership problem for MVDs. We also show that our results naturally extend to incorporate FDs also in a way that enables the solution of the membership problem for both FDs and MVDs put together. We finally show that our algorithms are more efficient than existing ones, when used to solve what we term the `generalized membership problem'.
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4030952
zbMATH Keywords: membership problem
zbMATH Keywords: functional dependencies
zbMATH Keywords: multivalued dependencies
zbMATH Keywords: relational database
zbMATH Keywords: inference basis
zbMATH Keywords: dependency-lattice
zbMATH Keywords: efficient algorithms
Wikidata QID: Q114683726
MaRDI profile type: Publication
full work available at URL: 0304-3975(87)90021-1
OpenAlex ID: W1979227787
cites work: Q4050122
cites work: On the menbership problem for functional and multivalued dependencies in relational databases
cites work: Q3912018
cites work: Q5331549
cites work: Inferences of multivalued dependencies in fixed and undetermined universes
cites work: A relational model of data for large shared data banks
cites work: Q3992694
cites work: Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra
cites work: An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database
cites work: Decision Problems for Multivalued Dependencies in Relational Databases
cites work: An Algebraic Theory of Relational Databases
cites work: Order-preserving representations of the partitions on the finite set
cites work: Q3668890
cites work: On Axiomatizing Multivalued Dependencies in Relational Databases
cites work: Q4749246
cites work: An Algorithm for Inferring Multivalued Dependencies with an Application to Propositional Logic
cites work: An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic
cites work: Q3347338
cites work: Inferring multivalued dependencies from functional and join dependencies
description: scientific article; zbMATH DE number 4030952