The implication and finite implication problems for typed template dependencies
type: Item
instance of: scholarly article
title: The implication and finite implication problems for typed template dependencies
zbMATH Open document ID: 0586.68084
DOI: 10.1016/0022-0000(84)90074-6
author: Moshe Y. Vardi
published in: Journal of Computer and System Sciences
publication date: 1984-01-01T00:00:00Z
review text: The class of typed template dependencies is a class of data dependencies that includes embedded multivalued and join dependencies. It is shown that the implication and the finite implication problems for this class are unsolvable. An immediate corollary is that this class has no formal system for finite implication. It is also shown how to construct a finite set of typed template dependencies whose implication and finite implication problems are unsolvable. The class of projected join dependencies is a proper subclass of the above class, and it generalizes slightly embedded join dependencies. It is shown that the implication and the finite implication problems for this class are also unsolvable. An immediate corollary is that this class has no universe-bounded formal system for either implication or finite implication.
Mathematics Subject Classification ID: 68P20
zbMATH DE Number: 3940769
zbMATH Keywords: relational database
zbMATH Keywords: data dependencies
zbMATH Keywords: join dependencies
MaRDI profile type: Publication
full work available at URL: 0022-0000(84)90074-6
OpenAlex ID: W2172111502
Wikidata QID: Q114685268
cites work: Equivalences among Relational Expressions
cites work: Equivalence of Relational Database Schemes
cites work: Q3912018
cites work: Formal Systems for Tuple and Equality Generating Dependencies
cites work: Q4877295
cites work: A relational model of data for large shared data banks
cites work: Horn clauses and database dependencies
cites work: Tools for Template Dependencies
cites work: The word problem for cancellation semigroups with zero
cites work: Q4162638
cites work: Q5573961
cites work: A Complete Axiomatization of Full Join Dependencies
cites work: Template Dependencies
cites work: Algebraic dependencies
Recommended article: The inference problem for template dependencies
Recommended article: The implication problem for functional and inclusion dependencies
Recommended article: A typed resolution principle for deduction with conditional typing theory
Recommended article: The Implicit Calculus of Constructions as a Programming Language with Dependent Types
Recommended article: Dependent types and formal synthesis
Recommended article: Q3702495
Recommended article: On the decidability of subtyping with bounded existential types and implementation constraints
Recommended article: Q4944851
Recommended article: Q3976029
description: scientific article; zbMATH DE number 3940769