A Proof System for Dependencies for Information Relations

Abstract

Using a relational approach, we investigate the implication problem for dependencies for information relations, focusing on functional dependencies, association rules and multivalued dependencies. We develop a Rasiowa/Sikorski-style relational calculus and show that the associated tableaux style of reasoning gives a decidable procedure for each of the three kinds of inference problems under consideration. This work has applications to classical database theory and to Rough Set Theory. The techniques may be generalized to the many other data dependencies which have formulations via binary relations and they can be applied to other information relations which arise in the study of incomplete information.