Inclusion dependencies and their interaction with functional dependencies
type: Item
instance of: scholarly article
title: Inclusion dependencies and their interaction with functional dependencies
zbMATH Open document ID: 0586.68082
DOI: 10.1016/0022-0000(84)90075-8
author: Marco A. Casanova
author: Ronald Fagin
author: Christos Papadimitriou
published in: Journal of Computer and System Sciences
publication date: 1984-01-01T00:00:00Z
review text: Inclusion dependencies, or INDs (which can say, for example, that every manager is an employee) are studied, including their interaction with functional dependencies, or FDs. A simple complete axiomatization for INDs is presented, and the decision problem for INDs is shown to be PSPACE-complete. (The decision problem for INDs is the problem of determining whether or not \(\Sigma\) logically implies \(\sigma\), given a set \(\Sigma\) of INDs and a single IND \(\sigma)\). It is shown that finite implication (implication over databases with a finite number of tuples) is the same as unrestricted implications for INDs, although finite implication and unrestricted implication are distinct for FDs and INDs taken together. It is shown that, although there are simple complete axiomatizations for FDs alone and for INDs alone, there is no complete axiomatization for FDs and INDs taken together, in which every rule is k- ary for some fixed k (and in particular, there is no finite complete axiomatization). Thus, no k-ary axiomatization can fully describe the interaction between FDs and INDs. This is true whether we consider finite implication or unrestricted implication. In the case of finite implication, this result holds, even if no relation scheme has more than two attributes, and if all of the dependencies are unary (a dependency is unary if the left-hand side and right-hand side each contain only one attribute). In the case of unrestricted implication, the result holds, even if no relation scheme has more than three attributes, each FD is unary, and each IND is binary.
Mathematics Subject Classification ID: 68P20
zbMATH DE Number: 3940767
zbMATH Keywords: relational database
zbMATH Keywords: complete axiomatization
zbMATH Keywords: decision problem
zbMATH Keywords: finite implication
zbMATH Keywords: unrestricted implication
Wikidata QID: Q56619908
MaRDI profile type: Publication
full work available at URL: 0022-0000(84)90075-8
OpenAlex ID: W2050480346
cites work: Formal systems for join dependencies
cites work: Q4050122
cites work: The Implication Problem for Functional and Inclusion Dependencies is Undecidable
cites work: Q3992694
cites work: Q3905252
cites work: Functional Dependencies in a Relational Database and Propositional Logic
cites work: A normal form for relational databases that is based on domains and keys
cites work: Horn clauses and database dependencies
cites work: Tools for Template Dependencies
cites work: Armstrong databases for functional and inclusion dependencies
cites work: Q4198056
cites work: Testing containment of conjunctive queries under functional and inclusion dependencies
cites work: Q3915990
cites work: The implication problem for functional and inclusion dependencies
cites work: Q4162638
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Template Dependencies
cites work: Subset Dependencies and a Completeness Result for a Subclass of Embedded Multivalued Dependencies
cites work: Algebraic dependencies
description: scientific article; zbMATH DE number 3940767