Report Number: CS-TR-82-912
Institution: Stanford University, Department of Computer Science
Title: The implication and finite implication problems for typed template dependencies
Author: Varde, Moshe Y.
Date: May 1982
Abstract: The class of typed template dependencies is a class of data dependencies that includes embedded multivalued and join dependencies. We show 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. We also show 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 impllication or finite implication.
http://i.stanford.edu/pub/cstr/reports/cs/tr/82/912/CS-TR-82-912.pdf